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

arXiv:2609.33508

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

Gil Kalai

quant-phcs.CCSubmitted Sep 27, 2026• Announced Sep 29, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

AI Summary

The paper revisits the Fully Depolarizing Noise Conjecture (FDNC), proposed as a possible obstruction to scalable quantum fault tolerance. It conjectures that entangled physical qubits necessarily experience a joint fully depolarizing channel component whose weight is comparable to elementary two-qubit depolarizing noise, including when entanglement is generated indirectly. Formally, it proposes $w_{AB}(\mathcal E)\ge cE(\psi)$, where $w_{AB}$ is the largest admissible convex weight of joint depolarization and $E$ is entanglement entropy, with an extension to localizable entanglement. A three-qubit mediated-CNOT example sharpens the proposed distinction from independent gate-local noise. If each elementary two-qubit gate fully depolarizes its pair with probability $t$, the effective endpoint channel has joint depolarizing weight exactly $t^2$, although its Bell-state output has a maximally mixed contribution $2t-t^2$. FDNC instead predicts an order-$t$ channel weight. Proposed tests therefore use process tomography rather than Bell-state tomography alone. An elementary moment-problem theorem illustrates error synchronization under a specified classical pair-error law: marginal error probability $2t/3$ and joint probability $t/3$ force, for fixed $0<s<1/2$ in a stated low-noise regime, $\Pr(S\ge sn)\ge [(1-2s)/(3(1-s))]t+o(1)$. A quadratic polynomial certificate and matching three-point distribution establish sharpness. This model illustrates rather than derives synchronization from general FDNC channels. The conjecture remains open; no new experimental test or microscopic derivation is supplied. Channel inference, preparation/measurement errors, drift, leakage, and tomography gauge freedoms are identified as obstacles. The paper also surveys noise-sensitivity arguments and statistical critiques of quantum-advantage claims.

Some signs of AI-generated textOverclaimsStrong assumptionsUnclear novelty

Central claim may not hold: The claimed implication from FDNC to large-scale error synchronization lacks a derivation connecting its separate channel-decomposition bounds to the common classical error distribution and marginal constraints assumed in Appendix B.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
50 pages, 4 figures, to appear in: Fields of Logic and Computation IV: Essays dedicated to Yuri Gurevich, Guillermo Badia, Manfred Droste, Andreas Blass, and Nachum Dershowitz, editors

Related papers

A framework of partial error correction for intermediate-scale quantum computers

Nikolaos Koukoulekidis, Samson Wang, Tom O’Leary +3 more

Abstract As quantum computing hardware steadily increases in qubit count and quality, one important question is how to allocate these resources to mitigate the effects of hardware noise. In a transitional era between noisy small-scale and fully fault-tolerant systems, we envisage a scenario in which we are only able to error-correct a fraction of the qubits required to perform an interesting computation. In this work, we develop concrete constructions of logical operations on a joint system of a collection of noisy and a collection of error-corrected logical qubits. Within this setting and under Pauli noise assumptions, we provide analytic evidence that brick-layered circuits display on average slower concentration to the “useless” uniform distribution with increasing circuit depth compared to fully noisy circuits. We corroborate these findings by numerical demonstration of slower decoherence with an increasing fraction of error-corrected qubits under depolarizing noise acting at the circuit level. We find that this advantage only manifests when the number of error-corrected qubits passes a specified threshold which depends on the number of couplings between error-corrected and noisy registers.

arXiv:2306.15531•npj Quantum Information•Jul 1, 2026•12 citations

Correlated Decoherence and the Possible Limits of Scalable Fault-Tolerant Quantum Computing: A Symmetry-Based Perspective

Pavel Straňák

