Near-optimal ground state preparation

Lin Lin1,2 and Yu Tong1

1Department of Mathematics, University of California, Berkeley, CA 94720, USA
2Computational Research Division, Lawrence Berkeley National Laboratory, Berkeley, CA 94720, USA

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


Preparing the ground state of a given Hamiltonian and estimating its ground energy are important but computationally hard tasks. However, given some additional information, these problems can be solved efficiently on a quantum computer. We assume that an initial state with non-trivial overlap with the ground state can be efficiently prepared, and the spectral gap between the ground energy and the first excited energy is bounded from below. With these assumptions we design an algorithm that prepares the ground state when an upper bound of the ground energy is known, whose runtime has a logarithmic dependence on the inverse error. When such an upper bound is not known, we propose a hybrid quantum-classical algorithm to estimate the ground energy, where the dependence of the number of queries to the initial state on the desired precision is exponentially improved compared to the current state-of-the-art algorithm proposed in [Ge et al. 2019]. These two algorithms can then be combined to prepare a ground state without knowing an upper bound of the ground energy. We also prove that our algorithms reach the complexity lower bounds by applying it to the unstructured search problem and the quantum approximate counting problem.

► BibTeX data

► References

[1] D. Aharonov, D. Gottesman, S. Irani, and J. Kempe. The power of quantum systems on a line. Comm. Math. Phys., 287 (1): 41–65, 2009. 10.1007/​s00220-008-0710-3.

[2] A. Ambainis. Variable time amplitude amplification and quantum algorithms for linear algebra problems. In STACS'12 (29th Symposium on Theoretical Aspects of Computer Science), volume 14, pages 636–647, 2012.

[3] A. Ambainis. On physical problems that are slightly more difficult than QMA. In 2014 IEEE 29th Conference on Computational Complexity (CCC), pages 32–43. IEEE, 2014. 10.1109/​CCC.2014.12.

[4] R. Babbush, N. Wiebe, J. McClean, J. McClain, H. Neven, and G. K.-L. Chan. Low-depth quantum simulation of materials. Phys. Rev. X, 8 (1): 011044, 2018. 10.1103/​PhysRevX.8.011044.

[5] J. Bausch, T. Cubitt, A. Lucia, and D. Perez-Garcia. Undecidability of the spectral gap in one dimension. arXiv preprint arXiv:1810.01858, 2018. 10.1103/​PhysRevX.10.031038.

[6] C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani. Strengths and weaknesses of quantum computing. SIAM J. Comput., 26 (5): 1510–1523, 1997. 10.1137/​S0097539796300933.

[7] D. W. Berry and A. M. Childs. Black-box hamiltonian simulation and unitary implementation. arXiv preprint arXiv:0910.4157, 2009. 10.26421/​QIC12.1-2.

[8] D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma. Simulating Hamiltonian dynamics with a truncated taylor series. Phys. Rev. Lett., 114 (9): 090502, 2015a. 10.1103/​PhysRevLett.114.090502.

[9] D. W. Berry, A. M. Childs, and R. Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 792–809. IEEE, 2015b. 10.1109/​FOCS.2015.54.

[10] A. J. Bessen. Lower bound for quantum phase estimation. Phys. Rev. A, 71 (4): 042313, 2005. 10.1103/​PhysRevA.71.042313.

[11] S. Boixo, E. Knill, and R. D. Somma. Eigenpath traversal by phase randomization. Quantum Info. Comput., 9: 833–855, 2009.

[12] G. Brassard, P. Hoyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. Contemp. Math., 305: 53–74, 2002. 10.1090/​conm/​305/​05215.

[13] R. Chao, D. Ding, A. Gilyén, C. Huang, and M. Szegedy. Finding Angles for Quantum Signal Processing with Machine Precision. 2020. https:/​/​​abs/​2003.02831.

[14] A. M. Childs, E. Deotto, E. Farhi, J. Goldstone, S. Gutmann, and A. J. Landahl. Quantum search by measurement. Phys. Rev. A, 66 (3): 032314, 2002. 10.1103/​PhysRevA.66.032314.

[15] A. M. Childs, R. Kothari, and R. D. Somma. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM J. Comput., 46: 1920–1950, 2017. 10.1137/​16M1087072.

