Measurement-based quantum computation in finite one-dimensional systems: string order implies computational power

Robert Raussendorf1,2, Wang Yang3, and Arnab Adhikary4,2

1Leibniz University Hannover, Hannover, Germany
2Stewart Blusson Quantum Matter Institute, University of British Columbia, Vancouver, Canada
3School of Physics, Nankai University, Tianjin, China
4Department of Physics and Astronomy, University of British Columbia, Vancouver, Canada

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


We present a new framework for assessing the power of measurement-based quantum computation (MBQC) on short-range entangled symmetric resource states, in spatial dimension one. It requires fewer assumptions than previously known. The formalism can handle finitely extended systems (as opposed to the thermodynamic limit), and does not require translation-invariance. Further, we strengthen the connection between MBQC computational power and string order. Namely, we establish that whenever a suitable set of string order parameters is non-zero, a corresponding set of unitary gates can be realized with fidelity arbitrarily close to unity.

Computational phases of quantum matter are symmetry-protected phases with uniform computational power for measurement-based quantum computation. Being phases, they are defined for infinite systems only. But then, how is the computational power affected when transitioning from infinite to finite systems? A practical motivation for this question is that quantum computation is about efficiency, hence resource counting. In this paper, we develop a formalism that can handle finite one-dimensional spin systems, and strengthen the relation between string order and computational power.

► BibTeX data

► References

[1] R. Raussendorf and H.-J. Briegel, A one-way quantum computer, Phys. Rev. Lett. 86, 5188 (2001). doi: 10.1103/​PhysRevLett.86.5188.

[2] D. Gross, S. T. Flammia, and J. Eisert, Most Quantum States Are Too Entangled To Be Useful As Computational Resources, Phys. Rev. Lett. 102, 190501 (2009). doi: 10.1103/​PhysRevLett.102.190501.

[3] A. C. Doherty and S. D. Bartlett, Identifying Phases of Quantum Many-Body Systems That Are Universal for Quantum Computation, Phys. Rev. Lett. 103, 020506 (2009). doi: 10.1103/​PhysRevLett.103.020506.

[4] T. Chung, S. D. Bartlett and A. C. Doherty, Characterizing measurement-based quantum gates in quantum many-body systems using correlation functions, Can. J. Phys. 87, 219 (2009). doi: 10.1139/​P08-112.

[5] A. Miyake, Quantum computation on the edge of a symmetry-protected topological order, Phys. Rev. Lett. 105, 040501 (2010). doi: 10.1103/​PhysRevLett.105.040501.

[6] A.S. Darmawan, G.K. Brennen, S.D. Bartlett, Measurement-based quantum computation in a two-dimensional phase of matter, New J. Phys. 14, 013023 (2012). doi: 10.1088/​1367-2630/​14/​1/​013023.

[7] D.V. Else, I. Schwarz, S.D. Bartlett and A.C. Doherty, Symmetry-protected phases for measurement-based quantum computation, Phys. Rev. Lett. 108, 240505 (2012). doi: 10.1103/​PhysRevLett.108.240505.

[8] D.V. Else, S.D. Bartlett, and A.C. Doherty, Symmetry protection of measurement-based quantum computation in ground states, New J. Phys. 14, 113016 (2012). doi: 10.1088/​1367-2630/​14/​11/​113016.

[9] Z.C. Gu and X.G. Wen, Tensor-entanglement-filtering renormalization approach and symmetry-protected topological order, Phys. Rev. B 80, 155131 (2009). doi: 10.1103/​PhysRevB.80.155131.

[10] X. Chen, Z.C. Gu, and X.G. Wen, Local unitary transformation, long-range quantum entanglement, wave function renormalization, and topological order, Phys. Rev. B 82, 155138 (2010). doi: 10.1103/​PhysRevB.82.155138.

[11] Norbert Schuch, David Perez-Garcia, and Ignacio Cirac, Classifying quantum phases using matrix product states and projected entangled pair states, Phys. Rev. B 84, 165139 (2011). doi: 10.1103/​PhysRevB.84.165139.

[12] Yoshiko Ogata, Classification of symmetry protected topological phases in quantum spin chains, arXiv:2110.04671. doi: 10.48550/​arXiv.2110.04671.

[13] X. Chen, Z.C. Gu, Z.X. Liu, X.G. Wen, Symmetry protected topological orders and the group cohomology of their symmetry group, Phys. Rev. B 87, 155114 (2013). doi: 10.1103/​PhysRevB.87.155114.

[14] R. Raussendorf, J. Harrington, K. Goyal, A fault-tolerant one-way quantum computer, Ann. Phys. (N.Y.) 321, 2242 (2006). doi: 10.1016/​j.aop.2006.01.012.

