Fault-tolerance thresholds for long-range correlated non-Markovian Hamiltonian noise: realistic fault-path phases, spatial layout, tailored gadgets, and the marginal decay regime $z\le D$

Aharonov, Kitaev, and Preskill (PRL 96, 050504, 2006) proved a version of the quantum accuracy threshold theorem for non-Markovian noise in which always-on perturbations $H_{ij}$ act collectively on arbitrary pairs of system qubits and on the bath: scalable fault-tolerant quantum computation is possible if the cumulative per-qubit coupling $\eta=\max_i(\sum_j\|H_{ij}\|)t_0$ is below a constant $\eta_0$, which holds for algebraically decaying interactions $\|H_{ij}\|\sim 1/r^z$ whenever $z>D$ in $D$ spatial dimensions. The authors themselves flag, however, that the rigorous threshold estimates ($\varepsilon_0\approx 10^{-5}$, $\eta_0\approx 10^{-10}$ for two-body interactions) are likely far too pessimistic because the proof allows worst-case constructive interference of fault-path amplitudes, and that the analysis leaves several directions unquantified. The paper leaves the following directions open: (i) quantify the threshold when the phases of distinct fault paths are only weakly correlated; (ii) rigorously quantify how spatial layout choices, such as separating qubits of the same code block, raise the threshold; (iii) construct and analyze fault-tolerant gadgets tailored to suppress correlated long-range faults; and (iv) determine threshold existence and scaling in the marginal and slow-decay regimes $z\le D$ where the AKP per-qubit coupling sum diverges.

Background

The quantum accuracy threshold theorem is the central result of quantum fault-tolerance theory: an arbitrarily long ideal quantum computation can be simulated with high reliability by noisy hardware, with reasonable overhead, provided the noise is below a critical accuracy threshold. Early proofs assumed Markovian noise, modeled as a completely positive trace-preserving map applied at each circuit location, which corresponds physically to a bath whose state is refreshed after every gate. The theorem was later extended to non-Markovian noise, where the bath has an arbitrarily long memory, via a system-bath Hamiltonian description $H=H_S+H_B+H_{SB}$: Terhal and Burkard (Phys. Rev. A 71, 012336, 2005) handled local system-bath couplings, and Aliferis, Gottesman, and Preskill (arXiv:quant-ph/0504218, 2005) proved a rigorous threshold $\varepsilon_0>2.73\times 10^{-5}$ for local noise using concatenated distance-3 codes — quantum codes built by recursively nesting a short code whose smallest block corrects any single-qubit error — a result whose recursive gadget-level analysis is the machinery the present question builds on. In these 'short-range' models, two system qubits interact directly only when an ideal gate couples them during a time step. The long-range question was then formulated by Aharonov, Kitaev, and Preskill (PRL 96, 050504, 2006): they let the always-on perturbation act collectively on arbitrary pairs of system qubits and on the bath, $H_{SB}=\sum_{ij}H_{ij}$ with $\|H_{ij}\|$ decaying algebraically with the qubit separation $r$, and proved that scalable fault-tolerant computation survives when the cumulative per-qubit coupling is small, which the decay faster than $1/r^D$ in $D$ spatial dimensions guarantees. Their proof reduces the long-range noise to the local-noise framework above through an interaction-picture perturbation expansion summed to all orders, in which the contribution of each 'fault path' — a combinatorial set of circuit locations at which faults occur along the level-reduction argument — is bounded; here a 'gadget' is the prescribed fault-tolerant implementation of one ideal operation (elementary gates plus error correction), whose failure the recursive, level-by-level analysis bounds in terms of a small number of faults in the level below. The authors state that the resulting rigorous threshold numbers are 'probably much too pessimistic' because the analysis lets all bad fault paths add with a common phase and interfere constructively, and they leave unquantified how much stronger noise could be tolerated under realistic weakly correlated phases, how spatial layout and gadget design raise the threshold, and what happens when the decay is no faster than $1/r^D$.

