⚛️ quantum physics

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

In this paper honoring Yuri Gurevich, the author revisits a twenty-year-old conjecture that correlated noise in entangled qubits contains a fully depolarizing component posing a fundamental challenge to quantum fault tolerance, while also discussing noise sensitivity in NISQ systems, the statistical analysis of quantum advantage claims, and personal reflections on their scientific relationship.

Original authors: Gil Kalai

Published 2026-09-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Gil Kalai

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The dream of building a quantum computer has captivated scientists and engineers for decades, promising machines that could solve problems far beyond the reach of today's most powerful supercomputers. At the heart of this dream is the idea of entanglement, a strange connection where two tiny particles, such as atoms or electrons, become linked so that the state of one instantly influences the other, no matter how far apart they are. This connection is the fuel for quantum power, but it is also incredibly fragile. In the real world, these particles are constantly bombarded by heat, vibration, and electromagnetic waves, causing them to lose their delicate quantum states in a process called decoherence. To build a working computer, engineers must protect these particles from this noise, a challenge so difficult that it requires a concept called fault tolerance. This approach assumes that if errors happen rarely enough and independently of one another, a system can detect and fix them faster than they accumulate, allowing the computer to run complex calculations without collapsing.

However, a twenty-year-old idea proposed by mathematician Gil Kalai suggests that this entire strategy might be built on a flawed assumption about how nature works. In a paper written for a volume honoring his friend and colleague Yuri Gurevich, Kalai revisits a hypothesis he first put forward in 2006. He argues that the noise affecting quantum particles is not as random and independent as current models assume. Instead, he proposes that whenever two physical particles are entangled, the noise acting on them is inherently linked. Specifically, he suggests that there is a significant chance that both particles will be wiped clean of their information at the exact same time, a phenomenon known as joint fully depolarizing noise. If this is true, the errors would not be isolated incidents that a computer could easily fix; they would be synchronized events that overwhelm the system's ability to correct itself, potentially making large-scale quantum computers impossible to build.

Kalai's paper does not claim to have proven this impossibility yet. Rather, it serves as a roadmap for how to test this structural constraint against the physical world. He argues that the standard models used by engineers treat errors on different particles as separate events, like two people dropping their own distinct items. His conjecture posits that in reality, the errors are more like a single gust of wind knocking over two people standing close together. The paper outlines a specific way to check this: by comparing how errors behave when two particles are entangled directly versus when they are entangled indirectly through a third particle. In standard models, indirect entanglement should make the chance of a simultaneous error much smaller, dropping from a linear probability to a quadratic one. Kalai predicts that nature does not allow this reduction; even when the connection is indirect, the probability of both particles failing together should remain high, comparable to the error rate of a direct connection.

The implications of this idea are profound for the field of quantum computing. If Kalai is correct, the errors in a quantum system would not just be a few scattered mistakes that can be cleaned up. Instead, they would be large-scale, synchronized failures where many particles lose their information at once. This would break the mathematical theorems that promise fault tolerance, suggesting that no matter how good the engineering becomes, the noise will always grow too fast to be controlled. The paper also touches on a broader skepticism regarding recent claims of "quantum advantage," where companies have announced that their devices have performed tasks impossible for classical computers. Kalai and his collaborators have developed statistical tools to scrutinize these claims, arguing that the data might not be as robust as reported and that the observed results could be influenced by the very classical computers used to design and calibrate the experiments.

To settle the question, Kalai proposes a series of experiments that could be performed on current devices, which already contain dozens of qubits. He suggests looking at the statistical patterns of errors in these machines to see if they show the signs of the synchronized noise he predicts. This would involve analyzing not just how often errors happen, but how they are correlated across different parts of the system. The paper acknowledges that these tests are difficult and require precise measurements, but it insists that the technology is now advanced enough to attempt them. The goal is not to dismiss the field, but to subject its most optimistic assumptions to a rigorous stress test. If the conjecture holds, it would mean that the path to a universal quantum computer is blocked by a fundamental law of physics. If it is disproven, it would remove a major theoretical obstacle and validate the current engineering approaches.

Throughout the paper, Kalai reflects on the nature of scientific progress and the relationship between theory and reality. He draws parallels between the challenges of quantum computing and other areas where theoretical models struggle to capture the messiness of the real world, such as parallel computing or the limits of human creativity. He also shares personal reflections on his long friendship with Yuri Gurevich, a logician and computer scientist, noting how their shared interest in the gap between abstract theory and practical application has shaped their careers. This personal dimension underscores the paper's central theme: that understanding the limits of computation requires not just mathematical rigor, but a deep, critical engagement with how physical systems actually behave. The paper concludes by emphasizing that the answer to whether quantum computers can be built will not come from a new equation, but from careful observation of the noise in the machines we are building today.

Technical Summary: The Fully Depolarizing Noise Conjecture for Entangled Physical States

1. The Problem
The paper addresses the fundamental feasibility of scalable fault-tolerant quantum computation (FTQC). While the Threshold Theorem asserts that FTQC is possible provided noise rates are below a constant threshold and satisfy locality and weak-correlation assumptions, the author argues these assumptions may be physically unrealistic. The core problem is whether the noise in physical quantum systems inherently contains structural features—specifically, correlated errors—that prevent the exponential suppression of errors required for fault tolerance. The paper revisits a conjecture proposed in 2006 to identify a specific structural obstruction: the inevitability of joint fully depolarizing noise in entangled physical states.

2. Methodology and Formulation
The paper employs a structural approach to noise modeling, distinguishing between mechanistic derivations (specific physical sources like thermal photons) and structural constraints on the effective noise channel.

