Hard questions about quantum crypto and quantum computing

February 1st, 2013 at 11:47 UTC by Ross Anderson

We’ve been assured for 29 years that quantum crypto is secure, and for 19 years that quantum computing is set to make public-key cryptography obsolete. Yet despite immense research funding, attempts to build a quantum computer that scales beyond a few qubits have failed. What’s going on?

In a new paper Why quantum computing is hard – and quantum cryptography is not provably secure, Robert Brady and I try to analyse what’s going on. We argue that quantum entanglement may be modelled by coupled oscillators (as it already is in the study of Josephson junctions) and this could explain why it’s hard to get more than about three qubits. A companion paper of Robert’s on The irrotational motion of a compressible inviscid fluid presents a soliton model of the electron which shows for the first time how spin-1/2 symmetry, and the Dirac equation, can emerge in a completely classical system. There has been a growing amount of work recently on classical models of quantum behaviour; see for example Yves Couder’s beautiful experiments.

The soliton model challenges the Bell tests which purport to show that the wavefunctions of entangled particles are nonlocal. It also challenges the assumption that the physical state of a quantum system is entirely captured by its wavefunction Ψ. It follows that local hidden-variable theories of quantum mechanics are not excluded by the Bell tests, and that in consequence we do not have to believe the security proofs offered for EPR-based quantum cryptography. We gave a talk on this at the theoretical physics seminar at Warwick on January 31st; here are the slides and here’s the video, parts 1, 2, 3, 4 and 5.

Entry filed under: Academic papers

