Kalai is known for finding variants of the
simplex algorithm in
linear programming that can be proven to run in subexponential time, for showing that every
monotone property of graphs has a sharp
phase transition, for solving
Borsuk's problem on the number of pieces needed to partition convex sets into subsets of smaller diameter, and for his work on the
Hirsch conjecture on the diameter of
convex polytopes and in
polyhedral combinatorics more generally.
Quantum computing skepticism and conjectures Kalai is a noted skeptic of
quantum computing and argues that true quantum computing, which would give exponential speedups over classical computing, cannot be achieved because of inherent limitations when trying to implement
quantum error correction experimentally. He has engaged in a series of public debates with quantum computing researcher
Aram Harrow on his blog, and has formalized his argument by stating a series of conjectures. Harrow and Steven Flammia published a preprint on
arXiv in 2012 claiming to refute Kalai's Conjecture C, although Kalai later argued in 2022 that there were flaws in their argument. In 2025, Kalai publicly debated quantum computing researcher Matthias Christandl at the
Learned Society of the Czech Republic on whether true quantum computing had already been achieved. Kalai's conjectures are stated as follows:
Conjecture 1 (No quantum error correction). The process for creating a quantum error-correcting code will necessarily lead to a mixture of the desired codewords with undesired codewords. The probability of the undesired codewords is uniformly bounded away from zero. (In every implementation of quantum error-correcting codes with one encoded qubit, the probability of not getting the intended qubit is at least some δ > 0, independently of the number of qubits used for encoding.)
Conjecture 2. A noisy quantum computer is subject to noise in which information leaks for two substantially entangled qubits have a substantial positive correlation.
Conjecture 3. In any quantum computer at a highly entangled state there will be a strong effect of error-synchronization.
Conjecture 4. Noisy quantum processes are subject to detrimental noise. ==Recognition==