Over three decades after the formulation of early quantum algorithms, the realization of large-scale, fault-tolerant quantum computers remains constrained within the Noisy Intermediate-Scale Quantum (NISQ) regime. This paper critically re-evaluates the foundational assumptions underlying the Quantum Threshold Theorem and scalable Quantum Error Correction (QEC). We contrast classical error-suppression paradigms—specifically von Neumann’s majority-logic architecture for unreliable components—with the physical realities of continuous SU(2) symmetries in Hilbert space. We argue that the physical implementation of fault-tolerant quantum computing relies on a highly idealized model of uncorrelated, local Markovian noise, whose physical realizability at macroscopic scales remains contested. By examining interaction Hamiltonians in highly entangled macroscopic states, we demonstrate that collective decoherence channels and spatial noise correlations scale nonlinearly with register size n. This correlated phase drift acts as a directional force field—analogous to a long-wavelength hydrodynamic gradient across a field of coupled oscillators—rendering spatial averaging and independent syndrome measurements mathematically incapable of distinguishing systemic logic from collective environmental shifts. Consequently, we propose that universal quantum computers should not be conceptualized as scalable digital Turing machines, but rather as highly specialized, analog physical emulators bound by fundamental physical limits of continuous symmetry preservation.

•Oct 26, 2026•0 citations

Strategies for a practical advantage of fault-tolerant circuit design in noisy trapped-ion quantum computers

Sascha Heußen, Lukas Postler, Manuel Rispler +5 more

Fault-tolerant quantum error correction provides a strategy to protect information processed by a quantum computer against noise which would otherwise corrupt the data. A fault-tolerant universal quantum computer must implement a universal gate set on the logical level in order to perform arbitrary calculations to in principle unlimited precision. In this paper we characterize the recent demonstration of a fault-tolerant universal gate set in a trapped-ion quantum computer [Postler et al., Nature (London) 605, 7911 (2022)] and identify aspects to improve the design of experimental setups to reach an advantage of logical over physical qubit operation. We show that various criteria to assess the break-even point for fault-tolerant quantum operations are within reach for the ion trap quantum computing architecture under consideration. Furthermore, we analyze the influence of crosstalk in entangling gates for logical state preparation circuits. These circuits can be designed to respect fault tolerance for specific microscopic noise models. We find that an experimentally informed depolarizing noise model captures the essential noise dynamics of the fault-tolerant experiment that we consider, and crosstalk is negligible in the currently accessible regime of physical error rates. For deterministic Pauli state preparation, we provide a fault-tolerant unitary logical qubit initialization circuit, which can be realized without in-sequence measurement and feed-forward of classical information. Additionally, we show that nondeterministic state preparation schemes, i.e., repeat until success, for logical Pauli and magic states perform with higher logical fidelity over their deterministic counterparts for the current and anticipated future regime of physical error rates. Our results offer guidance on improvements of physical qubit operations and validate the experimentally informed noise model as a tool to predict logical failure rates in quantum computing architectures based on trapped ions.

arXiv:2301.10017•Physical Review A•Apr 17, 2023•26 citations

Detrimental Decoherence

Gil Kalai

We propose and discuss two conjectures on the nature of information leaks (decoherence) for quantum computers. These conjectures, if (or when) they hold, are damaging for quantum error-correction as required by fault-tolerant quantum computation. The first conjecture asserts that information leaks for a pair of substantially entangled qubits are themselves substantially positively correlated. The second conjecture asserts that in a noisy quantum computer with highly entangled qubits there will be a strong effect of error synchronization. We present more general conjectures for arbitrary noisy quantum systems.

arXiv:0806.2443•Jun 15, 2008•7 citations

Characterizing Errors in Quantum Information Processors

Yuval R. Sanders

