December 2018 - mathfun@mailman.xmission.com

[math-fun] Egyptian Fractions (was Re: Messages in pi (cont'd))
by Keith F. Lynch 10 Dec '18

10 Dec '18

Bill Gosper <billgosper(a)gmail.com> wrote: > Off-list I grumbled that no self-respecting Deity would bother > sending clues to worshipers dumb enough to use decimal instead > of continued fractions. Perhaps there's a hidden message in the continued fraction for e. :-) Why not Egyptian fractions? The Egyptians, ancient and modern, have always been very religious. Any positive real number can be approximated to any desired precision by an Egyptian fraction, i.e. the sum of reciprocals of distinct integers, a subset of the harmonic series. They aren't unique for a given real number, but the *greedy* Egyptian fraction for that real number is unique. Has anyone inspected the greedy Egyptian fraction for pi? The first few terms are: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 27, 744, 1173268, 2586625801171, 14348276635209672362238685, 1062286904072440687703470835520966381484062674280821 (A243020). See the pattern? Me neither. Except the first 12 terms. Maybe if it continued that way? After all, a friend of mine once confidently asserted that pi was infinite. (I think he may have been exaggerating.) Speaking of infinite, try to find an Egyptian fraction for a thousand. Good luck. Unlike the Egyptian fraction for pi, it's finite. But it contains more terms than there are atoms in the known universe, most of them consecutive integers starting with 1. What are some exotic ways to approximate real numbers to any desired precision? Extra points if you can come up with something completely original.

4 4

[math-fun] π's CF (cont'd)
by Bill Gosper 10 Dec '18

10 Dec '18

Reiterating, for a burst of terms L := {a, b, . . .}, the Gauss-Kuzmin distribution predicts a probability of cfprob[L_List] := Abs@Log[2, (1 + 1/FromContinuedFraction@L)/(1 + 1/FromContinuedFraction@MapAt[# + 1 &, L, -1])] or cfprob[r : (Integer_ | Rational_)] := cfprob@ContinuedFraction@r where r := a+1/(b + 1/. . . ) I neglected to compare the probability of . . . /(1+1/(2 + 1/(3 +. . .))) cfprob@{1, 2, 3} Log[221/220]/Log[2] N@% 0.00654284586677209 against the similar but incorrect cfprob /@ Range@3 {Log[4/3]/Log[2], Log[9/8]/Log[2], Log[16/15]/Log[2]} Times @@ % // N 0.00656656380451684 assuming that those three probabilities were independent. Since Log[4/3]/Log[2] ~ 41% of π's terms ought to be 1, let's find in π some bursts of at least a dozen non-1s: Function[cf, Take[cf, #] & /@ Echo@SequencePosition[cf, {Repeated[Except@1, {12, \[Infinity]}]}, Overlaps -> False]]@ContinuedFraction[\[Pi], 9999] // tim {{3191,3202}, {3315,3326}, {6778,6790}} During evaluation of In[136]:= 1058.655331 (*secs, almost prohibitive *), 3 {{2, 4, 2, 2, 32, 2, 4, 16, 3, 46, 2, 5}, {2, 33, 3, 3, 2, 3, 9, 6, 4, 4, 5, 7}, {32, 2, 2, 9, 3, 2, 3, 2, 5, 3, 3, 2, 54}} The same computation extended to the bursts ≥13 of non-1s among 99999 terms has thus far consumed most of a day. (Veridically prohibitive.) (Small scale experiments just now suggest that the time complexity is *worse* than cubic! Time to back off. 30000 should run overnight.) —rwg

1 2

Re: [math-fun] Egyptian Fractions
by Dan Asimov 09 Dec '18

09 Dec '18

Hmm, so consider the analytic function f(z) = Sum_{0 <= n < oo} z^(2^n) which converges only on the open disk |z| < 1. Is it true that f takes rational numbers in (-1, 1) to transcendentals? —Dan Keith Lynch wrote: ----- ... So 1/2 + 1/4 + 1/16 + 1/256 + 1/65536 + ... is not a greedy sequence. Still, I wonder whether its sum has any significance. Similarly with other starting points, e.g. 1/3 + 1/9 + 1/81 + 1/6561 ... -----

1 0

Re: [math-fun] Egyptian Fractions
by Keith F. Lynch 08 Dec '18

08 Dec '18

"Keith F. Lynch" <kfl(a)KeithLynch.net> wrote: > For "random" irrational numbers, the expected distribution of terms > in distributed fractions ... Sorry, I meant in *continued* fractions. > My impression from looking at a few of them is that each term is > roughly the square of the previous. That raises the question of > whether ... any number has terms that consistently grow more slowly, > e.g. each term is on average only the 1.5 power of the previous, > forever. That was stupid of me. The difference between 1/(n-1) and 1/n will always be 1/((n-1)*n), so the greedy algorithm will always grab 1/(n-1) rather tnan 1/n if the remainder of the latter would be less than 1/((n-1)*n). The only exception is if it grabbed both, which can only happen as part of a run of consecutive numbers at the beginning of the sequence. So 1/2 + 1/4 + 1/16 + 1/256 + 1/65536 + ... is not a greedy sequence. Still, I wonder whether its sum has any significance. Similarly with other starting points, e.g. 1/3 + 1/9 + 1/81 + 1/6561 ...

1 0

Re: [math-fun] Egyptian Fractions
by Keith F. Lynch 08 Dec '18

08 Dec '18

Cris Moore <moore(a)santafe.edu> wrote: > The Egyptians were ok with integers, so I think they would have called > one thousand one thousand, I'm less interested in what the actual Egyptians did than in the abstraction loosely based on it. For instance they also allowed 2/3. > as opposed to 1+1/2+1/3+?1/e^1000 :-) Shouldn't gamma be in there somewhere? Also, e^1000 is not an integer. > But it?s a lovely exercise that the greedy algorithm for Egyptian > fractions ? that is, subtract the largest reciprocal ? terminates > for any rational number between 0 and 1. (Note that non-ASCII characters, including "smart" quotes, are turned into question marks on this list, at least on the digest option.) Are you implying that it doesn't always terminate for rational numbers greater than 1? If so, can you give me an example? Thanks. For "random" irrational numbers, the expected distribution of terms in distributed fractions are well understood. What about the expected distribution of terms in greedy Egyptian fractions? Obviously, there can't be a non-zero asymptotic density, as that wouldn't converge. My impression from looking at a few of them is that each term is roughly the square of the previous. That raises the question of whether there's anything special about 1/2 + 1/4 + 1/16 + 1/256 + 1/65536 + ..., and about whether any number has terms that consistently grow more slowly, e.g. each term is on average only the 1.5 power of the previous, forever.

1 0

Re: [math-fun] Stupid QM question
by Henry Baker 08 Dec '18

08 Dec '18

Re: finite v. infinite spectrum Fair enough. But I don't really need a full harmonic oscillator; I just need something that has periodic activity -- a heartbeat, if you will. I presume that this can be done with qbits? But now you're going to tell me that this periodic activity *requires a constant application of some sort of unitary operator*; it can't simply sit there and vibrate/spin/whatever without any forces coming into play? Can't there be some oscillations between two discrete energy levels -- e.g., two different energy levels of an outer electron of an atom? For example, an atom in a 1-D echo chamber with perfect reflectors at both ends whose distance is consistent with the wavelength of the difference in energy levels. At 01:54 PM 12/7/2018, Mike Stay wrote: >On Fri, Dec 7, 2018 at 2:24 PM Henry Baker <hbaker1(a)pipeline.com> wrote: >> Is the "state" of the system a 3-vector of complex numbers or a 3x3 (constant?) matrix of complex numbers? > >It's a 2^3=8-dimensional vector of complex numbers |Ï> = âáµ¢ cáµ¢|i> where i ranges from 000 to 111. > >Note that I've implicitly chosen an orthonormal basis for this vector; this amounts to picking a direction "z" in space. > >> By "state change", I presume that we pre- (or post-) multiply this initial "state" by a 3x3 unitary matrix; correct? > >Premultiply by an 8x8 matrix U(t) = exp(iHt) where H is a Hermitian perturbation of the system. > >> So our computation consists of k steps -- an ordered sequence of k matrix multiplications; correct? Yep. >> The time-reversed computation is the conjugate transpose of the entire sequence; correct? Yep. >> So how can I represent a simple harmonic oscillator using one (more more) qbits? Wouldn't a harmonic oscillator "DO" something even if isolated from the rest of the universe? Wouldn't there be some time-variation of the "state" -- i.e., a periodicity? > >A quantum harmonic oscillator assumes a quadratic potential V(x) = (x^2)/2. > >The nth eigenvector of the system has energy proportional to (n+1/2). > >In the Schrodinger picture, the states with energy E change phase by exp(-iEt/â). > >In the Heisenberg picture, that phase is absorbed into the Hamiltonian operator. > >To get the particles in the QHO to change energy levels, you perturb H = (p^2 + x^2)/2 for some period of time, which multiplies the state by a unitary matrix as above.

2 1

[math-fun] NAS 2018: QC: Progress and Prospects
by Henry Baker 07 Dec '18

07 Dec '18

FYI -- Pretty readable description of the current (unclassified) state of the art. You can download this report for free after some negotiation (at least in the U.S.). http://nap.edu/25196 Quantum Computing: Progress and Prospects National Academy of Sciences 206 pages PDF file 9.3 MB Contents SUMMARY S-1 1 PROGRESS IN COMPUTING 1-1 1.1 Origins of Contemporary Computing 1-1 1.2 Quantum Computing 1-2 1.3 Historical Progress in Computing: Moore's Law 1-3 1.4 Converting Transistors to Cheap Computers 1-5 1.5 A Slow Down in Scaling 1-6 1.6 Quantum: A New Approach to Computing 1-7 2 QUANTUM COMPUTING: A NEW PARADIGM 2-1 2.1 The Nonintuitive Physics of the Quantum World 2-1 2.2 The Landscape of Quantum Technology 2-3 2.3 Bits and Qubits 2-5 2.3.1 Classical Computing: From Analog Signals to Bits and Digital Gates 2-5 2.3.2 The Quantum Bit, or "Qubit" 2-8 2.3.3 Multiqubit Systems. 2-10 2.4 Computing With Qubits 2-11 2.4.1 Quantum Simulation, Quantum Annealing, and Adiabatic Quantum Computation 2-13 2.4.2 Gate-Based Quantum Computing 2-13 2.5 Quantum Computer Design Constraints 2-18 2.6 The Potential for Functional Quantum Computers 2-20 3 QUANTUM ALGORITHMS AND APPLICATIONS 3-1 3.1 Quantum Algorithms for an Ideal Gate-Based Quantum Computer 3-2 3.1.1 The Quantum Fourier Transform and Quantum Fourier Sampling 3-3 3.1.2 Quantum Factoring and Finding Hidden Structures 3-5 3.1.3 Grover's Algorithm and Quantum Random Walks 3-6 3.1.4 Hamiltonian Simulation Algorithms 3-7 3.1.5 Quantum Algorithms for Linear Algebra 3-9 3.1.6 Required Machine Quality 3-10 3.2 Quantum Error Correction and Mitigation 3-10 3.2.1 Quantum Error Mitigation Strategies 3-11 3.2.2 Quantum Error Correction Codes 3-11 3.2.3 Quantum Error Correction Overhead 3-13 3.3 Quantum Approximation Algorithms 3-15 3.3.1 Variational Quantum Algorithms 3-16 3.3.2 Analog Quantum Algorithms 3-16 3.4 applications of a Quantum Computer 3-17 3.4.1 Near-Term Applications of a Quantum Computer 3-18 3.4.2 Quantum Supremacy 3-18 3.4.3 Applications for an Ideal Quantum Computer 3-20 3.5 The Potential Role of Quantum Computers in the Computing Ecosystem 3-20 4 QUANTUM COMPUTING'S IMPLICATIONS FOR CRYPTOGRAPHY 4-1 4.1 Cryptographic Algorithms in Current Use 4-1 4.1.1 Key Exchange and Asymmetric Encryption 4-2 4.1.2 Symmetric Encryption 4-2 4.1.3 Certificates and Digital Signatures 4-3 4.1.4 Cryptographic Hash Functions and Password Hashing 4-4 4.2 Sizing Estimates 4-5 4.3 Post-quantum Cryptography 4-6 4.3.1 Symmetric Encryption and Hashing 4-7 4.3.2 Key Exchange and Signatures 4-7 4.4 Practical Deployment Challenges 4-9 5 ESSENTIAL HARDWARE COMPONENTS OF A QUANTUM COMPUTER 5-1 5.1 Hardware Structure of a Quantum Computer 5-1 5.1.1 Quantum Data Plane 5-2 5.1.2 Control and Measurement Plane 5-2 5.1.3 Control Processor Plane and Host Processor 5-3 5.1.4 Qubit Technologies 5-4 5.2 Trapped Ion Qubits 5-4 5.2.1 Current Trapped Ion Quantum "Computers" 5-5 5.2.2 Challenges and Opportunities for Creating a Scalable Ion Trap Quantum Computer 5-5 5.3 Superconducting Qubits 5-7 5.3.1 Current Superconducting Quantum "Computers" 5-7 5.3.2 Challenges and Opportunities for Creating a Scalable Quantum Computer 5-8 5.4 Other Technologies 5-10 5.5 Future Outlook 5-11 6 ESSENTIAL SOFTWARE COMPONENTS OF A SCALABLE QUANTUM COMPUTER 6-1 6.1 Challenges and Opportunities 6-1 6.2 Quantum Programming Languages 6-2 6.2.1 Programmer-Facing (High-Level) Programming Languages 6-3 6.2.2 Control Processing (Low-Level) Languages 6-4 6.2.3 Software Library Support 6-6 6.2.4 Algorithm Resource Analysis 6-6 6.3 Simulation 6-7 6.4 Specification, Verification, and Debugging 6-8 6.5 Compiling from a High-Level Program to Hardware 6-9 6.5.1 Gate Synthesis 6-11 6.5.2 Quantum Error Correction 6-11 6.6 Summary 6-12 7 FEASIBILITY AND TIME FRAMES OF QUANTUM COMPUTING 7-1 7.1 The Current State of Progress 7-1 7.1.1 Creating a Virtuous Cycle 7-2 7.1.2 Criticality of Applications for a Near-Term Quantum Computer 7-3 7.2 A Framework for Assessing Progress in Quantum Computing 7-4 7.2.1 How to Track Physical and Logical Qubit Scaling 7-4 7.2.2 Current Status of Qubit Technologies 7-7 7.3 Milestones and Time Estimates 7-9 7.3.1 Small (Tens of Qubits) Computer (G1) 7-11 7.3.2 Gate-Based Quantum Supremacy (G2a) 7-11 7.3.3 Annealer-Based Quantum Supremacy (A2) 7-12 7.3.4 Running QEC Successfully at Scale (G2b) 7-12 7.3.5 Commercially Useful Quantum Computer (A3/G3) 7-13 7.3.6 Large Modular Quantum Computer (G4) 7-14 7.3.7 Milestone Summary 7-15 7.4 Quantum Computing R&D 7-16 7.4.1 The Global Research Landscape 7-16 7.4.2 Importance of Quantum Computing R&D 7-18 7.4.3 An Open Ecosystem 7-21 7.5 Targeting A Successful Future 7-22 7.5.1 Cybersecurity Implications of Building a Quantum Computer 7-22 7.5.2 Future Outlook for Quantum Computing 7-22 APPENDIXES A Statement of Task A-1 B Trapped Ion Quantum Computers B-1 C Superconducting Quantum Computer C-1 D Other Approaches to Building Qubits D-1 E Global R&D Investment E-1 F Committee and Staff Biographical Information F-1 G Briefers to the Committee G-1 H Acronyms and Abbreviations H-1 I Glossary I-1

1 0

Re: [math-fun] Stupid QM question
by Henry Baker 07 Dec '18

07 Dec '18

I don't understand. Perhaps I have 2 different problems: the actual physical system and the mathematical abstraction of it. Let's take the math abstraction first. (I prefer a physics-free matrix notation.) Forget about "pure" or "mixed" states; we're talking about matrices & vectors over the standard (uncountable) complex numbers, aren't we? Let's not even get into wave function "collapse"/"measurement"; I'm trying to understand the wave-function evolution first. Let's consider a small set of qbits -- say 3. If I understand what you're saying, the 3 qbits just sit there unless hit by a unitary operator; is this correct? (By "just sit there", I mean *nothing* changes, not even any phase factors, whether observable or not.) Is the "state" of the system a 3-vector of complex numbers or a 3x3 (constant?) matrix of complex numbers? By "state change", I presume that we pre- (or post-) multiply this initial "state" by a 3x3 unitary matrix; correct? So our computation consists of k steps -- an ordered sequence of k matrix multiplications; correct? The time-reversed computation is the conjugate transpose of the entire sequence; correct? So how can I represent a simple harmonic oscillator using one (more more) qbits? Wouldn't a harmonic oscillator "DO" something even if isolated from the rest of the universe? Wouldn't there be some time-variation of the "state" -- i.e., a periodicity? At 12:54 PM 12/7/2018, Mike Stay wrote: >The pure states of a quantum system are given by the eigenvectors of a Hamiltonian operator, which is Hermitian. > >The states are stationary, in the sense that only their phases change over time: |Ï_t> = exp(-iHt/â) |Ï_0>. > >If you want something to *happen*, then you need to perturb the Hamiltonian for some period of time. > >If you want to measure the state, you typically start with two independent Hamiltonians (one for the quantum system and one for a pointer state) and then add a coupling perturbation for some period of time. > >On Fri, Dec 7, 2018 at 12:22 PM Henry Baker <hbaker1(a)pipeline.com> wrote: >> >> As I understand it, a simple quantum system undergoes transitions via unitary transformations. >> >> Unitary transformations preserve inner products, so they are "rigid" rotations of a "configuration" in N-space (assuming that a finite dimensional quantum system can exist). >> >> Nevertheless, from a given "state" (whatever that means), not all unitary transformations seem possible. >> >> For example, if a system is isolated from its environment, wouldn't it "evolve" in an "inertial-like frame" manner? If the rotation analogy is correct, wouldn't this be a rigid constant-speed spin about some axis/plane? Wouldn't this spin have some "angular momentum" (resistance to slowing down) ? >> >> Aren't there other unitary evolutions which will require some external "effort" to change its course -- i.e., axis ? And in this case, wouldn't reversibility require the re-appearance of the conjugate of this "effort" to change the course back?

2 2

Re: [math-fun] Some questions from the 2018 Putnam Exam
by Dan Asimov 07 Dec '18

07 Dec '18

I never got a few things right in the statement of this problem, even on the second try. But now it's right: ----- A2 Let S_1, S_2, ..., S_(2^n−1) be the nonempty subsets of {1,2,...,n} in some order, and let M be the (2^n−1)×(2^n−1) matrix whose (i,j)th entry m(i,j) = 0 if S_i ∩ S_j is empty; m(i,j) = 1 otherwise. Calculate the determinant of this matrix. ----- Allan's point that if the order doesn't matter, the determinant must be 0 also occurred to me. But maybe they're looking for an answer of the form ±[expression] ??? In any case, if the answer doesn't turn out to be too trivial, this is a very cool problem. —Dan

4 3

[math-fun] Stupid QM question
by Henry Baker 07 Dec '18

07 Dec '18

As I understand it, a simple quantum system undergoes transitions via unitary transformations. Unitary transformations preserve inner products, so they are "rigid" rotations of a "configuration" in N-space (assuming that a finite dimensional quantum system can exist). Nevertheless, from a given "state" (whatever that means), not all unitary transformations seem possible. For example, if a system is isolated from its environment, wouldn't it "evolve" in an "inertial-like frame" manner? If the rotation analogy is correct, wouldn't this be a rigid constant-speed spin about some axis/plane? Wouldn't this spin have some "angular momentum" (resistance to slowing down) ? Aren't there other unitary evolutions which will require some external "effort" to change its course -- i.e., axis ? And in this case, wouldn't reversibility require the re-appearance of the conjugate of this "effort" to change the course back?

2 1