Nearly-frustration-free ground state preparation

Matthew Thibodeau and Bryan K. Clark

Department of Physics, University of Illinois at Urbana-Champaign, IL 61801, USA
IQUIST and Institute for Condensed Matter Theory and NCSA Center for Artificial Intelligence Innovation, University of Illinois at Urbana-Champaign, IL 61801, USA

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

Abstract

Solving for quantum ground states is important for understanding the properties of quantum many-body systems, and quantum computers are potentially well-suited for solving for quantum ground states. Recent work [1] has presented a nearly optimal scheme that prepares ground states on a quantum computer for completely generic Hamiltonians, whose query complexity scales as $\delta^{-1}$, i.e. inversely with their normalized gap. Here we consider instead the ground state preparation problem restricted to a special subset of Hamiltonians, which includes those which we term "nearly-frustration-free": the class of Hamiltonians for which the ground state energy of their block-encoded and hence normalized Hamiltonian $\alpha^{-1}H$ is within $\delta^y$ of -1, where $\delta$ is the spectral gap of $\alpha^{-1}H$ and $0 \leq y \leq 1$. For this subclass, we describe an algorithm whose dependence on the gap is asymptotically better, scaling as $\delta^{y/2-1}$, and show that this new dependence is optimal up to factors of $\log \delta$. In addition, we give examples of physically motivated Hamiltonians which live in this subclass. Finally, we describe an extension of this method which allows the preparation of excited states both for generic Hamiltonians as well as, at a similar speedup as the ground state case, for those which are nearly frustration-free.

► BibTeX data

► References

[1] Lin Lin and Yu Tong. Near-optimal ground state preparation. Quantum, 4: 1–22, 2020a. 10.22331/​Q-2020-12-14-372.
https:/​/​doi.org/​10.22331/​Q-2020-12-14-372

[2] A. Yu. Kitaev. Quantum measurements and the Abelian Stabilizer Problem. pages 1–22, 1995. 10.48550/​arXiv.quant-ph/​9511026.
https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​9511026
arXiv:quant-ph/9511026

[3] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Quantum Computation and Information, page 53–74, 2002. 10.48550/​arXiv.quant-ph/​0005055.
https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​0005055
arXiv:quant-ph/0005055

[4] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics. Proceedings of the Annual ACM Symposium on Theory of Computing, pages 193–204, 2019. 10.1145/​3313276.3316366.
https:/​/​doi.org/​10.1145/​3313276.3316366

[5] Yimin Ge, Jordi Tura, and J. Ignacio Cirac. Faster ground state preparation and high-precision ground energy estimation with fewer qubits. Journal of Mathematical Physics, 60 (2): 1–25, 2019. 10.1063/​1.5027484.
https:/​/​doi.org/​10.1063/​1.5027484

[6] Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC '96, page 212–219, New York, NY, USA, 1996. Association for Computing Machinery. 10.1145/​237814.237866.
https:/​/​doi.org/​10.1145/​237814.237866

[7] Guang Hao Low and Isaac L. Chuang. Hamiltonian Simulation by Qubitization. Quantum, 3: 163, 2019. 10.22331/​q-2019-07-12-163.
https:/​/​doi.org/​10.22331/​q-2019-07-12-163

[8] Sergey Bravyi, David P. Divincenzo, Roberto Oliveira, and Barbara M. Terhal. The complexity of stoquastic local Hamiltonian problems. Quantum Information and Computation, 8 (5): 0361–0385, 2008. 10.26421/​qic8.5-1.
https:/​/​doi.org/​10.26421/​qic8.5-1

[9] R. D. Somma and S. Boixo. Spectral gap amplification. SIAM Journal on Computing, 42 (2): 593–610, 2013. 10.1137/​120871997.
https:/​/​doi.org/​10.1137/​120871997

[10] Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by uniform spectral amplification. arXiv, pages 1–32, 2017a. 10.48550/​arXiv.1707.05391.
https:/​/​doi.org/​10.48550/​arXiv.1707.05391

