Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems

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.

Abstract

We present a quantum eigenstate filtering algorithm based on quantum signal processing (QSP) and minimax polynomials. The algorithm allows us to efficiently prepare a target eigenstate of a given Hamiltonian, if we have access to an initial state with non-trivial overlap with the target eigenstate and have a reasonable lower bound for the spectral gap. We apply this algorithm to the quantum linear system problem (QLSP), and present two algorithms based on quantum adiabatic computing (AQC) and quantum Zeno effect respectively. Both algorithms prepare the final solution as a pure state, and achieves the near optimal $\mathcal{\widetilde{O}}(d\kappa\log(1/\epsilon))$ query complexity for a $d$-sparse matrix, where $\kappa$ is the condition number, and $\epsilon$ is the desired precision. Neither algorithm uses phase estimation or amplitude amplification.

We present a quantum eigenstate filtering algorithm that allows us to efficiently prepare a target eigenstate of a given Hamiltonian to high precision under reasonable assumptions. We apply this algorithm to the quantum linear system problem, and present two algorithms based on quantum adiabatic computing and quantum Zeno effect respectively. Both algorithms prepare the final solution as a pure state, and achieves the near optimal query complexity. Neither algorithm uses phase estimation or amplitude amplification.

► BibTeX data

► References

[1] D. Aharonov and A. Ta-Shma. Adiabatic quantum state generation and statistical zero knowledge. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 20–29. ACM, 2003. 10.1145/​780542.780546.
https:/​/​doi.org/​10.1145/​780542.780546

[2] T. Albash and D. A. Lidar. Adiabatic quantum computation. Rev. Mod. Phys., 90: 015002, 2018. 10.1103/​RevModPhys.90.015002.
https:/​/​doi.org/​10.1103/​RevModPhys.90.015002

[3] A. Ambainis. Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations. arXiv preprint arXiv:1010.4458, 2010.
arXiv:1010.4458

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

[5] D. An and L. Lin. Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm. arXiv:1909.05500, 2019.
arXiv:1909.05500

[6] S. Apers and A. Sarlette. Quantum fast-forwarding: Markov chains and graph property testing. Quantum Information & Computation, 19 (3-4): 181–213, 2019. URL https:/​/​dl.acm.org/​doi/​10.5555/​3370245.3370246.
https:/​/​dl.acm.org/​doi/​10.5555/​3370245.3370246

[7] S. Apers, A. Gilyén, and S. Jeffery. A unified framework of quantum walk search. arXiv preprint arXiv:1912.04233, 2019.
arXiv:1912.04233

[8] J. M. Arrazola, A. Delgado, B. R. Bardhan, and S. Lloyd. Quantum-inspired algorithms in practice. arXiv preprint arXiv:1905.10415, 2019. 10.22331/​q-2020-08-13-307.
https:/​/​doi.org/​10.22331/​q-2020-08-13-307
arXiv:1905.10415

[9] A. Balachandran and S. Roy. Quantum anti-Zeno paradox. Physical review letters, 84 (18): 4019, 2000. 10.1103/​PhysRevLett.84.4019.
https:/​/​doi.org/​10.1103/​PhysRevLett.84.4019

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

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

[12] S. Boixo, E. Knill, and R. D. Somma. Eigenpath traversal by phase randomization. Quantum Info. Comput., 9: 833–855, 2009. URL https:/​/​dl.acm.org/​doi/​10.5555/​2011804.2011811.
https:/​/​dl.acm.org/​doi/​10.5555/​2011804.2011811

[13] 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

[14] C. Bravo-Prieto, R. LaRose, M. Cerezo, Y. Subasi, L. Cincio, and P. J. Coles. Variational quantum linear solver: A hybrid algorithm for linear systems. arXiv:1909.05820, 2019.
arXiv:1909.05820

[15] D. Burgarth, P. Facchi, V. Giovannetti, H. Nakazato, S. Pascazio, and K. Yuasa. Non-abelian phases from quantum Zeno dynamics. Physical Review A, 88 (4): 042107, 2013. 10.1103/​PhysRevA.88.042107.
https:/​/​doi.org/​10.1103/​PhysRevA.88.042107

[16] Y. Cao, A. Papageorgiou, I. Petras, J. Traub, and S. Kais. Quantum algorithm and circuit design solving the poisson equation. New J. Phys., 15 (1): 013021, 2013. 10.1088/​1367-2630/​15/​1/​013021.
https:/​/​doi.org/​10.1088/​1367-2630/​15/​1/​013021

