{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T00:35:23Z","timestamp":1776126923914,"version":"3.50.1"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"7505","license":[{"start":{"date-parts":[[2014,6,1]],"date-time":"2014-06-01T00:00:00Z","timestamp":1401580800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nature"],"published-print":{"date-parts":[[2014,6]]},"DOI":"10.1038\/nature13460","type":"journal-article","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T11:13:42Z","timestamp":1402485222000},"page":"351-355","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":498,"title":["Contextuality supplies the \u2018magic\u2019 for quantum computation"],"prefix":"10.1038","volume":"510","author":[{"given":"Mark","family":"Howard","sequence":"first","affiliation":[]},{"given":"Joel","family":"Wallman","sequence":"additional","affiliation":[]},{"given":"Victor","family":"Veitch","sequence":"additional","affiliation":[]},{"given":"Joseph","family":"Emerson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,6,11]]},"reference":[{"key":"BFnature13460_CR1","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1109\/SFCS.1994.365700","volume-title":"Proc. IEEE Foundations of Computer Science (FOCS)","author":"PW Shor","year":"1994","unstructured":"Shor, P. W. in Proc. IEEE Foundations of Computer Science (FOCS) (ed. Goldwasser, S. ) 124\u2013134 \n                    http:\/\/dx.doi.org\/10.1109\/SFCS.1994.365700\n                    \n                   (IEEE Computer Society, 1994)"},{"key":"BFnature13460_CR2","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1126\/science.273.5278.1073","volume":"273","author":"S Lloyd","year":"1996","unstructured":"Lloyd, S. Universal quantum simulators. Science 273, 1073\u20131078 (1996)","journal-title":"Science"},{"key":"BFnature13460_CR3","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1098\/rspa.1985.0070","volume":"400","author":"D Deutsch","year":"1985","unstructured":"Deutsch, D. Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. R. Soc. A. 400, 97\u2013117 (1985)","journal-title":"Proc. R. Soc. A."},{"key":"BFnature13460_CR4","doi-asserted-by":"publisher","first-page":"147902","DOI":"10.1103\/PhysRevLett.91.147902","volume":"91","author":"G Vidal","year":"2003","unstructured":"Vidal, G. Efficient classical simulation of slightly entangled quantum computations. Phys. Rev. Lett. 91, 147902 (2003)","journal-title":"Phys. Rev. Lett."},{"key":"BFnature13460_CR5","doi-asserted-by":"publisher","first-page":"050502","DOI":"10.1103\/PhysRevLett.100.050502","volume":"100","author":"A Datta","year":"2008","unstructured":"Datta, A., Shaji, A. & Caves, C. M. Quantum discord and the power of one qubit. Phys. Rev. Lett. 100, 050502 (2008)","journal-title":"Phys. Rev. Lett."},{"key":"BFnature13460_CR6","unstructured":"Steane, A. M. A quantum computer only needs one universe. Preprint at \n                    http:\/\/arxiv.org\/abs\/quant-ph\/0003084\n                    \n                   (2000)"},{"key":"BFnature13460_CR7","doi-asserted-by":"publisher","first-page":"1141","DOI":"10.1007\/s10701-010-9452-0","volume":"40","author":"V Vedral","year":"2010","unstructured":"Vedral, V. The elusive source of quantum speedup. Found. Phys. 40, 1141\u20131154 (2010)","journal-title":"Found. Phys."},{"key":"BFnature13460_CR8","doi-asserted-by":"publisher","first-page":"022307","DOI":"10.1103\/PhysRevA.88.022307","volume":"88","author":"A Brodutch","year":"2013","unstructured":"Brodutch, A. Discord and quantum computational resources. Phys. Rev. A 88, 022307 (2013)","journal-title":"Phys. Rev. A"},{"key":"BFnature13460_CR9","doi-asserted-by":"publisher","first-page":"060504","DOI":"10.1103\/PhysRevLett.110.060504","volume":"110","author":"M Van den Nest","year":"2013","unstructured":"Van den Nest, M. Universal quantum computation with little entanglement. Phys. Rev. Lett. 110, 060504 (2013)","journal-title":"Phys. Rev. Lett."},{"key":"BFnature13460_CR10","doi-asserted-by":"publisher","first-page":"5672","DOI":"10.1103\/PhysRevLett.81.5672","volume":"81","author":"E Knill","year":"1998","unstructured":"Knill, E. & Laflamme, R. Power of one bit of quantum information. Phys. Rev. Lett. 81, 5672\u20135675 (1998)","journal-title":"Phys. Rev. Lett."},{"key":"BFnature13460_CR11","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1038\/nphys1157","volume":"5","author":"HJ Briegel","year":"2009","unstructured":"Briegel, H. J., Browne, D. E., D\u00fcr, W., Raussendorf, R. & Van den Nest, M. Measurement-based quantum computation. Nature Phys. 5, 19\u201326 (2009)","journal-title":"Nature Phys."},{"key":"BFnature13460_CR12","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1103\/RevModPhys.38.447","volume":"38","author":"J Bell","year":"1966","unstructured":"Bell, J. On the problem of hidden variables in quantum mechanics. Rev. Mod. Phys. 38, 447\u2013452 (1966)","journal-title":"Rev. Mod. Phys."},{"key":"BFnature13460_CR13","first-page":"59","volume":"17","author":"S Kochen","year":"1968","unstructured":"Kochen, S. & Specker, E. P. The problem of hidden variables in quantum mechanics. J Math. Mech. 17, 59\u201387 (1968)","journal-title":"J Math. Mech."},{"key":"BFnature13460_CR14","doi-asserted-by":"publisher","first-page":"022316","DOI":"10.1103\/PhysRevA.71.022316","volume":"71","author":"S Bravyi","year":"2005","unstructured":"Bravyi, S. & Kitaev, A. Universal quantum computation with ideal Clifford gates and noisy ancillas. Phys. Rev. A 71, 022316 (2005)","journal-title":"Phys. Rev. A"},{"key":"BFnature13460_CR15","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1038\/nature03350","volume":"434","author":"E Knill","year":"2005","unstructured":"Knill, E. Quantum computing with realistically noisy devices. Nature 434, 39\u201344 (2005)","journal-title":"Nature"},{"key":"BFnature13460_CR16","first-page":"041021","volume":"2","author":"ET Campbell","year":"2012","unstructured":"Campbell, E. T., Anwar, H. & Browne, D. E. Magic state distillation in all prime dimensions using quantum Reed-Muller codes. Phys. Rev. X 2, 041021 (2012)","journal-title":"Phys. Rev. X"},{"key":"BFnature13460_CR17","doi-asserted-by":"publisher","first-page":"3373","DOI":"10.1103\/PhysRevLett.65.3373","volume":"65","author":"ND Mermin","year":"1990","unstructured":"Mermin, N. D. Simple unified form for the major no-hidden-variables theorems. Phys. Rev. Lett. 65, 3373\u20133376 (1990)","journal-title":"Phys. Rev. Lett."},{"key":"BFnature13460_CR18","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1103\/RevModPhys.82.665","volume":"82","author":"H Buhrman","year":"2010","unstructured":"Buhrman, H., Cleve, R., Massar, S. & de Wolf, R. Nonlocality and communication complexity. Rev. Mod. Phys. 82, 665\u2013698 (2010)","journal-title":"Rev. Mod. Phys."},{"key":"BFnature13460_CR19","doi-asserted-by":"publisher","first-page":"230501","DOI":"10.1103\/PhysRevLett.98.230501","volume":"98","author":"A Ac\u00edn","year":"2007","unstructured":"Ac\u00edn, A. et al. Device-independent security of quantum cryptography against collective attacks. Phys. Rev. Lett. 98, 230501 (2007)","journal-title":"Phys. Rev. Lett."},{"key":"BFnature13460_CR20","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1038\/nature12035","volume":"496","author":"BW Reichardt","year":"2013","unstructured":"Reichardt, B. W., Unger, F. & Vazirani, U. Classical command of quantum systems. Nature 496, 456\u2013460 (2013)","journal-title":"Nature"},{"key":"BFnature13460_CR21","unstructured":"Vazirani, U. & Vidick, T. Fully device independent quantum key distribution. Preprint at \n                    http:\/\/arxiv.org\/abs\/1210.1810\n                    \n                   (2012)"},{"key":"BFnature13460_CR22","doi-asserted-by":"publisher","first-page":"022322","DOI":"10.1103\/PhysRevA.88.022322","volume":"88","author":"R Raussendorf","year":"2013","unstructured":"Raussendorf, R. Contextuality in measurement-based quantum computation. Phys. Rev. A 88, 022322 (2013)","journal-title":"Phys. Rev. A"},{"key":"BFnature13460_CR23","doi-asserted-by":"publisher","first-page":"062107","DOI":"10.1103\/PhysRevA.84.062107","volume":"84","author":"MJ Hoban","year":"2011","unstructured":"Hoban, M. J., Wallman, J. J. & Browne, D. E. Generalized Bell-inequality experiments and computation. Phys. Rev. A 84, 062107 (2011)","journal-title":"Phys. Rev. A"},{"key":"BFnature13460_CR24","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1103\/PhysRevA.57.127","volume":"57","author":"D Gottesman","year":"1998","unstructured":"Gottesman, D. Theory of fault-tolerant quantum computation. Phys. Rev. A 57, 127\u2013137 (1998)","journal-title":"Phys. Rev. A"},{"key":"BFnature13460_CR25","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/S0003-4916(02)00018-0","volume":"303","author":"A Yu","year":"2003","unstructured":"Yu, A. Fault-tolerant quantum computation by anyons. Ann. Phys. 303, 2\u201330 (2003)","journal-title":"Ann. Phys."},{"key":"BFnature13460_CR26","doi-asserted-by":"publisher","first-page":"2242","DOI":"10.1016\/j.aop.2006.01.012","volume":"321","author":"R Raussendorf","year":"2006","unstructured":"Raussendorf, R., Harrington, J. & Goyal, K. A fault-tolerant one-way quantum computer. Ann. Phys. 321, 2242\u20132270 (2006)","journal-title":"Ann. Phys."},{"key":"BFnature13460_CR27","doi-asserted-by":"publisher","first-page":"4452","DOI":"10.1063\/1.1499754","volume":"43","author":"E Dennis","year":"2002","unstructured":"Dennis, E., Kitaev, A., Landahl, A. & Preskill, J. Topological quantum memory. J. Math. Phys. 43, 4452\u20134505 (2002)","journal-title":"J. Math. Phys."},{"key":"BFnature13460_CR28","unstructured":"Anwar, H., Brown, B. J., Campbell, E. T. & Browne, D. E. Efficient decoders for qudit topological codes. Preprint at \n                    http:\/\/arxiv.org\/abs\/1311.4895\n                    \n                   (2013)"},{"key":"BFnature13460_CR29","doi-asserted-by":"publisher","first-page":"032324","DOI":"10.1103\/PhysRevA.86.032324","volume":"86","author":"AG Fowler","year":"2012","unstructured":"Fowler, A. G., Mariantoni, M., Martinis, J. M. & Cleland, A. N. Surface codes: towards practical large-scale quantum computation. Phys. Rev. A 86, 032324 (2012)","journal-title":"Phys. Rev. A"},{"key":"BFnature13460_CR30","doi-asserted-by":"publisher","first-page":"052328","DOI":"10.1103\/PhysRevA.70.052328","volume":"70","author":"S Aaronson","year":"2004","unstructured":"Aaronson, S. & Gottesman, D. Improved simulation of stabilizer circuits. Phys. Rev. A 70, 052328 (2004)","journal-title":"Phys. Rev. A"},{"key":"BFnature13460_CR31","unstructured":"Cabello, A., Severini, S. & Winter, A. (Non-)Contextuality of physical theories as an axiom. Preprint at \n                    http:\/\/arxiv.org\/abs\/1010.2163\n                    \n                   (2010)"},{"key":"BFnature13460_CR32","doi-asserted-by":"publisher","first-page":"040401","DOI":"10.1103\/PhysRevLett.112.040401","volume":"112","author":"A Cabello","year":"2014","unstructured":"Cabello, A., Severini, S. & Winter, A. Graph-theoretic approach to quantum correlations. Phys. Rev. Lett. 112, 040401 (2014)","journal-title":"Phys. Rev. Lett."},{"key":"BFnature13460_CR33","doi-asserted-by":"publisher","first-page":"012301","DOI":"10.1103\/PhysRevA.73.012301","volume":"73","author":"C Cormick","year":"2006","unstructured":"Cormick, C., Galv\u00e3o, E. F., Gottesman, D., Pablo Paz, J. & Pittenger, A. O. Classicality in discrete Wigner functions. Phys. Rev. A 73, 012301 (2006)","journal-title":"Phys. Rev. A"},{"key":"BFnature13460_CR34","doi-asserted-by":"publisher","first-page":"022316","DOI":"10.1103\/PhysRevA.86.022316","volume":"86","author":"M Howard","year":"2012","unstructured":"Howard, M. & Vala, J. Qudit versions of the qubit \u03c0\/8 gate. Phys. Rev. A 86, 022316 (2012)","journal-title":"Phys. Rev. A"},{"key":"BFnature13460_CR35","doi-asserted-by":"publisher","first-page":"113011","DOI":"10.1088\/1367-2630\/14\/11\/113011","volume":"14","author":"V Veitch","year":"2012","unstructured":"Veitch, V., Ferrie, C., Gross, D. & Emerson, J. Negative quasi-probability as a resource for quantum computation. N. J. Phys. 14, 113011 (2012)","journal-title":"N. J. Phys."},{"key":"BFnature13460_CR36","doi-asserted-by":"publisher","first-page":"230503","DOI":"10.1103\/PhysRevLett.109.230503","volume":"109","author":"A Mari","year":"2012","unstructured":"Mari, A. & Eisert, J. Positive Wigner functions render classical simulation of quantum computation efficient. Phys. Rev. Lett. 109, 230503 (2012)","journal-title":"Phys. Rev. Lett."},{"key":"BFnature13460_CR37","doi-asserted-by":"publisher","first-page":"032310","DOI":"10.1103\/PhysRevA.83.032310","volume":"83","author":"W van Dam","year":"2011","unstructured":"van Dam, W. & Howard, M. Noise thresholds for higher-dimensional systems using the discrete Wigner function. Phys. Rev. A 83, 032310 (2011)","journal-title":"Phys. Rev. A"},{"key":"BFnature13460_CR38","doi-asserted-by":"publisher","first-page":"012102","DOI":"10.1063\/1.2824479","volume":"49","author":"DM Appleby","year":"2008","unstructured":"Appleby, D. M., Bengtsson, I. & Chaturvedi, S. Spectra of phase point operators in odd prime dimensions and the extended Clifford group. J. Math. Phys. 49, 012102 (2008)","journal-title":"J. Math. Phys."},{"key":"BFnature13460_CR39","doi-asserted-by":"publisher","first-page":"062121","DOI":"10.1103\/PhysRevA.85.062121","volume":"85","author":"JJ Wallman","year":"2012","unstructured":"Wallman, J. J. & Bartlett, S. D. Non-negative subtheories and quasiprobability representations of qubits. Phys. Rev. A 85, 062121 (2012)","journal-title":"Phys. Rev. A"},{"key":"BFnature13460_CR40","doi-asserted-by":"publisher","first-page":"122107","DOI":"10.1063\/1.2393152","volume":"47","author":"D Gross","year":"2006","unstructured":"Gross, D. Hudson\u2019s theorem for finite-dimensional quantum systems. J. Math. Phys. 47, 122107 (2006)","journal-title":"J. Math. Phys."},{"key":"BFnature13460_CR41","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1111\/j.1749-6632.1986.tb12431.x","volume":"480","author":"WK Wootters","year":"1986","unstructured":"Wootters, W. K. The discrete Wigner function. Ann. NY Acad. Sci. 480, 275\u2013282 (1986)","journal-title":"Ann. NY Acad. Sci."},{"key":"BFnature13460_CR42","doi-asserted-by":"publisher","first-page":"062101","DOI":"10.1103\/PhysRevA.70.062101","volume":"70","author":"KS Gibbons","year":"2004","unstructured":"Gibbons, K. S., Hoffman, M. J. & Wootters, W. K. Discrete phase space based on finite fields. Phys. Rev. A 70, 062101 (2004)","journal-title":"Phys. Rev. A"},{"key":"BFnature13460_CR43","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/S0166-218X(01)00290-6","volume":"120","author":"PRJ \u00d6sterg\u00e5rd","year":"2002","unstructured":"\u00d6sterg\u00e5rd, P. R. J. A fast algorithm for the maximum clique problem. Discrete Appl. Math. 120, 197\u2013207 (2002)","journal-title":"Discrete Appl. Math."},{"key":"BFnature13460_CR44","doi-asserted-by":"publisher","first-page":"013009","DOI":"10.1088\/1367-2630\/16\/1\/013009","volume":"16","author":"V Veitch","year":"2014","unstructured":"Veitch, V., Mousavian, S. A. H., Gottesman, D. & Emerson, J. The resource theory of stabilizer computation. N. J. Phys. 16, 013009 (2014)","journal-title":"N. J. Phys."},{"key":"BFnature13460_CR45","doi-asserted-by":"publisher","first-page":"2340","DOI":"10.3390\/e15062340","volume":"15","author":"M Howard","year":"2013","unstructured":"Howard, M., Brennan, E. & Vala, J. Quantum contextuality with stabilizer states. Entropy 15, 2340\u20132362 (2013)","journal-title":"Entropy"},{"key":"BFnature13460_CR46","doi-asserted-by":"publisher","first-page":"L175","DOI":"10.1088\/0305-4470\/24\/4\/003","volume":"24","author":"A Peres","year":"1991","unstructured":"Peres, A. Two simple proofs of the Kochen-Specker theorem. J. Phys. A 24, L175\u2013L178 (1991)","journal-title":"J. Phys. A"},{"key":"BFnature13460_CR47","doi-asserted-by":"publisher","first-page":"052108","DOI":"10.1103\/PhysRevA.71.052108","volume":"71","author":"RW Spekkens","year":"2005","unstructured":"Spekkens, R. W. Contextuality for preparations, transformations, and unsharp measurements. Phys. Rev. A 71, 052108 (2005)","journal-title":"Phys. Rev. A"},{"key":"BFnature13460_CR48","unstructured":"Ac\u00edn, A., Fritz, T., Leverrier, A. & Sainz, A. B. A combinatorial approach to nonlocality and contextuality. Preprint at \n                    http:\/\/arxiv.org\/abs\/1212.4084\n                    \n                   (2012)"}],"container-title":["Nature"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.nature.com\/articles\/nature13460.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/www.nature.com\/articles\/nature13460","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/www.nature.com\/articles\/nature13460.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,18]],"date-time":"2023-05-18T18:22:15Z","timestamp":1684434135000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.nature.com\/articles\/nature13460"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6]]},"references-count":48,"journal-issue":{"issue":"7505","published-print":{"date-parts":[[2014,6]]}},"alternative-id":["BFnature13460"],"URL":"https:\/\/doi.org\/10.1038\/nature13460","relation":{},"ISSN":["0028-0836","1476-4687"],"issn-type":[{"value":"0028-0836","type":"print"},{"value":"1476-4687","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,6]]},"assertion":[{"value":"16 January 2014","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 April 2014","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 June 2014","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare no competing financial interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}