[16] A. M. Childs, D. Maslov, Y. Nam, N. J. Ross, and Y. Su. Toward the first quantum simulation with quantum speedup. Proc. Natl. Acad. Sci, 115 (38): 9456–9461, 2018. 10.1073/​pnas.1801723115.

[17] A. M. Childs, Y. Su, M. C. Tran, N. Wiebe, and S. Zhu. A theory of Trotter error. arXiv preprint arXiv:1912.08854, 2019.

[18] T. S. Cubitt, D. Perez-Garcia, and M. M. Wolf. Undecidability of the spectral gap. Nature, 528 (7581): 207–211, 2015. 10.1038/​nature16059.

[19] Y. Dong, X. Meng, K. B. Whaley, and L. Lin. Efficient phase factor evaluation in quantum signal processing. arXiv preprint arXiv:2002.11649, 2020.

[20] A. Eremenko and P. Yuditskii. Uniform approximation of $\mathrm{sgn}(x)$ by polynomials and entire functions. Journal d'Analyse Mathématique, 101 (1): 313–324, 2007. 10.1007/​s11854-007-0011-3.

[21] Y. Ge, J. Tura, and J. I. Cirac. Faster ground state preparation and high-precision ground energy estimation with fewer qubits. J. Math. Phys., 60 (2): 022202, 2019. 10.1063/​1.5027484.

[22] A. Gilyén, Y. Su, G. H. Low, and N. Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. arXiv preprint arXiv:1806.01838, 2018. 10.1145/​3313276.3316366.

[23] A. Gilyén, Y. Su, G. H. Low, and N. Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 193–204, 2019. 10.1145/​3313276.3316366.

[24] L. K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219, 1996. 10.1145/​237814.237866.

[25] J. Haah. Product decomposition of periodic functions in quantum signal processing. Quantum, 3: 190, 2019. 10.22331/​q-2019-10-07-190.

[26] Z. Jiang, K. J. Sung, K. Kechedzhi, V. N. Smelyanskiy, and S. Boixo. Quantum algorithms to simulate many-body physics of correlated fermions. Phys. Rev. Applied, 9 (4): 044036, 2018. 10.1103/​PhysRevApplied.9.044036.

[27] J. Kempe, A. Kitaev, and O. Regev. The complexity of the local Hamiltonian problem. SIAM J. Comput., 35 (5): 1070–1097, 2006. 10.1007/​978-3-540-30538-5_31.

[28] A. Y. Kitaev. Quantum measurements and the abelian stabilizer problem. arXiv preprint quant-ph/​9511026, 1995.

[29] A. Y. Kitaev, A. Shen, and M. N. Vyalyi. Classical and quantum computation. Number 47. American Mathematical Soc., 2002. 10.1090/​gsm/​047.

[30] I. D. Kivlichan, J. McClean, N. Wiebe, C. Gidney, A. Aspuru-Guzik, G. K.-L. Chan, and R. Babbush. Quantum simulation of electronic structure with linear depth and connectivity. Phys. Rev. Lett., 120 (11): 110501, 2018. 10.1103/​PhysRevLett.120.110501.

[31] L. Lin and Y. Tong. Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems. Quantum, 4: 361, 2020. 10.22331/​q-2020-11-11-361.

[32] S. Lloyd. Universal quantum simulators. Science, pages 1073–1078, 1996. 10.1126/​science.273.5278.1073.

[33] G. H. Low and I. L. Chuang. Optimal Hamiltonian simulation by quantum signal processing. Phys. Rev. Lett., 118: 010501, 2017. 10.1103/​PhysRevLett.118.010501.

[34] G. H. Low and I. L. Chuang. Hamiltonian simulation by qubitization. Quantum, 3: 163, 2019. 10.22331/​q-2019-07-12-163.

[35] G. H. Low and N. Wiebe. Hamiltonian simulation in the interaction picture. arXiv preprint arXiv:1805.00675, 2018.

[36] G. H. Low, T. J. Yoder, and I. L. Chuang. Methodology of resonant equiangular composite quantum gates. Phys. Rev. X, 6: 041067, 2016. 10.1103/​PhysRevX.6.041067.

[37] M. Motta, C. Sun, A. T. K. Tan, M. J. O'Rourke, E. Ye, A. J. Minnich, F. G. Brandao, and G. K. Chan. Quantum imaginary time evolution, quantum lanczos, and quantum thermal averaging. arXiv preprint arXiv:1901.07653, 2019. 10.1038/​s41567-019-0704-4.

