Efficient Verification of Ground States of Frustration-Free Hamiltonians

Huangjun Zhu, Yunting Li, and Tianyi Chen

State Key Laboratory of Surface Physics and Department of Physics, Fudan University, Shanghai 200433, China
Institute for Nanoelectronic Devices and Quantum Computing, Fudan University, Shanghai 200433, China
Center for Field Theory and Particle Physics, Fudan University, Shanghai 200433, China

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


Ground states of local Hamiltonians are of key interest in many-body physics and also in quantum information processing. Efficient verification of these states are crucial to many applications, but very challenging. Here we propose a simple, but powerful recipe for verifying the ground states of general frustration-free Hamiltonians based on local measurements. Moreover, we derive rigorous bounds on the sample complexity by virtue of the quantum detectability lemma (with improvement) and quantum union bound. Notably, the number of samples required does not increase with the system size when the underlying Hamiltonian is local and gapped, which is the case of most interest. As an application, we propose a general approach for verifying Affleck-Kennedy-Lieb-Tasaki (AKLT) states on arbitrary graphs based on local spin measurements, which requires only a constant number of samples for AKLT states defined on various lattices. Our work is of interest not only to many tasks in quantum information processing, but also to the study of many-body physics.

We propose a general recipe for verifying the ground states of frustration-free Hamiltonians based on local measurements and determine the sample complexity. When the Hamiltonian is local and gapped, we can verify the ground state with a constant sample cost that is independent of the system size, which is tens of thousands of times more efficient than previous protocols for large and intermediate quantum systems. Notably, we can verify Affleck-Kennedy-Lieb-Tasaki (AKLT) states on arbitrary graphs, and the resource cost is independent of the system size for most AKLT states of practical interest, including those defined on various 1D and 2D lattices. Our work reveals an intimate connection between the quantum verification problem and many-body physics. The protocols we constructed are useful not only to addressing various tasks in quantum information processing, but also to studying many-body physics.

► BibTeX data

► References

[1] I. Affleck, T. Kennedy, E. H. Lieb, and H. Tasaki. ``Rigorous results on valence-bond ground states in antiferromagnets''. Phys. Rev. Lett. 59, 799–802 (1987).

[2] I. Affleck, T. Kennedy, E. H. Lieb, and H. Tasaki. ``Valence bond ground states in isotropic quantum antiferromagnets''. Commun. Math. Phys. 115, 477–528 (1988).

[3] D. Pérez-García, F. Verstraete, M. M. Wolf, and J. I. Cirac. ``PEPS as unique ground states of local Hamiltonians''. Quantum Info. Comput. 8, 650–663 (2008).

[4] J. I. Cirac, D. Pérez-García, N. Schuch, and F. Verstraete. ``Matrix product states and projected entangled pair states: Concepts, symmetries, theorems''. Rev. Mod. Phys. 93, 045003 (2021).

[5] X. Chen, Z.-C. Gu, Z.-X. Liu, and X.-G. Wen. ``Symmetry-protected topological orders in interacting Bosonic systems''. Science 338, 1604–1606 (2012).

[6] T. Senthil. ``Symmetry-protected topological phases of quantum matter''. Annu. Rev. Condens. Matter Phys. 6, 299–324 (2015).

[7] C.-K. Chiu, J. C. Y. Teo, A. P. Schnyder, and S. Ryu. ``Classification of topological quantum matter with symmetries''. Rev. Mod. Phys. 88, 035005 (2016).

[8] T.-C. Wei, R. Raussendorf, and I. Affleck. ``Some aspects of Affleck–Kennedy–Lieb–Tasaki models: Tensor network, physical properties, spectral gap, deformation, and quantum computation''. In Entanglement in Spin Chains, edited by A. Bayat, S. Bose, and H. Johannesson, pages 89–125. Springer. (2022).

[9] F. Verstraete, M. M. Wolf, and J. I. Cirac. ``Quantum computation and quantum-state engineering driven by dissipation''. Nat. Phys. 5, 633–636 (2009).

