New Limits on Fault-Tolerant Quantum Computation
Open accessThe DOI matches its Crossref record; 13 of the 13 references it cites were found in a registry or an index.
Abstract
We show that quantum circuits cannot be made fault-tolerant against a depolarizing noise level of thetas = (6 - 2radic2)/7 ap 45%, thereby improving on a previous bound of 50% (due to Razborov, 2004). More precisely, the circuit model for which we prove this bound contains perfect gates from the Clifford group (CNOT, Hadamard, S, X, Y, Z) and arbitrary additional one-qubit gates that are subject to depolarizing noise thetas. We prove that this set of gates cannot be universal for arbitrary (even classical) computation, from which the upper bound on the noise threshold for fault-tolerant quantum computation follows
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Scheme for reducing decoherence in quantum computer memory
Shor, P. W. (1995) · Physical Review A · doi:10.1103/physreva.52.r2493 · Cited by 4,479
Raussendorf, R., & Briegel, H. J. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.5188 · Cited by 4,477
Good quantum error-correcting codes exist
Calderbank, A. R., & Shor, P. W. (1996) · Physical Review A · doi:10.1103/physreva.54.1098 · Cited by 2,516
Gottesman, D., & Chuang, I. L. (1999) · Nature · doi:10.1038/46503 · Cited by 1,860 · cited 1×
“Finally, we note that our work is related to, and partly stimulated by, the circle of ideas surrounding measurement-based quantum computation that was largely initiated by [10, 17].”
BackgroundUniversal quantum computation with ideal Clifford gates and noisy ancillas
Bravyi, S., & Kitaev, A. (2005) · Physical Review A · doi:10.1103/physreva.71.022316 · Cited by 1,525 · cited 2×
“Note that a probabilistic mixture of 1-qubit Clifford operations C = i p i C i can map v X only into the octahedron O spanned by v X = (1 , 0 , 0) , v Y = (0 , 1 , 0) and v Z = (0 , 0 , 1) and their negatives − v X , − v Y , − v Z (see also [5]).”
BackgroundImproved simulation of stabilizer circuits
Aaronson, S., & Gottesman, D. (2004) · Physical Review A · doi:10.1103/physreva.70.052328 · Cited by 1,515
Quantum computing with realistically noisy devices
Knill, E. (2005) · Nature · doi:10.1038/nature03350 · Cited by 1,184
Fault-tolerant quantum computation with constant error
Aharonov, D., & Ben-Or, M. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258579 · Cited by 631
Robustness of quantum gates in the presence of noise
Harrow, A. W., & Nielsen, M. A. (2003) · Physical Review A · doi:10.1103/physreva.68.012308 · Cited by 164
Quantum Universality from Magic States Distillation Applied to CSS Codes
Reichardt, B. W. (2005) · Quantum Information Processing · doi:10.1007/s11128-005-7654-8 · Cited by 143
Cited by
Achieving quantum supremacy with sparse and noisy commuting quantum computations
Bremner, M. J., Montanaro, A., & Shepherd, D. J. (2017) · Quantum · doi:10.22331/q-2017-04-25-8 · Cited by 191
“A number of authors have provided converses to this, in a variety of different models [34, 43, 14, 25].”
BackgroundFault-tolerant quantum computing with color codes
Landahl, A. J., Anderson, J. T., & Rice, P. R. (2011) · arXiv · doi:10.48550/arxiv.1108.5738 · Cited by 79
Quantifying the effect of gate errors on variational quantum eigensolvers for quantum chemistry
Dalton, K., Long, C. K., Yordanov, Y. S., Smith, C. G., Barnes, C. H. W., Mertig, N., & Arvidsson-Shukur, D. R. M. (2024) · npj Quantum Information · doi:10.1038/s41534-024-00808-x · Cited by 43
Metadata
- Authors
- Buhrman, H., Cleve, R., Laurent, M., Linden, N., Schrijver, A., & Unger, F.
- Venue
- 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)
- Publisher
- IEEE
- Published
- 2006
- Pages
- 411-419
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2035757233
- Cited by
- 59
- References
- 13
- FWCI
- 3.36
- Type
- conference paper
- Language
- en
- Open access
- green
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.