19
$\begingroup$

An answer to another question mentions that

There are arguments that suggests that such machines ["quantum Turing machines"] cannot even be built...

I'm not sure I fully understand the problem, so perhaps I'm not asking the right question, but here's what I could gather.

The slides are presented in a lecture (from 2013) by Professor Gil Kalai (Hebrew University of Jerusalem and Yale University). I watched most of the lecture, and it seems his claim is that there is a barrier to creating fault-tolerant quantum computers (FTCQ), and this barrier probably lies around creating logical qubits from physical components. (timestamp 26:20):

barrier between physical and logical qubits

It sounds like the reason for such a barrier is due to the problem of noise and error-correction. And even though current research takes into account noise, it doesn't do so in the right manner (this is the part I don't understand).

I know many people (e.g., Scott Aaronson) are skeptical of this claim of impossibility, but I'm just trying to better understand the argument:

What is the reason for suggesting that practical quantum computers cannot be built (as presented by Professor Gil Kalai, and has anything changed since 2013)?

$\endgroup$
  • 2
    $\begingroup$ Some good reads: scottaaronson.com/democritus/lec14.html and rjlipton.wordpress.com/2012/01/30/…. $\endgroup$ – Sanchayan Dutta Apr 6 '18 at 20:18
  • 1
    $\begingroup$ Regarding the question if anything have changed since 2013: My 2014 paper with Kindler proposes an argument for why the error-rate cannot be pushed down below the fault-tolerance threshold. This argument (reflected in Sanketh's answer, quotes and links) does not refer to the issue of error-corellation which I studied extensively before 2013. Another thing that has changed is that experiments putting my view into test are now occuring. $\endgroup$ – Gil Kalai Apr 10 '18 at 11:58
  • $\begingroup$ @GilKalai Thank you for the update, it's always an honor to get a response from the original author $\endgroup$ – BurnsBA Apr 10 '18 at 12:12
  • $\begingroup$ related question on mathoverflow: mathoverflow.net/q/302492/84108 $\endgroup$ – glS Jun 11 '18 at 12:09
  • $\begingroup$ A good read by Craig Gidney: Why Will Quantum Computers be Slow? $\endgroup$ – Thomas Klimpel Jun 11 '18 at 19:43
8
$\begingroup$

If your intent is to understand Gil Kalai's arguments, I recommend the following blog post of his: My Argument Against Quantum Computers: An Interview with Katia Moskvitch on Quanta Magazine (and the links therein).

For good measure, I'd also throw in Perpetual Motion of The 21st Century? (especially the comments). You can also see the highlights in My Quantum Debate with Aram Harrow: Timeline, Non-technical Highlights, and Flashbacks I and My Quantum Debate with Aram II. Finally, if you haven't already, see Scott Aaronson's Whether or not God plays dice, I do.

Edit. In response to the comment by @heather, here are some quotes:

First, a brief summary of Kalai's view from his Notices article (see also The Quantum Computer Puzzle @ Notices of the AMS):

Understanding quantum computers in the presence of noise requires consideration of behavior at different scales. In the small scale, standard models of noise from the mid-90s are suitable, and quantum evolutions and states described by them manifest a very low-level computational power. This small-scale behavior has far-reaching consequences for the behavior of noisy quantum systems at larger scales. On the one hand, it does not allow reaching the starting points for quantum fault tolerance and quantum supremacy, making them both impossible at all scales. On the other hand, it leads to novel implicit ways for modeling noise at larger scales and to various predictions on the behavior of noisy quantum systems.

Second, a recent argument for why he thinks classical error correction is possible but quantum error correction is not.

Unlike the repetition/majority mechanism which is supported by very primitive computational power, creating a quantum error correcting code and the easier task of demonstrating quantum supremacy are not likely to be achieved by devices which are very low-level in terms of computational complexity.

(In the above mentioned conversation with Aram Harrow, it is pointed out that if one were to take Kalai's initial arguments directly, then even classical error correction would not possible.)

In the post, Kalai goes on to argue that a primitive quantum computer would not be able to do error correction.

Q: But why can’t you simply create good enough qubits to allow universal quantum circuits with 50 qubits?

A: This will allow very primitive devices (in terms of the asymptotic behavior of computational complexity) to perform superior computation.

Kalai also gave a lecture (YouTube) on why topological quantum computing would not work.

$\endgroup$
  • $\begingroup$ Hello Sanketh, and welcome to Physics Stack Exchange! Link rot can make links unclickable. Because of this, I'd recommend you quote some of the relevant sections of your sources (no need to quote all; just some pertinent bits); that way future readers can see what they said even if the links go dead. Thanks! $\endgroup$ – heather Apr 7 '18 at 2:37
  • 6
    $\begingroup$ @heather Eh. It's Quantum Computing Stack Exchange ;) $\endgroup$ – Sanchayan Dutta Apr 7 '18 at 5:14
  • $\begingroup$ @Blue what do you mean? $\endgroup$ – heather Apr 7 '18 at 21:32
  • 1
    $\begingroup$ @heather Read your previous comment :) $\endgroup$ – Sanchayan Dutta Apr 7 '18 at 21:39
  • $\begingroup$ @Blue shoot! Lol, I guess I've spent too much time reviewing on P.SE! $\endgroup$ – heather Apr 7 '18 at 22:20
5
$\begingroup$

Q: "What is the reason for suggesting that practical quantum computers cannot be built (as presented by Professor Gil Kalai, and has anything changed since 2013)?".

In an interview titled "Perpetual Motion of The 21st Century?" Prof. Kalai states:

"For quantum systems there are special obstacles, such as the inability to make exact copies of quantum states in general. Nevertheless, much of the theory of error-correction has been carried over, and the famous threshold theorem shows that fault-tolerant quantum computation (FTQC) is possible if certain conditions are met. The most-emphasized condition sets a threshold for the absolute rate of error, one still orders of magnitude more stringent than what current technology achieves but approachable. One issue raised here, however, is whether the errors have sufficient independence for these schemes to work or correlations limited to what they can handle.".

In an earlier paper of his titled "Quantum Computers: Noise Propagation and Adversarial Noise Models" he states:

Page 2: "The feasibility of computationally superior quantum computers is one of the most fascinating scientific problems of our time. The main concern regarding quantum-computer feasibility is that quantum systems are inherently noisy. The theory of quantum error correction and fault-tolerant quantum computation (FTQC) provides strong support for the possibility of building quantum computers. In this paper we will discuss adversarial noise models that may fail quantum computation. This paper presents a critique of quantum error correction and skepticism on the feasibility of quantum computers.".

Page 19: "The main issue is therefore to understand and describe the fresh (or infinitesimal) noise operations. The adversarial models we consider here should be regarded as models for fresh noise. But the behavior of accumulative errors in quantum circuits that allow error propagation is sort of a “role model” for our models of fresh noise.

The common picture of FTQC asserts:

  • Fault tolerance will work if we are able to reduce the fresh gate/qubit errors to below a certain threshold. In this case error propagation will be suppressed.

What we propose is:

  • Fault tolerance will not work because the overall error will behave like accumulated errors for standard error propagation (for circuits that allow error propagation), although not necessarily because of error propagation.

Therefore, for an appropriate modeling of noisy quantum computers the fresh errors should behave like accumulated errors for standard error propagation (for circuits that allow error propagation).

(As a result, in the end we will not be able to avoid error propagation.)".

Page 23: "Conjecture B: In any noisy quantum computer in a highly entangled state there will be a strong effect of error synchronization.

We should informally explain already at this point why these conjectures, if true, are damaging. We start with Conjecture B. The states of quantum computers that apply error-correcting codes needed for FTQC are highly entangled (by any formal definition of “high entanglement”). Conjecture B will imply that at every computer cycle there will be a small but substantial probability that the number of faulty qubits will be much larger than the threshold. This is in contrast to standard assumptions that the probability of the number of faulty qubits being much larger than the threshold decreases exponentially with the number of qubits. Having a small but substantial probability of a large number of qubits to be faulty is enough to fail the quantum error correction codes.".

See also his paper: "How Quantum Computers Fail: Quantum Codes, Correlations in Physical Systems, and Noise Accumulation".

Many people disagee, and much has changed, see this Wikipedia page: "Quantum Threshold Theorem", or this paper "Experimental Quantum Computations on a Topologically Encoded Qubit", there's even this paper on quantum metrology where the authors claim that: "Making use of coherence and entanglement as metrological quantum resources allows to improve the measurement precision from the shot-noise or quantum limit to the Heisenberg limit." in their paper: "Quantum metrology with a transmon qutrit" by utilizing additional dimensions.

$\endgroup$
3
$\begingroup$

I can’t comment on the specifics of his arguments, because I don’t claim to understand them fully. But in general, we have to wonder whether quantum mechanics will continue to be valid for many qubit systems and states that are deep within the Hilbert space.

Physics is all about observing nature, building theories, confirming the theories, and then finding where they break down. Then the cycle begins again.

We have never had quantum systems as clean, well-controlled and large as current quantum processors. Devices capable of pulling off ‘supremacy’ are even further beyond our current experimental experience. So it is valid to wonder if this unprobed corner of QM might be where it all breaks down. Perhaps new ‘post-quantum’ effects will appear, that effectively act as uncorrectable forms of noise.

Of course, most of us don’t think it will. And we hope it won’t, or there will be no quantum computers. Nevertheless, we must be open to the possibility we are wrong.

And the minority who think quantum computing will fail should be open to the idea that they are wrong, too. Hopefully, they won’t turn out to be the new brand of ‘Bell violation deniers’.

$\endgroup$
-3
$\begingroup$

This is a false argument, considering that they have already been built. DWave's 2000 qubit system is an adiabatic quantum computer using Grover's algorithm and can work on NP-complete problems. Shor's algorithm is currently implemented for NP-incomplete problems by IBM cloud computing with 16 (cloud maintentance today), 20 (cloud online) and 50 qubit (offline) systems.


The arguments presented by Kalai and others are talking about qubit computing as reliable as silicon computation. As a programmer, I would treat the Shor's algorithm systems as a "guess with quantum and check with silicon" computing platform. The "check" is usually fast enough it can be done in middleware like python. IBM's systems are available using Python and QSM, so a single platform stack can do both on the cloud.


I personally think that Kalai created a paper to further his career. Other people have contributed more reliable quantum circuits recently, but the circuit designs are very problem specific and algorithm implementation specific.


Making full Turing Complete quantum computers (to avoid some silicon components) could involve quantum storage for tracking state. I've discussed but not read about some methods for immutable crystal storage, and the results may involve quantum level storage in extremely durable formats (more durable than thumb drives). Making many assumptions about how Turing Complete Quantum Machines is probably very premature, please consider the answers regarding Turing Machines.

$\endgroup$
  • 3
    $\begingroup$ regardless of the validity of the Kalai's arguments, neither D-Wave "quantum computer" nor current proof-of-principle implementations can be used as empirical evidence against them, as fully fault-tolerant computation has not been demonstrated yet. It is however true that present-day quantum devices could be used to disprove his claims, according to what he himself says (see last paragraph here) $\endgroup$ – glS Apr 6 '18 at 17:59
  • 3
    $\begingroup$ also, the last remark is totally unnecessary $\endgroup$ – glS Apr 6 '18 at 18:00
  • 1
    $\begingroup$ To whoever flagged as low quality/NAA: there is an argument about whether or not this answer is correct, but it is a valid attempt to answer the question, so should be kept here $\endgroup$ – Mithrandir24601 Apr 7 '18 at 7:24
  • 1
    $\begingroup$ @IanSmith Kalai's claim is essentially that there never will be a machine for executing quantum algorithms that is practical and scalable, i.e. with reasonable increasing costs per qubit. This has little to do with Turing completeness. I mean, we're already able to run quantum algorithms by simulating a quantum computer on a classical computer. The question is whether we'll be able to run quantum algorithms efficiently. $\endgroup$ – Discrete lizard Apr 9 '18 at 16:08
  • 3
    $\begingroup$ Claiming that Gil Kalai invented his argument to further his career is completely ridiculous. He had a very distinguished career before he started arguing against quantum computing; if he hadn't, nobody would have listened to him. I think he is wrong, but you deserve all the downvotes you got for calling him dishonest without any evidence. $\endgroup$ – Peter Shor Jun 12 '18 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.