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] Kianna Wan, "Exponentially faster implementations of Select(H) for fermionic Hamiltonians", arXiv:2004.04170, Quantum 5, 380 (2021).

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

[3] Yuan Su, Hsin-Yuan Huang, and Earl T. Campbell, "Nearly tight Trotterization of interacting electrons", arXiv:2012.09194.

[4] Kianna Wan and Isaac Kim, "Fast digital methods for adiabatic state preparation", arXiv:2004.04164.

[5] Sirui Lu, Mari Carmen Bañuls, and J. Ignacio Cirac, "Algorithms for quantum simulation at finite energies", arXiv:2006.03032.

[6] Yu Tong, Dong An, Nathan Wiebe, and Lin Lin, "Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions", arXiv:2008.13295.

[7] 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", arXiv:2007.08697.

[8] Lindsay Bassman, Miroslav Urbanek, Mekena Metcalf, Jonathan Carter, Alexander F. Kemper, and Wibe de Jong, "Simulating Quantum Materials with Digital Quantum Computers", arXiv:2101.08836.

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

[10] Francesco Turro, Valentina Amitrano, Piero Luchi, Kyle A. Wendt, Jonathan L DuBois, Sofia Quaglioni, and Francesco Pederiva, "Imaginary Time Propagation on a Quantum Chip", arXiv:2102.12260.

The above citations are from Crossref's cited-by service (last updated successfully 2021-04-21 20:05:59) and SAO/NASA ADS (last updated successfully 2021-04-21 20:06:00). The list may be incomplete as not all publishers provide suitable and complete citation data.