The Conjecture (FDNC): The central hypothesis is that for any physical implementation of a quantum computer, whenever two physical qubits are entangled (or possess localizable entanglement), the effective noise channel acting on them contains a joint fully depolarizing component.
- Formal Definition: Let $E$ be the effective noise channel on a system containing qubits $A$ and $B$ . Let $D_{AB}$ be the joint fully depolarizing channel (replacing the state of $A$ and $B$ with the maximally mixed state $I_{AB}/4$ ). The conjecture posits that the "depolarizing weight" $w_{AB}(E)$ , defined as the maximum $\lambda$ such that $E = \lambda D_{AB} + (1-\lambda)F$ for some CPTP map $F$ , satisfies:
  $w_{AB}(E) \geq c \cdot E(\psi)$
  where $E(\psi)$ is the entropy of entanglement of the state $|\psi\rangle$ and $c > 0$ is a constant depending on the physical implementation.
- Bell State Case: For maximally entangled Bell states, the conjecture asserts that the weight of the joint fully depolarizing component is comparable to the rate of such noise in elementary two-qubit entangling gates.
- Indirect Entanglement: A critical aspect of the methodology is the claim that this noise component cannot be "purified" or suppressed quadratically (e.g., from $t$ to $t^2$ ) when entanglement is generated indirectly via mediating qubits, measurements, or circuit identities. Standard stochastic noise models allow for such suppression; FDNC asserts nature does not.
Extension to Localizable Entanglement: The conjecture is generalized to pairs of qubits with non-zero localizable entanglement (in the sense of Verstraete–Popp–Cirac), asserting that the noise structure persists even when entanglement is extracted from larger many-qubit states via local measurements.

3. Key Contributions and Theoretical Results

Error Synchronization: The paper demonstrates that the presence of pairwise correlated fully depolarizing errors leads to error synchronization. Using a probabilistic model (Theorem 4.1), the author shows that even if individual error probabilities are small, strong pairwise correlations can force a non-negligible probability of linear-scale simultaneous errors (a "tail event" where $O(n)$ qubits are depolarized).
Distinction in Error Metrics: The analysis highlights a discrepancy between error rates measured by trace distance and those measured by qubit-error counts. A small trace-distance error (distinguishability from the ideal state) can correspond to a large number of physical qubit errors if the error is synchronized and spreads through the computation. This suggests that standard fault-tolerance metrics based on trace distance may underestimate the burden of correlated noise.
Noise Sensitivity and Computational Complexity: The paper contextualizes FDNC within a broader skeptical framework involving noise sensitivity. Citing work with Guy Kindler, the author argues that constant-level noise destroys the high-degree structure of ideal sampling distributions (e.g., in Boson Sampling or random circuit sampling). Consequently, noisy intermediate-scale quantum (NISQ) devices may produce distributions approximable by low-complexity classical processes, rendering "quantum supremacy" claims unattainable without fault tolerance.
Statistical Analysis of Experiments: The paper introduces a statistical framework for scrutinizing experimental claims of quantum advantage (specifically Google's 2019 supremacy experiment). It critiques the reliance on Linear Cross-Entropy Benchmarking (XEB) as a sole metric, arguing it provides limited information about the internal structure of errors. The author raises the concept of "classical-computing interference," where classical processing in calibration or data selection may artificially inflate reported fidelities.

4. Proposed Experimental Tests
The paper outlines feasible experimental avenues to test FDNC, noting that current NISQ devices (10–50 qubits) are within reach of these tests:

Direct vs. Indirect Comparison: Compare the effective noise channel of a Bell pair created directly via a two-qubit gate versus one created indirectly (e.g., via a GHZ state and measurement). FDNC predicts the joint depolarizing weight should remain linear ( $O(t)$ ) in the indirect case, whereas standard models predict quadratic suppression ( $O(t^2)$ ).
Process Tomography: Instead of state tomography of a single Bell state (which cannot distinguish single-qubit from joint depolarization), the paper proposes process tomography using a spanning set of product inputs to reconstruct the full channel and isolate the joint depolarizing component.
Syndrome Analysis: Analyze syndrome data from quantum error-correcting codes for "heavy tails" in the distribution of affected checks, indicative of error synchronization.
Correlation Structure: Examine random-circuit-sampling data for correlations between qubit errors that exceed the $p^2$ expectation of independent noise models.

5. Significance and Claims
The paper claims that FDNC serves as a "structural stress test" for quantum computing. Its significance lies in:

Challenging the Threshold Theorem: If valid, FDNC implies that the weak-correlation assumptions of the Threshold Theorem are physically unattainable, potentially rendering scalable FTQC impossible regardless of engineering improvements.
Operational Principles: The author suggests that in a world without FTQC, standard quantum principles (like the time-energy uncertainty principle or the no-cloning theorem) may acquire stronger operational meanings. For instance, complex quantum states might be unreproducible in practice even if their ideal descriptions are known.
Scientific Rigor: The paper advocates for a shift from "verification" (consistency with a model) to "validation" (accuracy of the model itself) in experimental quantum computing, urging for transparency, raw data access, and statistical scrutiny to detect implausible results or "too good to be true" claims.

The author maintains a modest stance, acknowledging that the conjecture remains open and that the answer lies in precise experimental scrutiny. The paper does not claim to prove the impossibility of quantum computers via a mathematical theorem but rather posits a testable physical obstruction that, if confirmed, would fundamentally alter the trajectory of the field.

Technical Summary: The Fully Depolarizing Noise Conjecture for Entangled Physical States

More like this