Error-free computation is an unattainable ideal, yet our world now contains many computers that appear error-free to their users. That such things are possible is explained by sophisticated theorems that demonstrate the possibility of efficiently reducing computational errors introduced by reasonably well-behaved noise. My thesis is about the problem of determining whether noise in prototype quantum information processors is sufficiently well-behaved for fault-tolerant quantum computing to be possible. My work is divided into two themes. The first theme is the interpretation of average gate fidelity, a quantity that has become the standard performance metric for assessing progress towards fault tolerance. I have elucidated the connection between average gate fidelity and the requirements of fault-tolerant quantum computing by demonstrating the limits of fidelity as a proxy for error rate, the usual metric in fault-tolerance literature. I thereby conclude that information additional to fidelity is required to assess progress towards fault-tolerance. The second theme is the characterization of two-level defect systems, a particularly deleterious kind of noise that can affect superconducting-integrated-circuit-based quantum computing prototypes. I have designed statistical experimental design algorithms that can rigorously assess the influence of these defect systems, and I helped develop a proposal to mitigate their influence. I thereby demonstrate that existing experimental techniques can become much more powerful by employing advanced data collection procedures. My work has immediate implications for current research efforts towards the first working quantum computer. Theoretical work should be directed at assessing noise sources using metrics other than average gate fidelity, and future experimental characterization techniques should become more modular in order to incorporate advanced statistical inference techniques like the ones I develop herein.

•May 12, 2016•2 citations

Decoherence Impediments in Quantum Computing and Fundamental Challenges of Quantum Error Correction

Shahebaz Ahmed Khan, Abdul Ahad Afroz, Shaik Subhan Ali

This review synthesizes current understanding of decoherence pathways across leading hardware platforms and explains why several experimentally observed noise features—drift, burst events, coherent components, correlated and non-Markovian structure, and leakage—can be disproportionately damaging for QEC. Decoherence remains the dominant impediment to scalable quantum computing because it is not a single error mechanism but a system-level phenomenon arising from materials defects, electromagnetic loss, control electronics, measurement backaction, and the broader environment in which a processor operates. Quantum error correction (QEC) is designed to algorithmically suppress physical noise, yet its practical success depends on how closely real devices satisfy the assumptions under which fault tolerance is proved: approximate locality, weak temporal correlations, sufficiently stochastic error statistics, low leakage, and reliable syndrome extraction. We then evaluate fundamental and engineering challenges that shape the viability of QEC at scale: syndrome measurement fidelity, correlated error suppression, decoding latency and classical co-processing, architectural constraints (connectivity, crosstalk, calibration overhead), and the resource cost of implementing a universal fault-tolerant gate set. Recent demonstrations of below-threshold behaviour and “break-even” regimes show that QEC is transitioning from theory to practice, but also clarify what remains unresolved: maintaining stable noise below fault-tolerance targets over long times, scaling to many logical qubits with low correlated-error rates, and integrating hardware-aware codes and decoders. We conclude with research priorities that treat decoherence and QEC as part of a co-designed stack spanning device physics, control, architecture, and algorithms.

