9

If you drop a glass cup on the ground, it will break and shatter into pieces. This happens all the time and is consistent with quantum mechanics. But it never happens that a shattered glass cup rearranges itself from the ground into someone's hand as a whole glass cup, even though this is also consistent with quantum mechanics. We see from this example that not everything that is consistent with quantum mechanics is possible.

As far as I know, scalable quantum computing has never been demonstrated either backwards in time or forwards in time. So a fortiori, I would think that this would be good enough evidence to suggest that scalable quantum computing is impossible. Yet, some physicists believe that scalable quantum computing is still possible. Why?

Craig Feinstein
  • 980

6 Answers6

10

The reason is Shor error correction. Shor demonstrated that by using 9 bits for every bit, you can reverse any decoherence event on any of the 9 bits by doing some measurements on auxiliary quantities. Before the existence of error correction, it was plausible to say (and Unruh did say) the quantum computers are unphysical, because they require no error in a macroscopic system. This is an impossible position to hold past 1996.

The error correction method has been made more efficient since, by Shor and collaborators, and the upshot is that if you make a small quantum computer which is coherent for long enough time, and you can encode some dozens of qubits robustly so that you can reverse the errors faster than they occur, you can scale up the computation indefinitely without problems.

This makes quantum computation feasable for sure, and there is no way to argue that it is impossible without arguing that quantum mechanics fails.

Ron Maimon
  • 1
  • That's only on paper and 16 years ago. – Craig Feinstein Aug 31 '12 at 03:20
  • 3
    @CraigFeinstein: It's a series of papers for one, with many citations and extensions (including a demonstration that at some finite small decoherence rate quantum computation becomes feasable), and it completely solves the problem. Why would you need another? – Ron Maimon Aug 31 '12 at 08:36
  • Craig your arguments make no sense. There are no known theoretical barriers to a quantum computer working, but there are well understood engineering challenges. This doesn't prove scalable QC is possible, but it certainly doesn't prove the opposite. You can't say something is impossible because it's hard to do, it's like you're saying fusion is impossible because we've been trying to build a reactor for 50 years. –  Aug 31 '12 at 13:50
  • 2
    16 years ago and also an active field since then. See for instance the QEC 2011 conference. – Emilio Pisanty Aug 31 '12 at 14:01
  • The error correction is based on assumptions that are most likely false. – Craig Feinstein Aug 31 '12 at 15:03
  • @CraigFeinstein any evidence or citation for this? It really seems like you're just here to argue. –  Aug 31 '12 at 15:30
  • @zephyr I'm not here just to argue. I'm trying to get to the truth via the Socratic Method. My evidence is the fact that scalable quantum computing requires control of an exponential amount of information. From this, I would expect an exponential amount of errors to correct. – Craig Feinstein Aug 31 '12 at 16:01
  • 1
    @CraigFeinstein: The error correction is based on the assumption of uncorrelated errors. The evidence for this is that this is the same assumption as for classical error correction, and classical error correction works. If quantum error correction fails, it is not likely because the correlations in the environment are correlated by magic, but rather it is because quantum mechanics is not exact. – Ron Maimon Aug 31 '12 at 16:53
  • @RonMaimon That seems to be the consensus among physicists who believe in quantum computing. Then I guess I'm one of those people who believe that quantum mechanics is not exact. Thank you very much. – Craig Feinstein Aug 31 '12 at 17:10
  • 1
    @CraigFeinstein: You are not alone in this belief--- this is at the heart of what makes QM mysterious, and it has finally been distilled to an experimental question. I am not sure if quantum mechanics is exact. If you look at the question 't Hooft asks "Why do some people dismiss simple quantum models?", you will see that like you, he believes quantum mechanics is not exact. I gave a proposal for a hidden variable scheme which in my opinion works, but I genuinely don't know if nature is quantum mechanical or not, at these system sizes. Nobody knows. We'll find out with a quantum computer. – Ron Maimon Aug 31 '12 at 17:28
  • @RonMaimon Can you post your proposal for a hidden variable scheme? – Craig Feinstein Aug 31 '12 at 18:10
  • I think Einstein made sense when he said "God doesn't play dice." That's why I think QM will break down for scalable quantum computing. I think the randomness is not true randomness. It's just a result of us not knowing enough about the system. – Craig Feinstein Aug 31 '12 at 23:07
  • @CraigFeinstein: I gave the basic idea in an answer to 't Hooft's very nice question: http://physics.stackexchange.com/questions/34217/why-do-people-categorically-dismiss-some-simple-quantum-models . His models are the inspiration for these ideas, but I disagree with the precise technical form his models take (the disputes are there too). Frankly, I can only get unitrary amplitude looking rotations from probability, but I have had difficulty even reproducing the free particle Schrodinger equation! But I am reasonably confident it should work, really, despite it's hokey appearence. – Ron Maimon Sep 01 '12 at 03:39
2

