Monday, July 5, 2021

Why Quantum Systems are Hard to Simulate

I just listened to Mindscape 153 | John Preskill on Quantum Computers and What They’re Good For:
Depending on who you listen to, quantum computers are either the biggest technological change coming down the road or just another overhyped bubble. Today we’re talking with a good person to listen to: John Preskill, one of the leaders in modern quantum information science. We talk about what a quantum computer is and promising technologies for actually building them. John emphasizes that quantum computers are tailor-made for simulating the behavior of quantum systems like molecules and materials; whether they will lead to breakthroughs in cryptography or optimization problems is less clear. Then we relate the idea of quantum information back to gravity and the emergence of spacetime. (If you want to build and run your own quantum algorithm, try the IBM Quantum Experience.)
Preskill coined the term "quantum supremacy", and supposedly that is the biggest accomplishment in the field, but oddly the term is never mentioned.

Sean M. Carroll is an advocate of many-worlds theory, and Preskill said he is comfortable with that belief.

Preskill referred to Feynman kickstarting the field by a lecture that said that quantum systems are hard to simulate. This supposedly implied that quantum computers are inevitable.

As I see it, there are three main views underlying this thinking.

Many-worlds. If computers are constantly splitting into multiple computers doing different computers, then possibly they can be put to work doing parallel computation, and reporting back a result in one world.

This used to be the eccentric view of David Deutsch, but now Carroll, Preskill, Aaronson, and many others are on board.

Negative probability. In this view, quantum entanglement is a mysterious resource that can have negative or imaginary probabilities, so maybe it can do things better than classical computers that are limited by [0,1] probabilities. This is the preferred explanation of Scott Aaronson.

Pinball. The game of pinball is also hard to simulate because a ball can hit a bumper, be forced to one side or the other in a way that is hard to predict, and then the subsequent action of that ball is wildly different, depending on the side of the bumper. It is a simple example of chaos.

Quantum systems can be like pinball. Imagine a series of 100 double-slits. You fire an electron thru all the slits. At the first slit, the electron goes thru one slit, or the other, or some superposition. The electron has the same choice at the next slit, and it is influenced by what happened at the first slit. Simulating the 100 slits requires keep track of 2100 possibilities.

So pinball is hard to simulate, but no one would try to build a super-computer out of pinball machines.

My theory here is that your faith in quantum computers depends on which of the above three views you hold.

If quantum experiments are glimpses into parallel worlds, then it is reasonable to expect parallel computation to do useful work. If quantum experiments unlock the power of negative probabilities, then it is also plausible there is a quantum magic to be used in a computer. But it quantum experiments are just pinball machines, then nothing special should be expected.

You might say that we know quantum experiments are not classical, as Bell proved that. My answer is that they are not literally parallel universes or negative probabilities either. Maybe the human mind cannot even grasp what is really going on, so we have to use simple metaphors.

The many-worlds and negative probability views do not even make any mathematical sense. Many-worlds is so nutty that Carroll, Aaronson, and Preskill discredit much of what they have to say by expressing these opinions.

Now Aaronson says:

To confine myself to some general comments: since Google’s announcement in Fall 2019, I’ve consistently said that sampling-based quantum supremacy is not yet a done deal. I’ve said that quantum supremacy seems important enough to want independent replications, and demonstrations in other hardware platforms like ion traps and photonics, and better gate fidelity, and better classical hardness, and better verification protocols. Most of all, I’ve said that we needed a genuine dialogue between the “quantum supremacists” and the classical skeptics: the former doing experiments and releasing all their data, the latter trying to design efficient classical simulations for those experiments, and so on in an iterative process. Just like in applied cryptography, we’d only have real confidence in a quantum supremacy claim once it had survived at least a few years of attacks by skeptics. So I’m delighted that this is precisely what’s now happening.
Wow. He consistently said that?

He was the referee who approved Google's claim of quantum supremacy. He has collected awards for papers on that "sampling-based quantum supremacy". Maybe his referee report should have recommended that Google scale back its claims.

