Top all-time · #1412
Combinatorics and more
Personal blog · gilkalai.wordpress.commath
Combinatorics and more is a personal blog at gilkalai.wordpress.com about math. Since 2009, 53 different Hacker News readers have linked it 74 times, most often “The Argument Against Quantum Computers – A Very Short Introduction”. It is still writing: the last post was on 2026-10-27, and you can follow it by feed.
Gil Kalai's blog
Most-linked posts?
- The Argument Against Quantum Computers – A Very Short Introduction5 people · 5 mentions · first linked 2020-12-29
- Quantum Computers: A Brief Assessment of Progress in the Past Decade – Gil Kalai4 people · 5 mentions · first linked 2022-05-31
- Quantum computers: amazing progress, but probably false supremacy claims4 people · 4 mentions · first linked 2019-09-24
- The case against Google's claims of "quantum supremacy"4 people · 4 mentions · first linked 2024-12-09
- Poincaré and his friend the baker3 people · 3 mentions · first linked 2019-10-13
- Photonic Quantum Advantage?3 people · 3 mentions · first linked 2020-12-05
- The polynomial Freiman-Ruzsa conjecture has been solved2 people · 2 mentions · first linked 2023-11-13
- /2019/05/10/sansation-in-the-morning-news-yaroslav-shitov-counterexamples-to-hedetniemis-conjecture/2 people · 2 mentions · first linked 2019-06-17
- If quantum computers are not possible, why are classical computers possible?2 people · 2 mentions · first linked 2018-08-14
- An Exponential Improvement for Ramsey Lower Bounds2 people · 2 mentions · first linked 2025-07-23
What Hacker News says?
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-g... . We found in that experiment statistically unreasonable predictions (predictions that were "too good to be true") indicating methodological flaws. We also fo…
Comment linking /2024/12/09/the-case-against-googles-claims-of-quantum-supremacy-a-very-short-introduction/
on “Willow, Our Quantum Chip”Submitted The case against Google's claims of "quantum supremacy" as a story · 183 points
HN discussionThis is yet another attempt to posit NISQ results (Noisy Intermediate Scale Quantum) as demonstrations of quantum supremacy. This does not allow us to do useful computational work; it's just making the claim that a bathtub full of water can do fluid dynamic simulations faster than a computer with a bathtub-full-of-water-number-of-cores can do the same computation. If history is any guide we'll soon see that there ar…
Comment linking /2024/12/09/the-case-against-googles-claims-of-quantum-supremacy-a-very-short-introduction/
on “Willow, Our Quantum Chip”Submitted Quantum computers: amazing progress, but probably false supremacy claims as a story · 126 points
HN discussionFrom what I've parsed of the paper, this appears to fall firmly in the first category. This is a quantum computer simulating a quantum circuit; it's like saying that swirly water in a sink is achieving fluid dynamics supremacy, because we can't compute the results as fast as the water moves. Q12 touches on this. I'd be really interested to hear what Gil Kalai has to say on this particular subject; he's generally pre…
Comment linking /2019/09/23/quantum-computers-amazing-progress-google-ibm-and-extraordinary-but-probably-false-supremacy-claims-google/
on “Scott’s Supreme Quantum Supremacy FAQ”Submitted Test Your Intuition: What does it Take to Win Tic-Tac-Toe as a story · 46 points
HN discussion> 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/quan…
Comment linking /2019/09/23/quantum-computers-amazing-progress-google-ibm-and-extraordinary-but-probably-false-supremacy-claims-google/
on “Scott’s Supreme Quantum Supremacy FAQ”Submitted Photonic Quantum Advantage? as a story · 43 points
HN discussionThe 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-p...
Comment linking /2022/04/02/amazing-jinyoung-park-and-huy-tuan-pham-settled-the-expectation-threshold-conjecture/
on “Elegant six-page proof reveals the emergence of random structure”Submitted Justin Gilmer gave a constant lower bound for the union-closed sets conjecture as a story · 8 points
HN discussionEntry at Gil Kalai's blog on this result: https://gilkalai.wordpress.com/2022/04/02/amazing-jinyoung-p...
Comment linking /2022/04/02/amazing-jinyoung-park-and-huy-tuan-pham-settled-the-expectation-threshold-conjecture/
on “Elegant six-page proof reveals the emergence of random structure”Submitted The Argument Against Quantum Computers – A Very Short Introduction as a story · 7 points
HN discussionInteresting 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...
Comment linking /2018/04/10/aubrey-de-grey-the-chromatic-number-of-the-plane-is-at-least-5/
on “Decades-Old Graph Problem Yields to Amateur Mathematician”Submitted Quantum Computers: A Brief Assessment of Progress in the Past Decade – Gil Kalai as a story · 5 points
HN discussionMy 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-m... Congratulations to Yaroslav Shitov!
Comment linking /2019/05/10/sansation-in-the-morning-news-yaroslav-shitov-counterexamples-to-hedetniemis-conjecture/
on “Mathematician Disproves Hedetniemi’s Graph Theory Conjecture”Submitted Combinatorial Theory Is Born as a story · 5 points
HN discussionNot 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…
Comment linking /2019/10/13/the-story-of-poincare-and-his-friend-the-baker/
on “IBM casts doubt on Google's claims of quantum supremacy”Submitted Recogntion of Algebraic Matroids is Undecidable as a story · 4 points
HN discussionAlso of note is Gil Kalai's updated take on the experiment [1]. The heart of the complaint is that the quantum computer's solution to this problem relies on a calibration process, which is done on a classical computer and requires resources orders of magnitudes higher than the quantum portion of the computation: > The Google experiment actually showed that a quantum computer running for 100 seconds PLUS a classic co…
Comment linking /2019/10/13/the-story-of-poincare-and-his-friend-the-baker/
on “IBM casts doubt on Google's claims of quantum supremacy”Submitted The Case Against Google's Claims of "Quantum Supremacy" as a story · 4 points
HN discussionAnother 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-mich...
Comment linking /2025/02/17/robert-alicki-michel-dyakonov-leonid-levin-oded-goldreich-and-others-a-summary-of-some-skeptical-views-on-quantum-computing/
on “FAQ on Microsoft's topological qubit thing”Submitted Ordinary computers can beat Google’s quantum computer after all as a story · 4 points
HN discussionMy reply was glib but I think in principle correct. The idea of a strictly controlled system in the NISQ domain to validate quantum supremacy in theory is an interesting approach, but it feel deceptive to me because this 127-qubit computer cannot in fact factor 127-bit numbers with Shor's algorithm or anything like that. The accomplishment is more akin to creating a bathtub with 127 atoms and doing fluid dynamic sim…
Comment linking /2021/11/04/face-to-face-talks-and-recorded-videotaped-introductions/
on “IBM unveils 127-qubit quantum processor”Submitted Quantum Computers: A Brief Assessment of Progress in the Past Decade as a story · 4 points
HN discussionI see your Scott Aaronson and raise you one Gil Kalai. https://gilkalai.wordpress.com/2020/12/29/the-argument-again...
Comment linking /2020/12/29/the-argument-against-quantum-computers-a-very-short-introduction/
on “The Great Software Stagnation”Submitted Randomness in Nature as a story · 4 points
HN discussionHere’s a nice write-up by Gil Kalai: https://gilkalai.wordpress.com/2019/05/10/sansation-in-the-m...
Comment linking /2019/05/10/sansation-in-the-morning-news-yaroslav-shitov-counterexamples-to-hedetniemis-conjecture/
on “A Breakthrough in Graph Theory [video]”Submitted Gil’s Collegial Quantum Supremacy Skepticism FAQ as a story · 3 points
HN discussionThe 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 theori…
Comment linking /2008/11/12/impagliazzos-multiverse/
on “NP Complete 3rd Grade Math Problems (2018)”Submitted Why Quantum Computers Cannot Work: The Movie as a story · 3 points
HN discussion