[38] A. Nayak and F. Wu. The quantum query complexity of approximating the median and related statistics. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 384–393, 1999. 10.1145/​301250.301349.

[39] R. Oliveira and B. M. Terhal. The complexity of quantum spin systems on a two-dimensional square lattice. arXiv preprint quant-ph/​0504050, 2005.

[40] R. M. Parrish and P. L. McMahon. Quantum filter diagonalization: Quantum eigendecomposition without full quantum phase estimation. arXiv preprint arXiv:1909.08925, 2019.

[41] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O'brien. A variational eigenvalue solver on a photonic quantum processor. Nat. Commun., 5: 4213, 2014. 10.1038/​ncomms5213.

[42] D. Poulin and P. Wocjan. Preparing ground states of quantum many-body systems on a quantum computer. Phys. Rev. Lett., 102 (13): 130503, 2009. 10.1103/​PhysRevLett.102.130503.

[43] E. Remes. Sur le calcul effectif des polynomes d’approximation de tchebichef. C. R. Acad. Sci. Paris, 199: 337–340, 1934.

[44] N. H. Stair, R. Huang, and F. A. Evangelista. A multireference quantum Krylov algorithm for strongly correlated electrons. arXiv preprint arXiv:1911.05163, 2019. 10.1021/​acs.jctc.9b01125.

Cited by

[1] John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang, "Grand Unification of Quantum Algorithms", PRX Quantum 2 4, 040203 (2021).

[2] J. Wayne Mullinax and Norm M. Tubman, "Large-scale sparse wavefunction circuit simulator for applications with the variational quantum eigensolver", arXiv:2301.05726, (2023).

[3] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv:2310.03011, (2023).

[4] Mark R. Hirsbrunner, Diana Chamaki, J. Wayne Mullinax, and Norm M. Tubman, "Beyond MP2 initialization for unitary coupled cluster quantum circuits", arXiv:2301.05666, (2023).

[5] Joonho Lee, Dominic W. Berry, Craig Gidney, William J. Huggins, Jarrod R. McClean, Nathan Wiebe, and Ryan Babbush, "Even More Efficient Quantum Computations of Chemistry Through Tensor Hypercontraction", PRX Quantum 2 3, 030305 (2021).

[6] Guang Hao Low, Yuan Su, Yu Tong, and Minh C. Tran, "On the complexity of implementing Trotter steps", arXiv:2211.09133, (2022).

[7] Yulong Dong, Lin Lin, and Yu Tong, "Ground-State Preparation and Energy Estimation on Early Fault-Tolerant Quantum Computers via Quantum Eigenvalue Transformation of Unitary Matrices", PRX Quantum 3 4, 040305 (2022).

[8] Lin Lin and Yu Tong, "Heisenberg-Limited Ground-State Energy Estimation for Early Fault-Tolerant Quantum Computers", PRX Quantum 3 1, 010318 (2022).

[9] Thomas E. O'Brien, Michael Streif, Nicholas C. Rubin, Raffaele Santagati, Yuan Su, William J. Huggins, Joshua J. Goings, Nikolaj Moll, Elica Kyoseva, Matthias Degroote, Christofer S. Tautermann, Joonho Lee, Dominic W. Berry, Nathan Wiebe, and Ryan Babbush, "Efficient quantum computation of molecular forces and other energy gradients", Physical Review Research 4 4, 043210 (2022).

[10] Alain Delgado, Pablo A. M. Casares, Roberto dos Reis, Modjtaba Shokrian Zini, Roberto Campos, Norge Cruz-Hernández, Arne-Christian Voigt, Angus Lowe, Soran Jahangiri, M. A. Martin-Delgado, Jonathan E. Mueller, and Juan Miguel Arrazola, "Simulating key properties of lithium-ion batteries with a fault-tolerant quantum computer", Physical Review A 106 3, 032428 (2022).

[11] Yu Tong, Dong An, Nathan Wiebe, and Lin Lin, "Fast inversion, preconditioned quantum linear system solvers, fast Green's-function computation, and fast evaluation of matrix functions", Physical Review A 104 3, 032422 (2021).

[12] Lindsay Bassman, Miroslav Urbanek, Mekena Metcalf, Jonathan Carter, Alexander F. Kemper, and Wibe A. de Jong, "Simulating quantum materials with digital quantum computers", Quantum Science and Technology 6 4, 043002 (2021).