[10] E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser. ``Quantum computation by adiabatic evolution'' (2000). arXiv:quant-ph/​0001106.

[11] E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda. ``A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem''. Science 292, 472–475 (2001).

[12] T. Albash and D. A. Lidar. ``Adiabatic quantum computation''. Rev. Mod. Phys. 90, 015002 (2018).

[13] Y. Ge, A. Molnár, and J. I. Cirac. ``Rapid adiabatic preparation of injective projected entangled pair states and Gibbs states''. Phys. Rev. Lett. 116, 080503 (2016).

[14] E. Cruz, F. Baccari, J. Tura, N. Schuch, and J. I. Cirac. ``Preparation and verification of tensor network states''. Phys. Rev. Research 4, 023161 (2022).

[15] D. T. Stephen, D.-S. Wang, A. Prakash, T.-C. Wei, and R. Raussendorf. ``Computational power of symmetry-protected topological phases''. Phys. Rev. Lett. 119, 010504 (2017).

[16] 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).

[17] D. T. Stephen, H. P. Nautrup, J. Bermejo-Vega, J. Eisert, and R. Raussendorf. ``Subsystem symmetries, quantum cellular automata, and computational phases of quantum matter''. Quantum 3, 142 (2019).

[18] A. K. Daniel, R. N. Alexander, and A. Miyake. ``Computational universality of symmetry-protected topologically ordered cluster phases on 2D Archimedean lattices''. Quantum 4, 228 (2020).

[19] M. Goihl, N. Walk, J. Eisert, and N. Tarantino. ``Harnessing symmetry-protected topological order for quantum memories''. Phys. Rev. Research 2, 013120 (2020).

[20] D. Hangleiter and J. Eisert. ``Computational advantage of quantum random sampling''. Rev. Mod. Phys. 95, 035001 (2023).

[21] J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, and J. Eisert. ``Architectures for quantum simulation showing a quantum speedup''. Phys. Rev. X 8, 021010 (2018).

[22] R. Kaltenbaek, J. Lavoie, B. Zeng, S. D. Bartlett, and K. J. Resch. ``Optical one-way quantum computing with a simulated valence-bond solid''. Nat. Phys. 6, 850 (2010).

[23] T.-C. Wei, I. Affleck, and R. Raussendorf. ``Affleck-Kennedy-Lieb-Tasaki state on a honeycomb lattice is a universal quantum computational resource''. Phys. Rev. Lett. 106, 070501 (2011).

[24] A. Miyake. ``Quantum computational capability of a 2D valence bond solid phase''. Ann. Phys. 326, 1656–1671 (2011).

[25] T.-C. Wei, I. Affleck, and R. Raussendorf. ``Two-dimensional Affleck-Kennedy-Lieb-Tasaki state on the honeycomb lattice is a universal resource for quantum computation''. Phys. Rev. A 86, 032328 (2012).

[26] T.-C. Wei. ``Quantum spin models for measurement-based quantum computation''. Adv. Phys.: X 3, 1461026 (2018).

[27] J. Eisert, D. Hangleiter, N. Walk, I. Roth, D. Markham, R. Parekh, U. Chabaud, and E. Kashefi. ``Quantum certification and benchmarking''. Nat. Rev. Phys. 2, 382–390 (2020).

[28] J. Carrasco, A. Elben, C. Kokail, B. Kraus, and P. Zoller. ``Theoretical and experimental perspectives of quantum verification''. PRX Quantum 2, 010102 (2021).

[29] M. Kliesch and I. Roth. ``Theory of quantum system certification''. PRX Quantum 2, 010201 (2021).

[30] X.-D. Yu, J. Shang, and O. Gühne. ``Statistical methods for quantum state verification and fidelity estimation''. Adv. Quantum Technol. 5, 2100126 (2022).

[31] J. Morris, V. Saggio, A. Gočanin, and B. Dakić. ``Quantum verification and estimation with few copies''. Adv. Quantum Technol. 5, 2100118 (2022).

[32] M. Hayashi, K. Matsumoto, and Y. Tsuda. ``A study of LOCC-detection of a maximally entangled state using hypothesis testing''. J. Phys. A: Math. Gen. 39, 14427 (2006).