[15] J. Miller and A. Miyake, Resource Quality of a Symmetry-Protected Topologically Ordered Phase for Quantum Computation, Phys. Rev. Lett. 114, 120506 (2015). doi: 10.1103/​PhysRevLett.114.120506.

[16] Robert Raussendorf, Dongsheng Wang, Abhishodh Prakash, Tzu-Chieh Wei, David Stephen, Symmetry-protected topological phases with uniform computational power in one dimension, Phys. Rev. A 96, 012302 (2017). doi: 10.1103/​PhysRevA.96.012302.

[17] D.T. Stephen, D.-S. Wang, A. Prakash, T.-C. Wei, R. Raussendorf, Computational Power of Symmetry-Protected Topological Phases, Phys. Rev. Lett. 119, 010504 (2017). doi: 10.1103/​PhysRevLett.119.010504.

[18] D.T. Stephen, Computational power of one-dimensional symmetry-protected topological phases, MSc Thesis, University of British Columbia (2017). doi: 10.14288/​1.0354465.

[19] R. Raussendorf, C. Okay, D.-S. Wang, D. T. Stephen, and H. P. Nautrup, Computationally universal phase of quantum matter, Phys. Rev. Lett. 122, 090501 (2019). doi: 10.1103/​PhysRevLett.122.090501.

[20] T. Devakul and D.J. Williamson, Universal quantum computation using fractal symmetry-protected cluster phases, Phys. Rev. A 98, 022332 (2018). doi: 10.1103/​PhysRevA.98.022332.

[21] David T. Stephen, Hendrik Poulsen Nautrup, Juani Bermejo-Vega, Jens Eisert, Robert Raussendorf, Subsystem symmetries, quantum cellular automata, and computational phases of quantum matter, Quantum 3, 142 (2019). doi: 10.22331/​q-2019-05-20-142.

[22] Austin K. Daniel, Rafael N. Alexander, Akimasa Miyake, Computational universality of symmetry-protected topologically ordered cluster phases on 2D Archimedean lattices, Quantum 4, 228 (2020). doi: 10.22331/​q-2020-02-10-228.

[23] A. Miyake, Quantum computational capability of a 2D valence bond solid phase, Ann. Phys. 326, 1656-1671 (2011). doi: 10.1016/​j.aop.2011.03.006.

[24] Tzu-Chieh Wei, Ian Affleck, Robert Raussendorf, The Affleck-Kennedy-Lieb-Tasaki State on a Honeycomb Lattice is a Universal Quantum Computational Resource, Phys. Rev. Lett. 106, 070501 (2011). doi: 10.1103/​PhysRevLett.106.070501.

[25] Sam Roberts and Stephen D. Bartlett, Symmetry-Protected Self-Correcting Quantum Memories, Phys. Rev. X 10, 031041 (2020). doi: 10.1103/​PhysRevX.10.031041.

[26] D. Gross and J. Eisert, Novel Schemes for Measurement-Based Quantum Computation, Phys. Rev. Lett. 98, 220503 (2007). doi: 10.1103/​PhysRevLett.98.220503.

[27] Gabriel Wong, Robert Raussendorf, Bartlomiej Czech The Gauge Theory of Measurement-Based Quantum Computation, arXiv:2207.10098. doi: 10.48550/​arXiv.2207.10098.

[28] M. den Nijs and K. Rommelse, Preroughening transitions in crystal surfaces and valence-bond phases in quantum spin chains, Phys. Rev. B 40, 4709 (1989). doi: 10.1103/​PhysRevB.40.4709.

[29] H. Tasaki, Quantum liquid in antiferromagnetic chains: A stochastic geometric approach to the Haldane gap, Phys. Rev. Lett. 66, 798 (1991). doi: 10.1103/​PhysRevLett.66.798.

[30] D. Perez-Garcia, M.M. Wolf, M. Sanz, F. Verstraete, and J.I. Cirac, String Order and Symmetries in Quantum Spin Lattices, Phys. Rev. Lett. 100, 167202 (2008). doi: 10.1103/​PhysRevLett.100.167202.

[31] A. Molnar, J. Garre-Rubio, D. Perez-Garcia, N. Schuch, J.I. Cirac, Normal projected entangled pair states generating the same state, New J. Phys. 20, 113017 (2018). doi: 10.1088/​1367-2630/​aae9fa.

[32] J.I. Cirac, D. Perez-Garcia, N. Schuch, and F. Verstraete, Matrix product states and projected entangled pair states: Concepts, symmetries, theorems, Rev. Mod. Phys. 93, 045003 (2021). doi: 10.1103/​RevModPhys.93.045003.

[33] M.B. Hastings, Lieb-Schultz-Mattis in higher dimensions, Phys. Rev. B 69, 104431 (2004). doi: 10.1103/​PhysRevB.69.104431.

