CS Paper Radar

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

Gil Kalai

cs.CC quant-ph ·submitted 2026-09-27 12:26 UTC · v1
published

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.

Comment
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

Closest papers

Nearest neighbours by meaning across the whole index.

Fault-Tolerant Quantum Computation with Adversarial Errors

cs.CC quant-phcs.IT ·2026-08-17 ·Nikolas P. Breuckmann, Louis Golowich, Umesh Vazirani
theory similarity 0.67
Abstract · v2: minor edits to exposition, updated funding acknowledgments

We prove a fault-tolerance theorem for quantum computation against adversarial noise. For every quantum circuit on $\bar{N}$ logical qudits of depth $\bar{T}$, we construct a fault-tolerant circuit on $N=\text{poly}(\bar{N})$ physical qudits of depth $\bar{T}\cdot\bar{N}^{o(1)}$, which is robust against an adversary who may arbitrarily choose and corrupt an almost-linear number $N^{1-o(1)}$ of physical qudits at each time step. This robustness significantly improves upon prior fault-tolerance theorems, which assumed corruptions were either local and stochastic, or else only act on a polynomially vanishing fraction of qudits. Our fault-tolerance scheme addresses a key bottleneck towards constructing quantum PCPs via the circuit-to-Hamiltonian mapping of Anshu, Breuckmann, and Nguyen (STOC'24). More fundamentally, our result demonstrates that fault-tolerant quantum computation remains possible under noise models that are global, worst-case, and non-Markovian over the full duration of the computation, directly countering concerns that correlated noise could fundamentally undermine quantum fault tolerance. Our construction is based on a new family of subsystem product codes we develop, which have large dimension and distance along with low-weight parity-checks, and which support transversal non-Clifford gates. We show how to perform single-shot fault-tolerant error correction on these codes using a Floquet-like procedure based on the local testability of classical tensor codes. We then obtain a universal fault-tolerance scheme using repeated code switching in a hypercubic qudit architecture. Finally, we recursively compose our scheme with itself to reduce an initially exponential qudit dimension down to a constant.

0.10

Fault-tolerant quantum computation cannot be achieved with constant spacetime overhead

cs.IT quant-ph ·2026-08-26 ·Kishor Bharti, Tobias Haug, Andrew Tanggara
theory similarity 0.65
Abstract · 40 pages

The threshold theorem states that quantum computations can be made reliable below a physical error threshold, at the cost of additional physical qubits and circuit depth. Recent work has reduced these space and time overheads to polylogarithmic or nearly logarithmic scalings, but whether the cumulative spacetime overhead can be constant has remained unclear. Here, we show that even for the simplest task of preserving quantum information in a quantum memory, under an optimistic noise model and allowing general adaptive protocols, there is an unavoidable logarithmic contribution to the cumulative spacetime overhead. This additional cost can nevertheless be shared among many logical qubits, so sufficiently wide computations, including standard implementations of Shor's algorithm, may still achieve constant relative overhead. We further give a positive-rate CSS code construction that attains the memory bound, identify sufficient conditions under which the same scaling extends from quantum memory to fault-tolerant circuit implementations, and derive circuit-size bounds for subsystem spacetime codes. Our work establishes fundamental limits on the resources required for quantum fault tolerance.

0.26

Noise-Awareness in Quantum Software Testing: An Empirical Landscape Analysis

cs.SE quant-ph ·2026-10-18 ·Mir Mohammad Yousuf, Shabir Ahmad Sofi, Bisma Majid
similarity 0.63
Abstract · 25 pages, 7 figures, 10 tables, 1 algorithm

Noisy Intermediate-Scale Quantum (NISQ) hardware has transformed quantum computing into a practical experimental platform while introducing fundamental challenges associated with hardware noise, decoherence, and probabilistic execution. Although quantum software testing (QST) has rapidly emerged as an active research area, it remains unclear to what extent existing testing methodologies explicitly engage with noisy and hardware-constrained execution environments. This paper presents a systematic empirical landscape analysis of noise-awareness in QST research through a deterministic, taxonomy-guided analytical framework applied to 61 papers published between 2018 and 2025 across eight testing paradigms, contrasting how contributions are framed with how they are evaluated. Among the analyzed papers, 47 (77.0%) are noise-oblivious and only 14 (23.0%) explicitly engage with noise-related execution concerns, while only 11 (18.0%) report evaluation on physical hardware or a noisy simulator. Test generation, the largest paradigm, exhibits a noise-awareness rate of only 14.3%, and debugging and repair 18.2%; coverage-based, metamorphic, and differential testing contain no noise-aware contributions. Noise-aware methodologies emerged late and remain outnumbered in all analyzed years. Framing and evaluation are strongly associated (odds ratio 40.5, p < 0.001) yet diverge for individual papers: 5 of the 14 noise-aware papers evaluate only on ideal simulators. Inferential statistical tests are reported in only 16.4% of papers. The classification framework was validated against a blinded, human-coded reference sample, achieving almost perfect inter-rater agreement on testing-technique classification and substantial agreement on noise-awareness. The framework provides a reusable empirical basis for longitudinal analysis of hardware-conscious testing practice.

0.09

Weakly Supervised Quantum Error Mitigation

cs.AI ·2026-09-22 ·Seyed Mohamad Ali Tousi, G. N. DeSouza
similarity 0.63
Abstract

Supervised approaches to quantum error mitigation learn a map from noisy circuit outputs to ideal ones, and therefore require the ideal outputs. Producing those ideal outputs demands noiseless classical simulation, whose cost grows exponentially with system size, so supervision is unavailable in exactly the regime where mitigation matters most. We ask whether cheap, individually unreliable signals drawn from circuit structure and hardware calibration can take the place of ideal labels. We assemble sixteen heuristic labeling functions (stabilizer and parity constraints, relaxation and readout characteristics, local depth, gate counts, and neighboring activity), reconcile their disagreements with a probabilistic label model, and read the resulting per-qubit error probabilities as a readout channel whose inverse mitigates the measured distribution. No ideal output enters the training path. On $147{,}000$ five-qubit circuits executed on two IBM devices, the method removes $24.3\%$ (Algiers) and $28.8\%$ (Hanoi) of the Kullback-Leibler divergence to the ideal distribution, against $15.4\%$ and $21.5\%$ for the strongest published analytical baseline, a margin that holds on both devices and lies far outside its bootstrap interval. Supervised neural models trained on ideal distributions remain stronger where such labels exist, and we quantify that gap rather than setting it aside; the method's claim is to the regime where they do not, since the labels they require cannot be computed for the circuits mitigation is needed for. The codes will be released shortly.

0.22

Entangled Futures: Quantum Computing's Potential and Challenges in Computer Science

cs.ET ·2026-10-21 ·Devki Nandan Jha, Jonte R. Hance, Tomasz Szydlo, Nick Chancellor, Omer F. Rana +1 more
published similarity 0.63
Abstract · 7 pages, 1 figure, 2 tables. Accepted at IEEE IT Professional magazine (just accepted, I got the doi but it may not redirect currently)

Quantum computing represents a fundamental shift in computation, promising to solve problems currently intractable for classical computers. However, misconceptions persist; quantum computers are not universally faster, nor do they replace classical systems. Current Noisy Intermediate-Scale Quantum (NISQ) devices face significant challenges, including decoherence, high error rates, and limited scalability. Additionally, leveraging quantum systems requires rethinking traditional computing principles, adopting different programming models, and addressing the complexities of integrating quantum and classical workflows, making their practical use in computer science both demanding and non-trivial. This article provides a system-level perspective on quantum computing for computer scientists, software engineers, and IT professionals, examining its current capabilities, key architectural and software challenges, and potential paths toward quantum advantage in real-world applications within hybrid quantum-classical environments.

0.29

Live Noise Fingerprints for Quantum Program Analysis

cs.SE quant-ph ·2026-11-14 ·Avner Bensoussan, Karine Even-Mendoza, Debalina Banerjee, Elena Chachkarova, Sophie Fortz +2 more
benchmark similarity 0.63
Abstract

Quantum programs are probabilistic in nature, and noisy execution due to current imperfect hardware further complicates their analysis. In this paper, we study abstract semantics for analysing quantum programs under these conditions. We introduce noise fingerprints, compact descriptions of the observable effects of noise relative to a finite interface of input states and output measurements. We use them to define our abstract domain with respect to the concrete noise-related behaviour. We relate the concrete and abstract domains through a probabilistic Galois connection, extending the Galois-connection framework to distribution-valued interpretations. We study the resulting abstraction in terms of observational soundness, conciseness, efficiency, and ability to adapt to changing noise. We show that polynomial-size interfaces yield exponentially smaller fingerprints than full noise models while preserving the chosen observations, and that fingerprint distance characterises the largest observational discrepancy over the chosen interface. Further, we develop ChanShadow, which reuses noise fingerprints of commonly used short program fragments to analyse noisy execution of whole programs and provides a uniform finite-sample error bound. We construct working examples showing how fingerprints support program analysis. We evaluate fingerprint precision, representation cost, measurement requirements, and behaviour under noise drift. On a synthetic benchmark, fingerprints retain $(99 \pm 1)\%$ of the noise strength information of a full noise model. On simulated noise drift, reusing earlier measurements reduces the number of fresh measurement rounds needed to reach an error tolerance of $0.10$ by a factor of $2.3$ at $95\%$ confidence and by a factor of $27$ under the median-error criterion.

0.22

Noise-Resilient Testing of Quantum Programs Based on Output Dominance

cs.SE ·2026-10-03 ·Yuechen Li, Yige Yang, Tao Yue
similarity 0.63
Abstract

Quantum software testing (QST) is a central quality-assurance activity for checking whether quantum programs conform to their specifications. In the noisy intermediate-scale quantum (NISQ) era, gate, decoherence, and measurement errors distort observed outputs, making it difficult to distinguish program defects from noise. The existing noise-aware QST literature typically mitigates or models noise before applying a test oracle. However, these strategies can incur substantial cost and depend on calibration data, model training, or backend-specific information, limiting their applicability. We present Qomino, a dominance-guided QST approach for judging tests from noisy samples without a separate noise-estimation or mitigation phase. The approach combines decomposition-aware inverse construction, comparison of the expected outcome with the strongest observed competitor, and bounded retries for inconclusive decisions. We evaluate Qomino on 30 controlled buggy variants from six Qiskit programs and six simulated noisy backends, comparing it with six baselines spanning statistical, quantum-specific, and learning-based methods. Qomino achieves 85.65% accuracy over all six programs and 99.95% in the restricted two-program evaluation, significantly outperforming the corresponding baselines. Across the evaluated programs and backends under the stated settings, Qomino is faster than the compared quantum-specific and learning-based methods. Ablation and retry analyses support the contributions of its main components.

0.09

Constant-Overhead Injection into Quantum Codes

cs.IT quant-ph ·2026-09-30 ·Louis Golowich, Venkatesan Guruswami
similarity 0.63
Abstract

We construct the first known fault-tolerant scheme for injecting states into quantum error-correcting codes with constant space and time overhead. That is, we construct a family of constant-rate quantum error-correcting codes for which a set of bare physical qubits can be injected, i.e. fault-tolerantly encoded, into a code block. Similarly, a code state can be ejected, i.e. fault-tolerantly decoded, back into bare physical qubits. We show that these injection and ejection procedures succeed under circuit-level locally stochastic noise, while incurring just a small constant probability of corrupting each qubit, which is unavoidable for bare physical qubits. We also show how to perform fault-tolerant error correction and code-state preparation under locally stochastic noise. All of our gadgets can be implemented with constant quantum circuit depth (i.e. are single-shot), and with a number of physical qubits growing linearly with the number of logical qubits, assuming the ability to run polynomial-sized noiseless classical circuits on the side. We construct our quantum codes by taking a high-dimensional hypergraph product of classical LDPC codes, which in turn are a simplified version of Spielman's linear-time encodable codes (STOC'95). As our resulting product codes are only resilient to physical errors occurring with non-uniform probabilities across qubits, we then show how to concatenate with inner codes of various sizes to obtain fault-tolerance against uniform noise.

0.18