{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,7]],"date-time":"2024-02-07T00:53:38Z","timestamp":1707267218350},"reference-count":94,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2024,2,6]],"date-time":"2024-02-06T00:00:00Z","timestamp":1707177600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/K022512\/1"],"award-info":[{"award-number":["EP\/K022512\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["2360717"],"award-info":[{"award-number":["2360717"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>We provide new examples of pure entangled systems related to cluster state quantum computation that can be efficiently simulated classically. In cluster state quantum computation input qubits are initialised in the `equator' of the Bloch sphere, <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>C<\/mml:mi><mml:mi>Z<\/mml:mi><\/mml:math> gates are applied, and finally the qubits are measured adaptively using <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>Z<\/mml:mi><\/mml:math> measurements or measurements of <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>cos<\/mml:mi><mml:mo>&amp;#x2061;<\/mml:mo><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mi>&amp;#x03B8;<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><mml:mi>X<\/mml:mi><mml:mo>+<\/mml:mo><mml:mi>sin<\/mml:mi><mml:mo>&amp;#x2061;<\/mml:mo><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mi>&amp;#x03B8;<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><mml:mi>Y<\/mml:mi><\/mml:math> operators. We consider what happens when the initialisation step is modified, and show that for lattices of finite degree <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>D<\/mml:mi><\/mml:math>, there is a constant <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>&amp;#x03BB;<\/mml:mi><mml:mo>&amp;#x2248;<\/mml:mo><mml:mn>2.06<\/mml:mn><\/mml:math> such that if the qubits are prepared in a state that is within <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mi>&amp;#x03BB;<\/mml:mi><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo>&amp;#x2212;<\/mml:mo><mml:mi>D<\/mml:mi><\/mml:mrow><\/mml:msup><\/mml:math> in trace distance of a state that is diagonal in the computational basis, then the system can be efficiently simulated classically in the sense of sampling from the output distribution within a desired total variation distance. In the square lattice with <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>D<\/mml:mi><mml:mo>=<\/mml:mo><mml:mn>4<\/mml:mn><\/mml:math> for instance, <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mi>&amp;#x03BB;<\/mml:mi><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo>&amp;#x2212;<\/mml:mo><mml:mi>D<\/mml:mi><\/mml:mrow><\/mml:msup><mml:mo>&amp;#x2248;<\/mml:mo><mml:mn>0.056<\/mml:mn><\/mml:math>. We develop a coarse grained version of the argument which increases the size of the classically efficient region. In the case of the square lattice of qubits, the size of the classically simulatable region increases in size to at least around <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mo>&amp;#x2248;<\/mml:mo><mml:mn>0.070<\/mml:mn><\/mml:math>, and in fact probably increases to around <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mo>&amp;#x2248;<\/mml:mo><mml:mn>0.1<\/mml:mn><\/mml:math>. The results generalise to a broader family of systems, including qudit systems where the interaction is diagonal in the computational basis and the measurements are either in the computational basis or unbiased to it. Potential readers who only want the short version can get much of the intuition from figures 1 to 3.<\/jats:p>","DOI":"10.22331\/q-2024-02-06-1243","type":"journal-article","created":{"date-parts":[[2024,2,6]],"date-time":"2024-02-06T14:01:04Z","timestamp":1707228064000},"page":"1243","update-policy":"http:\/\/dx.doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":0,"title":["Efficient classical simulation of cluster state quantum circuits with alternative inputs"],"prefix":"10.22331","volume":"8","author":[{"given":"Sahar","family":"Atallah","sequence":"first","affiliation":[{"name":"Department of Mathematics, Brunel University London, Kingston Ln, Uxbridge, UB8 3PH, United Kingdom"}]},{"given":"Michael","family":"Garn","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Brunel University London, Kingston Ln, Uxbridge, UB8 3PH, United Kingdom"}]},{"given":"Sania","family":"Jevtic","sequence":"additional","affiliation":[{"name":"Phytoform Labs Ltd., Lawes Open Innovation Hub, West Common, Harpenden, Hertfordshire, England, AL5 2JQ, United Kingdom"}]},{"given":"Yukuan","family":"Tao","sequence":"additional","affiliation":[{"name":"Department of Physics and Astronomy, Dartmouth College, Hanover, New Hampshire, 03755, USA"}]},{"given":"Shashank","family":"Virmani","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Brunel University London, Kingston Ln, Uxbridge, UB8 3PH, United Kingdom"}]}],"member":"9598","published-online":{"date-parts":[[2024,2,6]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"J. Preskill, Quantum computing 40 years later. arXiv:2106.10522 [quant-ph]. DOI: 10.48550\/arXiv.2106.10522.","DOI":"10.48550\/arXiv.2106.10522"},{"key":"1","doi-asserted-by":"publisher","unstructured":"R. Raussendorf and H.J. Briegel, A One-Way Quantum Computer. Phys. Rev. Lett. 86, 5188 (2001). DOI: 10.1103\/PhysRevLett.86.5188.","DOI":"10.1103\/PhysRevLett.86.5188"},{"key":"2","doi-asserted-by":"publisher","unstructured":"A. Harrow and M. Nielsen, Robustness of quantum gates in the presence of noise. Phys. Rev. A 68, 012308 (2003). DOI: 10.1103\/PhysRevA.68.012308.","DOI":"10.1103\/PhysRevA.68.012308"},{"key":"3","doi-asserted-by":"publisher","unstructured":"D. Aharonov and M. Ben-Or, Polynomial simulations of decohered quantum computers. 37th Annual Symposium on Foundations of Computer Science (FOCS) pp 46\u201355, (1996). DOI: 10.1109\/SFCS.1996.548463.","DOI":"10.1109\/SFCS.1996.548463"},{"key":"4","doi-asserted-by":"publisher","unstructured":"S. Aaronson and D. Gottesman, Improved simulation of stabilizer circuits. Phys. Rev. A 70 (5): 052328, (2004). DOI: 10.1103\/PhysRevA.70.052328.","DOI":"10.1103\/PhysRevA.70.052328"},{"key":"5","doi-asserted-by":"publisher","unstructured":"E. Knill, Fault-Tolerant Postselected Quantum Computation: Schemes. arXiv:quant-ph\/0402171. DOI: 10.48550\/arXiv.quant-ph\/0402171.","DOI":"10.48550\/arXiv.quant-ph\/0402171"},{"key":"6","doi-asserted-by":"publisher","unstructured":"S. Bravyi and A. Kitaev, Universal quantum computation with ideal Clifford gates and noisy ancillas. Phys. Rev. A 71, 022316, (2005). DOI: 10.1103\/PhysRevA.71.022316.","DOI":"10.1103\/PhysRevA.71.022316"},{"key":"7","doi-asserted-by":"publisher","unstructured":"H. Barnum, E. Knill, G. Ortiz, and L. Viola. Generalizations of entanglement based on coherent states and convex sets. Phys. Rev. A 68, 032308 (2003). DOI: 10.1103\/PhysRevA.68.032308.","DOI":"10.1103\/PhysRevA.68.032308"},{"key":"8","doi-asserted-by":"publisher","unstructured":"H. Barnum, E. Knill, G. Ortiz, R. Somma, and L. Viola. A Subsystem-Independent Generalization of Entanglement. Phys. Rev. Lett. 92, 107902 (2004). DOI: 10.1103\/PhysRevLett.92.107902.","DOI":"10.1103\/PhysRevLett.92.107902"},{"key":"9","doi-asserted-by":"publisher","unstructured":"A. Klyachko, Coherent States, Entanglement, and Geometric Invariant Theory,arXiv:quant-ph\/0206012, (2002). DOI: 10.48550\/arXiv.quant-ph\/0206012.","DOI":"10.48550\/arXiv.quant-ph\/0206012"},{"key":"10","doi-asserted-by":"publisher","unstructured":"K. S. Gibbons, M. J. Hoffman, and W. K. Wootters. Discrete phase space based on finite fields. Phys. Rev. A 70, 062101 (2004). DOI: 10.1103\/PhysRevA.70.062101.","DOI":"10.1103\/PhysRevA.70.062101"},{"key":"11","doi-asserted-by":"publisher","unstructured":"D. Gross. Hudson\u2019s theorem for finite-dimensional quantum systems. J. Math. Phys., 47(12):122107 (2006). DOI: 10.1063\/1.2393152.","DOI":"10.1063\/1.2393152"},{"key":"12","doi-asserted-by":"publisher","unstructured":"J. Barrett, Information processing in generalized probabilistic theories. Phys. Rev. A 75, 032304 (2007). DOI: 10.1103\/PhysRevA.75.032304.","DOI":"10.1103\/PhysRevA.75.032304"},{"key":"13","doi-asserted-by":"publisher","unstructured":"L. Hardy, Quantum Theory From Five Reasonable Axioms. quant-ph\/0101012 , (2001). DOI: 10.48550\/arXiv.quant-ph\/0101012.","DOI":"10.48550\/arXiv.quant-ph\/0101012"},{"key":"14","doi-asserted-by":"publisher","unstructured":"A. S. Holevo, ``Probabilistic and Statistical Aspects of Quantum Theory\", North Holland (1982). DOI: 10.1007\/978-88-7642-378-9.","DOI":"10.1007\/978-88-7642-378-9"},{"key":"15","doi-asserted-by":"publisher","unstructured":"S. Popescu and D. Rohrlich, Quantum nonlocality as an axiom. Foundations of Physics, 24, 379 (1994). DOI: 10.1007\/BF02058098.","DOI":"10.1007\/BF02058098"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Barrett, J., de Beaudrap, N., Hoban, M.J., and Lee, C., The computational landscape of general physical theories. NPJ Quantum Inf 5, 41 (2019). DOI: 10.1038\/s41534-019-0156-9.","DOI":"10.1038\/s41534-019-0156-9"},{"key":"17","doi-asserted-by":"publisher","unstructured":"N. Ratanje and S. Virmani, Generalized state spaces and nonlocality in fault-tolerant quantum-computing schemes. Phys. Rev. A 83 032309 (2011). DOI: 10.1103\/PhysRevA.83.032309.","DOI":"10.1103\/PhysRevA.83.032309"},{"key":"18","doi-asserted-by":"publisher","unstructured":"N. Ratanje and S. Virmani, Exploiting non-quantum entanglement to widen applicability of limited-entanglement classical simulations of quantum systems. arXiv:1201.0613v1. DOI: 10.48550\/arXiv.1201.0613.","DOI":"10.48550\/arXiv.1201.0613"},{"key":"19","doi-asserted-by":"publisher","unstructured":"H. Anwar, S Jevtic, O. Rudolph, and S. Virmani, Families of pure PEPS with efficiently simulatable local hidden variable models for most measurements. arXiv:1412.3780v2. DOI: 10.48550\/arXiv.1412.3780.","DOI":"10.48550\/arXiv.1412.3780"},{"key":"20","doi-asserted-by":"publisher","unstructured":"H. Anwar, S. Jevtic, O. Rudolph, and S. Virmani. Smallest disentangling state spaces for general entangled bipartite quantum states. New J. Phys. 17, 093047 (2015). DOI: 10.1088\/1367-2630\/17\/9\/093047.","DOI":"10.1088\/1367-2630\/17\/9\/093047"},{"key":"21","doi-asserted-by":"publisher","unstructured":"H. Anwar, S. Jevtic, O. Rudolph, and S. Virmani. Generalised versions of separable decompositions applicable to bipartite entangled quantum states. New J. Phys. 21, 093031 (2019). DOI: 10.1088\/1367-2630\/ab3adc.","DOI":"10.1088\/1367-2630\/ab3adc"},{"key":"22","doi-asserted-by":"publisher","unstructured":"O. Rudolph, A separability criterion for density operators, J. Phys. A: Math. Gen. 33 3951 (2000). DOI: 10.1088\/0305-4470\/33\/21\/308; O. Rudolph, A new class of entanglement measures, J. Math. Phys. 42 5306 (2001). DOI: 10.1088\/0305-4470\/33\/21\/308.","DOI":"10.1088\/0305-4470\/33\/21\/308"},{"key":"23","doi-asserted-by":"publisher","unstructured":"F. Verstraete and J.I. Cirac, Valence-bond states for quantum computation. Phys. Rev. A 70, 060302(R) (2004). DOI: 10.1103\/PhysRevA.70.060302.","DOI":"10.1103\/PhysRevA.70.060302"},{"key":"24","doi-asserted-by":"publisher","unstructured":"R F Werner, Quantum states with Einstein-Podolsky-Rosen correlations admitting a hidden-variable model. Phys. Rev. A 40 4277 (1989). DOI: 10.1103\/PhysRevA.40.4277.","DOI":"10.1103\/PhysRevA.40.4277"},{"key":"25","unstructured":"Avis, D. (2010). Polyhedral Computation: Lecture 2. Kyoto University. Retrieved from http:\/\/www.lab2.kuis.kyoto-u.ac.jp\/ avis\/courses\/pc\/2010\/notes\/lec2.pdf."},{"key":"26","doi-asserted-by":"publisher","unstructured":"Barrett, S., Bartlett, S., Doherty, A., Jennings, D. & Rudolph, T. Transitions in the computational power of thermal states for measurement-based quantum computation. Physical Review A. 80, 062328 (2009). DOI: 10.1103\/PhysRevA.80.062328.","DOI":"10.1103\/PhysRevA.80.062328"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Browne, D., Elliott, M., Flammia, S., Merkel, S., Miyake, A. & Short, A. Phase transition of computational power in the resource states for one-way quantum computation. New Journal Of Physics. 10, 023010 (2008). DOI: 10.1088\/1367-2630\/10\/2\/023010.","DOI":"10.1088\/1367-2630\/10\/2\/023010"},{"key":"28","doi-asserted-by":"publisher","unstructured":"A. Peres. Separability Criterion for Density Matrices. Phys. Rev. Lett. 77 (8): 1413 (1996). DOI: 10.1103\/PhysRevLett.77.1413.","DOI":"10.1103\/PhysRevLett.77.1413"},{"key":"29","doi-asserted-by":"publisher","unstructured":"M. Horodecki, P. Horodecki, and R. Horodecki. Separability of mixed states: necessary and sufficient conditions. Phys. Lett. A. 223 (1\u20132): 1\u20138. (1996). DOI: 10.1016\/S0375-9601(96)00706-2.","DOI":"10.1016\/S0375-9601(96)00706-2"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Mora, C., Piani, M., Miyake, A., Van den Nest, M., D\u00fcr, W. & Briegel, H. Universal resources for approximate and stochastic measurement-based quantum computation. Physical Review A. 81, 042315 (2010). DOI: 10.1103\/PhysRevA.81.042315.","DOI":"10.1103\/PhysRevA.81.042315"},{"key":"31","doi-asserted-by":"publisher","unstructured":"B. Terhal and D. DiVincenzo, Adaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin Games. Quant. Inf. Comp. Vol. 4 (No. 2), pages 134\u2013145 (2004). DOI: 10.26421\/QIC4.2-5.","DOI":"10.26421\/QIC4.2-5"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Harrow, A. & Montanaro, A. Quantum computational supremacy. Nature. 549, 203-209 (2017). DOI: 10.1038\/nature23458.","DOI":"10.1038\/nature23458"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Bremner, M., Jozsa, R. & Shepherd, D. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proceedings Of The Royal Society A: Mathematical, Physical And Engineering Sciences. 467, 459-472 (2011). DOI: 10.1098\/rspa.2010.0301.","DOI":"10.1098\/rspa.2010.0301"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Bremner, M., Montanaro, A. & Shepherd, D. Average-case complexity versus approximate simulation of commuting quantum computations. Physical Review Letters. 117, 080501 (2016). DOI: 10.1103\/PhysRevLett.117.080501.","DOI":"10.1103\/PhysRevLett.117.080501"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Aaronson, S. & Chen, L. Complexity-theoretic foundations of quantum supremacy experiments. Proc. 32 Comput. Complex. Conf., CCC \u201917 (2017). DOI: 10.4230\/LIPIcs.CCC.2017.22.","DOI":"10.4230\/LIPIcs.CCC.2017.22"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Bremner, M., Montanaro, A. & Shepherd, D. Achieving quantum supremacy with sparse and noisy commuting quantum computations. Quantum. 1 pp. 8 (2017). DOI: 10.22331\/q-2017-04-25-8.","DOI":"10.22331\/q-2017-04-25-8"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Miller, J., Sanders, S. & Miyake, A. Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification. Physical Review A. 96, 062320 (2017). DOI: 10.1103\/PhysRevA.96.062320.","DOI":"10.1103\/PhysRevA.96.062320"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Gao, X., Wang, S. & Duan, L. Quantum supremacy for simulating a translation-invariant Ising spin model. Physical Review Letters. 118, 040502 (2017). DOI: 10.1103\/PhysRevLett.118.040502.","DOI":"10.1103\/PhysRevLett.118.040502"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Yoganathan, M., Jozsa, R. & Strelchuk, S. Quantum advantage of unitary Clifford circuits with magic state inputs. Proceedings Of The Royal Society A. 475, 20180427 (2019). DOI: 10.1098\/rspa.2018.0427.","DOI":"10.1098\/rspa.2018.0427"},{"key":"40","doi-asserted-by":"publisher","unstructured":"Haferkamp, J., Hangleiter, D., Bouland, A., Fefferman, B., Eisert, J. & Bermejo-Vega, J. Closing gaps of a quantum advantage with short-time Hamiltonian dynamics. Physical Review Letters. 125, 250501 (2020). DOI: 10.1103\/PhysRevLett.125.250501.","DOI":"10.1103\/PhysRevLett.125.250501"},{"key":"41","doi-asserted-by":"publisher","unstructured":"R. Jozsa and N. Linden, On the role of entanglement in quantum-computational speed-up. Proc. Roy. Soc. A, 459 2036 (2003). DOI: 10.1098\/rspa.2002.1097.","DOI":"10.1098\/rspa.2002.1097"},{"key":"42","doi-asserted-by":"publisher","unstructured":"M. Yoganathan and C. Cade, The one clean qubit model without entanglement is classically simulable. arXiv:1907.08224v1. DOI: 10.48550\/arXiv.1907.08224.","DOI":"10.48550\/arXiv.1907.08224"},{"key":"43","doi-asserted-by":"publisher","unstructured":"G. Vidal, Efficient Classical Simulation of Slightly Entangled Quantum Computations. Phys. Rev. Lett. 91 147902, (2003). DOI: 10.1103\/PhysRevLett.91.147902.","DOI":"10.1103\/PhysRevLett.91.147902"},{"key":"44","doi-asserted-by":"publisher","unstructured":"M. A. Nielsen, Cluster-state quantum computation. Rep. Math. Phys. 57 147\u201361 (2006). DOI: 10.1016\/S0034-4877(06)80014-5.","DOI":"10.1016\/S0034-4877(06)80014-5"},{"key":"45","doi-asserted-by":"publisher","unstructured":"N. Yoran and A. J. Short, Classical Simulation of Limited-Width Cluster-State Quantum Computation. Phys. Rev. Lett. 96, 170503 (2006). DOI: 10.1103\/PhysRevLett.96.170503.","DOI":"10.1103\/PhysRevLett.96.170503"},{"key":"46","doi-asserted-by":"publisher","unstructured":"I. L. Markov and Y. Shi, Simulating Quantum Computation by Contracting Tensor Networks. SIAM Journal on Computing, 38(3):963-981, (2008). DOI: 10.1137\/050644756.","DOI":"10.1137\/050644756"},{"key":"47","doi-asserted-by":"publisher","unstructured":"S. Ghosh, A. Deshpande, D. Hangleiter, Alexey V. Gorshkov, and B. Fefferman, Complexity Phase Transitions Generated by Entanglement. Phys. Rev. Lett. 131, 030601 (2023). DOI: 10.1103\/PhysRevLett.131.030601.","DOI":"10.1103\/PhysRevLett.131.030601"},{"key":"48","doi-asserted-by":"publisher","unstructured":"S Bravyi, D Gosset, R K\u00f6nig, and M Tomamichel, Quantum advantage with noisy shallow circuits in 3D. Nature Physics 16 (10), 1040-1045, 2020. DOI: 10.1038\/s41567-020-0948-z.","DOI":"10.1038\/s41567-020-0948-z"},{"key":"49","doi-asserted-by":"publisher","unstructured":"Jozsa, R. & Miyake, A. Matchgates and classical simulation of quantum circuits. Proceedings Of The Royal Society A: Mathematical, Physical And Engineering Sciences. 464, 3089-3106 (2008). DOI: 10.1098\/rspa.2008.0189.","DOI":"10.1098\/rspa.2008.0189"},{"key":"50","doi-asserted-by":"publisher","unstructured":"Jozsa, R. & Van den Nest, M. Classical simulation complexity of extended Clifford circuits. Quantum Info.Comput., 14, pp. 633\u2013648, (2014). DOI: 10.26421\/QIC14.7-8-7.","DOI":"10.26421\/QIC14.7-8-7"},{"key":"51","doi-asserted-by":"publisher","unstructured":"S. Virmani, S. F. Huelga, and M. B. Plenio, Classical simulability, entanglement breaking, and quantum computation thresholds. Phys. Rev. A, 71, 042328 (2005). DOI: 10.1103\/PhysRevA.71.042328.","DOI":"10.1103\/PhysRevA.71.042328"},{"key":"52","doi-asserted-by":"publisher","unstructured":"Napp, J., La Placa, R., Dalzell, A., Brandao, F. & Harrow, A. Efficient classical simulation of random shallow 2D quantum circuits. ArXiv Preprint ArXiv:2001.00021. (2019). DOI: 10.48550\/arXiv.2001.00021.","DOI":"10.48550\/arXiv.2001.00021"},{"key":"53","doi-asserted-by":"publisher","unstructured":"Noh, K., Jiang, L. & Fefferman, B. Efficient classical simulation of noisy random quantum circuits in one dimension. Quantum. 4 pp. 318 (2020). DOI: 10.22331\/q-2020-09-11-318.","DOI":"10.22331\/q-2020-09-11-318"},{"key":"54","doi-asserted-by":"publisher","unstructured":"Okay, C., Zurel, M. & Raussendorf, R. On the extremal points of the $\\Lambda$ -polytopes and classical simulation of quantum computation with magic states. Quantum Info. and Comput. 21 No.13 & 14, 1533-7146 (2021). DOI: 10.26421\/QIC21.13-14-2.","DOI":"10.26421\/QIC21.13-14-2"},{"key":"55","doi-asserted-by":"publisher","unstructured":"Pashayan, H., Reardon-Smith, O., Korzekwa, K. & Bartlett, S. Fast estimation of outcome probabilities for quantum circuits. Quantum 5, 606 (2021). DOI: 10.1103\/PRXQuantum.3.020361.","DOI":"10.1103\/PRXQuantum.3.020361"},{"key":"56","doi-asserted-by":"publisher","unstructured":"Gosset, D., Grier, D., Kerzner, A. & Schaeffer, L. Fast simulation of planar Clifford circuits. ArXiv Preprint ArXiv:2009.03218. (2020). DOI: 10.48550\/arXiv.2009.03218.","DOI":"10.48550\/arXiv.2009.03218"},{"key":"57","doi-asserted-by":"publisher","unstructured":"Van den Nest, M. Universal quantum computation with little entanglement. Physical Review Letters. 110, 060504 (2013). DOI: 10.1103\/PhysRevLett.110.060504.","DOI":"10.1103\/PhysRevLett.110.060504"},{"key":"58","doi-asserted-by":"publisher","unstructured":"Qassim, H., Pashayan, H. & Gosset, D. Improved upper bounds on the stabilizer rank of magic states. ArXiv Preprint ArXiv:2106.07740. (2021). DOI: 10.48550\/arXiv.2106.07740.","DOI":"10.48550\/arXiv.2106.07740"},{"key":"59","doi-asserted-by":"publisher","unstructured":"Raussendorf, R., Bermejo-Vega, J., Tyhurst, E., Okay, C. & Zurel, M. Phase-space-simulation method for quantum computation with magic states on qubits. Physical Review A. 101, 012350 (2020). DOI: 10.1103\/PhysRevA.101.012350.","DOI":"10.1103\/PhysRevA.101.012350"},{"key":"60","doi-asserted-by":"publisher","unstructured":"Schwarz, M. & Van den Nest, M. Simulating quantum circuits with sparse output distributions. ArXiv Preprint ArXiv:1310.6749. (2013). DOI: 10.48550\/arXiv.1310.6749.","DOI":"10.48550\/arXiv.1310.6749"},{"key":"61","doi-asserted-by":"publisher","unstructured":"Seddon, J., Regula, B., Pashayan, H., Ouyang, Y. & Campbell, E. Quantifying quantum speedups: Improved classical simulation from tighter magic monotones. PRX Quantum. 2, 010345 (2021).DOI: 10.1103\/PRXQuantum.2.010345.","DOI":"10.1103\/PRXQuantum.2.010345"},{"key":"62","doi-asserted-by":"publisher","unstructured":"H. Pashayan, J. J. Wallman, and S. D. Bartlett, Estimating Outcome Probabilities of Quantum Circuits Using Quasiprobabilities. Phys. Rev. Lett. 115, 070501 (2015). DOI: 10.1103\/PhysRevLett.115.070501.","DOI":"10.1103\/PhysRevLett.115.070501"},{"key":"63","doi-asserted-by":"publisher","unstructured":"Van den Nest, M. Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond. Quant. Inf. Comp. 10, 3-4 pp. pp0258-0271 (2010). DOI: 10.26421\/QIC10.3-4-6.","DOI":"10.26421\/QIC10.3-4-6"},{"key":"64","doi-asserted-by":"publisher","unstructured":"Van den Nest, M., D\u00fcr, W., Vidal, G. & Briegel, H. Classical simulation versus universality in measurement-based quantum computation. Physical Review A. 75, 012337 (2007). DOI: 10.1103\/PhysRevA.75.012337.","DOI":"10.1103\/PhysRevA.75.012337"},{"key":"65","doi-asserted-by":"publisher","unstructured":"Zurel, M., Okay, C. & Raussendorf, R. Hidden Variable Model for Universal Quantum Computation with Magic States on Qubits. Physical Review Letters. 125, 260404 (2020).DOI: 10.1103\/PhysRevLett.125.260404.","DOI":"10.1103\/PhysRevLett.125.260404"},{"key":"66","doi-asserted-by":"publisher","unstructured":"Gross, D., Eisert, J., Schuch, N. & Perez-Garcia, D. Measurement-based quantum computation beyond the one-way model. Physical Review A. 76, 052315 (2007). DOI: 10.1103\/PhysRevA.76.052315.","DOI":"10.1103\/PhysRevA.76.052315"},{"key":"67","doi-asserted-by":"publisher","unstructured":"M. Van den Nest, A. Miyake, W. D\u00fcr, H. J. Briegel, Universal Resources for Measurement-Based Quantum Computation. Phys. Rev. Lett. 97, 150504 (2006).DOI: 10.1103\/PhysRevLett.97.150504.","DOI":"10.1103\/PhysRevLett.97.150504"},{"key":"68","doi-asserted-by":"publisher","unstructured":"Jozsa, R. On the simulation of quantum circuits. ArXiv Preprint Quant-ph\/0603163. (2006). DOI: 10.48550\/arXiv.quant-ph\/0603163.","DOI":"10.48550\/arXiv.quant-ph\/0603163"},{"key":"69","doi-asserted-by":"publisher","unstructured":"F. Verstraete, M. Popp, and J. I. Cirac, Entanglement versus Correlations in Spin Systems. Phys. Rev. Lett. 92, 027901 (2004). DOI: 10.1103\/PhysRevLett.92.027901.","DOI":"10.1103\/PhysRevLett.92.027901"},{"key":"70","doi-asserted-by":"publisher","unstructured":"A. Kissinger, J. van de Wetering, Universal MBQC with generalised parity-phase interactions and Pauli measurements. Quantum 3, 134 (2019). DOI: 10.22331\/q-2019-04-26-134.","DOI":"10.22331\/q-2019-04-26-134"},{"key":"71","doi-asserted-by":"publisher","unstructured":"Y. Takeuchi, T. Morimae, M. Hayashi, Quantum computational universality of hypergraph states with Pauli-X and Z basis measurements. Sci Rep. 9, 13585 (2019). DOI: 10.1038\/s41598-019-49968-3.","DOI":"10.1038\/s41598-019-49968-3"},{"key":"72","doi-asserted-by":"publisher","unstructured":"J. Miller, A. Miyake. Hierarchy of universal entanglement in 2D measurement-based quantum computation. npj Quantum Information 2, 16036 (2016). DOI: 10.1038\/npjqi.2016.36.","DOI":"10.1038\/npjqi.2016.36"},{"key":"73","doi-asserted-by":"publisher","unstructured":"M. Gachechiladze, O. G\u00fchne, A. Miyake. Changing the circuit-depth complexity of measurement-based quantum computation with hypergraph states. Phys. Rev. A, 99, 052304 (2019). DOI: 10.1103\/PhysRevA.99.052304.","DOI":"10.1103\/PhysRevA.99.052304"},{"key":"74","doi-asserted-by":"publisher","unstructured":"D. L. Zhou, B. Zeng, Z. Xu, and C. P. Sun, Quantum computation based on d-level cluster state. Phys. Rev. A 68, 062303 (2003); W. Hall, Cluster state quantum computation for many-level systems. Quant. Inf. & Comp., 7, Issue 3 pp 184\u2013208 (2007). DOI: 10.1103\/PhysRevA.68.0623034.","DOI":"10.1103\/PhysRevA.68.0623034"},{"key":"75","doi-asserted-by":"publisher","unstructured":"L. P. Hughston, R. Jozsa, and W. K. Wootters, A complete classification of quantum ensembles having a given density matrix. Phys. Lett. A 183, 1, P.14-18 (1993). DOI: 10.1016\/0375-9601(93)90880-9.","DOI":"10.1016\/0375-9601(93)90880-9"},{"key":"76","doi-asserted-by":"publisher","unstructured":"H. Pashayan, S Bartlett, and D. Gross, From estimation of quantum probabilities to simulation of quantum circuits. Quantum 4, 223 (2020). DOI: 10.22331\/q-2020-01-13-223.","DOI":"10.22331\/q-2020-01-13-223"},{"key":"77","doi-asserted-by":"publisher","unstructured":"L. Gurvitz and H. Barnum, Largest separable balls around the maximally mixed bipartite quantum state. Phys. Rev. A, 66, 062311 (2002) DOI: 10.1103\/PhysRevA.66.062311.","DOI":"10.1103\/PhysRevA.66.062311"},{"key":"78","doi-asserted-by":"publisher","unstructured":"B. Terhal, Bell inequalities and the separability criterion. Phys. Lett. A, 271, 319 (2000). DOI: 10.1016\/S0375-9601(00)00401-1.","DOI":"10.1016\/S0375-9601(00)00401-1"},{"key":"79","doi-asserted-by":"publisher","unstructured":"M. Van den Nest, Simulating quantum computers with probabilistic methods. Quant. Inf. Comp. 11, 9-10 pp. 784-812 (2011) DOI: 10.26421\/QIC11.9-10-5.","DOI":"10.26421\/QIC11.9-10-5"},{"key":"80","doi-asserted-by":"publisher","unstructured":"H. J. Garcia, I. L. Markov, and A. W. Cross. Efficient inner-product algorithm for stabilizer states. arXiv preprint arXiv:1210.6646, (2012). DOI: 10.48550\/arXiv.1210.6646.","DOI":"10.48550\/arXiv.1210.6646"},{"key":"81","doi-asserted-by":"publisher","unstructured":"S. Bravyi, G. Smith, and J. A. Smolin. Trading classical and quantum computational resources. Physical Review X, 6:021043, (2016). DOI: 10.1103\/PhysRevX.6.021043.","DOI":"10.1103\/PhysRevX.6.021043"},{"key":"82","doi-asserted-by":"publisher","unstructured":"H. Buhrman, R. Cleve, M. Laurent, N. Linden, A. Schrijver, and F. Unger, New limits on fault-tolerant quantum computation. Proc. of the 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201906) (IEEE, New York, 2006), pp. 411\u2013419. DOI: 10.1109\/FOCS.2006.50.","DOI":"10.1109\/FOCS.2006.50"},{"key":"83","doi-asserted-by":"publisher","unstructured":"L. G. Valiant, Quantum circuits that can be simulated classically in polynomial time. SIAM Journal on Computing, 31(4):1229\u20131254, (2002). DOI: 10.1137\/S0097539700377025.","DOI":"10.1137\/S0097539700377025"},{"key":"84","doi-asserted-by":"publisher","unstructured":"B. M. Terhal and D. P. DiVincenzo, Classical simulation of noninteracting-fermion quantum circuits. Phys. Rev. A, 65(3):032325, (2002). DOI: 10.1103\/PhysRevA.65.032325.","DOI":"10.1103\/PhysRevA.65.032325"},{"key":"85","doi-asserted-by":"publisher","unstructured":"M. B. Hastings, An area law for one dimensional quantum systems. J. Stat. Mech., 2007:08024, (2007). DOI: 10.1088\/1742-5468\/2007\/08\/P08024.","DOI":"10.1088\/1742-5468\/2007\/08\/P08024"},{"key":"86","doi-asserted-by":"publisher","unstructured":"E. F. Galvao, Discrete Wigner functions and quantum computational speedup. Phys. Rev. A 71, 042302 (2005). DOI: 10.1103\/PhysRevA.71.042302 ; C. Cormick, E. F. Galvao, D. Gottesman, J. P. Paz, and A. O. Pittenger, Classicality in discrete Wigner functions, Phys. Rev. A 73 012301 (2006). DOI: 10.1103\/PhysRevA.71.042302.","DOI":"10.1103\/PhysRevA.71.042302"},{"key":"87","doi-asserted-by":"publisher","unstructured":"D. J. Brod, Efficient classical simulation of matchgate circuits with generalized inputs and measurements. Phys. Rev. A 93, 062332 (2016) DOI: 10.1103\/PhysRevA.93.062332.","DOI":"10.1103\/PhysRevA.93.062332"},{"key":"88","doi-asserted-by":"publisher","unstructured":"Arute et. al., Quantum supremacy using a programmable superconducting processor. Nature, 574(7779):505\u2013510, 2019. DOI: 10.1038\/s41586-019-1666-5.","DOI":"10.1038\/s41586-019-1666-5"},{"key":"89","doi-asserted-by":"publisher","unstructured":"R. Raz, Exponential separation of quantum and classical communication complexity. Proc. 31st Annual ACM Symp. Theory of Computing, pages 358\u2013367, (1999). DOI: 10.1145\/301250.301343.","DOI":"10.1145\/301250.301343"},{"key":"90","doi-asserted-by":"publisher","unstructured":"F Pan, K Chen and P Zhan, Solving the sampling problem of the sycamore quantum circuits. Phys. Rev. Lett. 129 (9), 090502 (2022). DOI: 10.1103\/PhysRevLett.129.090502.","DOI":"10.1103\/PhysRevLett.129.090502"},{"key":"91","doi-asserted-by":"publisher","unstructured":"D. Aharonov, X. Gao, Z. Landau, Y. Liu, and U. Vazirani. A polynomial-time classical algorithm for noisy random circuit sampling. arXiv:2211.03999, (2022). DOI: 10.48550\/arXiv.2211.03999.","DOI":"10.48550\/arXiv.2211.03999"},{"key":"92","doi-asserted-by":"publisher","unstructured":"S. Popescu and D. Rohrlich, Generic quantum nonlocality. Phys. Lett. A 166, 293 (1992). DOI: 10.1016\/0375-9601(92)90711-T.","DOI":"10.1016\/0375-9601(92)90711-T"},{"key":"93","doi-asserted-by":"publisher","unstructured":"R. Somma, H. Barnum, G. Ortiz, and E. Knill, Efficient Solvability of Hamiltonians and Limits on the Power of Some Quantum Computational Models. Phys. Rev. Lett. 97, 190501 (2006). DOI: 10.1103\/PhysRevLett.97.190501.","DOI":"10.1103\/PhysRevLett.97.190501"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-02-06-1243\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,2,6]],"date-time":"2024-02-06T14:01:24Z","timestamp":1707228084000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-02-06-1243\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,6]]},"references-count":94,"URL":"https:\/\/doi.org\/10.22331\/q-2024-02-06-1243","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,6]]},"article-number":"1243"}}