Aaronson has also argued that the quantum computing skeptics have been proven wrong. I guess not. It will still take a few years of consensus building.

I am one of those quantum computing skeptics. I thought that maybe someday and experiment would be done that proves me wrong. But apparently that is not how it works.

The experiments are inconclusive, but the experts will eventually settle into the pro or con sides. Only when that happens will I be seen to be right or wrong.

No, I don't accept that. Expert opinion is shifting towards many-worlds, but it is still a crackpot unscientific theory of no value. When Shor's algorithm on a quantum computer factors a number that could not previously be factored, then I will accept that I was wrong. Currently, Dr. Boson Sampling Supremacy himself admits that I have not been proven wrong.

Update: Here is a SciAm explanation:

If you think of a computer solving a problem as a mouse running through a maze, a classical computer finds its way through by trying every path until it reaches the end.

What if, instead of solving the maze through trial and error, you could consider all possible routes simultaneously?

Even now, experts are still trying to get quantum computers to work well enough to best classical supercomputers.


  1. I'm neither quantum nor classical, because I think they can be reconciled. I think what has happened with Many Worlds Interpretations is that there are now enough of them that many people have eventually found one they're OK enough with, which saves having to argue about it, and the negative/imaginary probability thing is a direct enough transliteration of the Hilbert space formalism of QM into a phase space formalism that we can almost say that there's not much to object to except mathematical niceties.
    To the Pinball approach, I think we can't just say it can be done, though de Broglie-Bohm arguably has done it, I think we have to find a detailed way to do it better. If it isn't done in a mathematically general enough way, we'll be constructing models for Bell violation, GHZ, and every new experiment that comes along, so it has to be good in that way.
    I'm pretty sure I've suggested to you before "An algebraic approach to Koopman classical mechanics", in Annals of Physics 2020 and on arXiv, as one way to forge a new mathematical relationship between quantum and classical that is as mathematically general as the negative/imaginary probability approach, so in principle it *might* be able to carry the day, but that also keeps slightly more connection to the pinball approach? It's not just pinball, it's pinball + not-yet-identified-noise, so you may not like that it's different in that way from deBB, which puts all the noise in its initial conditions. I'm not someone who writes a perfect paper every time, unfortunately, so Section 7.1 has its flaws, so there's a followup paper on arXiv (and recently submitted to Annals of Physics), "The collapse of a quantum state as a signal analytic sleight of hand". I discovered as I wrote that paper that because of its mathematics I was becoming OK with a specific form of no-collapse interpretation, so perhaps you might find it curious to see whether you can find a version of Many Worlds that you're OK with through the window it offers. My work gets some but never enough feedback, so I'd welcome you writing a post about that paper's failings, but of course you may not have time when there are so many things to be annoyed at in the quantum boosterism landscape.
    I'm enjoying your posts as usual, with some curiosity in the air whether that will last if you take aim at me and/or my work.

    1. Dear Peter,

      I haven't studied Bohmian mechanics all that well, but still, looking at the papers on Bohmian mechanics and chaos, I seem to agree with your assessment as to how BM handles chaos.

      However, I also think that the "detailed way to do it better" won't be very easy for them either. Reason: They have their particles living in the 3D physical space but their wavefunction in the 3ND configuration space. This fact is bound to keep introducing *theoretical* complexities for them---not just difficulties of calculations.

      I had a look at the two papers you mention, but found them way above my head. So, here is a suggestion / request:

      How would you explain your idea (especially of the second paper)... no, not to *high-school* students, but... say, to such *UG* students who have taken one semester of Modern Physics, followed by one or two semesters of Quantum Chemistry or QM?

      If you write something along this line, then, I guess, feedback even from *experts* will be easier in the coming!


    2. Ajit, I made a number of attempts to write something at a more accessible level last year. In three parts, you could try these (they're not very long),
      (2), and
      As well, Annals of Physics chose AlgKoopman, as I call it, as a highlighted article, so that a journalist, Rob Lea, wrote a "highlight" for it,

      Another way in might be the latest talk I gave about this, at IQOQI in Vienna (by Zoom, of course),, but that's an hour long. The first twenty minutes are not mathematical, but then everything gets into medium algebra.
      I'm coming out of almost nowhere with this, and at 64 I'm some old guy, so it shouldn't be much surprise that the ideas haven't received more attention. Either I'll discover sooner or later why it's nonsense or else, I suppose, some big name will pick up the ideas, with or without many people knowing about these flawed papers of mine.

      The mathematics isn't much above UG physics, except for the Poisson bracket. If it were really sophisticated it would be beyond me doing it. I've come to suspect that a lot of people reading it are more waiting for someone to tell them whether it's right or not than that they don't understand it. If it was in a textbook and you were told you must learn it, you'd be able to with only a little help, but when there are many other and more important calls on your time this rightly doesn't get much.

      I'm not yet ready to write something that tries to be more accessible about the second paper. Its way of sidestepping the measurement problem is kinda tricky and I still don't know what is the best way to say what it does and how. As I make clear in the paper, there are at least premonitions of the idea in the literature already that haven't taken, and this attempt of mine may also fall by the wayside. If it's published by Annals of Physics or elsewhere I'll go on a spree of trying to get people to think about its way of thinking about QM and its relationship to CM, but that's a few months away, even assuming that it's accepted there.

      What I might emphasize now is that I think everything you've learned about "quantization" of a classical system might be best set aside, despite 90 years of being the dominant story. As well, more than as a replacement, we now can have "Koopmanization" as a way to construct a Hilbert space formalism that includes a noise model, *very* loosely as if a pinball is jostled by something like Brownian motion from a lower level, then we can have, with some important details to be noted, isomorphisms between CM and QM.

    3. Ooops...


      I posted a reply to *this* comment of yours, but by mistake, I posted it at the end of this post (all the way down). So, please see there.

      [PS: BTW, while posting it, I also forgot the ending salutation in that reply!]

  2. Roger,

    No, quantum experiments aren't "just" pinball machines. Neither are they "just" Borcherds' tea-pots, or Davis and Aaronson's terra-cotta flower-pots.


    Behaviour of pinball machines, etc., is *primarily* characterized using concepts from classical mechanics. We don't first model these as primarily quantum systems (i.e. with $\Psi$ as the primary unknown), and then use such models to output classical results too. What we lack aren't just powerful enough computers, but, looking at how they go about modeling, I think, we may not even be clear enough about the kind of multi-scaling issues that would be involved in such a task. That is, even if every one would surely agree that "in principle", such "scaling up" is possible.

    OTOH, behaviour of quantum experiments can be modelled using only QM. You can't start with classical mechanics and then "scale down".

    So, there is a definite directionality involved in here, a definite asymmetry.

    In any case, quantum experiments don't involve parallel universes.

    I don't know almost anything about negative probabilities except that their RV has a signed distribution which, in turn, can be expressed as a difference of two strictly non-negative distributions. (See: Gábor J. Székely, "Half of a Coin: Negative Probabilities", a ref to the Wiki article on negative probabilities.)

    Given this factoid, negative probabilities might perhaps stand *some* chance, at least for *some* metaphorical usages, IMO. But parallel universes? Hah!


  3. Peter, it appears that your paper is a good explanation of how a quantum-like formalism also applies to classical mechanics.

    Ajit, I say that the quantum experiments are not classical pinball machines. It is an analogy.

    1. Roger:

      OK, thanks.

      Might as well add another point which I actually had forgotten while writing. As an analogy, the pinball machine is better than the tea-pot, because with the pinball machine, you do have the element of *control* too. Also, the 100 double-slit apparatus in which the slits at any stage can be moved at will.

      Roger and Peter:

      Regarding "how a quantum-like formalism also applies to classical mechanics", here are a couple of links to (patented) ideas of Prof. M. Arif Hasan et al.:

      (Had forgotten this work for a while by now!)


    2. Ajit, thanks for the link to Hasan et al.'s paper in Communications Physics, which I hadn't seen before. I think it doesn't carry the day because it's in terms of amplitudes, not in terms of probabilities. That's more-or-less characteristic of the optics papers they cite (such as [11]). A lot of enthusiasm has been expended on the Hilbert space approach to polarization in optics over quite a number of years, but, I think rightly, to no avail.

      My own work is as abstruse as anything you'll find as I struggle with making it clear to myself as much as to other people what the mathematics might or might not mean, but here I think there's not nearly enough contact with how Hilbert spaces are used as part of quantum measurement, which is all about probability and moments of probability densities. It's crucial, I think, and not easy, to construct a mathematically compelling relationship between classical and quantum mechanics.

    3. Thanks, Roger. I know these papers are far from perfect, as I try to make clear in my responses to Ajit, so if that's it for now, that's fine. If you can figure out something to tell me about what you think it is I'm doing here, however, please tell me, because I'm always trying to tell it better. I'm specially keen on anything that can lead me or anyone else to a compelling elevator pitch.

  4. Dear Peter,

    Thanks for a detailed and considerate response.


    I went through the blog articles, and also watched the first 21 minutes of your IQOQI talk.

    What I've gathered is this much:

    You are attempting to build a new mathematical structure which would allow an isomorphism to be established in between CM and QM. The specific ideas related to CM+ are to be seen in this light.

    Yours is very much a work in progress.

    Your paper *should* be accessible even to the advanced *UG* student of *physics*.

    However, it won't be accessible to students of chemistry or engg., not even to the PG students (and not even if they've taken the QM-I and QM-II sequence), because they wouldn't know the Poisson bracket formalism by heart. ...

    ... No, *maths* by itself is not the main issue. The main issue is: the lack of an "intuition" which *only* develops by seeing how a mathematical formalism is applied in a diverse set of dynamical contexts---in *CM*. One must already know *that*. Only then could one understand the use of Poisson brackets in Dirac's work---or yours.

    Unfortunately, as an engineer, I never studied Poisson brackets. Still, I would like to make the following comment...


    I have two points in mind.

    1. Complex Numbers:

    No matter what mathematical formalism or methods you adopt (Schrodinger, Heisenberg, Dirac, Feynman, ...), QM necessarily involves complex numbers.

    In QM, the *state description* itself must be complex-valued---else, you must work with a *system* of two *coupled* real-valued Schrodinger equations *at all times* (including for specifying the boundary / initial conditions).

    However, CM, in *all* its incarnations (original Newtonian, Leibnitz-Euler-Lagrangian, or the reformulation by Hamilton), has only real-valued *states*. Complex numbers appear in CM only as an intermediate convenience in calculations. But the boundary / initial conditions, as also the final results, are only real-valued quantities. No exception to this characteristic. (Not even in optics / EM waves / polarization / etc.)

    Relevance to your program: The signals you show in the slides are, I guess, all real-valued. Indeed, *any* signal produced by any *actual* detector must always be real-valued, wouldn't it?

    2. Irreversibility:

    Consider a signal produced by a detector, reported as a continuous funtion of time. Suppose it consists of some small noise plus some two different peaks that are irregular but definitely high, and distinct.

    It's our overall phenomenological or empirical knowledge which tells us that such a signal corresponds to two *different* quantum particles---and not to a single quantum particle which happened to get measured twice.

    Yet, going *purely* by the contents of the signal alone, the following scenario *too* is plausible: There was some particle which got measured; it then jumped back into the quantum system, from the detector; some time later, the same particle once again got measured for a second time. (The Bicyle Thief.)

    I am not clear how a mathematical structure which exclusively focuses on (all) the information contained in the detector signals *alone*, might go on to capture this physically crucial fact---namely, that measurements are *irreversible* processes.


    I don't mean to imply that you haven't thought of incorporating features like the two points. Actually, quite on the contrary: I am *unable* to tell whether points like the above two have *already* been incorporated in your framework or not! Your formalism could very well be general and powerful enough to *automatically imply* features like these; you may not have to separately incorporate these features. It's just that *I* don't know the Lagrangian mechanics and the Poisson bracket well enough, to be able to tell such things. So, please take these comments in that sense.

    OK, enough, I guess!

    1. I certainly take your point about the accessibility or otherwise of the Poisson bracket, Ajit. I'm not even knowedgable enough about CM to be able to claim to understand it well. My main point of contact is through what I think of as Dirac's approach: the Poisson bracket is how we construct symmetry transformations of the phase space. If we have the symmetry transformations of the phase space straight in our heads, we don't that much need the Poisson bracket any more.

      "CM, in *all* its incarnations (original Newtonian, Leibnitz-Euler-Lagrangian, or the reformulation by Hamilton), has only real-valued *states*." Except, I would say, in the case of the Liouvillian formalism, where there are probability distributions. Where there are probability distributions there are also their fourier transforms, which are typically called "characteristic functions". As it happens, these can be very useful indeed. Now, we can manage fourier transforms either as sine and cosine transforms or we can introduce an imaginary that makes the management somewhat more easy. The Gibbs thermal state gives us a starting point for a probability distribution, which we then use to construct a Hilbert space. If you read up about real Hilbert spaces, you'll find that they're horrible beasts, so if there's a complex structure we can use it will be far better to use it than not. The noncommutative algebra of transformations that we constructed using the Poisson bracket induces a noncommutative algebra of transformations that act on that Hilbert space.

      I try to make clear, and I believe it's really best, that we should keep particle and other approaches in our heads as well as a Koopman approach. A particle approach works pretty well, provided we're careful when we work with trajectories such as de Broglie-Bohm or other approaches give us, but of course there are many places where people feel that their intuition about particles fails for experiments that are characteristically QMical: in due course we'll discover how effective a Koopman and signal analysis intuition can be. Furthermore, any undergraduate or graduate student who starts putting Koopman ideas into their exam scripts without their professors telling them to had better feel very sure of themselves. This is too much a work in progress, as you say, for students to take this material seriously (yet, or perhaps ever.)

      Irreversibility is definitely an issue! If a model that is intended to be realistic does not include absolutely all degrees of freedom, then I think it ought not to be time-reversal invariant. Models that are time-reversal invariant can be quite good enough, however, for planets et cetera. I suppose one thing that happens is that physics tends to look for situations in which time-reversal invariance applies, more-or-less, as a starting point for investigating how such situations change as increasing irreversibility is added.
      Certainly events in what we call a "detector" are not time-reversal invariant when considered in detail on a short time-scale, because restoring the device to its ready-for-another-event takes much longer than the sudden current increase that causes a record of the time of the event to be saved. Given many such events, however, as in the graphs of events in the YouTube video I linked to, I suspect it wouldn't be specially easy to tell if I had reversed those graphs on the time axis. If that's right, then at the level of statistics irreversibility would not be as much an issue, and, wishing for an easy life, it's easier to work with that case, even though we know that the engineers whose job it is to produce a working avalanche photodiode definitely worried about irreversibility in a practical way.

      OK, enough, I guess!

  5. Dear Peter,

    1. Oh.

    The idea of "symmetry transformations of the phase space" is *totally* absent in my head. Ditto, for the "Liouvillian formalism", and even "Gibbs thermal state". ...Exactly the reason why I stopped after 21 minutes into your talk. (Else, I would've surely continued. (I did skip through the remaining part.))

    As to Dirac's work and the Poisson brackets structure, I gathered the *association* between these two *phrases* from the pop-sci books. And, that's *all* I know about either of them!

    2. Thanks for the explanation regarding:

    Gibbs thermal state -> real-valued probability distribution(s) -> apply Fourier transform -> complex-valued distributions -> a ray in a Hilbert space.

    As I said, I don't know about the "Gibbs thermal state". But it was nice to get to know how you are approaching the issues.

    A question:

    Do you mean to say that you are proposing a layer beneath the first postulate of QM, viz., that the state of a QM system is completely specified by a complex-valued state function? (For the *statements* of postulates, I refer to: )

    A thought:

    What would be the "Gibbs thermal state" and the real-valued probability distribution(s) for: (i) the ground state of a single particle in a 1D box of finite length, and with infinite potential walls at the boundaries? (ii) the "1s" state of the electron in an isolated hydrogen atom (in the infinite 3D space)? ... A tutorial would be handy---for those students who know the pre-requisites.

    3. As I see it, the in-principle time-reversal invariance (TIR for short) is not at all a major issue; *irreversibility* is.

    Here is one way to look at it. A catastrophic branching could still satisfy TIR, and yet, it could still be an irreversible change.

    Simplest example: Consider a 3-body classical system. One of them can permanently escape away from the remaining two.

    A second-simplest example: Two infinitesimally small Lagrangian parcels of fluid follow divergent paths if they fall on different sides of the mathematical singular surface in the flow before a stagnation point.

    In both examples, if you reverse time, all particles would precisely retrace their respective paths---but in reverse. So, instead of a catastrophic branching, you would have a catastrophic "merging" (at least up to the instant specified for the initial condition during the forward time problem).

    As to me: An exponential divergence in trajectories over a finite time interval is good enough to qualify as an "irreversible" change. It doesn't have to be an infinitely large divergence. Mathematicians may disagree. Let them.

    4. Re. Measurement events:

    No, I don't concur with your drift here.

    Reversing the temporal order of the signal would mean *two* things: (i) The region of space (control volume) which we initially called the system now becomes the detector, and the detector now becomes the system. (ii) The order of the two detection *events* reverses.

    However, note, the two particles would still remain two distinct entities---physically. They would *not* become a single particle measured twice---physically. (Wheeler---and also his PhD student---were boringly wrong on this count (though, again, I hasten to add: I haven't studied the path integral approach).)

    Indeed, if the two particles come from different species (say one is an electron and the other a proton), then they would even retain their respective identities. In this case, we could say: the order of the (distinguishable) *particles* has reversed, too.

    5. In case you didn't know: I myself am working on a new approach to the non-relativistic QM.

    [I promise the (potential) bearer of the document that it will arrive in his hands/computer/device, even if none has ever paid for it---with my copyright, of course.]


    1. Typo's:

      1. TIR -> TRI.

      2. [I promise the (future) bearer of the document on my approach that it will arrive in his hands/computer/device, even if none has ever paid *me* for the work---and with my copyright, of course.]


    2. I've looked at your postulates document, though only quickly. It's surprising to me that you mention the tensor product as a way to construct new state spaces only for Dorabantu. There are a LOT more constructions than you have listed here: in particular the algebraic approaches that are often adopted for QFT can also be adopted for QM, but also there have been many more-or-less axiomatic constructions since Lucien Hardy's Have you seen this account in Quanta,

      The algebraic approach is to me not so much "a layer BENEATH the first postulate of QM, viz., that the state of a QM system is completely specified by a complex-valued state function" as an alternative approach to the same mathematics. Physicists commonly focus on the wave function, a vector in a Hilbert space, typically presented in a position or momentum basis, but a vacuum state over an algebra that is more common in the mathematical quantum measurement theory literature. To me it's just a matter of preference for one picture or another of what are very close to being the same mathematical system (though there can be differences of detail that matter): one should try to understand and feel more-or-less comfortable with different approaches, although there are so many that I feel that one is allowed to not know them all:-)

    3. Dear Peter,

      Thanks for the links. As I said in the "preface" to the Postulates document, it's a work in progress. I plan to add other interesting views of the postulates too, though it's not on a high priority. (My current research is limited to non-relativistic QM, for which I guess the material as gathered so far is quite OK.)

      Yes, I had seen the Quanta Mag article. My impression? I wouldn't start from there!

      Frankly speaking, my own research thinking is limited to the Foundational issues, i.e., most saliently, the measurement problem. And this problem can be solved within the context of the non-relativistic QM theory too. My interest in the "quantum-ness" does not go beyond that. Not as of today, anyway.

      I am happy to note that I am *allowed* to not know them *all*! [... BTW, I wouldn't wish it even on my worst enemy ;-) ]

      May be we could close this thread on that happy note?