[33] M. Cramer, M. B. Plenio, S. T. Flammia, R. Somma, D. Gross, S. D. Bartlett, O. Landon-Cardinal, D. Poulin, and Y.-K. Liu. ``Efficient quantum state tomography''. Nat. Commun. 1, 149 (2010).

[34] L. Aolita, C. Gogolin, M. Kliesch, and J. Eisert. ``Reliable quantum certification of photonic state preparations''. Nat. Commun. 6, 8498 (2015).

[35] B. P. Lanyon, C. Maier, M. Holzäpfel, T. Baumgratz, C. Hempel, P. Jurcevic, I. Dhand, A. S. Buyskikh, A. J. Daley, M. Cramer, M. B. Plenio, R. Blatt, and C. F. Roos. ``Efficient tomography of a quantum many-body system''. Nat. Phys. 13, 1158–1162 (2017).

[36] D. Hangleiter, M. Kliesch, M. Schwarz, and J. Eisert. ``Direct certification of a class of quantum simulations''. Quantum Sci. Technol. 2, 015004 (2017).

[37] S. Pallister, N. Linden, and A. Montanaro. ``Optimal verification of entangled states with local measurements''. Phys. Rev. Lett. 120, 170502 (2018).

[38] Y. Takeuchi and T. Morimae. ``Verification of many-qubit states''. Phys. Rev. X 8, 021060 (2018).

[39] H. Zhu and M. Hayashi. ``Efficient verification of pure quantum states in the adversarial scenario''. Phys. Rev. Lett. 123, 260504 (2019).

[40] H. Zhu and M. Hayashi. ``General framework for verifying pure quantum states in the adversarial scenario''. Phys. Rev. A 100, 062335 (2019).

[41] Y.-D. Wu, G. Bai, G. Chiribella, and N. Liu. ``Efficient verification of continuous-variable quantum states and devices without assuming identical and independent operations''. Phys. Rev. Lett. 126, 240503 (2021).

[42] Y.-C. Liu, J. Shang, R. Han, and X. Zhang. ``Universally optimal verification of entangled states with nondemolition measurements''. Phys. Rev. Lett. 126, 090504 (2021).

[43] A. Gočanin, I. Šupić, and B. Dakić. ``Sample-efficient device-independent quantum state verification and certification''. PRX Quantum 3, 010317 (2022).

[44] M. Hayashi. ``Group theoretical study of LOCC-detection of maximally entangled states using hypothesis testing''. New J. Phys. 11, 043028 (2009).

[45] H. Zhu and M. Hayashi. ``Optimal verification and fidelity estimation of maximally entangled states''. Phys. Rev. A 99, 052346 (2019).

[46] Z. Li, Y.-G. Han, and H. Zhu. ``Efficient verification of bipartite pure states''. Phys. Rev. A 100, 032316 (2019).

[47] K. Wang and M. Hayashi. ``Optimal verification of two-qubit pure states''. Phys. Rev. A 100, 032315 (2019).

[48] X.-D. Yu, J. Shang, and O. Gühne. ``Optimal verification of general bipartite pure states''. npj Quantum Inf. 5, 112 (2019).

[49] M. Hayashi and T. Morimae. ``Verifiable measurement-only blind quantum computing with stabilizer testing''. Phys. Rev. Lett. 115, 220502 (2015).

[50] K. Fujii and M. Hayashi. ``Verifiable fault tolerance in measurement-based quantum computation''. Phys. Rev. A 96, 030301(R) (2017).

[51] M. Hayashi and M. Hajdušek. ``Self-guaranteed measurement-based quantum computation''. Phys. Rev. A 97, 052308 (2018).

[52] H. Zhu and M. Hayashi. ``Efficient verification of hypergraph states''. Phys. Rev. Appl. 12, 054047 (2019).

[53] Z. Li, Y.-G. Han, and H. Zhu. ``Optimal verification of Greenberger-Horne-Zeilinger states''. Phys. Rev. Appl. 13, 054002 (2020).