[13] William Kirby, Mario Motta, and Antonio Mezzacapo, "Exact and efficient Lanczos method on a quantum computer", Quantum 7, 1018 (2023).

[14] Mark Steudtner, Sam Morley-Short, William Pol, Sukin Sim, Cristian L. Cortes, Matthias Loipersberger, Robert M. Parrish, Matthias Degroote, Nikolaj Moll, Raffaele Santagati, and Michael Streif, "Fault-tolerant quantum computation of molecular observables", Quantum 7, 1164 (2023).

[15] Yuan Su, Hsin-Yuan Huang, and Earl T. Campbell, "Nearly tight Trotterization of interacting electrons", Quantum 5, 495 (2021).

[16] Jordi Weggemans, Marten Folkertsma, and Chris Cade, "Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture", arXiv:2302.11578, (2023).

[17] A. Roggero, "Spectral-density estimation with the Gaussian integral transform", Physical Review A 102 2, 022409 (2020).

[18] Kianna Wan and Isaac H. Kim, "Fast digital methods for adiabatic state preparation", arXiv:2004.04164, (2020).

[19] F. Turro, A. Roggero, V. Amitrano, P. Luchi, K. A. Wendt, J. L. Dubois, S. Quaglioni, and F. Pederiva, "Imaginary-time propagation on a quantum chip", Physical Review A 105 2, 022440 (2022).

[20] Zhiyan Ding and Lin Lin, "Even Shorter Quantum Circuit for Phase Estimation on Early Fault-Tolerant Quantum Computers with Applications to Ground-State Energy Estimation", PRX Quantum 4 2, 020331 (2023).

[21] Guang Hao Low, Yuan Su, Yu Tong, and Minh C. Tran, "Complexity of Implementing Trotter Steps", PRX Quantum 4 2, 020323 (2023).

[22] Patrick Rall, "Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation", Quantum 5, 566 (2021).

[23] Kosuke Mitarai, Kiichiro Toyoizumi, and Wataru Mizukami, "Perturbation theory with quantum signal processing", Quantum 7, 1000 (2023).

[24] Lucas K. Kovalsky, Fernando A. Calderon-Vargas, Matthew D. Grace, Alicia B. Magann, James B. Larsen, Andrew D. Baczewski, and Mohan Sarovar, "Self-Healing of Trotter Error in Digital Adiabatic State Preparation", Physical Review Letters 131 6, 060602 (2023).

[25] Alicja Dutkiewicz, Barbara M. Terhal, and Thomas E. O'Brien, "Heisenberg-limited quantum phase estimation of multiple eigenvalues with few control qubits", Quantum 6, 830 (2022).

[26] William J. Huggins, Kianna Wan, Jarrod McClean, Thomas E. O'Brien, Nathan Wiebe, and Ryan Babbush, "Nearly Optimal Quantum Algorithm for Estimating Multiple Expectation Values", Physical Review Letters 129 24, 240501 (2022).

[27] Stefano Polla, Yaroslav Herasymenko, and Thomas E. O'Brien, "Quantum digital cooling", Physical Review A 104 1, 012414 (2021).

[28] Kaito Mizukami and Akihisa Koga, "Quantum algorithm for the microcanonical thermal pure quantum state method", Physical Review A 108 1, 012404 (2023).

[29] Yulong Dong, K. Birgitta Whaley, and Lin Lin, "A quantum hamiltonian simulation benchmark", npj Quantum Information 8, 131 (2022).

[30] Qisheng Wang and Zhicheng Zhang, "Quantum Lower Bounds by Sample-to-Query Lifting", arXiv:2308.01794, (2023).

[31] S. Pathak, A. E. Russo, S. K. Seritan, and A. D. Baczewski, "Quantifying T -gate-count improvements for ground-state-energy estimation with near-optimal state preparation", Physical Review A 107 4, L040601 (2023).

[32] Hirofumi Nishi, Koki Hamada, Yusuke Nishiya, Taichi Kosugi, and Yu-ichiro Matsushita, "Optimal scheduling in probabilistic imaginary-time evolution on a quantum computer", Physical Review Research 5 4, 043048 (2023).

[33] Shantanav Chakraborty, Aditya Morolia, and Anurudh Peduri, "Quantum Regularized Least Squares", Quantum 7, 988 (2023).

