Gil Kalai

> 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/

> Let’s remember that it took Google 53 qubits to create an application that could accomplish a supercomputer function. If we want to explore new applications that go beyond today’s supercomputers, we’ll need to see system sizes that are orders of magnitude larger. And it turns out that Google didn't even do that. Further research [1] has indicated that the suspected case of quantum supremacy was not valid, as the problem can be solved classically without a supercomputer. So we have yet to see a demonstration of quantum supremacy from an NISQ system. [1] https://gilkalai.wordpress.com/2022/08/06/ordinary-computers-can-beat-…

Entry at Gil Kalai's blog on this result: https://gilkalai.wordpress.com/2022/04/02/amazing-jinyoung-park-and-hu…

The Hamiltonian cycle is only a motivating example. The conjecture which was proven is much more general. https://gilkalai.wordpress.com/2022/04/02/amazing-jinyoung-park-and-hu…

The Quantum Computer scientists Scott Aaronson and Gil Kalai have casted doubt on this result[1][2]. Also good to note is that Kalai casted doubt on the original Google supremacy result. There are now classical algorithms 6 orders of magnitude faster than the Google quantum experiment[3]. 1.https://www.scottaaronson.com/blog/?p=5122 2.https://gilkalai.wordpress.com/2020/12/06/photonic-huge-quantum-advant… 3.https://arxiv.org/abs/1910.09534

Not sure it's that clear cut, as per the blog post[0] linked elsewhere in this thread[1]: > Recall that a quantum supremacy demonstration would be an experiment where a quantum computer can compute in 100 seconds something that requires a classical computer 10 hours. (Say.) >The Google experiment actually showed that a quantum computer running for 100 seconds PLUS a classic computer that runs 1000 hours can compute something that requires a classic computer 10 hours. 0: https://gilkalai.wordpress.com/2019/10/13/the-story-of-poincare-and-hi… 1: https://news.ycombinator.com/item?id=21334403

> But others, including my good friend Gil Kalai, are on record, right here on this blog predicting that even quantum supremacy can never be achieved for fundamental reasons. I won’t let them wiggle out of it now. Here is Gil Kalai's post from yesterday: "Quantum computers: amazing progress (Google & IBM), and extraordinary but probably false supremacy claims (Google)." https://gilkalai.wordpress.com/2019/09/23/quantum-computers-amazing-pr…

My lesson for today: "Sometimes, the reason that a conjecture is very hard to prove is simply that it is false." Worth to see: https://gilkalai.wordpress.com/2019/05/10/sansation-in-the-morning-new… Congratulations to Yaroslav Shitov!

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…

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…

- 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…

Another recent writeup that adds some nuance to this (and other claims), summarizing the quantum-skeptic positions: https://gilkalai.wordpress.com/2025/02/17/robert-alicki-michel-dyakono…

Quantum Computers: A Brief Assessment of Progress in the Past Decade https://gilkalai.wordpress.com/2022/05/26/waging-war-on-quantum/

Here's a well-informed argument to that end: https://arxiv.org/abs/1908.02499 and a nuanced lay-opinion by the same author: https://gilkalai.wordpress.com/2022/05/26/waging-war-on-quantum/

The current mainstream view is that QC is a very hard but tractable engineering problem. There is no fundamental reason for quantum error-correction to not work, and a demonstration that it cannot would be a major and surprising breakthrough in fundamental physics. This has been our state of understanding for a couple of decades now, and the progress we have been seeing is consistent with this view. To be clear, there are people making sophisticated arguments for fundamental barriers to quantum computation. For instance, the quantum-skeptical mathematician Gil Kalai writes about his thoughts on recent progress on QC at (https://gilkalai.wordpress.com/2022/05/26/waging-war-on-quantum/). His view is considerably more nuanced than this FT article, and much more conducive to learning and discussion. I hope you take the time to read it, and I think I'll submit this to HN main as well.

note for readers: this was prior to 3 quantum supremacy demos, Gil's argument had to...evolve...considerably. here's the latest update: https://gilkalai.wordpress.com/2020/12/29/the-argument-against-quantum…

Unfortunately it's likely to turns out to be spoof: https://gilkalai.wordpress.com/2020/12/29/the-argument-against-quantum…

Some related links: An introduction to the area from before this new breakthrough -- https://www.ams.org/journals/notices/201910/rnoti-p1618.pdf Gil Kalai on the mathematical implications -- https://gilkalai.wordpress.com/2020/01/17/amazing-zhengfeng-ji-anand-n… Lance Fortnow -- https://blog.computationalcomplexity.org/2020/01/quantum-provers-to-in… KW Regen -- https://rjlipton.wordpress.com/2020/01/15/halting-is-poly-time-quantum… Boaz Barak -- https://windowsontheory.org/2020/01/14/mipre-connes-embedding-conjectu… Scott Aaronson -- https://www.scottaaronson.com/blog/?p=4512

Here’s a nice write-up by Gil Kalai: https://gilkalai.wordpress.com/2019/05/10/sansation-in-the-morning-new…

Here's a fun twist on that: https://gilkalai.wordpress.com/2017/09/07/tyi-30-expected-number-of-di…

Interesting tidbit, there was a bug in the computer assisted part of the proof (now fixed): "Many thanks to Brendan McKay and Gordon Royle for letting me know overnight that they had successfully 4-coloured my 1567er; as a result I found a bug in the part of my code that implements the relaxation described in section 5.4 and now it agrees. " Source: https://gilkalai.wordpress.com/2018/04/10/aubrey-de-grey-the-chromatic…

In the past five years I participated in a project (with Yosi Rinott and Tomer Shoham) to carefully examine the Google's 2019 "supremacy" claim. A short introduction to our work is described here: https://gilkalai.wordpress.com/2024/12/09/the-case-against-googles-cla… We found in that experiment statistically unreasonable predictions (predictions that were "too good to be true") indicating methodological flaws. We also found evidence of undocumented global optimization in the calibration process. In view of these and other findings my conclusion is that Google Quantum AI’s claims (including published ones) should be approached with caution, particularly those of an extraordinary nature. These claims may stem from significant methodological errors and, as such, may reflect the researchers’ expectations more than objective scientific reality.

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…

Fast on the heels of me gleefully noticing that the New York Times has apparently started linking to primary source material, we get a University that fails to live up to the same standard (in an article that has a vested interest in having people actually read the article). http://arxiv.org/PS_cache/arxiv/pdf/1011/1011.4105v1.pdf Also, here is an post from the mathematician who solved it himself (from November of last year) http://gilkalai.wordpress.com/2010/11/20/janos-pach-guth-and-katzs-sol… For those who want a simple example of the sort of thing the problem is trying to solve, consider an equilateral triangle. There are 3 points, but only one distance between any pair of points. Consider a square, you have 4 points, but it looks like you are going to be forced to have at least two different distances (the nearest neighbor distance, and the diagonal distance). In general, given n points (placed however we wish), what's the minimal number of distances?

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… 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…