Gil Kalai, a mathematician, writes about combinatorics, probability and his skepticism that quantum computers can achieve quantum supremacy.
HN cites him as a prominent skeptic of Google's supremacy claims, and links his post on the expectation threshold conjecture proof.
Hi! I am under the impression that you're one of the better-known skeptics of the practicality of QEC. And to my untrained eye, the recent QEC claim is the more interesting one of the two.
(I am inclined to ignore the claims about quantum supremacy, especially when they're based on random circuit sampling which as you pointed out made assertions that were orders of magnitude off because nobody cares about this problem classically, and so there is not much research effort into finding better classical algorithms. And of course, there's a problem with efficient verification, as Aaronson mentions in his recent post.)
I've seen a few comments of yours where you mentioned that this is indeed a nice result (predicated on the assumption that it's true) [0, 1]. I worry a bit that you're moving the goalposts with this blog post, even as I can't fault any of your skepticism.
I work at Google, but not anywhere close to quantum computing, and I don't know any of the authors or anyone who works on this. But I'm in a space where I feel impacts of the push for post-quantum crypto (e.g. bloat in TLS handshakes) and have historically pooh-poohed the "store now, decrypt later" threat model that Google has adopted -- I have assumed that any realistic attacks are at a minimum decades away (if they ever come to fruition), and very little (if any) of the user data we process today will be relevant to a nation-state actor in, say, 30 years.
If I take the Willow announcement at face value (in…
- This particular problem was artificially constructed with the specific goal of demonstrating quantum supremacy. It has little to none practical use. Essentially they looked what the easiest thing is for current quantum computers to do, and formulated a problem based on that
- Because of the above point, this does not mean that the quantum computer can do anything useful (definitely not factor numbers). It is nowhere near high fidelity enough to run highly error corrected algorithms (which Shor's and Grover's algorithms demand)
Since this is a mostly theoretical exercise to begin with, it's weird that they mention the computational cost of the classical method in terms of real computer times on supercomputers, and almost don't mention the theoretical bounds. The practical cost doesn't matter much as far as demonstrating quantum supremacy is concerned.
As far as I know, the key to claiming true quantum supremacy in this case, is actually the proof of the theoretical complexity of the classical algorithm. The quantum computer is obviously efficient at solving the problem, considering that the problem was constructed with what a QC is good at in mind. And the hardness of any classical algorithms had been somewhat demonstrated already, by Aaronson and Arkhipov in 2011. They managed to show that if there is a polynomial time classical algorithm capable of solving this sampling problem, then the polynomial hierarchy would collapse, which is seen as extremely unlikely (on the…
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-against-quantum-computers-a-cern-colloquium-and-a-new-paper/
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…
We are very far away.
We are several theoretical and engineering breakthroughs away from a scalable quantum computer with sufficiently many error-corrected, logical qubits to do something useful with Shor's algorithm. The current rate of error-correction needs to decrease by a factor of 10 - 100. The current state of the art in physical qubits needs to increase by a factor of at least 10,000.
If we assume the number of usable physical qubits doubles every year while the decoherence rate halves every year, it's plausible a quantum computer could be designed to break 2048-bit RSA in slightly under 20 years.[1] To be generous, we'll also assume the implementation and engineering work doesn't meaningfully increase that estimate once the design is finished.
This is an optimistic forecast, to put it mildly. There are credible arguments from skeptics[2][3] in the academic community that it's not actually possible to build a quantum computer capable of breaking RSA in practice. Likewise, everything I've mentioned is only in regard to the known unknowns we need to resolve. It's very probable there are a variety of unknown unknowns to contend with as well.
This is also all aside from the possibility (emphasized by the first report I cited) of a looming winter in quantum computing research. In order to actually reach a point where RSA can be broken, the field needs to start paying out the checks it's been writing. This means actually achieving quantum supremacy and developing…
The simplex method is an algorithm for solving LPs; the comparison of a particular algorithm's running time to the complexity of a problem isn't exactly one-to-one. In this particular case, there are algorithms with polynomial-time worst-case guarantees for solving the same problem as simplex, including the classical ellipsoid method and a whole battery of interior point methods.
The only technique complexity theorists have at the moment for finding unconditional lower bounds for a problem's running time is diagonalization, as in the method used for proving the time hierarchy theorem. While this can be used to prove that some problems require exponential time to solve, it is provably too weak to separate P from PSPACE, let alone P from NP. But it is enough to separate P from EXPTIME, meaning that any EXPTIME-hard problem such as Generalized Chess is provably not in P.
The point you touch on with Simplex is interesting, because as you mentioned it works extremely well in practice despite the well-studied lower bounds. There is some line of work that tries to explain it with "Smoothed Complexity" analysis, but despite the polynomial bound the current results are still not terribly satisfying. More generally, I think you were hypothesizing something along the lines of Imagliazzo's "Heuristica" (see https://gilkalai.wordpress.com/2008/11/12/impagliazzos-multiverse/ ), where NP-hard problems are hard in the worst case but actually finding these hard instances is equally…
> From a very amateur perspective, it looked like Gil Kalai was arguing that physical realizations would not be impossible, but work at UIST and Google's "quantum supremacy" result, somehow have proved him wrong ?
I assume you meant "would be impossible"? At any rate, from my slightly less amateurish understanding of the subject, I think that the main contrast between Kalai's claims and Google's results boils down to the following:
- broadly speaking, Kalai is referring to pure quantum computation, more specifically he is computing limits about the efficiency and energy requirements of computers that work exclusively using quantum/linear logic;
- Google's experiment made extensive use of classical computation, and it's unclear to what extent quantum computation actually impacted the result (to the point that some people claim that the entire experiment could be performed classically, see e.g. [1])
Unfortunately, many of the nuances in the debate are lost on me--in the past, I had some forays into the physics and mathematics of QC but was ultimately driven away from the dumb money flowing around--but I would recommend Gil Kalai's blog [2] as it is both accessible and rigorous (albeit being obviously biased toward one side of the argument).
[1] https://arxiv.org/abs/2103.03074
[2] https://gilkalai.wordpress.com/