Problem Statement

Within the always-on system-bath Hamiltonian framework of Aharonov, Kitaev, and Preskill — noise $H_{SB}=\sum_{\langle ij\rangle}H_{ij}$ acting collectively on qubit pairs (or $k$-body generalizations) and on an arbitrarily long-lived bath, with cumulative per-qubit coupling $\eta=\max_{i,\text{time}}(\sum_j\|H_{ij}\|)t_0$ (the maximum over qubits $i$ and, for time-dependent couplings, over time; $t_0$ is the gate time) — determine the actual conditions and magnitude under which scalable fault-tolerant quantum computation remains possible, going beyond the pessimistic adversarial bounds and the $z>D$ sufficiency established in 2006. Concretely, the problem is the one the source paper leaves open, with the following jointly supporting the single objective of matching the rigorous theory to the expected practical tolerability of long-range correlated, non-Markovian noise: (i) prove a threshold theorem, or a rigorous improved bound on the threshold ($\varepsilon_0\approx 10^{-5}$, $\eta_0\approx 10^{-10}$ in the original analysis), under assumptions on the relative phases of distinct fault-path amplitudes that are weaker than the worst case of a common phase (e.g., phases only weakly correlated), with the admissible class of phase-correlation models to be stated explicitly and required to be physically well motivated, quantifying how much stronger noise can then be tolerated; (ii) give a rigorous analysis, within this framework, of how spatial layout choices — such as spatially separating qubits belonging to the same error-correcting code block — raise the effective threshold; (iii) construct fault-tolerant gadget designs tailored to suppress correlated long-range faults and prove their effectiveness against the long-range Hamiltonian noise model, quantifying the resulting threshold improvement; and (iv) determine whether a positive threshold exists, and how it scales with system size and geometry, in the marginal and slow-decay regimes $z\le D$ where the per-qubit sum $\sum_j\|H_{ij}\|$ diverges in the thermodynamic limit — including whether the $z>D$ condition is necessary, or an impossibility/adversarial-noise result holds. Directions (i)-(iv) are all in scope and jointly constitute the objective within the single framework above, each to be resolved to the rigorous standard stated in its own clause above (a threshold theorem or improved bound under the phase assumption for (i); a quantitative layout-dependence analysis for (ii); a gadget construction with an effectiveness proof for (iii); and an existence, scaling, or impossibility determination for the marginal regime $z\le D$ for (iv)). Any answer should preserve the source's conventions (recursive fault-tolerant constructions for which the local-noise condition $\|E(I_r)\|\le\varepsilon^r$ suffices — where $I_r$ denotes the ideal operation restricted to a specified set of $r$ qubits, so that an $r$-qubit fault carries weight at most $\varepsilon^r$ — gate time $t_0$, $D$ spatial dimensions, algebraic decay $\|H_{ij}\|\lesssim 1/r^z$) and should not be restricted to particular finite sizes, geometries, or code families.

References

