The DOI matches its Crossref record; 43 of the 43 references it cites were found in a registry or an index.
Contextuality supplies the ‘magic’ for quantum computation
Open accessAbstract
Quantum computers promise dramatic advantages over their classical counterparts, but the source of the power in quantum computing has remained elusive. Here we prove a remarkable equivalence between the onset of contextuality and the possibility of universal quantum computation via ‘magic state’ distillation, which is the leading model for experimentally realizing a fault-tolerant quantum computer. This is a conceptually satisfying link, because contextuality, which precludes a simple ‘hidden variable’ model of quantum mechanics, provides one of the fundamental characterizations of uniquely quantum phenomena. Furthermore, this connection suggests a unifying paradigm for the resources of quantum information: the non-locality of quantum theory is a particular kind of contextuality, and non-locality is already known to be a critical resource for achieving advantages with quantum communication. In addition to clarifying these fundamental issues, this work advances the resource framework for quantum computation, which has a number of practical applications, such as characterizing the efficiency and trade-offs between distinct theoretical and experimental schemes for achieving robust quantum computation, and putting bounds on the overhead cost for the classical simulation of quantum algorithms.
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
Algorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713
Fault-tolerant quantum computation by anyons
Kitaev, A. Y. (2003) · Annals of Physics · doi:10.1016/s0003-4916(02)00018-0 · Cited by 7,238
Quantum theory, the Church–Turing principle and the universal quantum computer
Deutsch, D. (1985) · Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences · doi:10.1098/rspa.1985.0070 · Cited by 4,597
Lloyd, S. (1996) · Science · doi:10.1126/science.273.5278.1073 · Cited by 3,088 · cited 1×
“Quantum information enables dramatic new advantages for computation, such as Shor’s factoring algorithm [1] and quantum simulation algorithms [2].”
Surface codes: Towards practical large-scale quantum computation
Fowler, A. G., Mariantoni, M., Martinis, J. M., & Cleland, A. N. (2012) · Physical Review A · doi:10.1103/physreva.86.032324 · Cited by 3,059
On the Problem of Hidden Variables in Quantum Mechanics
BELL, J. S. (1966) · Reviews of Modern Physics · doi:10.1103/revmodphys.38.447 · Cited by 2,845
Efficient Classical Simulation of Slightly Entangled Quantum Computations
Vidal, G. (2003) · Physical Review Letters · doi:10.1103/physrevlett.91.147902 · Cited by 2,368
Dennis, E., Kitaev, A., Landahl, A., & Preskill, J. (2002) · Journal of Mathematical Physics · doi:10.1063/1.1499754 · Cited by 1,768
The Problem of Hidden Variables in Quantum Mechanics
Kochen, S., & Specker, E. P. (1975) · The Logico-Algebraic Approach to Quantum Mechanics · doi:10.1007/978-94-010-1795-4_17 · Cited by 1,650
Device-independent security of quantum cryptography against collective attacks
Acín, A., Brunner, N., Gisin, N., Massar, S., Pironio, S., & Scarani, V. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.230501 · Cited by 1,537
Universal 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 4×
“It is in this latter context that we establish that the boundary for the set of quantum states currently known to be unsuitable for magic state distillation [13, 24, 25] is defined by a set of noncontextuality inequalities.”
InfluentialImproved simulation of stabilizer circuits
Aaronson, S., & Gottesman, D. (2004) · Physical Review A · doi:10.1103/physreva.70.052328 · Cited by 1,515 · cited 18×
“The independence number of the exclusivity graph associated with Σ~r is α(Γ~r) = p3 for all A~r ∈ ASIM so that, relative to our construction, exactly the states ρ /∈ PSIM are those that exhibit contextuality.”
InfluentialDennis, E., Kitaev, A., Landahl, A., & Preskill, J. (2001) · CERN Document Server (European Organization for Nuclear Research) · Cited by 1,485
Quantum Discord and the Power of One Qubit
Datta, A., Shaji, A., & Caves, C. M. (2008) · Physical Review Letters · doi:10.1103/physrevlett.100.050502 · Cited by 1,258
Quantum computing with realistically noisy devices
Knill, E. (2005) · Nature · doi:10.1038/nature03350 · Cited by 1,184 · cited 3×
“Forming the exclusivity graph C of {P} and applying the results of refs 31 and 32 identifies the left-hand side of equation (15) as a witness for the contextuality of r.”
InfluentialMeasurement-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 · cited 2×
“that is, we take the p(p(2) 2 1) separable projectors consisting of all tensor products of projectors in equation (11) for the first qudit and computational basis states for the second qudit.”
Theory of fault-tolerant quantum computation
Gottesman, D. (1998) · Physical Review A · doi:10.1103/physreva.57.127 · Cited by 947
Power of One Bit of Quantum Information
Knill, E., & Laflamme, R. (1998) · Physical Review Letters · doi:10.1103/physrevlett.81.5672 · Cited by 884
Simple unified form for the major no-hidden-variables theorems
Mermin, N. D. (1990) · Physical Review Letters · doi:10.1103/physrevlett.65.3373 · Cited by 753 · cited 1×
“The contextuality of quantum theory means that a particular outcome of a quantum measurement cannot be understood as revealing the pre-existing definite value of some underlying “hidden variable” [16].”
Contextuality for preparations, transformations, and unsharp measurements
Spekkens, R. W. (2005) · Physical Review A · doi:10.1103/physreva.71.052108 · Cited by 630
Nonlocality and communication complexity
Buhrman, H., Cleve, R., Massar, S., & de Wolf, R. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.665 · Cited by 622
A fast algorithm for the maximum clique problem
Östergård, P. R. J. (2002) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(01)00290-6 · Cited by 590
The resource theory of stabilizer quantum computation
Veitch, V., Hamed Mousavian, S. A., Gottesman, D., & Emerson, J. (2014) · New Journal of Physics · doi:10.1088/1367-2630/16/1/013009 · Cited by 501
Self-citationPositive Wigner Functions Render Classical Simulation of Quantum Computation Efficient
Mari, A., & Eisert, J. (2012) · Physical Review Letters · doi:10.1103/physrevlett.109.230503 · Cited by 451
Two simple proofs of the Kochen-Specker theorem
Peres, A. (1991) · Journal of Physics A: Mathematical and General · doi:10.1088/0305-4470/24/4/003 · Cited by 420
A fault-tolerant one-way quantum computer
Raussendorf, R., Harrington, J., & Goyal, K. (2006) · Annals of Physics · doi:10.1016/j.aop.2006.01.012 · Cited by 397
Discrete phase space based on finite fields
Gibbons, K. S., Hoffman, M. J., & Wootters, W. K. (2004) · Physical Review A · doi:10.1103/physreva.70.062101 · Cited by 390
Negative quasi-probability as a resource for quantum computation
Veitch, V., Ferrie, C., Gross, D., & Emerson, J. (2012) · New Journal of Physics · doi:10.1088/1367-2630/14/11/113011 · Cited by 377
Self-citationGraph-Theoretic Approach to Quantum Correlations
Cabello, A., Severini, S., & Winter, A. (2014) · Physical Review Letters · doi:10.1103/physrevlett.112.040401 · Cited by 336
Hudson’s theorem for finite-dimensional quantum systems
Gross, D. (2006) · Journal of Mathematical Physics · doi:10.1063/1.2393152 · Cited by 336
Classical command of quantum systems
Reichardt, B. W., Unger, F., & Vazirani, U. (2013) · Nature · doi:10.1038/nature12035 · Cited by 294
Contextuality in measurement-based quantum computation
Raussendorf, R. (2013) · Physical Review A · doi:10.1103/physreva.88.022322 · Cited by 252
Magic-State Distillation in All Prime Dimensions Using Quantum Reed-Muller Codes
Campbell, E. T., Anwar, H., & Browne, D. E. (2012) · UCL Discovery (University College London) · doi:10.17169/refubium-18291 · Cited by 159
Qudit versions of the qubit π/8 gate
Howard, M., & Vala, J. (2012) · Physical Review A · doi:10.1103/physreva.86.022316 · Cited by 153
Self-citationClassicality in discrete Wigner functions
Cormick, C., Galvão, E. F., Gottesman, D., Paz, J. P., & Pittenger, A. O. (2006) · Physical Review A · doi:10.1103/physreva.73.012301 · Cited by 145
Universal Quantum Computation with Little Entanglement
den Nest, M. V. (2013) · Physical Review Letters · doi:10.1103/physrevlett.110.060504 · Cited by 127
The Elusive Source of Quantum Speedup
Vedral, V. (2010) · Foundations of Physics · doi:10.1007/s10701-010-9452-0 · Cited by 73
Noise thresholds for higher-dimensional systems using the discrete Wigner function
van Dam, W., & Howard, M. (2011) · Physical Review A · doi:10.1103/physreva.83.032310 · Cited by 48
Self-citationNon-negative subtheories and quasiprobability representations of qubits
Wallman, J. J., & Bartlett, S. D. (2012) · Physical Review A · doi:10.1103/physreva.85.062121 · Cited by 45
Self-citationDiscord and quantum computational resources
Brodutch, A. (2013) · Physical Review A · doi:10.1103/physreva.88.022307 · Cited by 36
Spectra of phase point operators in odd prime dimensions and the extended Clifford group
Appleby, D. M., Bengtsson, I., & Chaturvedi, S. (2008) · Journal of Mathematical Physics · doi:10.1063/1.2824479 · Cited by 30
Generalized Bell-inequality experiments and computation
Hoban, M. J., Wallman, J. J., & Browne, D. E. (2011) · Physical Review A · doi:10.1103/physreva.84.062107 · Cited by 28
Self-citationQuantum Contextuality with Stabilizer States
Howard, M., Brennan, E., & Vala, J. (2013) · Entropy · doi:10.3390/e15062340 · Cited by 26
Self-citation
Cited by
Chitambar, E., & Gour, G. (2019) · Reviews of Modern Physics · doi:10.1103/revmodphys.91.025001 · Cited by 1,276
The Variational Quantum Eigensolver: A review of methods and best practices
Tilly, J., Chen, H., Cao, S., Picozzi, D., Setia, K., Li, Y., Grant, E., Wossnig, L., Rungger, I., Booth, G. H., et al. (2022) · Physics Reports · doi:10.1016/j.physrep.2022.08.003 · Cited by 1,031
Qudits and High-Dimensional Quantum Computing
Wang, Y., Hu, Z., Sanders, B. C., & Kais, S. (2020) · Frontiers in Physics · doi:10.3389/fphy.2020.589504 · Cited by 478
Application of a Resource Theory for Magic States to Fault-Tolerant Quantum Computing
Howard, M., & Campbell, E. (2017) · Physical Review Letters · doi:10.1103/physrevlett.118.090501 · Cited by 387
Self-citationHow to quantify coherence: Distinguishing speakable and unspeakable notions
Marvian, I., & Spekkens, R. W. (2016) · Physical Review A · doi:10.1103/physreva.94.052324 · Cited by 336
Metadata
- Authors
- Howard, M., Wallman, J., Veitch, V., & Emerson, J.
- Venue
- Nature
- Published
- 2014-06
- Volume
- 510
- Issue
- 7505
- Pages
- 351-355
- ISSN
- 0028-0836 (ISSN-L)
- 1476-4687
- OpenAlex
- W2145928944
- Cited by
- 616
- References
- 43
- FWCI
- 44.23
- Type
- journal article
- 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.