[11] Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. The power of block-encoded matrix powers: Improved regression techniques via faster Hamiltonian simulation. In Leibniz International Proceedings in Informatics, LIPIcs, volume 132, pages 1–58, 2019. 10.4230/​LIPIcs.ICALP.2019.33.
https:/​/​doi.org/​10.4230/​LIPIcs.ICALP.2019.33

[12] Jeongwan Haah. Product decomposition of periodic functions in quantum signal processing. Quantum, 3 (September): 1–22, 2019. 10.22331/​q-2019-10-07-190.
https:/​/​doi.org/​10.22331/​q-2019-10-07-190

[13] Guang Hao Low and Isaac L. Chuang. Optimal Hamiltonian Simulation by Quantum Signal Processing. Physical Review Letters, 118 (1): 1–6, 2017b. 10.1103/​PhysRevLett.118.010501.
https:/​/​doi.org/​10.1103/​PhysRevLett.118.010501

[14] Yulong Dong, Xiang Meng, K. Birgitta Whaley, and Lin Lin. Efficient phase-factor evaluation in quantum signal processing. Physical Review A, 103 (4): 1–26, 2021. 10.1103/​PhysRevA.103.042419.
https:/​/​doi.org/​10.1103/​PhysRevA.103.042419

[15] Lin Lin and Yu Tong. Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems. Quantum, 4: 1–35, 2020b. 10.22331/​Q-2020-11-11-361.
https:/​/​doi.org/​10.22331/​Q-2020-11-11-361

[16] Antoine Georges, Gabriel Kotliar, Werner Krauth, and Marcelo J. Rozenberg. Dynamical mean-field theory of strongly correlated fermion systems and the limit of infinite dimensions. Rev. Mod. Phys., 68: 13–125, Jan 1996. 10.1103/​RevModPhys.68.13.
https:/​/​doi.org/​10.1103/​RevModPhys.68.13

[17] Iztok Pižorn and Frank Verstraete. Variational numerical renormalization group: Bridging the gap between NRG and density matrix renormalization group. Physical Review Letters, 108 (6): 1–8, 2012. 10.1103/​PhysRevLett.108.067202.
https:/​/​doi.org/​10.1103/​PhysRevLett.108.067202

[18] Frances Hellman, Axel Hoffmann, Yaroslav Tserkovnyak, Geoffrey S. D. Beach, Eric E. Fullerton, Chris Leighton, Allan H. MacDonald, Daniel C. Ralph, Dario A. Arena, Hermann A. Dürr, Peter Fischer, Julie Grollier, Joseph P. Heremans, Tomas Jungwirth, Alexey V. Kimel, Bert Koopmans, Ilya N. Krivorotov, Steven J. May, Amanda K. Petford-Long, James M. Rondinelli, Nitin Samarth, Ivan K. Schuller, Andrei N. Slavin, Mark D. Stiles, Oleg Tchernyshyov, André Thiaville, and Barry L. Zink. Interface-induced phenomena in magnetism. Rev. Mod. Phys., 89: 025006, Jun 2017. 10.1103/​RevModPhys.89.025006.
https:/​/​doi.org/​10.1103/​RevModPhys.89.025006

[19] E. M. Stoudenmire and Steven R. White. Studying two-dimensional systems with the density matrix renormalization group. Annual Review of Condensed Matter Physics, 3 (1): 111–128, 2012. 10.1146/​annurev-conmatphys-020911-125018.
https:/​/​doi.org/​10.1146/​annurev-conmatphys-020911-125018

[20] Fakher F. Assaad and Igor F. Herbut. Pinning the order: The nature of quantum criticality in the hubbard model on honeycomb lattice. Phys. Rev. X, 3: 031010, Aug 2013. 10.1103/​PhysRevX.3.031010.
https:/​/​doi.org/​10.1103/​PhysRevX.3.031010

Cited by

On Crossref's cited-by service no data on citing works was found (last attempt 2024-06-22 04:22:40). On SAO/NASA ADS no data on citing works was found (last attempt 2024-06-22 04:22:41).