Asian Journal of Research in Computer Science•Dec 24, 2025•2 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.
The paper revisits the Fully Depolarizing Noise Conjecture (FDNC), proposed as a possible obstruction to scalable quantum fault tolerance. It conjectures that entangled physical qubits necessarily experience a joint fully depolarizing channel component whose weight is comparable to elementary two-qubit depolarizing noise, including when entanglement is generated indirectly. Formally, it proposes wAB(E)≥cE(ψ)w_{AB}(\mathcal E)\ge cE(\psi)wAB​(E)≥cE(ψ), where wABw_{AB}wAB​ is the largest admissible convex weight of joint depolarization and EEE is entanglement entropy, with an extension to localizable entanglement.
A three-qubit mediated-CNOT example sharpens the proposed distinction from independent gate-local noise. If each elementary two-qubit gate fully depolarizes its pair with probability ttt, the effective endpoint channel has joint depolarizing weight exactly t2t^2t2, although its Bell-state output has a maximally mixed contribution 2t−t22t-t^22t−t2. FDNC instead predicts an order-ttt channel weight. Proposed tests therefore use process tomography rather than Bell-state tomography alone.
An elementary moment-problem theorem illustrates error synchronization under a specified classical pair-error law: marginal error probability 2t/32t/32t/3 and joint probability t/3t/3t/3 force, for fixed 0<s<1/20<s<1/20<s<1/2 in a stated low-noise regime, Pr⁡(S≥sn)≥[(1−2s)/(3(1−s))]t+o(1)\Pr(S\ge sn)\ge [(1-2s)/(3(1-s))]t+o(1)Pr(S≥sn)≥[(1−2s)/(3(1−s))]t+o(1). A quadratic polynomial certificate and matching three-point distribution establish sharpness. This model illustrates rather than derives synchronization from general FDNC channels.
The conjecture remains open; no new experimental test or microscopic derivation is supplied. Channel inference, preparation/measurement errors, drift, leakage, and tomography gauge freedoms are identified as obstacles. The paper also surveys noise-sensitivity arguments and statistical critiques of quantum-advantage claims.
Abstract As quantum computing hardware steadily increases in qubit count and quality, one important question is how to allocate these resources to mitigate the effects of hardware noise. In a transitional era between noisy small-scale and fully fault-tolerant systems, we envisage a scenario in which we are only able to error-correct a fraction of the qubits required to perform an interesting computation. In this work, we develop concrete constructions of logical operations on a joint system of a collection of noisy and a collection of error-corrected logical qubits. Within this setting and under Pauli noise assumptions, we provide analytic evidence that brick-layered circuits display on average slower concentration to the “useless” uniform distribution with increasing circuit depth compared to fully noisy circuits. We corroborate these findings by numerical demonstration of slower decoherence with an increasing fraction of error-corrected qubits under depolarizing noise acting at the circuit level. We find that this advantage only manifests when the number of error-corrected qubits passes a specified threshold which depends on the number of couplings between error-corrected and noisy registers.
Over three decades after the formulation of early quantum algorithms, the realization of large-scale, fault-tolerant quantum computers remains constrained within the Noisy Intermediate-Scale Quantum (NISQ) regime. This paper critically re-evaluates the foundational assumptions underlying the Quantum Threshold Theorem and scalable Quantum Error Correction (QEC). We contrast classical error-suppression paradigms—specifically von Neumann’s majority-logic architecture for unreliable components—with the physical realities of continuous SU(2) symmetries in Hilbert space. We argue that the physical implementation of fault-tolerant quantum computing relies on a highly idealized model of uncorrelated, local Markovian noise, whose physical realizability at macroscopic scales remains contested. By examining interaction Hamiltonians in highly entangled macroscopic states, we demonstrate that collective decoherence channels and spatial noise correlations scale nonlinearly with register size n. This correlated phase drift acts as a directional force field—analogous to a long-wavelength hydrodynamic gradient across a field of coupled oscillators—rendering spatial averaging and independent syndrome measurements mathematically incapable of distinguishing systemic logic from collective environmental shifts. Consequently, we propose that universal quantum computers should not be conceptualized as scalable digital Turing machines, but rather as highly specialized, analog physical emulators bound by fundamental physical limits of continuous symmetry preservation.
Fault-tolerant quantum error correction provides a strategy to protect information processed by a quantum computer against noise which would otherwise corrupt the data. A fault-tolerant universal quantum computer must implement a universal gate set on the logical level in order to perform arbitrary calculations to in principle unlimited precision. In this paper we characterize the recent demonstration of a fault-tolerant universal gate set in a trapped-ion quantum computer [Postler et al., Nature (London) 605, 7911 (2022)] and identify aspects to improve the design of experimental setups to reach an advantage of logical over physical qubit operation. We show that various criteria to assess the break-even point for fault-tolerant quantum operations are within reach for the ion trap quantum computing architecture under consideration. Furthermore, we analyze the influence of crosstalk in entangling gates for logical state preparation circuits. These circuits can be designed to respect fault tolerance for specific microscopic noise models. We find that an experimentally informed depolarizing noise model captures the essential noise dynamics of the fault-tolerant experiment that we consider, and crosstalk is negligible in the currently accessible regime of physical error rates. For deterministic Pauli state preparation, we provide a fault-tolerant unitary logical qubit initialization circuit, which can be realized without in-sequence measurement and feed-forward of classical information. Additionally, we show that nondeterministic state preparation schemes, i.e., repeat until success, for logical Pauli and magic states perform with higher logical fidelity over their deterministic counterparts for the current and anticipated future regime of physical error rates. Our results offer guidance on improvements of physical qubit operations and validate the experimentally informed noise model as a tool to predict logical failure rates in quantum computing architectures based on trapped ions.
We propose and discuss two conjectures on the nature of information leaks (decoherence) for quantum computers. These conjectures, if (or when) they hold, are damaging for quantum error-correction as required by fault-tolerant quantum computation. The first conjecture asserts that information leaks for a pair of substantially entangled qubits are themselves substantially positively correlated. The second conjecture asserts that in a noisy quantum computer with highly entangled qubits there will be a strong effect of error synchronization. We present more general conjectures for arbitrary noisy quantum systems.
Error-free computation is an unattainable ideal, yet our world now contains many computers that appear error-free to their users. That such things are possible is explained by sophisticated theorems that demonstrate the possibility of efficiently reducing computational errors introduced by reasonably well-behaved noise. My thesis is about the problem of determining whether noise in prototype quantum information processors is sufficiently well-behaved for fault-tolerant quantum computing to be possible. My work is divided into two themes. The first theme is the interpretation of average gate fidelity, a quantity that has become the standard performance metric for assessing progress towards fault tolerance. I have elucidated the connection between average gate fidelity and the requirements of fault-tolerant quantum computing by demonstrating the limits of fidelity as a proxy for error rate, the usual metric in fault-tolerance literature. I thereby conclude that information additional to fidelity is required to assess progress towards fault-tolerance. The second theme is the characterization of two-level defect systems, a particularly deleterious kind of noise that can affect superconducting-integrated-circuit-based quantum computing prototypes. I have designed statistical experimental design algorithms that can rigorously assess the influence of these defect systems, and I helped develop a proposal to mitigate their influence. I thereby demonstrate that existing experimental techniques can become much more powerful by employing advanced data collection procedures. My work has immediate implications for current research efforts towards the first working quantum computer. Theoretical work should be directed at assessing noise sources using metrics other than average gate fidelity, and future experimental characterization techniques should become more modular in order to incorporate advanced statistical inference techniques like the ones I develop herein.
This review synthesizes current understanding of decoherence pathways across leading hardware platforms and explains why several experimentally observed noise features—drift, burst events, coherent components, correlated and non-Markovian structure, and leakage—can be disproportionately damaging for QEC. Decoherence remains the dominant impediment to scalable quantum computing because it is not a single error mechanism but a system-level phenomenon arising from materials defects, electromagnetic loss, control electronics, measurement backaction, and the broader environment in which a processor operates. Quantum error correction (QEC) is designed to algorithmically suppress physical noise, yet its practical success depends on how closely real devices satisfy the assumptions under which fault tolerance is proved: approximate locality, weak temporal correlations, sufficiently stochastic error statistics, low leakage, and reliable syndrome extraction. We then evaluate fundamental and engineering challenges that shape the viability of QEC at scale: syndrome measurement fidelity, correlated error suppression, decoding latency and classical co-processing, architectural constraints (connectivity, crosstalk, calibration overhead), and the resource cost of implementing a universal fault-tolerant gate set. Recent demonstrations of below-threshold behaviour and “break-even” regimes show that QEC is transitioning from theory to practice, but also clarify what remains unresolved: maintaining stable noise below fault-tolerance targets over long times, scaling to many logical qubits with low correlated-error rates, and integrating hardware-aware codes and decoders. We conclude with research priorities that treat decoherence and QEC as part of a co-designed stack spanning device physics, control, architecture, and algorithms.