[34] Bei Zeng, Xie Chen, Duan-Lu Zhou, Xiao-Gang Wen, Quantum Information Meets Quantum Matter – From Quantum Entanglement to Topological Phase in Many-Body Systems, Springer (2019). doi: 10.48550/​arXiv.1508.02595.

[35] C. E. Agrapidis, J. van den Brink, and S. Nishimoto, Ordered states in the Kitaev-Heisenberg model: From 1D chains to 2D honeycomb, Sci. Rep. 8, 1815 (2018). doi: 10.1038/​s41598-018-19960-4.

[36] W. Yang, A. Nocera, T. Tummuru, H.-Y. Kee, and I. Affleck, Phase Diagram of the Spin-1/​2 Kitaev-Gamma Chain and Emergent SU(2) Symmetry, Phys. Rev. Lett. 124, 147205 (2020). doi: 10.1103/​PhysRevLett.124.147205.

[37] W. Yang, A. Nocera, and I. Affleck, Comprehensive study of the phase diagram of the spin-1/​2 Kitaev-Heisenberg-Gamma chain, Phys. Rev. Research 2, 033268 (2020). doi: 10.1103/​PhysRevResearch.2.033268.

[38] Q. Luo, J. Zhao, X. Wang, and H.-Y. Kee, Unveiling the phase diagram of a bond-alternating spin-$\frac{1}{2}$ $K$-$\Gamma$ chain, Phys. Rev. B 103, 144423 (2021). doi: 10.1103/​PhysRevB.103.144423.

[39] W. Yang, A. Nocera, P. Herringer, R. Raussendorf, I. Affleck, Symmetry analysis of bond-alternating Kitaev spin chains and ladders, Phys. Rev. B 105, 094432 (2022). doi: 10.1103/​PhysRevB.105.094432.

[40] W. Yang, A. Nocera, C. Xu, H.-Y. Kee, I. Affleck, Counter-rotating spiral, zigzag, and 120$^\circ$ orders from coupled-chain analysis of Kitaev-Gamma-Heisenberg model, and relations to honeycomb iridates, arXiv:2207.02188. doi: 10.48550/​arXiv.2207.02188.

[41] A. Kitaev, Anyons in an exactly solved model and beyond, Ann. Phys. (N. Y). 321, 2 (2006). doi: 10.1016/​j.aop.2005.10.005.

[42] C. Nayak, S. H. Simon, A. Stern, M. Freedman, and S. Das Sarma, Non-Abelian anyons and topological quantum computation, Rev. Mod. Phys. 80, 1083 (2008). doi: 10.1103/​RevModPhys.80.1083.

[43] G. Jackeli and G. Khaliullin, Mott Insulators in the Strong Spin-Orbit Coupling Limit: From Heisenberg to a Quantum Compass and Kitaev Models, Phys. Rev. Lett. 102, 017205 (2009). doi: 10.1103/​PhysRevLett.102.017205.

[44] J. G. Rau, E. K. H. Lee, and H. Y. Kee, Generic spin model for the honeycomb iridates beyond the Kitaev limit, Phys. Rev. Lett. 112, 077204 (2014). doi: 10.1103/​PhysRevLett.112.077204.

[45] J. G. Rau, E. K.-H. Lee, and H.-Y. Kee, Spin-Orbit Physics Giving Rise to Novel Phases in Correlated Systems: Iridates and Related Materials, Annu. Rev. Condens. Matter Phys. 7, 195 (2016). doi: 10.1146/​annurev-conmatphys-031115-011319.

[46] S. M. Winter, A. A. Tsirlin, M. Daghofer, J. van den Brink, Y. Singh, P. Gegenwart, and R. Valentí, Models and materials for generalized Kitaev magnetism, J. Phys. Condens. Matter 29, 493002 (2017). doi: 10.1088/​1361-648X/​aa8cf5.

[47] M. Hermanns, I. Kimchi, and J. Knolle, Physics of the Kitaev Model: Fractionalization, Dynamic Correlations, and Material Connections, Annu. Rev. Condens. Matter Phys. 9, 17 (2018). doi: 10.1146/​annurev-conmatphys-033117-053934.

[48] F. D. M. Haldane, Nonlinear field theory of large-spin Heisenberg antiferromagnets: semiclassically quantized solitons of the one-dimensional easy-axis Néel state, Phys. Rev. Lett. 50, 1153 (1983). doi: 10.1103/​PhysRevLett.50.1153.

[49] I. Affleck, T. Kennedy, E. H. Lieb, and H. Tasaki, Rigorous results on valence-bond ground states in antiferromagnets, Phys. Rev. Lett. 59, 799 (1987). doi: 10.1103/​PhysRevLett.59.799.

