{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T21:01:11Z","timestamp":1763499671146,"version":"build-2065373602"},"reference-count":23,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2021,9,28]],"date-time":"2021-09-28T00:00:00Z","timestamp":1632787200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>We consider a model of quantum computation using qubits where it is possible to measure whether a given pair are in a singlet (total spin <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mn>0<\/mml:mn><\/mml:math>) or triplet (total spin <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mn>1<\/mml:mn><\/mml:math>) state. The physical motivation is that we can do these measurements in a way that is protected against revealing other information so long as all terms in the Hamiltonian are <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>S<\/mml:mi><mml:mi>U<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mn>2<\/mml:mn><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math>-invariant. We conjecture that this model is equivalent to BQP. Towards this goal, we show: (1) this model is capable of universal quantum computation with polylogarithmic overhead if it is supplemented by single qubit <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>X<\/mml:mi><\/mml:math> and <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>Z<\/mml:mi><\/mml:math> gates. (2) Without any additional gates, it is at least as powerful as the weak model of \"permutational quantum computation\" of Jordan [14, 18]. (3) With postselection, the model is equivalent to PostBQP.<\/jats:p>","DOI":"10.22331\/q-2021-09-28-554","type":"journal-article","created":{"date-parts":[[2021,9,28]],"date-time":"2021-09-28T16:02:36Z","timestamp":1632844956000},"page":"554","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":7,"title":["Symmetry Protected Quantum Computation"],"prefix":"10.22331","volume":"5","author":[{"given":"Michael H.","family":"Freedman","sequence":"first","affiliation":[{"name":"Station Q, Microsoft Research, Santa Barbara, CA 93106-6105, USA"},{"name":"Microsoft Quantum, Redmond, WA 98052, USA"}]},{"given":"Matthew B.","family":"Hastings","sequence":"additional","affiliation":[{"name":"Station Q, Microsoft Research, Santa Barbara, CA 93106-6105, USA"},{"name":"Microsoft Quantum, Redmond, WA 98052, USA"}]},{"given":"Modjtaba","family":"Shokrian Zini","sequence":"additional","affiliation":[{"name":"Perimeter Institute for Theoretical Physics, Waterloo, ON N2L 2Y5, Canada"},{"name":"Research Consultant, Microsoft"}]}],"member":"9598","published-online":{"date-parts":[[2021,9,28]]},"reference":[{"key":"0","unstructured":"MathOverflow discussion."},{"key":"1","unstructured":"Mathematics Stack Exchange discussion."},{"key":"2","doi-asserted-by":"publisher","unstructured":"Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al. Quantum supremacy using a programmable superconducting processor. Nature, 574 (7779): 505\u2013510, 2019. 10.1038\/s41586-019-1666-5.","DOI":"10.1038\/s41586-019-1666-5"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal clifford gates and noisy ancillas. Physical Review A, 71 (2), 2005. 10.1103\/physreva.71.022316.","DOI":"10.1103\/physreva.71.022316"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Toby Cubitt and Ashley Montanaro. Complexity classification of local hamiltonian problems. SIAM Journal on Computing, 45 (2): 268\u2013316, 2016. 10.1137\/140998287.","DOI":"10.1137\/140998287"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Toby S. Cubitt, Ashley Montanaro, and Stephen Piddock. Universal quantum hamiltonians. Proceedings of the National Academy of Sciences, 115 (38): 9497\u20139502, 2018. 10.1073\/pnas.1804949115.","DOI":"10.1073\/pnas.1804949115"},{"key":"6","doi-asserted-by":"publisher","unstructured":"D. P. DiVincenzo, D. Bacon, J. Kempe, G. Burkard, and K. B. Whaley. Universal quantum computation with the exchange interaction. Nature, 408 (6810): 339\u2013342, nov 2000. 10.1038\/35042541.","DOI":"10.1038\/35042541"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Matthew PA Fisher. Quantum cognition: The possibility of processing with nuclear spins in the brain. Annals of Physics, 362: 593\u2013602, 2015. 10.1016\/j.aop.2015.08.020.","DOI":"10.1016\/j.aop.2015.08.020"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Michael Freedman, Modjtaba Shokrian-Zini, and Zhenghan Wang. Quantum computing with octonions. Peking Mathematical Journal, 2 (3): 239\u2013273, 2019. 10.1007\/s42543-019-00020-3.","DOI":"10.1007\/s42543-019-00020-3"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Daniel Gottesman. An introduction to quantum error correction and fault-tolerant quantum computation. pages 13\u201358, 2010. 10.1090\/psapm\/068\/2762145.","DOI":"10.1090\/psapm\/068\/2762145"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Aram W Harrow and Ashley Montanaro. Quantum computational supremacy. Nature, 549 (7671): 203\u2013209, 2017. https:\/\/doi.org\/10.1038\/nature23458.","DOI":"10.1038\/nature23458"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Vojt\u011bch Havl\u00ed\u010dek and Sergii Strelchuk. Quantum schur sampling circuits can be strongly simulated. Physical Review Letters, 121 (6), 2018. 10.1103\/physrevlett.121.060505.","DOI":"10.1103\/physrevlett.121.060505"},{"key":"12","doi-asserted-by":"publisher","unstructured":"A. C. Johnson, J. R. Petta, C. M. Marcus, M. P. Hanson, and A. C. Gossard. Singlet-triplet spin blockade and charge sensing in a few-electron double quantum dot. Physical Review B, 72 (16), 2005. 10.1103\/physrevb.72.165308.","DOI":"10.1103\/physrevb.72.165308"},{"key":"13","doi-asserted-by":"crossref","unstructured":"Stephen P Jordan. Permutational quantum computing. Quantum Information & Computation, 10 (5): 470\u2013497, 2010. DOI: 10.5555\/2011362.2011369.","DOI":"10.26421\/QIC10.5-6-7"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Torsten Karzig, Christina Knapp, Roman M. Lutchyn, Parsa Bonderson, Matthew B. Hastings, Chetan Nayak, Jason Alicea, Karsten Flensberg, Stephan Plugge, Yuval Oreg, Charles M. Marcus, and Michael H. Freedman. Scalable designs for quasiparticle-poisoning-protected topological quantum computation with majorana zero modes. Physical Review B, 95 (23), 2017. 10.1103\/physrevb.95.235305.","DOI":"10.1103\/physrevb.95.235305"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Aleksei Yur'evich Kitaev. Quantum computations: algorithms and error correction. Uspekhi Matematicheskikh Nauk, 52 (6): 53\u2013112, 1997. 10.1070\/rm1997v052n06abeh002155.","DOI":"10.1070\/rm1997v052n06abeh002155"},{"key":"16","doi-asserted-by":"publisher","unstructured":"A.Yu. Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics, 303 (1): 2\u201330, 2003. 10.1016\/s0003-4916(02)00018-0.","DOI":"10.1016\/s0003-4916(02)00018-0"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Annalisa Marzuoli and Mario Rasetti. Computing spin networks. Annals of Physics, 318 (2): 345\u2013407, 2005. 10.1016\/j.aop.2005.01.005.","DOI":"10.1016\/j.aop.2005.01.005"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Hendrik Poulsen Nautrup and Tzu-Chieh Wei. Symmetry-protected topologically ordered states for universal quantum computation. Physical Review A, 92 (5), 2015. 10.1103\/physreva.92.052309.","DOI":"10.1103\/physreva.92.052309"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Robert Raussendorf, Daniel E. Browne, and Hans J. Briegel. Measurement-based quantum computation on cluster states. Physical Review A, 68 (2), 2003. 10.1103\/physreva.68.022312.","DOI":"10.1103\/physreva.68.022312"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Terry Rudolph and Shashank Soyuz Virmani. A relational quantum computer using only two-qubit total spin measurement and an initial supply of highly mixed single-qubit states. New Journal of Physics, 7: 228\u2013228, oct 2005. 10.1088\/1367-2630\/7\/1\/228.","DOI":"10.1088\/1367-2630\/7\/1\/228"},{"key":"21","unstructured":"Terry Rudolph and Shashank Soyuz Virmani. Relational quantum computing using only maximally mixed initial qubit states. arXiv preprint arXiv:2107.03239, 2021."},{"key":"22","doi-asserted-by":"publisher","unstructured":"Zheng-Yuan Xue. Measurement based controlled not gate for topological qubits in a majorana fermion and quantum-dot hybrid system. The European Physical Journal D, 67 (4), 2013. 10.1140\/epjd\/e2013-30582-y.","DOI":"10.1140\/epjd\/e2013-30582-y"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-09-28-554\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,9,28]],"date-time":"2021-09-28T16:02:42Z","timestamp":1632844962000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-09-28-554\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,28]]},"references-count":23,"URL":"https:\/\/doi.org\/10.22331\/q-2021-09-28-554","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"type":"electronic","value":"2521-327X"}],"subject":[],"published":{"date-parts":[[2021,9,28]]},"article-number":"554"}}