[54] D. Markham and A. Krause. ``A simple protocol for certifying graph states and applications in quantum networks''. Cryptography 4, 3 (2020).

[55] Z. Li, H. Zhu, and M. Hayashi. ``Robust and efficient verification of graph states in blind measurement-based quantum computation''. npj Quantum Inf. 9, 115 (2023).

[56] M. Hayashi and Y. Takeuchi. ``Verifying commuting quantum computations via fidelity estimation of weighted graph states''. New J. Phys. 21, 093060 (2019).

[57] Y.-C. Liu, X.-D. Yu, J. Shang, H. Zhu, and X. Zhang. ``Efficient verification of Dicke states''. Phys. Rev. Appl. 12, 044020 (2019).

[58] Z. Li, Y.-G. Han, H.-F. Sun, J. Shang, and H. Zhu. ``Verification of phased Dicke states''. Phys. Rev. A 103, 022601 (2021).

[59] W.-H. Zhang, C. Zhang, Z. Chen, X.-X. Peng, X.-Y. Xu, P. Yin, S. Yu, X.-J. Ye, Y.-J. Han, J.-S. Xu, G. Chen, C.-F. Li, and G.-C. Guo. ``Experimental optimal verification of entangled states using local measurements''. Phys. Rev. Lett. 125, 030506 (2020).

[60] W.-H. Zhang, X. Liu, P. Yin, X.-X. Peng, G.-C. Li, X.-Y. Xu, S. Yu, Z.-B. Hou, Y.-J. Han, J.-S. Xu, Z.-Q. Zhou, G. Chen, C.-F. Li, and G.-C. Guo. ``Classical communication enhanced quantum state verification''. npj Quantum Inf. 6, 103 (2020).

[61] L. Lu, L. Xia, Z. Chen, L. Chen, T. Yu, T. Tao, W. Ma, Y. Pan, X. Cai, Y. Lu, S. Zhu, and X.-S. Ma. ``Three-dimensional entanglement on a silicon chip''. npj Quantum Inf. 6, 30 (2020).

[62] X. Jiang, K. Wang, K. Qian, Z. Chen, Z. Chen, L. Lu, L. Xia, F. Song, S. Zhu, and X. Ma. ``Towards the standardization of quantum state verification using optimal strategies''. npj Quantum Inf. 6, 90 (2020).

[63] M. Gluza, M. Kliesch, J. Eisert, and L. Aolita. ``Fidelity witnesses for fermionic quantum simulations''. Phys. Rev. Lett. 120, 190501 (2018).

[64] T. Chen, Y. Li, and H. Zhu. ``Efficient verification of Affleck-Kennedy-Lieb-Tasaki states''. Phys. Rev. A 107, 022616 (2023).

[65] D. Aharonov, I. Arad, Z. Landau, and U. Vazirani. ``The detectability lemma and quantum gap amplification''. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing. Page 417–426. STOC'09, New York, NY, USA (2009).

[66] A. Anshu, I. Arad, and T. Vidick. ``Simple proof of the detectability lemma and spectral gap amplification''. Phys. Rev. B 93, 205142 (2016).

[67] J. Gao. ``Quantum union bounds for sequential projective measurements''. Phys. Rev. A 92, 052331 (2015).

[68] R. O'Donnell and R. Venkateswaran. ``The quantum union bound made easy''. In Symposium on Simplicity in Algorithms (SOSA). Pages 314–320. SIAM (2022).

[69] P. Delsarte, J. M. Goethals, and J. J. Seidel. ``Spherical codes and designs''. Geom. Dedicata 6, 363–388 (1977).

[70] J. J. Seidel. ``Definitions for spherical designs''. J. Stat. Plan. Inference 95, 307 (2001).

[71] E. Bannai and E. Bannai. ``A survey on spherical designs and algebraic combinatorics on spheres''. Eur. J. Combinator. 30, 1392–1425 (2009).

[72] W.-M. Zhang, D. H. Feng, and R. Gilmore. ``Coherent states: Theory and some applications''. Rev. Mod. Phys. 62, 867–927 (1990).