[17] S. Chakraborty, A. Gilyén, and S. Jeffery. The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation. arXiv preprint arXiv:1804.01973, 2018. 10.4230/​LIPIcs.ICALP.2019.33.
https:/​/​doi.org/​10.4230/​LIPIcs.ICALP.2019.33
arXiv:1804.01973

[18] R. Chao, D. Ding, A. Gilyen, C. Huang, and M. Szegedy. Finding angles for quantum signal processing with machine precision. arXiv preprint arXiv:2003.02831, 2020.
arXiv:2003.02831

[19] N.-H. Chia, H.-H. Lin, and C. Wang. Quantum-inspired sublinear classical algorithms for solving low-rank linear systems. arXiv preprint arXiv:1811.04852, 2018.
arXiv:1811.04852

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

[21] 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

[22] A. N. Chowdhury, Y. Subasi, and R. D. Somma. Improved implementation of reflection operators. arXiv preprint arXiv:1803.02466, 2018.
arXiv:1803.02466

[23] 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

[24] A. Elgart and G. A. Hagedorn. A note on the switching adiabatic theorem. J. Math. Phys., 53 (10): 102202, 2012. 10.1063/​1.4748968.
https:/​/​doi.org/​10.1063/​1.4748968

[25] P. Erdös. Some remarks on polynomials. Bulletin of the American Mathematical Society, 53 (12): 1169–1176, 1947. 10.1090/​S0002-9904-1947-08938-2.
https:/​/​doi.org/​10.1090/​S0002-9904-1947-08938-2

[26] P. Facchi and S. Pascazio. Quantum Zeno dynamics: mathematical and physical aspects. Journal of Physics A: Mathematical and Theoretical, 41 (49): 493001, 2008. 10.1088/​1751-8113/​41/​49/​493001.
https:/​/​doi.org/​10.1088/​1751-8113/​41/​49/​493001

[27] P. Facchi, A. Klein, S. Pascazio, and L. Schulman. Berry phase from a quantum Zeno effect. Physics Letters A, 257 (5-6): 232–240, 1999. 10.1016/​S0375-9601(99)00323-0.
https:/​/​doi.org/​10.1016/​S0375-9601(99)00323-0

[28] E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser. Quantum computation by adiabatic evolution. arXiv preprint quant-ph/​0001106, 2000.
arXiv:quant-ph/0001106

[29] E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014.
arXiv:1411.4028

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

[31] A. Gilyén, S. Lloyd, and E. Tang. Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension. arXiv preprint arXiv:1811.04909, 2018a.
arXiv:1811.04909

[32] 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, 2018b. 10.1145/​3313276.3316366.
https:/​/​doi.org/​10.1145/​3313276.3316366
arXiv:1806.01838

[33] A. Gilyén, S. Arunachalam, and N. Wiebe. Optimizing quantum optimization algorithms via faster quantum gradient computation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1425–1444, 2019a. 10.1137/​1.9781611975482.87.
https:/​/​doi.org/​10.1137/​1.9781611975482.87

[34] 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, 2019b. 10.1145/​3313276.3316366.
https:/​/​doi.org/​10.1145/​3313276.3316366

[35] 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

[36] L. K. Grover. Fixed-point quantum search. Physical Review Letters, 95 (15): 150501, 2005. 10.1103/​PhysRevLett.95.150501.
https:/​/​doi.org/​10.1103/​PhysRevLett.95.150501

[37] 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

[38] A. W. Harrow, A. Hassidim, and S. Lloyd. Quantum algorithm for linear systems of equations. Phys. Rev. Lett., 103: 150502, 2009. 10.1007/​978-3-642-27848-8_771-1.
https:/​/​doi.org/​10.1007/​978-3-642-27848-8_771-1

[39] S. Jansen, M.-B. Ruskai, and R. Seiler. Bounds for the adiabatic approximation with applications to quantum computation. J. Math. Phys., 48 (10): 102111, 2007. 10.1063/​1.2798382.
https:/​/​doi.org/​10.1063/​1.2798382

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

[41] J. Lemieux, G. Duclos-Cianci, D. Sénéchal, and D. Poulin. Resource estimate for quantum many-body ground state preparation on a quantum computer. arXiv preprint arXiv:2006.04650, 2020.
arXiv:2006.04650

[42] 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

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

[44] 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

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

[46] B. Misra and E. G. Sudarshan. The Zeno's paradox in quantum theory. Journal of Mathematical Physics, 18 (4): 756–763, 1977. 10.1063/​1.523304.
https:/​/​doi.org/​10.1063/​1.523304

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

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

