- mathfun@mailman.xmission.com - mailman.xmission.com

[math-fun] High school physics problem
by Henry Baker 10 Dec '18

10 Dec '18

Suppose we have a large container not 100% filled with ball bearings (all of exactly the same material & hence density) but with a wide & random variety of radii. The largest ball bearings are << the smallest dimension of the container, and the smallest ball bearings can get into every corner of the container. Initially, the bearings of all sizes are equally distributed w.r.t. location within the filled portion of the container. We're on Earth with its standard gravity g and standard atmospheric pressure & temperature (if that matters). Now shake the container vigorously for quite a while (but not so vigorously enough that the balls become dented or heated!). What is the resulting distribution of sizes after this shaking? A. The same as before. B. The larger balls become more likely in the upper layers. C. The larger balls become more likely in the lower layers. I don't have a proof, but I have an intuition about which answer is correct. Has this problem been studied before?

5 5

Re: [math-fun] The moving now (was: Messages in pi)
by Dan Asimov 10 Dec '18

10 Dec '18

Thoughts about what Mike wrote below: 1. I don't know about this arrow of time. I haven't kept up to date, but isn't there a theorem that if you reverse charge, parity, and time, any movie of something physically possible would still be possible if run backward? (And if charge and parity are not involved, then you can just run the same movie backward without change.) Of course, in our neighborhood of spacetime, we are living in a part of the universe where stars radiate energy in the positive direction of time (t+). Given that fact, things like eggs breaking in t+ but seemingly never reassembling follow from the existence of evolution. But in principle if we could imagine where the recent past of [all spacetime that could affect our present] is being copied — in a CPT-reversed way, at least T — presumably the same past would unfold just like our own future. But Mike himself pointed out that "entropy increases" isn't by itself a fully adequate explanation. 2. Mike asks "More carefully, how could you distinguish the experience of living the events out of order from living them in order, or from living them simultaneously?" My first answer is, It sure *feels* as if the recent past is something that I lived very recently. And the recenter the past, the recenter it feels. It's enough to make one want to locate one's focus in a new place, to recenter oneself. *Maybe* it's just a coincidence that all these moments fit together into a continuous narrative. It feels much more likely that something crucial about how the moments came into being is real-numbery, i.e., somehow 1-dimensional. I think the real numbers R can be characterized as the only connected topological space such that the removal of any point leaves just two connected components. But there may be another condition like, y'know, Hausdorffness or local compactness or homogeneity, that I'd rather not mention, necessary for this uniqueness. But: Would we indeed feel as we in fact do, if all phases of our lives were being lived, kind of, "at the same time" ? Who is feeling all those other moments that we lived or will live? (Not 100% serious, but still.) —Dan "All you have is the state of your brain at that given point in time." I think. —Dan ----- On Wed, Nov 28, 2018 at 1:47 PM Dan Asimov <dasimov(a)earthlink.net> wrote: > > That's probably my preferred view, but there are problems reconciling it with > everyday experience. It would mean that all ages t of (say) me are living their > lives equally, in some sense of equally. > > But how does that explain the experience we have of living our lives in the order > of the real numbers, and the fact that it keeps getting later? A too-cute answer is, "Because the arrow of time points in the direction of increasing entropy." More carefully, how could you distinguish the experience of living the events out of order from living them in order, or from living them simultaneously? All you have is the state of your brain at that given point in time. -----

6 5

[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 08 Dec '18

08 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 07 Dec '18

07 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