Gil Kalai
2019 · arXiv
We give a computational complexity argument against the feasibility of quantum computers. We identify a very low complexity class of probability distributions described by noisy intermediate-scale quantum computers, and explain why it will allow neither good-quality quantum error-correction nor a demonstration of "quantum supremacy." Some general principles governing the behavior of noisy quantum systems are derived. Our work supports the "physical Church thesis" studied by Pitowsky (1990) and follows his vision of using abstract ideas about computation to study the performance of actual physical computers.
Metadata: arXiv. Abstracts retain their original authors’ rights.
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
5 selected excerpts · 5 total mentions
In 2019 you asserted [1] that attempts of creating distance-5 surface code will fail. Do you think you were wrong? If so, what was your mistake and why do you think you made it? If not, what's the problem with the Google's results? Have your estimations of feasibility of quantum computers changed in light of this publication? [1] https://arxiv.org/abs/1908.02499
What does homeopathy need to move forward? What does perpetual motion machinery need to move forward? This is not totally fair; it is possible given certain independence assumptions. But they are likely not physically realizable. It is almost certain that even within our understanding of quantum systems it is simply not possible to have a quantum computer (much less create one). The assumptions necessary to produce a completely uncoupled system are likely invalid; we have yet to produce a compelling experiment to indicate otherwise. [1] [1] https://arxiv.org/pdf/1908.02499
jlokier has explained this beautifully and in more detail than I would have known how. I will just add one thing: basically Quantum Supremacy is yet another test of QM. As long as quantum supremacy could not be demonstrated, there remained a possibility that QM was wrong in this prediction - just like until the Higgs boson was detected, there remained a possibility that the Standard Model was wrong/incomplete. If you're curious of some proposed possible barriers to quantum supremacy from the time before this experiment was completed, Gil Kalai is a major advocate of the impossibility of achieving QS in practice. This paper [0] details some of this arguments. In very…
short, his argument is that it is fundamentally impossible to control quantum states to a sufficient degree of precision to realize an actual quantum computer, that errors will always compound too much (he doesn't believe the Google paper will stand the test of time). I am not a believer in his view, but as far as I understand it is (or was, before the Google experiments) not completely absurd; and it is definitely not supernatural. [0] https://arxiv.org/abs/1908.02499
Many commenters are comparing this to the time sharing era of classical computing. There is an important difference here: we knew that classical computers were useful at the time, even though many people failed to predict that they would become millions of times cheaper and smaller. I’m not a physicist, but it seems to me that it’s still too early to say things like “when a quantum computer with enough qubits is available, factoring large integers will become instant and trivial.” Some experts still doubt whether quantum computing is possible at all [1]. You could not say that about classical computing before the transistor was discovered. And silicon-based computers…
weren’t preceded by a decade of hype about how they were about to blow vacuum tubes out of the water, just as soon as we work out the remaining engineering problems. [1]: https://arxiv.org/abs/1908.02499 I think P ≠ NP is a better analogy. Is it true? Well, most people with an interest in the problem think so, but we don’t know. I think this announcement is about as significant as Amazon releasing some tutorials on computational complexity and giving out a few PhD scholarships for people working on P ≠ NP. Maybe this is what leads to the invention of the “quantum transistor,” but it’s too early to say that integer factorisation will become trivial.
I couldn't disagree with you more. The "author" you are referring to is: https://en.wikipedia.org/wiki/Gil_Kalai He is a multi-award winner, internationally recognized researcher with several dozen publications on mathematics and computer science. > The author raises points in contention, but they largely just seem like nitpicks to me. I am not sure if you and I read the same post if you think that his points of contention are merely "nitpicks". https://gilkalai.wordpress.com/2019/08/21/the-argument-again... https://gilkalai.files.wordpress.com/2019/09/main-pr.pdf https://arxiv.org/abs/1908.02499 https://gilkalai.files.wordpress.com/2019/09/cern.pptx In the paper linked…
by this post, the author first very precisely defines how quantum supremacy is defined: > if you can show that D’ is close enough to D before you reach the supremacy regime, and you can carry out the sampling in the supremacy regime then this gives you good reason to think that your experiments in the supremacy regime demonstrate “quantum supremacy”. Author references an older paper running this experiment, brings up a very good point that there is no quantitative measurement provided of the similarity of D and D': > The Google group itself ran this experiment for 9 qubits in 2017. One concern I have with this experiment is that I did not see quantitative data indicating how close D’ is to D. First point of contention, doesn't seem like merely a "nitpick" and if you disagree I'd love to hear your reasoning. > The twist in Google’s approach is that they try to compute D’ based mainly on the 1-qubit and 2-qubit (and readout errors) errors and then run an experiment on 53 qubits where they can neither compute D nor verify that they sample from D’. In fact they sample 10^7 samples from 0-1 strings of length 53 so this is probably much too sparse to distinguish between D and the uniform distribution If they aren't sampling from D', then they can't compare it to D, and so this violates the basic definition of quantum supremacy via sampling of random circuits. The author's point about sample size being too sparse to compute the difference between D and the uniform distribution is also valid. He made this caveat at the start > A single run of the quantum computer gives you only one sample from D’ so to get a meaningful description of the target distribution you need to have many samples. > What is needed is experiments to understand probability distributions obtained by pseudorandom circuits on 9-, 15-, 20-, 25- qubits. How close they are to the ideal distribution D and how robust they are (namely, what is the gap between experimental distributions for two samples obtained by two runs of the experiment.) Seems like a big oversight to not do multiple runs and to compare the sampled D' distributions.
More from the same topics.
Anders Sandberg, Eric Drexler, Toby Ord
The Fermi paradox is the conflict between an expectation of a high {\em ex ante} probability of intelligent life elsewhere in the universe and the apparently lifeless universe we in fact observe.
Chiyuan Zhang, Samy Bengio, Moritz Hardt +2
Despite their massive size, successful deep artificial neural networks can exhibit a remarkably small difference between training and test performance.
Haoran Xu, Fredrik Kjolstad
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.
Scott Aaronson
In honor of Alan Turing's hundredth birthday, I unwisely set out some thoughts about one of Turing's obsessions throughout his life, the question of physics and free will.