[50] X. Chen, Z.-C. Gu, and X.-G. Wen, Classification of gapped symmetric phases in one-dimensional spin systems, Phys. Rev. B 83, 035107 (2011). doi: 10.1103/​PhysRevB.83.035107.

[51] David T. Stephen, Wen Wei Ho, Tzu-Chieh Wei, Robert Raussendorf, Ruben Verresen, Universal measurement-based quantum computation in a one-dimensional architecture enabled by dual-unitary circuits, arXiv:2209.06191. doi: 10.48550/​arXiv.2209.06191.

[52] R. Raussendorf and H.J. Briegel, Computational model underlying the one-way quantum computer, Quant. Inf. Comp. 6, 443 (2002). doi: 10.48550/​arXiv.quant-ph/​0108067.

[53] D. Aharonov, A. Kitaev, N. Nisan, Quantum circuits with mixed states, Proc. of the 30th Annual ACM Symposium on Theory of Computing, and quant-ph/​9806029 (1998). doi: 10.48550/​arXiv.quant-ph/​9806029.

[54] Austin K. Daniel and Akimasa Miyake, Quantum Computational Advantage with String Order Parameters of One-Dimensional Symmetry-Protected Topological Order, Phys. Rev. Lett. 126, 090505 (2021). doi: 10.1103/​PhysRevLett.126.090505.

[55] G. Brassard, A. Broadbent, and A. Tapp, Quantum Pseudo-Telepathy, Foundations of Physics 35, 1877 (2005). doi: 10.1007/​s10701-005-7353-4.

[56] S. Kochen and E. P. Specker, The Problem of Hidden Variables in Quantum Mechanics, J. Math. Mech. 17, 59 (1967). http:/​/​​stable/​24902153.

[57] Janet Anders, Dan E. Browne, Computational power of correlations, Phys. Rev. Lett. 102, 050502 (2009). doi: 10.1103/​PhysRevLett.102.050502.

[58] N. David Mermin, Hidden variables and the two theorems of John Bell, Rev. Mod. Phys. 65, 803 (1993). doi: 10.1103/​RevModPhys.65.803.

[59] Abhishodh Prakash, Tzu-Chieh Wei, Ground states of 1D symmetry-protected topological phases and their utility as resource states for quantum computation, Phys. Rev. A 92, 022310 (2015). doi: 10.1103/​PhysRevA.92.022310.

[60] Robert Raussendorf, Contextuality in measurement-based quantum computation, Phys. Rev. A 88, 022322 (2013). doi: 10.1103/​PhysRevA.88.022322.

[61] Matthew Fishman, Steven R. White, E. Miles Stoudenmire, The ITensor Software Library for Tensor Network Calculations, SciPost Phys. Codebases 4 (2022). doi: 10.21468/​SciPostPhysCodeb.4.

[62] Arnab Adhikary, https:/​/​​Quantumarnab/​SPT_Phases.

Cited by

[1] Daniel Azses, Jonathan Ruhman, and Eran Sela, "Nonunitary gates using measurements only", arXiv:2312.17325, (2023).

[2] Hiroki Sukeno and Takuya Okuda, "Measurement-based quantum simulation of Abelian lattice gauge theories", SciPost Physics 14 5, 129 (2023).

[3] Yifan Hong, David T. Stephen, and Aaron J. Friedman, "Quantum teleportation implies symmetry-protected topological order", arXiv:2310.12227, (2023).

[4] Chukwudubem Umeano, Annie E. Paine, Vincent E. Elfving, and Oleksandr Kyriienko, "What can we learn from quantum convolutional neural networks?", arXiv:2308.16664, (2023).

[5] Dawid Paszko, Dominic C. Rose, Marzena H. Szymańska, and Arijeet Pal, "Edge modes and symmetry-protected topological states in open quantum systems", arXiv:2310.09406, (2023).

[6] Zhangjie Qin, Daniel Azses, Eran Sela, Robert Raussendorf, and V. W. Scarola, "Redundant String Symmetry-Based Error Correction: Experiments on Quantum Devices", arXiv:2310.12854, (2023).

[7] James Lambert and Erik S. Sørensen, "State space geometry of the spin-1 antiferromagnetic Heisenberg chain", Physical Review B 107 17, 174427 (2023).

[8] Hiroki Sukeno and Takuya Okuda, "Measurement-based quantum simulation of Abelian lattice gauge theories", arXiv:2401.10259, (2023).

[9] Arnab Adhikary, Wang Yang, and Robert Raussendorf, "Counter-intuitive yet efficient regimes for measurement based quantum computation on symmetry protected spin chains", arXiv:2307.08903, (2023).

The above citations are from SAO/NASA ADS (last updated successfully 2024-02-27 10:36:36). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2024-02-27 10:36:35).