Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum Information and Computation

Counterexamples to Kalai's conjecture C

Steven T. Flammia, Aram W. Harrow

Published Jan 1, 2013• 1 citation
Publisher

Abstract

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.
DOI
10.26421/qic13.1-2-1

Related papers

Counterexamples to Kalai's Conjecture C

Steven T. Flammia, Aram W. Harrow

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.

arXiv:1204.3404•Apr 16, 2012•0 citations

Counterexamples to Kalai's conjecture C

Steven T. Flammia, Aram W. Harrow

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.

Quantum Information and Computation•Jan 1, 2013•1 citation

The Fully Depolarizing Noise Conjecture for Entangled Physical States: A Twenty-Year Perspective

Gil Kalai

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.

quant-pharXiv:2609.33508•Sep 29, 2026•0 citations

Conjecture C Still Stands

Gil Kalai

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.

arXiv:2209.01648•Sep 4, 2022•0 citations

Fault-Tolerant Quantum Computation

Daniel Gottesman

I give a brief overview of fault-tolerant quantum computation, with an emphasis on recent work and open questions.

arXiv:quant-ph/0701112•Jan 16, 2007•6 citations

Practicality of Fault-Tolerant Quantum Computation

Simon J. Devitt, Austin G. Fowler, Lloyd C. L. Hollenberg

•Jan 1, 2005•0 citations
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.
More than ten years ago the author described a parameter K(ρ)K(ρ)K(ρ) for the complexity of nnn-qubit quantum state ρρρ and raised the conjecture (referred to as "Conjecture C") that when this parameter is superpolynomial in nnn, 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 WWW states are counterexamples to "Conjecture C." We point out that Flammia and Harrow's argument regarding WWW-states is incomplete. Moreover, the emergent picture from experimental progress of the past decade on noisy intermediate scale quantum (NISQ) computers suggests that WWW-states, as simple as they appear, cannot be achieved experimentally by NISQ computers, and can not be constructed without quantum fault-tolerance.