Fault-Tolerant Quantum Computation with Long-Range Correlated Noise
Open accessAbstract
We prove a new version of the quantum accuracy threshold theorem that applies to non-Markovian noise with algebraically decaying spatial correlations. We consider noise in a quantum computer arising from a perturbation that acts collectively on pairs of qubits and on the environment, and we show that an arbitrarily long quantum computation can be executed with high reliability in D spatial dimensions, if the perturbation is sufficiently weak and decays with the distance r between the qubits faster than 1/r(D).
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
To perform a gate in G2, the gate is first applied pit-wise, which always achieves the correct operation but sometimes yields a state encoded by polynomial codes with degree twice the original degree d; a degree reduction using interpolation then follows.
“To perform a gates in G 2 , we apply two steps. First the gate is applied pit-wise. This always achieves the correct operation of the gate, but sometimes the final state is encoded by polynomial codes with degree which is twice the original degree d . The second step is therefore a degree reduction, which can be applied using interpolation techniques, as the quantum analogue of the degree reduc”
From Fault-Tolerant Quantum Computation with Constant Error Rate (2008) · cites this paper as [9]
Ben-Or, Goldwasser and Wigderson suggested using random polynomials evaluated at different points in a field of p elements to divide a secret among parties.
“Here, we adopt the scheme suggested by Ben-Or, Goldwasser and Wigderson[9], who suggested to use random polynomials, evaluated at different points in a field of p elements, as a way to divide a secret among a few parties.”
From Fault-Tolerant Quantum Computation with Constant Error Rate (2008) · cites this paper as [9]
A polynomial code of degree d with length m over Fp is a [p,m] quantum code.
“Theorem 3. A polynomial code of degree d with length m over F p is a [ p, m ] quantum code which corrects min {⌊ m -d -1 2 ⌋ , ⌊ d 2 ⌋} errors.”
From Fault-Tolerant Quantum Computation with Constant Error Rate (2008) · cites this paper as [9]
A polynomial code of degree d with length m over Fp corrects min{⌊(m-d-1)/2⌋, ⌊d/2⌋} errors.
“Theorem 3. A polynomial code of degree d with length m over F p is a [ p, m ] quantum code which corrects min {⌊ m -d -1 2 ⌋ , ⌊ d 2 ⌋} errors.”
From Fault-Tolerant Quantum Computation with Constant Error Rate (2008) · cites this paper as [9]
Proofs of fault-tolerance have been derived for error models showing characteristic features of realistic physical systems such as long-range correlated errors.
“Proofs of fault-tolerance have been derived for error-models showing the characteristic features of realistic physical systems such as long-range correlated errors 63 .”
From Measurement-based quantum computation (2009) · cites this paper as [63]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Proceedings of the 56th Annual ACM Symposium on Theory of Computing
(2024) · doi:10.1145/3618260 · Cited by 1,842 · see citing works
Quantum computations: algorithms and error correction
Kitaev, A. Y. (1997) · Russian Mathematical Surveys · doi:10.1070/rm1997v052n06abeh002155 · Cited by 1,424 · see citing works
Self-citationQuantum computing with realistically noisy devices
Knill, E. (2005) · Nature · doi:10.1038/nature03350 · Cited by 1,184 · see citing works
Resilient quantum computation: error models and thresholds
Knill, E., Laflamme, R., & Zurek, W. H. (1998) · Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.1998.0166 · Cited by 346 · see citing works
Proc. 26th annual symposium on Foundations of computer science
Tarjan, R. E. (1985) · Cited by 258 · see citing works
Proceedings 38th Annual Symposium on Foundations of Computer Science
(1997) · doi:10.1109/sfcs.1997 · Cited by 256 · see citing works
Fault-tolerant quantum computation for local non-Markovian noise
Terhal, B. M., & Burkard, G. (2005) · Physical Review A · doi:10.1103/physreva.71.012336 · Cited by 180 · see citing works
Flagged first, then by citations
Research works printed but not linked: 4
- [2]D. Aharonov and M. Ben-Or, Proc. 29th Annual ACM Symposium on Theory of Computing , p. 176 (New York, ACM, 1997); D. Aharonov and M. Ben-Or, arXiv:quanph/9906129 (1999)
- [4]E Knill, R. Laflamme, W. H. Zurek, Proc. Roy. Soc. London, Ser. A 454 , 365 (1998).
- [5]P. Aliferis, D. Gottesman, and J. Preskill, arXiv:quantph/0504218 (2005).
- [6]B. W. Reichardt, arXiv:quant-ph/0509203 (2005). · arXiv
Cited by
Sorted by citations
Quantum error correction for quantum memories
Terhal, B. M. (2015) · Reviews of Modern Physics · doi:10.1103/revmodphys.87.307 · Cited by 1,354 · see citing works
Measurement-based quantum computation
Briegel, H. J., Browne, D. E., Dür, W., Raussendorf, R., & Van den Nest, M. (2009) · Nature Physics · doi:10.1038/nphys1157 · Cited by 1,090 · see citing works
Assessing Non-Markovian Quantum Dynamics
Wolf, M. M., Eisert, J., Cubitt, T. S., & Cirac, J. I. (2008) · Physical Review Letters · doi:10.1103/physrevlett.101.150402 · Cited by 596 · see citing works
Measures of non-Markovianity: Divisibility versus backflow of information
Chruściński, D., Kossakowski, A., & Rivas, Á. (2011) · Physical Review A · doi:10.1103/physreva.83.052128 · Cited by 270 · see citing works
Fault-tolerant quantum computation against biased noise
Aliferis, P., & Preskill, J. (2008) · Physical Review A · doi:10.1103/physreva.78.052331 · Cited by 204 · see citing works
Self-citationDemonstration of a Scaling Advantage for a Quantum Annealer over Simulated Annealing
Albash, T., & Lidar, D. A. (2018) · Physical Review X · doi:10.1103/physrevx.8.031016 · Cited by 238 · see citing works
“Another concern we face is that while the accuracy threshold theorem provides a theoretical guarantee that for sufficiently low noise levels and through the use of quantum error correction a finite-size device can be scaled up fault tolerantly [57], in the absence of such an asymptotic guarantee for quantum annealing…”
BackgroundFinding the Kraus decomposition from a master equation and vice versa
Andersson, E., Cresser, J. D., & Hall, M. J. W. (2007) · Journal of Modern Optics · doi:10.1080/09500340701352581 · Cited by 155 · see citing works
Alicki, R., Lidar, D. A., & Zanardi, P. (2006) · Physical Review A · doi:10.1103/physreva.73.052311 · Cited by 132 · see citing works
Early Fault-Tolerant Quantum Computing
Katabarwa, A., Gratsea, K., Caesura, A., & Johnson, P. D. (2024) · PRX Quantum · doi:10.1103/prxquantum.5.020101 · Cited by 103 · see citing works
“The first piece of the puzzle was tackled by Peter Shor [12] and later, building on his work, threshold theorems were proved assuming various kinds of error models [13–15].”
BackgroundLearning high-accuracy error decoding for quantum processors
Bausch, J., Senior, A. W., Heras, F. J. H., Edlich, T., Davies, A., Newman, M., Jones, C., Satzinger, K., Niu, M. Y., Blackwell, S., et al. (2024) · Nature · doi:10.1038/s41586-024-08148-8 · Cited by 106 · see citing works
“A decoder that recognizes these patterns can be especially valuable, since correlated errors are highly damaging to fault-tolerance [1].”
Two-Level-System Dynamics in a Superconducting Qubit Due to Background Ionizing Radiation
Thorbeck, T., Eddins, A., Lauer, I., McClure, D. T., & Carroll, M. (2023) · PRX Quantum · doi:10.1103/prxquantum.4.020356 · Cited by 70 · see citing works
Efficient error characterization in quantum information processing
Lévi, B., López, C. C., Emerson, J., & Cory, D. G. (2007) · Physical Review A · doi:10.1103/physreva.75.022314 · Cited by 65 · see citing works
Coherence in logical quantum channels
Iverson, J. K., & Preskill, J. (2020) · New Journal of Physics · doi:10.1088/1367-2630/ab8e5c · Cited by 61 · see citing works
Self-citationMarkovianity criteria for quantum evolution
Chruściński, D., & Kossakowski, A. (2012) · Journal of Physics B: Atomic, Molecular and Optical Physics · doi:10.1088/0953-4075/45/15/154002 · Cited by 54 · see citing works
Quantifying the effects of local many-qubit errors and nonlocal two-qubit errors on the surface code
Fowler, A. G., & Martinis, J. M. (2014) · Physical Review A · doi:10.1103/physreva.89.032316 · Cited by 49 · see citing works
Quantum simulation of interacting high-dimensional systems: The influence of noise
Dür, W., Bremner, M. J., & Briegel, H. J. (2008) · Physical Review A · doi:10.1103/physreva.78.052325 · Cited by 41 · see citing works
Decoherence of up to 8-qubit entangled states in a 16-qubit superconducting quantum processor
Ozaeta, A., & McMahon, P. L. (2019) · Quantum Science and Technology · doi:10.1088/2058-9565/ab13e5 · Cited by 16 · see citing works
- Authors
- Aharonov, D., Kitaev, A., & Preskill, J.
- Affiliations
- Hebrew University of Jerusalem (IL)
- California Institute of Technology (US)
- Venue
- Physical Review Letters
- Publisher
- American Physical Society (APS)
- Published
- 2006-02-07
- Volume
- 96
- Issue
- 5
- Pages
- 050504-050504
- ISSN
- 0031-9007 (ISSN-L)
- 1079-7114
- OpenAlex
- W1989538270
- Cited by
- 243
- References
- 7
- Citations by year
- 2026: 15 · 2025: 13 · 2024: 13 · 2023: 14 · 2022: 14 · 2021: 10 · 2020: 6 · 2019: 10 · 2018: 9 · 2017: 9 · 2016: 12 · 2015: 11 · 2014: 10 · 2013: 14 · 2012: 10
- FWCI
- 20.16
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Physical Review Letters (publishedVersion)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- CaltechAUTHORS (California Institute of Technology) (submittedVersion)
- CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Keywords
- fault-tolerant quantum computing, non-Markovian noise, qubit-environment coupling, spatial dimension, error threshold
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