I would say it is not "some" but "most" physicists who believe that quantum computing is in principle possible (although many think the engineering challenges will be very hard and have doubts about whether the resulting computers would be worth the cost). The reasons are:

  1. The threshold theorem, which applies even to mildly correlated errors, e.g. see 1207.6131.
    What about skepticism about whether the assumptions are met? (a) I am not aware of serious proposals for error models that would violate this in the sort of systems being considered for quantum computing. Note that there are error models that violate this in chaotic or turbulent systems, like plasma. But these are separated by phase transitions from the systems we can build. (b) We have very good small-scale systems, e.g. see 1402.4848. Again no one has even a proposal for how this will fall apart when this is scaled up. (c) If correlated noise stopped quantum computing, then it would also stop classical computers, which use very similar techniques of error correction (once you see each bit as being encoded in repetition code involving many electrons).

  2. Maybe quantum mechanics is false? The problem is that it's been tested a ton over the last century in a wide range of regimes to a ridiculously high precision. No one can propose a modification that even works on paper that would stop quantum computers but allow all previous observations. One problem is that small modifications that add things like nonlinearity would lead to crazy consequences, like time travel.

In short, the hypothesis that quantum computing is possible is based on a foundation of (a) math, and (b) very well-tested observation. I think it is comparable to the hypothesis that a human mission to Mars is possible.

Urb
  • 2,608
Aram Harrow
  • 151
  • But if there is an entanglement of many qubits together, I would expect a great correlation of errors between the qubits, not the mild correlation that the threshold theorem assumes. After all, entanglement implies correlation in some sense. This is why I am still skeptical. – Craig Feinstein Feb 24 '14 at 16:44
  • Having the evolution depend on the state as you suggest would violate the linearity of the Schrodinger equation, so this is considered by physicists to be a radical and unlikely possibility. If this happened, we probably would have seen it in earlier quantum experiments.

    I mean maybe a radical change in the laws of quantum mechanics is always possible, but no one has put forward a proposal that matches existing experiment and differs from the Schrodinger equation.

     – Aram Harrow Feb 26 '14 at 17:35
  • So quantum mechanics implies that quantum computing is scalable? – Craig Feinstein Feb 28 '14 at 22:01
  • can you please explain further how it would violate the linearity of the schroedinger equation? – Craig Feinstein Feb 28 '14 at 22:13
  • The Schrodinger eq says that d psi / dt = -i H psi where H is the Hamiltonian and psi is the wavefunction. If the state is entangled, that is a statement about psi. If errors occur at some rate, this is a statement about H. If H depends on psi, then this becomes a nonlinear differential equation. – Aram Harrow Mar 03 '14 at 03:12
  • As for your earlier question, it's a long story. The axioms of quantum mechanics alone don't guarantee that we can ever reach very low temperatures for example. As for what is necessary for QC, google "DiVincenzo criteria". – Aram Harrow Mar 03 '14 at 03:15
2

You might find this lecture by Scott Aaronson insightful.

https://www.scottaaronson.com/democritus/lec14.html

He basically makes a very convincing defence of quantum computing against arguments made by quantum computing skeptics. I certainly found it very interesting when I read it!

Also, your "entropic" argument is not entirely correct. A physical system will not change its state to one with much lower entropy spontaneously (except with overwhelmingly low probability). However, it can be brought to a state of lower entropy by performing work on it. This for example is what a refrigerator does!

Urb
  • 2,608
Juan Miguel Arrazola
  • 1,344
  • My argument is not really about entropy. It's about things that don't happen in real life, but can happen in theory. Scalable QM can happen in theory, but there is no evidence that it can happen in real life. Yet, it seems that some physicists believe that it must happen in real life or else QM theory is wrong. – Craig Feinstein Aug 31 '12 at 03:26
  • What do you mean precisely by something that can happen in theory but cannot happen in real life? This is a very troublesome statement. As Aaronson points out, Immanuel Kant even wrote a complete treatise to demolish it. In any case, it is true that there might be some fundamental reason why a quantum computer cannot be built, but all we have is evidence that IT CAN be built. – Juan Miguel Arrazola Aug 31 '12 at 19:14
  • 1
    This whole thing is very confusing to me. I'll have to concede now that I think quantum mechanics must break down once you get things to be on the level of scalable quantum computing. There's just no way I can conceive of it working. Thank you for your answer. – Craig Feinstein Aug 31 '12 at 20:58
  • @craigfeinstein so the reasoning is: (a) I don't know quantum mechanics. (b) I don't see how a quantum computer could work (follows from prop. a). (c) A quantum computer can't work (follows from b). (d) since quantum mechanics provides for quantum computers, it must break at some point before a quantum computer is realized (follows from c). – JDługosz Jul 18 '15 at 09:57
1

Demonstration in "Real Life". Others have given you many other sources, what more do you want?

Survey of NMR Quantum Computing

D-Wave, a commercial vendor

Quantum Information Processing with Trapped ions, (PDF)

Urb
  • 2,608
Antillar Maximus
  • 1,301
  • 7
  • 14
1

Several prominent physicists are on record as being pessimistic about the prospects for unlimited scalability of Quantum Computing - See for example https://arxiv.org/abs/quant-ph/0311039

(I found that link when web-searching on "Gerard 't Hooft" and "sudden death", as I recall him speculating in an on-line lecture that at some calculation/complexity threshold, quantum computing devices would undergo an unaccountable but unavoidable "sudden death", the quantum equivalent of a core dump!)

Urb
  • 2,608
John R Ramsden
  • 817
0

Your information is slightly outdated. Quantum computing is possible. They even successfully implemented Shor's Algorithm to factorize a product of primes. In 2009.

Urb
  • 2,608
iblue
  • 632