Near-optimal ground state preparation

Lin Lin; Yu Tong

doi:10.22331/q-2020-12-14-372

Near-optimal ground state preparation

Lin Lin^1,2 and Yu Tong¹

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

Published:	2020-12-14, volume 4, page 372
Eprint:	arXiv:2002.12508v3
Doi:	https://doi.org/10.22331/q-2020-12-14-372
Citation:	Quantum 4, 372 (2020).

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

Abstract

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

@article{Lin2020nearoptimalground,
  doi = {10.22331/q-2020-12-14-372},
  url = {https://doi.org/10.22331/q-2020-12-14-372},
  title = {Near-optimal ground state preparation},
  author = {Lin, Lin and Tong, Yu},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {4},
  pages = {372},
  month = dec,
  year = {2020}
}

► 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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.1103/PhysRevX.10.031038
arXiv:1810.01858

[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.
https://doi.org/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.
https://doi.org/10.26421/QIC12.1-2
arXiv:0910.4157

[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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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://arxiv.org/abs/2003.02831.
arXiv: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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
arXiv:1912.08854

[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.
https://doi.org/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.
arXiv:2002.11649

[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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.1145/3313276.3316366
arXiv:1806.01838

[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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
arXiv:quant-ph/9511026

[29] A. Y. Kitaev, A. Shen, and M. N. Vyalyi. Classical and quantum computation. Number 47. American Mathematical Soc., 2002. 10.1090/gsm/047.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.22331/q-2020-11-11-361

[32] S. Lloyd. Universal quantum simulators. Science, pages 1073–1078, 1996. 10.1126/science.273.5278.1073.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
arXiv:1805.00675

[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.
https://doi.org/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.
https://doi.org/10.1038/s41567-019-0704-4
arXiv:1901.07653

[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.
https://doi.org/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.
arXiv:quant-ph/0504050

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

[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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.1021/acs.jctc.9b01125
arXiv:1911.05163

Cited by

[1] Sirui Lu, Mari Carmen Bañuls, and J. Ignacio Cirac, "Algorithms for Quantum Simulation at Finite Energies", PRX Quantum 2 2, 020321 (2021).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[16] I. Stetcu, A. Baroni, and J. Carlson, "Variational approaches to constructing the many-body nuclear ground state for quantum computing", Physical Review C 105 6, 064308 (2022).

[17] Davide Rattacaso, Gianluca Passarelli, Procolo Lucignano, and Rosario Fazio, Quantum Science and Technology 189 (2022) ISBN:978-3-031-03997-3.

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

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

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

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

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

[23] Natalie Klco, Alessandro Roggero, and Martin J Savage, "Standard model physics and the digital quantum revolution: thoughts about the interface", Reports on Progress in Physics 85 6, 064301 (2022).

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

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

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

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

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

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

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

[31] A. E. Russo, K. M. Rudinger, B. C. A. Morrison, and A. D. Baczewski, "Evaluating Energy Differences on a Quantum Computer with Robust Phase Estimation", Physical Review Letters 126 21, 210501 (2021).

[32] Yu Tong, "Designing algorithms for estimating ground state properties on early fault-tolerant quantum computers", Quantum Views 6, 65 (2022).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[50] 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 Crossref's cited-by service (last updated successfully 2023-03-15 06:48:59) and SAO/NASA ADS (last updated successfully 2023-05-29 21:39:17). 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-05-29 21:39:15: Encountered the unhandled forward link type postedcontent_cite while looking for citations to DOI 10.22331/q-2020-12-14-372.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.