[73] V. I. Voloshin. ``Introduction to graph and hypergraph theory''. Nova Science Publishers Inc. New York (2009). URL: https:/​/​lccn.loc.gov/​2008047206.

[74] V. G. Vizing. ``On an estimate of the chromatic class of a p-graph (Russian)''. Diskret. Analiz 3, 25–30 (1964). URL: https:/​/​mathscinet.ams.org/​mathscinet/​relay-station?mr=0180505.

[75] J. Misra and D. Gries. ``A constructive proof of Vizing's theorem''. Inf. Process. Lett. 41, 131–133 (1992).

[76] A. N. Kirillov and V. E. Korepin. ``The valence bond solid in quasicrystals'' (2009). arXiv:0909.2211.

[77] V. E. Korepin and Y. Xu. ``Entanglement in valence-bond-solid states''. I. J. Mod. Phys. B 24, 1361–1440 (2010).

[78] A. Bondarenko, D. Radchenko, and M. Viazovska. ``Optimal asymptotic bounds for spherical designs''. Ann. Math. 178, 443 (2013).

[79] R. S. Womersley. ``Efficient spherical designs with good geometric properties'' (2017). arXiv:1709.01624.

[80] H. Zhu, R. Kueng, M. Grassl, and D. Gross. ``The Clifford group fails gracefully to be a unitary 4-design'' (2016). arXiv:1609.08172.

[81] D. Hughes and S. Waldron. ``Spherical half-designs of high order''. Involve 13, 193 (2020).

[82] A. Garcia-Saez, V. Murg, and T.-C. Wei. ``Spectral gaps of Affleck-Kennedy-Lieb-Tasaki Hamiltonians using tensor network methods''. Phys. Rev. B 88, 245118 (2013).

[83] H. Abdul-Rahman, M. Lemm, A. Lucia, B. Nachtergaele, and A. Young. ``A class of two-dimensional AKLT models with a gap''. In Analytic Trends in Mathematical Physics, edited by H. Abdul-Rahman, R. Sims, and A. Young, volume 741 of Contemporary Mathematics, pages 1–21. American Mathematical Society. (2020).

[84] N. Pomata and T.-C. Wei. ``AKLT models on decorated square lattices are gapped''. Phys. Rev. B 100, 094429 (2019).

[85] N. Pomata and T.-C. Wei. ``Demonstrating the Affleck-Kennedy-Lieb-Tasaki Spectral Gap on 2D Degree-3 Lattices''. Phys. Rev. Lett. 124, 177203 (2020).

[86] M. Lemm, A. W. Sandvik, and L. Wang. ``Existence of a spectral gap in the Affleck-Kennedy-Lieb-Tasaki model on the hexagonal lattice''. Phys. Rev. Lett. 124, 177204 (2020).

[87] W. Guo, N. Pomata, and T.-C. Wei. ``Nonzero spectral gap in several uniformly spin-2 and hybrid spin-1 and spin-2 AKLT models''. Phys. Rev. Research 3, 013255 (2021).

Cited by

[1] Tianyi Chen, Yunting Li, and Huangjun Zhu, "Efficient verification of Affleck-Kennedy-Lieb-Tasaki states", Physical Review A 107 2, 022616 (2023).

[2] Siyuan Chen, Wei Xie, and Kun Wang, "Memory Effects in Quantum State Verification", arXiv:2312.11066, (2023).

[3] Zihao Li, Huangjun Zhu, and Masahito Hayashi, "Robust and efficient verification of graph states in blind measurement-based quantum computation", npj Quantum Information 9, 115 (2023).

[4] Ye-Chao Liu, Yinfei Li, Jiangwei Shang, and Xiangdong Zhang, "Efficient verification of arbitrary entangled states with homogeneous local measurements", arXiv:2208.01083, (2022).

[5] Joris Kattemölle, "Edge coloring lattice graphs", arXiv:2402.08752, (2024).

The above citations are from SAO/NASA ADS (last updated successfully 2024-02-27 15:08:22). 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 15:08:20).