We provide two simple counterexamples to Kalai's Conjecture C and discuss our perspective on the implications for the prospect of large-scale fault-tolerant quantum computation.
More than ten years ago the author described a parameter K(ρ) for the complexity of n-qubit quantum state ρ and raised the conjecture (referred to as "Conjecture C") that when this parameter is superpolynomial in n, the state ρ is not experimentally feasible (and will not be experimentally achieved without quantum fault-tolerance). Shortly afterward [6] (arXiv:1204.3404), Steve Flammia and Aram Harrow claimed that the simple easy-to-construct W states are counterexamples to "Conjecture C." We point out that Flammia and Harrow's argument regarding W-states is incomplete. Moreover, the emergent picture from experimental progress of the past decade on noisy intermediate scale quantum (NISQ) computers suggests that W-states, as simple as they appear, cannot be achieved experimentally by NISQ computers, and can not be constructed without quantum fault-tolerance.
In this paper I revisit my 2006 conjecture on correlated errors in entangled physical qubits, originally proposed as a potential obstruction to quantum fault tolerance. The conjecture asserts that, in any physical implementation of a quantum computer, the effective noise channel acting on entangled physical qubits contains a joint fully depolarizing component, with a rate comparable to that of two-qubit gate errors. This hypothesized structural constraint goes beyond standard noise models and, if valid, would pose a significant challenge to scalable quantum fault tolerance.
The conjecture remains open, but recent advances in experimental quantum computing bring it within reach of empirical testing on current devices. I also discuss two related directions in my critical study of quantum computation: the role of noise sensitivity and computational complexity in noisy intermediate-scale quantum systems, and the statistical analysis of experimental claims of quantum advantage. Finally, since this paper is written for a volume honoring Yuri Gurevich, I include some reflections on the ways in which my scientific and personal trajectory became intertwined with Yuri's.
The ability of quantum error correction (QEC) to protect logical qubits against physical noise is traditionally quantified by a noise threshold: a critical noise level below which the logical error rate decreases exponentially with code distance. This paper proposes that QEC itself can undergo a phase transition analogous to a physical phase change. We develop a theoretical framework that treats the logical error rate as an order parameter and maps the behavior of large stabilizer codes onto a statistical mechanics model. By analyzing the scaling of logical error probabilities with code distance and noise strength, we identify a continuous phase transition at the threshold, characterized by critical exponents that depend on the code family and noise model. The transition separates a "fault‑tolerant" phase where logical errors are exponentially suppressed from a "fault‑unreliable" phase where logical errors proliferate. We discuss implications for the design of large‑scale quantum computers, potential experimental signatures in current quantum hardware, and the prospect of discovering new quantum information physics through this phase‑transition perspective.