[49] D. Poulin and P. Wocjan. Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer. Physical review letters, 103 (22): 220502, 2009b. 10.1103/​PhysRevLett.103.220502.
https:/​/​doi.org/​10.1103/​PhysRevLett.103.220502

[50] D. Poulin, A. Kitaev, D. S. Steiger, M. B. Hastings, and M. Troyer. Quantum algorithm for spectral measurement with a lower gate count. Physical review letters, 121 (1): 010501, 2018. 10.1103/​PhysRevLett.121.010501.
https:/​/​doi.org/​10.1103/​PhysRevLett.121.010501

[51] E. Y. Remez. Sur la détermination des polynômes d’approximation de degré donnée. Comm. Soc. Math. Kharkov, 10 (196): 41–63, 1934.

[52] Y. Saad. Iterative methods for sparse linear systems, volume 82. SIAM, 2003. 10.1137/​1.9780898718003.
https:/​/​doi.org/​10.1137/​1.9780898718003

[53] S. Sachdeva and N. K. Vishnoi. Faster algorithms via approximation theory. Theoretical Computer Science, 9 (2): 125–210, 2013. 10.1561/​0400000065.
https:/​/​doi.org/​10.1561/​0400000065

[54] R. D. Somma, S. Boixo, H. Barnum, and E. Knill. Quantum simulations of classical annealing processes. Physical review letters, 101 (13): 130504, 2008. 10.1103/​PhysRevLett.101.130504.
https:/​/​doi.org/​10.1103/​PhysRevLett.101.130504

[55] 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

[56] Y. Subaşı, R. D. Somma, and D. Orsucci. Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing. Phys. Rev. Lett., 122: 060504, 2019. 10.1103/​PhysRevLett.122.060504.
https:/​/​doi.org/​10.1103/​PhysRevLett.122.060504

[57] M. Szegedy. Quantum speed-up of Markov chain based algorithms. In 45th Annual IEEE symposium on foundations of computer science, pages 32–41. IEEE, 2004. 10.1109/​FOCS.2004.53.
https:/​/​doi.org/​10.1109/​FOCS.2004.53

[58] E. Tang. Quantum-inspired classical algorithms for principal component analysis and supervised clustering. arXiv preprint arXiv:1811.00414, 2018.
arXiv:1811.00414

[59] E. Tang. A quantum-inspired classical algorithm for recommendation systems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 217–228, 2019. 10.1145/​3313276.3316310.
https:/​/​doi.org/​10.1145/​3313276.3316310

[60] P. Wocjan and A. Abeyesinghe. Speedup via quantum sampling. Physical Review A, 78 (4): 042336, 2008. 10.1103/​PhysRevA.78.042336.
https:/​/​doi.org/​10.1103/​PhysRevA.78.042336

[61] L. Wossnig, Z. Zhao, and A. Prakash. Quantum linear system algorithm for dense matrices. Phys. Rev. Lett., 120 (5): 050502, 2018. 10.1103/​PhysRevLett.120.050502.
https:/​/​doi.org/​10.1103/​PhysRevLett.120.050502

[62] X. Xu, J. Sun, S. Endo, Y. Li, S. C. Benjamin, and X. Yuan. Variational algorithms for linear algebra. arXiv:1909.03898, 2019.
arXiv:1909.03898

[63] T. J. Yoder, G. H. Low, and I. L. Chuang. Fixed-point quantum search with an optimal number of queries. Physical review letters, 113 (21): 210501, 2014. 10.1103/​PhysRevLett.113.210501.
https:/​/​doi.org/​10.1103/​PhysRevLett.113.210501

Cited by

[1] Dong An and Lin Lin, "Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm", arXiv:1909.05500.

[2] Lin Lin and Yu Tong, "Near-optimal ground state preparation", arXiv:2002.12508.

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

[4] Yulong Dong, Xiang Meng, K. Birgitta Whaley, and Lin Lin, "Efficient Phase Factor Evaluation in Quantum Signal Processing", arXiv:2002.11649.

[5] 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.

[6] Yulong Dong and Lin Lin, "Random circuit block-encoded matrix and a proposal of quantum LINPACK benchmark", arXiv:2006.04010.

[7] Bujiao Wu, Maharshi Ray, Liming Zhao, Xiaoming Sun, and Patrick Rebentrost, "Quantum-classical algorithms for skewed linear systems with optimized Hadamard test", arXiv:2009.13288.

[8] András Gilyén and Umesh Vazirani, "(Sub)Exponential advantage of adiabatic quantum computation with no sign problem", arXiv:2011.09495.

The above citations are from SAO/NASA ADS (last updated successfully 2020-11-25 12:04:41). 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 2020-11-25 12:04:39).