Symmetry Protected Quantum Computation

Michael H. Freedman1,2, Matthew B. Hastings1,2, and Modjtaba Shokrian Zini3,4

1Station Q, Microsoft Research, Santa Barbara, CA 93106-6105, USA
2Microsoft Quantum, Redmond, WA 98052, USA
3Perimeter Institute for Theoretical Physics, Waterloo, ON N2L 2Y5, Canada
4Research Consultant, Microsoft

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


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 $0$) or triplet (total spin $1$) 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 $SU(2)$-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 $X$ and $Z$ 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.

► BibTeX data

► References

[1] MathOverflow discussion.

[2] Mathematics Stack Exchange discussion.

[3] 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–510, 2019. 10.1038/​s41586-019-1666-5.

[4] 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.

[5] Toby Cubitt and Ashley Montanaro. Complexity classification of local hamiltonian problems. SIAM Journal on Computing, 45 (2): 268–316, 2016. 10.1137/​140998287.

[6] Toby S. Cubitt, Ashley Montanaro, and Stephen Piddock. Universal quantum hamiltonians. Proceedings of the National Academy of Sciences, 115 (38): 9497–9502, 2018. 10.1073/​pnas.1804949115.

[7] D. P. DiVincenzo, D. Bacon, J. Kempe, G. Burkard, and K. B. Whaley. Universal quantum computation with the exchange interaction. Nature, 408 (6810): 339–342, nov 2000. 10.1038/​35042541.

[8] Matthew PA Fisher. Quantum cognition: The possibility of processing with nuclear spins in the brain. Annals of Physics, 362: 593–602, 2015. 10.1016/​j.aop.2015.08.020.

[9] Michael Freedman, Modjtaba Shokrian-Zini, and Zhenghan Wang. Quantum computing with octonions. Peking Mathematical Journal, 2 (3): 239–273, 2019. 10.1007/​s42543-019-00020-3.

[10] Daniel Gottesman. An introduction to quantum error correction and fault-tolerant quantum computation. pages 13–58, 2010. 10.1090/​psapm/​068/​2762145.

[11] Aram W Harrow and Ashley Montanaro. Quantum computational supremacy. Nature, 549 (7671): 203–209, 2017. https:/​/​​10.1038/​nature23458.

[12] Vojtěch Havlíček and Sergii Strelchuk. Quantum schur sampling circuits can be strongly simulated. Physical Review Letters, 121 (6), 2018. 10.1103/​physrevlett.121.060505.

[13] 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.

[14] Stephen P Jordan. Permutational quantum computing. Quantum Information & Computation, 10 (5): 470–497, 2010. DOI: 10.5555/​2011362.2011369.

[15] 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.

[16] Aleksei Yur'evich Kitaev. Quantum computations: algorithms and error correction. Uspekhi Matematicheskikh Nauk, 52 (6): 53–112, 1997. 10.1070/​rm1997v052n06abeh002155.

[17] A.Yu. Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics, 303 (1): 2–30, 2003. 10.1016/​s0003-4916(02)00018-0.

[18] Annalisa Marzuoli and Mario Rasetti. Computing spin networks. Annals of Physics, 318 (2): 345–407, 2005. 10.1016/​j.aop.2005.01.005.

[19] 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.

[20] 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.

[21] 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–228, oct 2005. 10.1088/​1367-2630/​7/​1/​228.

[22] Terry Rudolph and Shashank Soyuz Virmani. Relational quantum computing using only maximally mixed initial qubit states. arXiv preprint arXiv:2107.03239, 2021.

[23] 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.

Cited by

[1] Constantin Schrade, Charles M. Marcus, and András Gyenis, "Protected Hybrid Superconducting Qubit in an Array of Gate-Tunable Josephson Interferometers", PRX Quantum 3 3, 030303 (2022).

[2] Josiah Couch, Yale Fan, and Sanjit Shashi, "Circuit Complexity in Topological Quantum Field Theory", arXiv:2108.13427, Fortschritte der Physik 70 9-10, 2200102 (2022).

[3] Terry Rudolph and Shashank Soyuz Virmani, "Relational quantum computing using only maximally mixed initial qubit states", arXiv:2107.03239.

[4] Matthew Brooks and Charles Tahan, "Hybrid Exchange-Measurement-Based Qubit Operations in Semiconductor Double-Quantum-Dot Qubits", Physical Review Applied 16 6, 064019 (2021).

The above citations are from Crossref's cited-by service (last updated successfully 2022-11-30 10:33:38) and SAO/NASA ADS (last updated successfully 2022-11-30 10:33:39). The list may be incomplete as not all publishers provide suitable and complete citation data.