[34] Xiantao Li, "Some error analysis for the quantum phase estimation algorithms", Journal of Physics A Mathematical General 55 32, 325303 (2022).

[35] Simon Apers, Shantanav Chakraborty, Leonardo Novo, and Jérémie Roland, "Quadratic Speedup for Spatial Search by Continuous-Time Quantum Walk", Physical Review Letters 129 16, 160502 (2022).

[36] Jiasu Wang, Yulong Dong, and Lin Lin, "On the energy landscape of symmetric quantum signal processing", Quantum 6, 850 (2022).

[37] Changhao Yi, "Success of digital adiabatic simulation with large Trotter step", Physical Review A 104 5, 052603 (2021).

[38] Patrick Rall and Bryce Fuller, "Amplitude Estimation from Quantum Signal Processing", Quantum 7, 937 (2023).

[39] Hongkang Ni, Haoya Li, and Lexing Ying, "On low-depth algorithms for quantum phase estimation", Quantum 7, 1165 (2023).

[40] Hans Hon Sang Chan, Richard Meister, Tyson Jones, David P. Tew, and Simon C. Benjamin, "Grid-based methods for chemistry simulations on a quantum computer", Science Advances 9 9, eabo7484 (2023).

[41] Ruizhe Zhang, Guoming Wang, and Peter Johnson, "Computing Ground State Properties with Early Fault-Tolerant Quantum Computers", Quantum 6, 761 (2022).

[42] Pablo A. M. Casares, Roberto Campos, and M. A. Martin-Delgado, "TFermion: A non-Clifford gate cost assessment library of quantum phase estimation algorithms for quantum chemistry", Quantum 6, 768 (2022).

[43] Matthew Thibodeau and Bryan K. Clark, "Nearly-frustration-free ground state preparation", Quantum 7, 1084 (2023).

[44] Judah F. Unmuth-Yockey, "Metropolis-style random sampling of quantum gates for the estimation of low-energy observables", Physical Review D 105 3, 034515 (2022).

[45] Guoming Wang, Sukin Sim, and Peter D. Johnson, "State Preparation Boosters for Early Fault-Tolerant Quantum Computation", Quantum 6, 829 (2022).

[46] Kianna Wan, "Exponentially faster implementations of Select(H) for fermionic Hamiltonians", Quantum 5, 380 (2021).

[47] Xinying Li and Yun Shang, "Faster quantum sampling of Markov chains in nonregular graphs with fewer qubits", Physical Review A 107 2, 022432 (2023).

[48] Daochen Wang, Xuchen You, Tongyang Li, and Andrew M. Childs, "Quantum exploration algorithms for multi-armed bandits", arXiv:2007.07049, (2020).

[49] Stefano Polla, Gian-Luca R. Anselmetti, and Thomas E. O'Brien, "Optimizing the information extracted by a single qubit measurement", Physical Review A 108 1, 012403 (2023).

[50] Trevor Keen, Bo Peng, Karol Kowalski, Pavel Lougovski, and Steven Johnston, "Hybrid quantum-classical approach for coupled-cluster Green's function theory", Quantum 6, 675 (2022).

[51] Duarte Magano and Miguel Murça, "Simplifying a classical-quantum algorithm interpolation with quantum singular value transformations", Physical Review A 106 6, 062419 (2022).

[52] L. Wright, F. Barratt, J. Dborin, G. H. Booth, and A. G. Green, "Automatic post-selection by ancillae thermalization", Physical Review Research 3 3, 033151 (2021).

[53] Kai Li, Ming Zhang, Xiaowen Liu, Yong Liu, Hongyi Dai, Yijun Zhang, and Chen Dong, "Quantum Linear System Algorithm for General Matrices in System Identification", Entropy 24 7, 893 (2022).

[54] Cheong Eung Ahn and Gil Young Cho, "Simulation and randomized measurement of topological phase on a trapped-ion quantum computer", Journal of Korean Physical Society 81 3, 258 (2022).

[55] Nikhil S. Mande and Ronald de Wolf, "Tight Bounds for Quantum Phase Estimation and Related Problems", arXiv:2305.04908, (2023).

The above citations are from SAO/NASA ADS (last updated successfully 2023-12-06 23:27:44). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2023-12-06 23:27:41: Encountered the unhandled forward link type postedcontent_cite while looking for citations to DOI 10.22331/q-2020-12-14-372.