19 comments Add your own

  • 1. Markus Kuhn  |  February 1st, 2013 at 12:58 UTC

    Which “security proofs offered for EPR-based quantum cryptography” exactly do you think may be affected by anything you say in that paper, and how exactly?

    Oddly, you provide not a single literature reference to any such security proof. I found only a single, extremely vague paragraph talking about quantum cryptography at all (end of page 5), but nothing resembling a sound argument.

    This paper discusses implications of Robert Brady’s new “sonon” interpretation of quantum mechanics. The latter sounds indeed very interesting, but its verification is outside my area of expertise, something I’ll happily leave to professional physicists. The main claim following from his sonon model in this paper is that it would be geometrically and physically impossible to entangle more that 4 qubits with each other simultaneously. If that limit were indeed in place for our universe, it would instantly kill any attempt of quantum computing: any practically useful quantum computer would have to entangle thousands of qubits simultaneously, and for thousands of operations. So I think I have understood the argument of the paper regarding the first half of its title: why quantum computing may be impossible.

    But what about the quantum cryptography half of the title?

    Quantum cryptography is a very different endeavour from quantum computing. Most practically implemented protocols are quantum key distribution systems based on the original BB84 scheme, which does not involve any entanglement, but merely exploits the fact that nobody can measure the exact polarization angle of a single photon. I see nothing in your paper affecting that assumption.

    If you refer to any other quantum-crypto proposals involving entanglement (which?), do these rely anywhere on Alice and Bob being able to entangle more than 4 qubits simultaneously? If not, what exactly does your paper say about these schemes?

    Traditional interpretations of quantum mechanics appear to be extremely weird, because of the “spooky interaction” in the EPR paradox, and Bell’s claim that quantum mechanics cannot be explained more sanely by local hidden variables, judging from experimental evidence. Your coauthor’s work tries to show that Bell might be wrong and that the universe might well run on hidden variables after all, and offers a model to do at least quantum-electrodynamics (electrons, photons). That is extremely interesting, but I am not sure where the implication for quantum cryptography are. You can still implement quantum cryptographic protocols on top of hidden variables.

    Your paper did not even hint at any new attacks against any quantum cryptographic protocol.

  • 2. Jonathan Oppenheim  |  February 4th, 2013 at 03:54 UTC

    Dear Ross,
    Hope things are well, and glad to see your interest in quantum information theory.

    Let me say though, that there are several significant misapprehensions in the paper:

    1) You espouse a local hidden variable model (LHV) of quantum theory. However, you won’t find a single reasonable physicist who believes such models, because they have all been ruled out by hundreds of experiments since 1982 where quantum theory is shown to violate a Bell inequality. All that’s required for Bell’s theorem to kick in, is for the measurements to be carried out at space-like seperated points. That’s it. What the measurements are being carried out on, how long the photons travelled, or how long some other wave travelled is irrelevant. So, you seem to dismiss a number of such experiments, but the reasons you give are irrelevant to Bell’s theorem. The reasons also seem somewhat opaque to me (information doesn’t travel faster than light in quantum theory; which arm the photons when through doesn’t matter; how long the photons travel doesn’t matter for Bell’s theorem; etc.). So, the point is that all we need is for the measurements to be space-like. If you’re going to claim that the entire experimental physics community doesn’t know how to make a space-like separated measurement, you’re going to have to provide more than a few lines of explanation!

    2) As mentioned by the previous commenter, security of quantum cryptography doesn’t rely on a violation of Bell’s theorem. The first, and major protocols (BB84, E91) use measurements which admit an LHV, and their first security proofs (Meyers, Lo-Chau, Shor-Preskill) don’t use a violation of Bell’s theorem to prove security.

    3) Perhaps more to the point than (2) — what conclusions you can draw on quantum cryptography or computation, depends on the extent to which you believe quantum theory or your theory correctly reproduces the results of measurements, and where they differ. It’s a bit unclear from your paper where you stand on this. At one point, you say that your theory reproduces quantum mechanics, and I get the impression you believe it correcly reproduces three qubits (since you seem to agree that we’ve demonstrated complete control, computation, and quantum mechanics for three qubits), but presumably you don’t believe that it reproduces the results of measurements on two qubits (e.g. as in Bell’s theorem). So, not sure what conclusions to draw here.. You also claim that your theory is a local hidden variable version of de Broglie Brohm. But the whole point of de Broglie Bohm is that it’s a non-local hidden variable theory which reproduces quantum theory. So, are you saying that your theory reproduces quantum theory? In which case, you might want to instead claim that you’ve found a classical poly time algorithm for factoring :)

    There’s a number of other perplexing parts of your paper. E.g. time-reversal symmetry does not imply a violation of micro-causality. All classical deterministic theories have this property, and they don’t violate micro-causality. Same with most QFTs (or all, depending on your meaning of time-reversal symmetry). Perhaps these are all better discussed off-line.

    Incidentally, the state of quantum computing is pretty exciting, and it’s not the case at all that we’re stuck at three qubits. See David Devincenco’s overview at this year’s QIP (the slides are there, and the video should be up soon)

    Best,
    Jonathan

  • 3. Anonymous Peon  |  February 5th, 2013 at 01:16 UTC

    What these people are trying to tell you is that your paper is foolish and wrong.

  • 4. Ross Anderson  |  February 5th, 2013 at 15:09 UTC

    Jonathan, you are right to say we have a local hidden-variable model of quantum mechanics. When Robert came up with his soliton model of the electron I was extremely impressed; we were not at the time aware of Yves Couder’s work, and I thought it was striking that a completely classical model could not only give us quantum electrodynamics and lead to a calculation of the fine structure constant. Like you, my immediate next reaction was “What about Bell’s theorem?” and then “Maybe that explains why quantum computing is stuck at three qubits.” We spent several months discussing these issues and, as we explain in our joint paper, we no longer believe that the Bell tests prove what most quantum theorists claim they do. The standard analysis assumes that the wavefunction ψ expresses all the physical state of the system, while in the soliton model there is the χ wave as well, on which ψ is modulated. Once that assumption is challenged, the whole game is open once more. This leaves two possibilities: that there still is spooky-action-at-a-distance, just less of it (what we call the weak soliton hypothesis, which is consistent with Cramer’s transactional interpretation of quantum mechanics and Mead’s version of quantum electrodynamics) or that we can have an underlying classical model of the world (the strong soliton hypothesis). Even if the soliton model turns out to be wrong in both its weak and strong forms, it makes an important contribution by forcing us to clarify the assumptions which underlie foundational arguments.

    Of course “most physicists” believe orthodox quantum mechanics, but then “most physicists” believe that action is local and causal. The apparent contradiction between these popular beliefs intrigued Bell and is what makes Bell tests important. But it’s excessive to claim that I “won’t find a single reasonable physicist who believes such models”; they are explored in fora such as the Emergent Quantum Mechanics workshop, with some of whose attendees we’re having interesting discussions. Incidentally, a number of the other theories being kicked around there also have significant implications for quantum computing, quantum crypto or both.

    As for the Bennett-Brassard quantum cryptosystem, I’m fully aware that it doesn’t use entanglement. In fact Markus and I had a long discussion at our security group meeting on Friday after I presented this work. It may well be that a particular implementation of quantum cryptography is secure (though watch out for this sort of thing); however the security case will be very different. Once there is a local hidden-variables theory of quantum mechanics, or even an emergent theory based on other assumptions, you will no longer be able to invoke a “proof” from physical principles. It will more like making a Tempest security case for a cryptographic device; you’ll have to analyse the electrodynamics of a particular design carefully and test it thoroughly.

    Incidentally, that discussion threw up yet another possible explanation of why we’re stuck at three qubits, and which Markus contributed: the MIMO model. The gist is that there are only three independent degrees of freedom in radio from a single location in a scattering environment. Even though a full description of electromagnetic wave scattering in a building might involve a lot of apparent degrees of freedom (as with the conventional explanation of the quantum mechanical wavefunction) it ultimately reduces to a transformation of the coupling between sender and receiver, given by a matrix that is usually not degenerate. This provides another reason to question the conventional view that since the DeBroglie Bohm guiding waves of two entangled particles formally have six dimensions, they have no interpretation in the geometry of physical space. That doesn’t necessarily follow.

  • 5. Joe Fitzsimons  |  February 5th, 2013 at 17:36 UTC

    Ross, I’m trying to understand your last comment, but I’m lost as soon as you mention the wave function in relation to Bell’s theorem. The fact of the matter is that Bell’s theorem makes no reference to the wave function, since it is not a theorem about quantum mechanics at all, but rather about local hidden variable models. The notion of a wave function should not appear in either the statement or the proof of the theorem.

  • 6. James Gallagher  |  February 5th, 2013 at 19:58 UTC

    Ross, forget multi-quibit arguments, are you aware of the many sophisticated tests of quantum mechanics that have been carried out in the last few decades which prove something like your classical soliton model can not possibly work

    eg from a 2006 paper (including Aspect)

    Experimental realization of Wheeler’s delayed-choice Gedanken Experiment

    Or look at the results of Zeilinger et al, involving many different types of experiments where a local classical theory is ruled out.

    I mean, seriously, are you suggesting you soliton model allows a loophole that all these people have missed?

  • 7. Jonathan Oppenheim  |  February 5th, 2013 at 23:48 UTC

    Dear Ross,
    Joe is right. Like I said in my original post, the only thing that’s required for a Bell-violation besides the statistics themselves is that the measurements to be space-like. That’s it. You need to avoid the situation where Alice’s measurement setting/outcome can be transmitted to Bob’s device before he makes his measurement.

    There are certainly classical theories which can mimic aspects of quantum mechanics (Stochastic Electrodynamics, Spekkens models etc.), and some of them are interesting for various reasons, but if they don’t violate a Bell inequality, then they’ve been falsified by experiment.

    I’m not sure what you mean by “less spooky-action-at-a-distance”, or why this is a desirable feature for a theory to have (sounds like being a little bit pregnant), but if you mean that you want to alter your theory just slightly so that it now has a small non-local hidden variable, then you have to contend with this theorem: http://arxiv.org/abs/0801.2218

    The link you give lists a number of researchers, but I know of none of them who would suggest that a theory of nature doesn’t need to violate a Bell inequality. Even ‘t Hooft.

    Best,
    Jonathan

  • 8. Robert Brady  |  February 6th, 2013 at 01:54 UTC

    Regarding Bell’s inequality, I hope the following clarification is helpful.

    It is recognised that Cramer’s transactional interpretation of quantum mechanics is consistent with experiments on Bell’s inequality, as is Mead’s adaptation of it. Both of these approaches are referenced in the sonon paper, together with a discussion of why the motion of sonons is consistent with them.

    The underlying reason for the consistency is that Euler’s equation is time reversal symmetric. Cramer’s model makes use of the same time reversal symmetry. It might be thought unsatisfactory to rely on this property, which is why we suggest the alternative hypothesis, that it may be possible to interpret the sum of the advanced and retarded solutions in terms of a spacelike function. When I presented the paper to fluid dynamicists at Warwick recently, they were surprised there was any problem with there being non-local motions as a result of Euler’s equation (which in turn surprised me because the equation itself is, strictly speaking, completely local). Nevertheless, this is an open suggestion regarding an interpretation. The motion itself is consistent with experiments on Bell’s inequality for the reason described above.

  • 9. Slava Kashcheyevs  |  February 6th, 2013 at 08:07 UTC

    Dear Ross and Robert,

    classical models, however beautiful, have no capacity to approach any problem that quantum mechanics solves using the the notion of entangled states (aka many-particle superpositions), regardless of interpretation. At behest of my quantum information colleagues, I have made an explicit list of well known physical phenomena that invalidate your approach:

    No threat to quantum cryptography (at least from quirks of fluid mechanics).

  • 10. Jules Winfield  |  February 6th, 2013 at 18:51 UTC

    English, motherf*****! Do you speak it?

    Seriously, though, I read this blog post five times and I’m completely lost. Is there any kind of layman’s explanation for what’s going on? I’m reasonably conversant in scientific terminology, but this is really obscure.

  • 11. James Gallagher  |  February 6th, 2013 at 23:02 UTC

    Hi,

    In case you didn’t get the point of my post above, even before you get to Bell inequalities and multi particle arguments your “classical” model of QM already fails according to modern experiments.

    I posted above an example of an experiment where a SINGLE photon is shown to exhibit behavior that cannot possibly be explained by a local classical model. This should be your first concern – forget anything more complicated.

    In fact, if you can refute the claim of the Aspect et al 2006 paper that no local hidden variable model could explain it then that in itself would be something pretty astonishing.

  • 12. Jan-Åke Larsson  |  February 7th, 2013 at 09:55 UTC

    Hi Ross and Robert,

    First of all, I do agree that Bell experiments up to now are not entirely conclusive. No single experiment rules out all the “loopholes” (locality, efficiency, …). However, I would also agree with Jonathan that the experiments together form a strong basis for argument. Any hidden-variable mechanism that gives the appropriate behavior for all of these experiments would have to be complicated. But I like to keep an open mind. I’d like to understand-not just postulate a Hilbert space and calculate.

    I really like Couder’s experiments but one has to keep in mind that it is a classical-physics example of a system that behaves almost like Bohmian mechanics. The important difference is that Couder’s fluid has a finite propagation speed, while Bohmian mechanics has infinite propagation speed of the “quantum potential.” Bohmian mechanics is manifestly nonlocal (and this has nothing to do with dimensionality, I might add). You seem to be saying that the soliton model is local, since it is Lorentz invariant. At low amplitude, you say-does this mean it is really only approximately Lorentz invariant? This would be a downer.

    My work on improving Bell tests has led me to look closely at quite a few local hidden variable proposals. They mainly fall in two categories: those that are in fact nonlocal, and those that cannot give the quantum predictions. A properly local hidden variable model is bounded by the Bell inequality, full stop. I might add here that the Bell inequality is not related to quantum mechanics as such; it is a statement about classical models (of a particular kind). Your model would be of the latter kind, unless it is really nonlocal because of the approximation I asked about. This means it cannot give all the quantum predictions, like long distance Bell violations. How fast does the correlations drop in your model? At what distance is there no violation anymore?

    I’ve also been looking at a single spin-1 system to determine what a hidden-variable model would look like for that system. No locality issues arise, but it turns out that the quantum-mecanical predictions can only be had if the model is – for lack of a better word – ugly. Robert’s paper is about a spin-1/2 particle. Any attempts to go to higher spins?

  • 13. Ross Anderson  |  February 7th, 2013 at 17:03 UTC

    Slava #9: I answered this question when you posed it on Scott Aaronson’s blog. Briefly, you think we must do a lot more work before we convince the mainstream physics community to take sonon theory seriously as an interpretation of quantum mechanics, like (say) the Copenhagen, transactional or many-worlds interpretations. We agree. However I think it’s unreasonable for you to ask us to rework the entire standard model, not to mention the exchange interaction, the gyromagnetic ratio, superconductivity and much else. That sets a much higher bar for us than for other people who have come up with novel interpretations. As a starter, would you be prepared to take sonon theory more seriously if we came up with further non-trivial results, such as on superconductivity or the weak interaction?

    James #11: In the 2006 paper, Aspect sends photons along two 48m fibres, combines them, and they display an interference fringe – even if the light source is dimmed to single photons. Carver Mead’s model explains this.

    Jan-Åke #12: This is a really interesting point, and one of the strong points of the soliton model rather than a “downer”. The nonlinear effects explain the Bose behaviour of light which is exploited all around us in lasers, while the fact that they average out over a cycle ensures that the expectation values (which are all you can measure) are all Lorentz covariant.

    We don’t have anything on spin-1 particles ready for publication.

    I’ll leave it to Robert to discuss the details of correlated spins and the standing wave between particles, but as a possibly useful analogy, consider a world in which no information travels faster than the speed of sound in water. A tsunami sets off from Indonesia and many hours later arrives simultaneously at Madras and Madagascar. The fact that the carrier wave is still phase coherent doesn’t mean that information can be transmitted instantaneously between these two places.

  • 14. Robert Brady  |  February 7th, 2013 at 17:27 UTC

    Jonathan #7, Jan-Åke #12 Here’s more on the correlated spins.

    Let’s refer to the correlated spins in Figure 5b as |ud>. As you would expect from Bell, most of the fluid energy is not localised near the sonons. It is in the standing wave between them, which has an antinode on the mirror line.

    The standing wave is mathematically equivalent to an advanced wave and a retarded one, as in the Feynman/Mead models of QED. That doesn’t mean information can be transmitted faster than c (whether the speed of sound, or of light, depending on the model) – See Ross #13.

    The usual spin superpositions are also valid solutions. For example, |ud> + |du>, which has two separate standing waves. Following Mead’s model, suppose another device resonates with the wave of, say, |ud>. It will parasitically drain energy from |du>. This corresponds to “measuring” |ud> and removing the |du> state. The measurement is nonlocal in the sense described above.

  • 15. Joe Fitzsimons  |  February 7th, 2013 at 19:05 UTC

    Ross, I’m afraid I am again having difficulty parsing your comments. In #13 you refer to “sonon theory” as an interpretation of quantum mechanics, yet your present preprint is based on the fact that it diverges from the predictions of quantum mechanics is certain regimes. These are mutually exclusive, since any interpretation must yield identical predictions to quantum mechanics in all regimes, as otherwise it would be an entirely distinct theory and not an interpretation at all.

  • 16. James Gallagher  |  February 7th, 2013 at 20:47 UTC

    Hi Ross,

    you forgot to mention that the Aspect et al 2006 experiment includes a spacelike separated quantum random number generator which “decides” the configuration of the interferometer.

    However, I assumed you were emphasizing a true local classical model, like the ones in fluids you discuss in the paper – but if you are saying that’s not possible (after all) and you do in fact require Mead’s time-travelling wave model then I’m not sure your conclusions on bounding entanglement to a few qubits are at all justified.

    btw, you quote Nikolic as saying the Copenhagen Interpretation would not have been needed if the Bohm Interpretation had come along first, well, in fact it did come first, as promoted by de Broglie and discussed at the famous 1927 Solvay conference ( see the free 533 page book Quantum Theory at the Crossroads: Reconsidering the 1927 Solvay Conference )

  • 17. Fred D.  |  February 10th, 2013 at 08:28 UTC

    Hi all,

    All the quantum experiments only indicate that Bell’s inequalities are violated and that is all. They don’t actually do anything to prove that Bell’s Theorem is correct. BT is all about probabilities on the real line. As soon as you go to topological arguments involving parallelized 3-spheres, you can get probabilities that match quantum mechanics. Joy Christian’s local realstic model does just that which you can find inin his book. And more generally, Dr. Christian has shown that all quantum correlations can be explained by parallelized 7-sphere topology.

    Now, since entanglement is shown to be just an illusion by Dr. Christian, if quantum computing is relying on that, then Ross and Robert are correct that it is going to be extremely difficult if not impossible to have scalable quantum computers. However, quantum probabilities do in fact beat Bell’s linear probabilities so perhaps some advantage could be had from that. Dr. Christian doesn’t think so.

    There is more about Dr. Christian’s work here “On the Origins of Quantum Correlations” . I’m afraid the quantum computer folks are going to be struggling with their problem for quite some time.

  • 18. Richard H  |  February 15th, 2013 at 15:45 UTC

    I wonder if the enormous funding is coming from military or here, for the promise to crack encryption.

    I seriously doubt there would be so much funding for the remainder of the limited applications identified that quantum computers *might* solve.

    Reversible logic would have been a far better way to spend the research money. (power reduction)

  • 19. Richard H  |  February 15th, 2013 at 15:47 UTC

    somehow my message got edited.

    on the first line it should say [insert national spook hq] after military.

Leave a Comment

Required

Required, hidden

Some HTML allowed:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Subscribe to the comments via RSS Feed


Calendar

February 2013
M T W T F S S
« Jan   Mar »
 123
45678910
11121314151617
18192021222324
25262728