1. Dorit Aharonov, Alexei Kitaev, and John Preskill, "Fault-tolerant quantum computation with long-range correlated noise", Phys. Rev. Lett. 96, 050504 (2006), DOI 10.1103/PhysRevLett.96.050504, https://arxiv.org/abs/quant-ph/0510231 (primary source)
2. Panos Aliferis, Daniel Gottesman, and John Preskill, "Quantum accuracy threshold for concatenated distance-3 codes", Quantum Information and Computation 6, 97-165 (2006), arXiv:quant-ph/0504218 (2005), DOI 10.48550/arXiv.quant-ph/0504218, https://arxiv.org/abs/quant-ph/0504218
3. Barbara M. Terhal and Guido Burkard, "Fault-tolerant quantum computation for local non-Markovian noise", Phys. Rev. A 71, 012336 (2005), DOI 10.1103/PhysRevA.71.012336, https://journals.aps.org/pra/abstract/10.1103/PhysRevA.71.012336
4. John Preskill, "Sufficient condition on noise correlations for scalable quantum computing", arXiv:1207.6131 (2012), DOI 10.48550/arXiv.1207.6131, https://arxiv.org/abs/1207.6131
5. Hui Khoon Ng and John Preskill, "Fault-tolerant quantum computation versus Gaussian noise", Phys. Rev. A 79, 032318 (2009), DOI 10.1103/PhysRevA.79.032318, https://arxiv.org/abs/0810.4953
6. E. Knill, "Quantum computing with realistically noisy devices", Nature 434, 39-44 (2005), DOI 10.1038/nature03350, https://www.nature.com/articles/nature03350
7. Smita Bagewadi and Avhishek Chatterjee, "Effect of Correlated Errors on Quantum Memory", arXiv:2408.08786 (2024, v2 2025), DOI 10.48550/arXiv.2408.08786, https://arxiv.org/abs/2408.08786
8. Yash Deepak Kashtikar, Pranay Mathur, Sudharsan Senthil, and Avhishek Chatterjee, "Expander qLDPC Codes against Long-range Correlated Errors in Memory", arXiv:2510.04561 (2025), DOI 10.48550/arXiv.2510.04561, https://arxiv.org/abs/2510.04561
9. Zhengyi Han, Yuanchen Zhao, Yijia Xu, Yixu Wang, and Zi-Wen Liu, "Coherent error threshold for quantum LDPC codes", arXiv:2609.20537 (2026), DOI 10.48550/arXiv.2609.20537, https://arxiv.org/abs/2609.20537
10. Matthias Christandl, Omar Fawzi, and Ashutosh Goswami, "Fault-tolerant quantum computation with constant overhead for general noise", PRX Quantum 6, 040334 (2025), arXiv:2512.02760, DOI 10.1103/k4cm-pp9p (journal), DOI 10.48550/arXiv.2512.02760 (arXiv), https://arxiv.org/abs/2512.02760
11. Joel J. Wallman and Joseph Emerson, "Noise tailoring for scalable quantum computation via randomized compiling", Phys. Rev. A 94, 052325 (2016), DOI 10.1103/PhysRevA.94.052325, https://arxiv.org/abs/1512.01098
12. Adam Winick, Joel J. Wallman, Dar Dahlen, Ian Hincks, Egor Ospadov, and Joseph Emerson, "Concepts and conditions for error suppression through randomized compiling", arXiv:2212.07500 (2022), DOI 10.48550/arXiv.2212.07500, https://arxiv.org/abs/2212.07500
13. Eric Huang, Andrew C. Doherty, and Steven Flammia, "Performance of quantum error correction with coherent errors", Phys. Rev. A 99, 022313 (2019), arXiv:1805.08227 (2018), DOI 10.1103/PhysRevA.99.022313, https://arxiv.org/abs/1805.08227
14. E. Novais and Eduardo R. Mucciolo, "Surface Code Threshold in the Presence of Correlated Errors", Phys. Rev. Lett. 110, 010502 (2013), DOI 10.1103/PhysRevLett.110.010502, https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.110.010502
15. Adrian Hutter and Daniel Loss, "Breakdown of Surface Code Error Correction Due to Coupling to a Bosonic Bath", Phys. Rev. A 89, 042334 (2014), arXiv:1402.3108, DOI 10.1103/PhysRevA.89.042334, https://arxiv.org/abs/1402.3108
16. Shi Jie Samuel Tan, Christopher A. Pattison, Matt McEwen, and John Preskill, "Resilience of the surface code to error bursts", arXiv:2406.18897 (2024), DOI 10.48550/arXiv.2406.18897, https://arxiv.org/abs/2406.18897
17. Angelo Di Bella, "Geometry-induced correlated noise in qLDPC syndrome extraction", arXiv:2604.01040 (2026), DOI 10.48550/arXiv.2604.01040, https://arxiv.org/abs/2604.01040