Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
1Department of Mathematics, University of California, Berkeley, CA 94720, USA
2Computational Research Division, Lawrence Berkeley National Laboratory, Berkeley, CA 94720, USA
| Published: | 2020-11-11, volume 4, page 361 |
| Eprint: | arXiv:1910.14596v4 |
| Doi: | https://doi.org/10.22331/q-2020-11-11-361 |
| Citation: | Quantum 4, 361 (2020). |
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.
Popular summary
► 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] Francoise Golse, Shi Jin, and Nana Liu, "Quantum algorithms for uncertainty quantification: Applications to partial differential equations", Science China Physics, Mechanics & Astronomy 68 10, 104704 (2025).
[2] Sam McArdle, András Gilyén,, and Mario Berta, "A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits", Quantum 10, 2058 (2026).
[3] Lin Lin and Yu Tong, "Near-optimal ground state preparation", Quantum 4, 372 (2020).
[4] Matthias Rosenkranz, Eric Brunner, Gabriel Marin-Sanchez, Nathan Fitzpatrick, Silas Dilkes, Yao Tang, Yuta Kikuchi, and Marcello Benedetti, "Quantum state preparation for multivariate functions", Quantum 9, 1703 (2025).
[5] Arthur Braida, Shantanav Chakraborty, Alapan Chaudhuri, Joseph Cunningham, Rutvij Menavlikar, Leonardo Novo, and Jérémie Roland, "Unstructured Adiabatic Quantum Optimization: Optimality with Limitations", Quantum 9, 1790 (2025).
[6] Pedro C.S. Costa, Dong An, Ryan Babbush, and Dominic Berry, "The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver", Quantum 9, 1887 (2025).
[7] Kavitha Velusamy, Sowmiya Ramasamy, George Washington Samuelraj Chrysolite, Mallika Arjunan Mani, and Seenith Sivasundaram, "A Residual-Adaptive Preconditioned ψ-Fractional Quantum Pseudo-Spectral Method: Delay-Memory Differential Equations", Mathematics 14 15, 2842 (2026).
[8] Jiasu Wang, Yulong Dong, and Lin Lin, "On the energy landscape of symmetric quantum signal processing", Quantum 6, 850 (2022).
[9] Lin Lin and Yu Tong, "Heisenberg-Limited Ground-State Energy Estimation for Early Fault-Tolerant Quantum Computers", PRX Quantum 3 1, 010318 (2022).
[10] Yulong Dong, Lin Lin, Hongkang Ni, and Jiasu Wang, "Infinite quantum signal processing", Quantum 8, 1558 (2024).
[11] Kaoru Mizuta and Keisuke Fujii, "Recursive quantum eigenvalue and singular-value transformation: Analytic construction of matrix sign function by Newton iteration", Physical Review Research 6 1, L012007 (2024).
[12] Hari Krovi, "Improved quantum algorithms for linear and nonlinear differential equations", Quantum 7, 913 (2023).
[13] S. E. Skelton, 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) 150 (2024) ISBN:979-8-3315-4137-8.
[14] Sven Danz, Mario Berta, Stefan Schröder, Pascal Kienast, Frank K. Wilhelm, and Alessandro Ciani, "Calculating response functions of coupled oscillators using quantum phase estimation", Physical Review Research 7 2, 023264 (2025).
[15] Zihao Liu, Guanzhong Li, and Lvzhou Li, "Improved quantum linear system solver via quantum phase discrimination", The European Physical Journal Special Topics 234 20, 6241 (2025).
[16] Davide Orsucci and Vedran Dunjko, "On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number", Quantum 5, 573 (2021).
[17] Guang Hao Low and Yuan Su, "Quantum linear system algorithm with optimal queries to initial state preparation", Quantum 10, 2041 (2026).
[18] Matthew Thibodeau and Bryan K. Clark, "Nearly-frustration-free ground state preparation", Quantum 7, 1084 (2023).
[19] Chuang-Chao Ye, Ning-Bo An, Teng-Yang Ma, Meng-Han Dou, Wen Bai, De-Jun Sun, Zhao-Yun Chen, and Guo-Ping Guo, "A hybrid quantum-classical framework for computational fluid dynamics", Physics of Fluids 36 12, 127111 (2024).
[20] M. Deiml and D. Peterseim, "Quantum realization of the finite element method", Mathematics of Computation 95 362, 2637 (2025).
[21] Zane M. Rossi and Isaac L. Chuang, "Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle", Quantum 6, 811 (2022).
[22] Pedro C.S. Costa, Dong An, Yuval R. Sanders, Yuan Su, Ryan Babbush, and Dominic W. Berry, "Optimal Scaling Quantum Linear-Systems Solver via Discrete Adiabatic Theorem", PRX Quantum 3 4, 040303 (2022).
[23] Liron Mor-Yosef, Shashanka Ubaru, Lior Horesh, and Haim Avron, "Multivariate Trace Estimation Using Quantum State Space Linear Algebra", SIAM Journal on Matrix Analysis and Applications 46 1, 172 (2025).
[24] Erenay Karacan, Conor Mc Keever, Michael Foss-Feig, David Hayes, and Michael Lubasch, "Filter-enhanced adiabatic quantum computing on a digital quantum processor", Physical Review Research 7 3, 033153 (2025).
[25] Dong An and Lin Lin, "Quantum Linear System Solver Based on Time-optimal Adiabatic Quantum Computing and Quantum Approximate Optimization Algorithm", ACM Transactions on Quantum Computing 3 2, 1 (2022).
[26] Guang Hao Low and Yuan Su, "Quantum Eigenvalue Processing", SIAM Journal on Computing 55 1, 135 (2026).
[27] Weitao Lin, Guojing Tian, and Xiaoming Sun, "Quantum multirow iteration algorithm for linear systems with nonsquare coefficient matrices", Physical Review A 110 2, 022438 (2024).
[28] Qisheng Wang and Zhicheng Zhang, "Tight quantum depth lower bound for solving systems of linear equations", Physical Review A 110 1, 012422 (2024).
[29] Grzegorz Rajchel-Mieldzioć, Szymon Pliś, and Emil Zak, "Quantum algorithm for solving generalized eigenvalue problems with application to the Schrödinger equation", Physical Review Research 8 2, 023192 (2026).
[30] Di Fang, Lin Lin, and Yu Tong, "Time-marching based quantum solvers for time-dependent linear differential equations", Quantum 7, 955 (2023).
[31] Xinying Li, Xian Lu, Yongmei Li, Xin Yi, Shuai Hou, and Chengkang Pan, 2025 2nd Asia Pacific Conference on Computing Technologies, Communications and Networking (CTCNet) 1 (2025) ISBN:979-8-3315-7944-9.
[32] Zhaoyuan Meng, Leyu Chen, Jin-Peng Liu, and Guowei He, "Toward end-to-end quantum simulation of rapidly distorted turbulence", Journal of Computational Physics 558, 114888 (2026).
[33] Zheng Zhang and Minzhong Luo, Proceedings of the 23rd ACM International Conference on Computing Frontiers 133 (2026) ISBN:9798400725685.
[34] Dong An, Noah Linden, Jin-Peng Liu, Ashley Montanaro, Changpeng Shao, and Jiasu Wang, "Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance", Quantum 5, 481 (2021).
[35] Kodai Shiba, Chih-Chieh Chen, Masaru Sogabe, Katsuyoshi Sakamoto, and Tomah Sogabe, "Quantum-Inspired Classification Algorithm from DBSCAN–Deutsch–Jozsa Support Vectors and Ising Prediction Model", Applied Sciences 11 23, 11386 (2021).
[36] Martina Nibbi and Christian B. Mendl, "Block encoding of matrix product operators", Physical Review A 110 4, 042427 (2024).
[37] Daan Camps and Roel Van Beeumen, 2022 IEEE International Conference on Quantum Computing and Engineering (QCE) 104 (2022) ISBN:978-1-6654-9113-6.
[38] Sevag Gharibian and François Le Gall, "Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture", SIAM Journal on Computing 52 4, 1009 (2023).
[39] Dong An, Akwum Onwunta, and Gengzhi Yang, "Fast-forwarding quantum algorithms for linear dissipative differential equations", Quantum 10, 1986 (2026).
[40] Quynh T. Nguyen, Bobak T. Kiani, and Seth Lloyd, "Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra", Quantum 6, 876 (2022).
[41] Sebastian Issel, Kilian Tscharke, and Pascal Debus, 2025 International Conference on Quantum Communications, Networking, and Computing (QCNC) 598 (2025) ISBN:979-8-3315-3159-1.
[42] Hongkang Ni and Lexing Ying, "Fast Phase Factor Finding for Quantum Signal Processing", SIAM Journal on Scientific Computing 48 4, B651 (2026).
[43] David Jennings, Matteo Lostaglio, Sam Pallister, Andrew T. Sornborger, and Yiğit Subaşı, "Randomized Adiabatic Quantum Linear Solver Algorithm with Optimal Complexity Scaling and Detailed Running Costs", PRX Quantum 6 4, 040373 (2025).
[44] Bjorn K. Berntson and Christoph Sünderhauf, "Complementary Polynomials in Quantum Signal Processing", Communications in Mathematical Physics 406 7, 161 (2025).
[45] Zane M. Rossi and Isaac L. Chuang, "Quantum hypothesis testing with group structure", Physical Review A 104 1, 012425 (2021).
[46] Koichi Miyamoto and Hiroshi Ueda, "Extracting a function encoded in amplitudes of a quantum state by tensor network and orthogonal function expansion", Quantum Information Processing 22 6, 239 (2023).
[47] Lin Lin, Volume 7: Invited Lectures: Sections 15–20 57 (2026) ISBN:978-1-61197-872-8.
[48] Dylan Herman, Ruslan Shaydulin, Yue Sun, Shouvanik Chakrabarti, Shaohan Hu, Pierre Minssen, Arthur Rattew, Romina Yalovetzky, and Marco Pistoia, "Constrained optimization via quantum Zeno dynamics", Communications Physics 6 1, 219 (2023).
[49] Sevag Gharibian and François Le Gall, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing 19 (2022) ISBN:9781450392648.
[50] Jinzhao Sun, Pei Zeng, Tom Gur, and M. S. Kim, "High-precision and low-depth quantum algorithm design for eigenstate problems", Science Advances 12 3, eaeb1622 (2026).
[51] Hsuan-Cheng Wu, Jingyao Wang, and Xiantao Li, "Quantum Algorithms for Nonlinear Dynamics: Revisiting Carleman Linearization with No Dissipative Conditions", SIAM Journal on Scientific Computing 47 2, A943 (2025).
[52] Yulong Dong, Lin Lin, Hongkang Ni, and Jiasu Wang, "Robust Iterative Method for Symmetric Quantum Signal Processing in All Parameter Regimes", SIAM Journal on Scientific Computing 46 5, A2951 (2024).
[53] Daan Camps, Lin Lin, Roel Van Beeumen, and Chao Yang, "Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices", SIAM Journal on Matrix Analysis and Applications 45 1, 801 (2024).
[54] Mancheon Han, Hyowon Park, and Sangkook Choi, "Quantum Zeno Monte Carlo for computing observables", npj Quantum Information 11 1, 46 (2025).
[55] Ruizhe Zhang, Guoming Wang, and Peter Johnson, "Computing Ground State Properties with Early Fault-Tolerant Quantum Computers", Quantum 6, 761 (2022).
[56] Yuki Ito, Hitomi Mori, Kazuki Sakamoto, and Keisuke Fujii, "Polynomial time constructive decision algorithm for multivariable quantum signal processing", Quantum 10, 2102 (2026).
[57] Ajinkya Borle, Vincent Elfving, and Samuel J. Lomonaco, "Quantum approximate optimization for hard problems in linear algebra", SciPost Physics Core 4 4, 031 (2021).
[58] Maria-Andreea Filip and Nathan Fitzpatrick, "Beyond asymptotic reasoning: the practicalities of a quantum ground state projector based on the wall-Chebyshev expansion", Quantum Science and Technology 11 1, 015027 (2026).
[59] Jin-Peng Liu, Dong An, Di Fang, Jiasu Wang, Guang Hao Low, and Stephen Jordan, "Efficient Quantum Algorithm for Nonlinear Reaction–Diffusion Equations and Energy Estimation", Communications in Mathematical Physics 404 2, 963 (2023).
[60] Shantanav Chakraborty, "Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers", Quantum 8, 1496 (2024).
[61] Yuan Su, Hsin-Yuan Huang, and Earl T. Campbell, "Nearly tight Trotterization of interacting electrons", Quantum 5, 495 (2021).
[62] Chelsea A. Williams, Antonio A. Gentile, Vincent E. Elfving, Daniel Berger, and Oleksandr Kyriienko, "Quantum Iterative Methods for Solving Differential Equations with Application to Computational Fluid Dynamics", Advanced Quantum Technologies 9 2, e00618 (2026).
[63] Erenay Karacan, Yanbin Chen, and Christian B. Mendl, "Enhancing Scalability of Quantum Eigenvalue Transformation of Unitary Matrices for Ground State Preparation through Adaptive Finer Filtering", Quantum 9, 1624 (2025).
[64] Yulong Dong and Lin Lin, "Random circuit block-encoded matrix and a proposal of quantum LINPACK benchmark", Physical Review A 103 6, 062412 (2021).
[65] Yulong Dong, Xiang Meng, K. Birgitta Whaley, and Lin Lin, "Efficient phase-factor evaluation in quantum signal processing", Physical Review A 103 4, 042419 (2021).
[66] Jintai Ding, Vlad Gheorghiu, András Gilyén, Sean Hallgren, and Jianqiang Li, "Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems", Quantum 7, 1069 (2023).
[67] Changpeng Shao and Ashley Montanaro, "Faster Quantum-inspired Algorithms for Solving Linear Systems", ACM Transactions on Quantum Computing 3 4, 1 (2022).
[68] Tyler Kharazi, Ahmad M. Alkadri, Jin-Peng Liu, Kranthi K. Mandadapu, and K. Birgitta Whaley, "Explicit block encodings of boundary value problems for many-body elliptic operators", Quantum 9, 1764 (2025).
[69] Chao Lu, Muralikrishnan Gopalakrishnan Meena, Antigoni Georgiadou, Kalyana Chakravarthi Gottiparthi, Michael Sandoval, Eduardo Antonio Coello Pérez, Paul Lin, In-Saeng Suh, Seongmin Kim, and Alessandro Baroni, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 180 (2025) ISBN:979-8-3315-5736-2.
[70] Dong An, Andrew M. Childs, and Lin Lin, "Quantum Algorithm for Linear Non-unitary Dynamics with Near-Optimal Dependence on All Parameters", Communications in Mathematical Physics 407 1, 19 (2026).
[71] Chelsea A. Williams, Annie E. Paine, Antonio A. Gentile, Daniel Berger, and Oleksandr Kyriienko, "Vortex detection from quantum data", Physical Review A 112 6, 062409 (2025).
[72] Guang Hao Low and Yuan Su, "Quantum Eigenvalue Processing", 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) 1051 (2024) ISBN:979-8-3315-1674-1.
[73] John M. Martyn and Patrick Rall, "Halving the cost of quantum algorithms with randomization", npj Quantum Information 11 1, 47 (2025).
[74] Xinchi Huang, Hirofumi Nishi, Yoshifumi Kawada, Tomofumi Zushi, and Yu-ichiro Matsushita, "Fourier space readout method for efficiently recovering functions encoded in quantum states", Quantum Science and Technology 11 3, 035050 (2026).
[75] 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).
[76] Oriel Kiss, Utkarsh Azad, Borja Requena, Alessandro Roggero, David Wakeham, and Juan Miguel Arrazola, "Early Fault-Tolerant Quantum Algorithms in Practice: Application to Ground-State Energy Estimation", Quantum 9, 1682 (2025).
[77] 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).
[78] Parikshit Pareek, Abhijith Jayakumar, Carleton Coffrin, and Sidhant Misra, "Limitations of Fault-Tolerant Quantum Linear System Solvers for Quantum Power Flow", IEEE Transactions on Power Systems 41 2, 811 (2026).
[79] Sasan Moradi, "Hybrid classical-quantum computation of heat diffusion in multilayer materials", (2025).
[80] William J. Huggins and Jarrod R. McClean, "Accelerating Quantum Algorithms with Precomputation", Quantum 8, 1264 (2024).
[81] Tyler Kharazi, Torin F. Stetina, Liwen Ko, Guang Hao Low, and K. Birgitta Whaley, "An efficient quantum algorithm for ab initio approximations of non-linear response functions", npj Quantum Information 11 1, 98 (2025).
[82] Lin Lin, "Dissipative preparation of many-body quantum states: Toward practical quantum advantage", APL Computational Physics 1 1, 010901 (2025).
[83] Chukwudubem Umeano, Stefano Scali, and Oleksandr Kyriienko, "Quantum community detection via deterministic elimination", Physical Review A 112 5, 052422 (2025).
[84] Dong An and Konstantina Trivisa, "Quantum algorithms for linear and non-linear fractional reaction-diffusion equations", Quantum 10, 1969 (2026).
[85] Thomas D. Cohen and Hyunwoo Oh, "Corrections to adiabatic behavior for long paths", Physical Review A 110 6, 062601 (2024).
[86] Manqoba Q. Hlatshwayo, Manav Babel, Dalila Islas-Sanchez, and Konstantinos Georgopoulos, "A Technical Review of Quantum Computing Use Cases for Finance and Economics", Quantum Reports 8 1, 26 (2026).
[87] Xian Lu, Xinying Li, Yongmei Li, Xin Yi, Shuai Hou, and Chengkang Pan, 2025 IEEE 4th International Conference on Computing, Communication, Perception and Quantum Technology (CCPQT) 1 (2025) ISBN:979-8-3315-2583-5.
[88] Yulong Dong, K. Birgitta Whaley, and Lin Lin, "A quantum hamiltonian simulation benchmark", npj Quantum Information 8 1, 131 (2022).
[89] Dong An, Jin-Peng Liu, Daochen Wang, and Qi Zhao, "Quantum Differential Equation Solvers: Limitations and Fast-Forwarding", Communications in Mathematical Physics 406 8, 189 (2025).
[90] Oleksandr Kyriienko, Annie E. Paine, and Vincent E. Elfving, "Solving nonlinear differential equations with differentiable quantum circuits", Physical Review A 103 5, 052416 (2021).
[91] Zane M. Rossi and Isaac L. Chuang, "Semantic embedding for quantum algorithms", Journal of Mathematical Physics 64 12, 122202 (2023).
[92] Elise Fressart, Michel Nowak, and Nicole Spillane, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 312 (2025) ISBN:979-8-3315-5736-2.
[93] Shantanav Chakraborty, Aditya Morolia, and Anurudh Peduri, "Quantum Regularized Least Squares", Quantum 7, 988 (2023).
[94] Bujiao Wu, Maharshi Ray, Liming Zhao, Xiaoming Sun, and Patrick Rebentrost, "Quantum-classical algorithms for skewed linear systems with an optimized Hadamard test", Physical Review A 103 4, 042422 (2021).
[95] Haoya Li, Hongkang Ni, and Lexing Ying, "On efficient quantum block encoding of pseudo-differential operators", Quantum 7, 1031 (2023).
[96] Alexandra. V Volosova, 2024 6th International Youth Conference on Radio Electronics, Electrical and Power Engineering (REEPE) 1 (2024) ISBN:979-8-3503-8289-1.
[97] Dong An, Andrew M. Childs, Lin Lin, and Lexing Ying, "Laplace Transform–Based Quantum Eigenvalue Transformation via Linear Combination of Hamiltonian Simulation", SIAM Journal on Computing 55 2, 376 (2026).
[98] Papagiannis Nikos and Vavalis Manolis, "On Quantum Solvers for Linear Algebraic Systems", Quantum Information & Computation 25 6, 640 (2025).
[99] Sander Gribling, Iordanis Kerenidis, and Dániel Szilágyi, "An Optimal Linear-combination-of-unitaries-based Quantum Linear System Solver", ACM Transactions on Quantum Computing 5 2, 1 (2024).
[100] Zhong-Xia Shang, Naixu Guo, Dong An, and Qi Zhao, "Designing a Nearly Optimal Quantum Algorithm for Linear Differential Equations via Lindbladians", Physical Review Letters 135 12, 120604 (2025).
[101] Alexander M. Dalzell, B. David Clader, Grant Salton, Mario Berta, Cedric Yen-Yu Lin, David A. Bader, Nikitas Stamatopoulos, Martin J. A. Schuetz, Fernando G. S. L. Brandão, Helmut G. Katzgraber, and William J. Zeng, "End-To-End Resource Analysis for Quantum Interior-Point Methods and Portfolio Optimization", PRX Quantum 4 4, 040325 (2023).
[102] Yatian Wang, Hua Xiang, and Songling Zhang, "Quantum algorithm for matrix logarithm by integral formula", Quantum Information Processing 22 1, 76 (2023).
[103] Nikitas Stamatopoulos and William J. Zeng, "Derivative Pricing using Quantum Signal Processing", Quantum 8, 1322 (2024).
[104] Samson Wang, Sam McArdle, and Mario Berta, "Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra", PRX Quantum 5 2, 020324 (2024).
[105] Mauro E. S. Morales, Lirandë Pira, Philipp Schleich, Kelvin Koor, Pedro C. S. Costa, Dong An, Alán Aspuru-Guzik, Lin Lin, Patrick Rebentrost, and Dominic W. Berry, "Quantum linear system solvers: A survey of algorithms and applications", Reviews of Modern Physics 98 2, 025005 (2026).
[106] András Gilyén, Matthew B. Hastings, and Umesh Vazirani, Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing 1357 (2021) ISBN:9781450380539.
[107] Lingxia Cui, Zongmin Wu, and Hua Xiang, "Quantum radial basis function method for the Poisson equation", Journal of Physics A: Mathematical and Theoretical 56 22, 225303 (2023).
[108] Ronald de Wolf, "Quantum Computing: Lecture Notes", arXiv:1907.09415, (2019).
[109] 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).
[110] Pablo Arnault, Pablo Arrighi, Steven Herbert, Evi Kasnetsi, and Tianyi Li, "A typology of quantum algorithms", arXiv:2407.05178, (2024).
[111] John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang, "Grand Unification of Quantum Algorithms", PRX Quantum 2 4, 040203 (2021).
[112] Ivan Novikau and Ilon Joseph, "Globalizing the Carleman linear embedding method for nonlinear dynamics", arXiv:2510.15715, (2025).
[113] Tobias Rohe, Federico Harjes Ruiloba, Sabrina Egger, Sebastian von Beck, Jonas Stein, and Claudia Linnhoff-Popien, "Quantum Computer Benchmarking: An Explorative Systematic Literature Review", arXiv:2509.03078, (2025).
[114] Shantanav Chakraborty, Soumyabrata Hazra, Tongyang Li, Changpeng Shao, Xinzhao Wang, and Yuxin Zhang, "Quantum singular value transformation without block encodings: Near-optimal complexity with minimal ancilla", arXiv:2504.02385, (2025).
[115] Alexander M. Dalzell, "A shortcut to an optimal quantum linear system solver", arXiv:2406.12086, (2024).
[116] Francisca Vasconcelos and András Gilyén, "Methods for Reducing Ancilla-Overhead in Block Encodings", arXiv:2507.07900, (2025).
[117] Zhenning Liu, Xiantao Li, Chunhao Wang, and Jin-Peng Liu, "Toward end-to-end quantum simulation for protein dynamics", arXiv:2411.03972, (2024).
[118] Xinchi Huang, Hirofumi Nishi, Taichi Kosugi, Yoshifumi Kawada, and Yu-ichiro Matsushita, "A probabilistic imaginary-time evolution quantum algorithm for advection-diffusion equation: Explicit gate-level implementation and comparisons to quantum linear system algorithms", arXiv:2409.18559, (2024).
[119] Tyler Kharazi, Torin F. Stetina, Liwen Ko, Guang Hao Low, and K. Birgitta Whaley, "An efficient quantum algorithm for generation of ab initio n-th order susceptibilities for non-linear spectroscopies", arXiv:2404.01454, (2024).
[120] András Gilyén and Alexander Poremba, "Improved Quantum Algorithms for Fidelity Estimation", arXiv:2203.15993, (2022).
[121] Songqinghao Yang and Jin-Peng Liu, "Circuit-Efficient Randomized Quantum Simulation of Non-Unitary Dynamics with Observable-Driven and Symmetry-Aware Designs", arXiv:2509.08030, (2025).
[122] Matthias Deiml and Daniel Peterseim, "Constrained Optimal Polynomials for Quantum Linear System Solvers", arXiv:2604.20513, (2026).
[123] Jonas Stein, Jannis Lutz, Moritz Sölderer, Maximilian Adler, Michael Lachner, David Bucher, and Claudia Linnhoff-Popien, "End-to-End Speedup for Quantum Simulation-Based Optimization in Power Grid Management", arXiv:2505.16444, (2025).
[124] Sam McArdle, András Gilyén, and Mario Berta, "A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits", arXiv:2209.12887, (2022).
[125] Loïc Balazi, Matthias Deiml, and Daniel Peterseim, "Quantum Enhanced Numerical Homogenization", arXiv:2603.28521, (2026).
[126] Jinghong Yang, Christopher F. Kane, and Shabnam Jabeen, "Tightening energy-based boson truncation bound using Monte Carlo-assisted methods", arXiv:2604.24896, (2026).
[127] S. E. Skelton, "Mostly Harmless Methods for QSP-Processing with Laurent Polynomials", arXiv:2408.04321, (2024).
[128] András Gilyén and Umesh Vazirani, "(Sub)Exponential advantage of adiabatic quantum computation with no sign problem", arXiv:2011.09495, (2020).
[129] Koichi Miyamoto, "Quantum algorithm for solving high-dimensional linear stochastic differential equations via amplitude encoding of the noise term", arXiv:2604.24133, (2026).
[130] Xinchi Huang, Hirofumi Nishi, Yoshifumi Kawada, Tomofumi Zushi, and Yu-ichiro Matsushita, "Real and Fourier space readout methods: Comparison of complexity and applications to CFD problems", arXiv:2511.20017, (2025).
[131] Kianna Wan and Isaac H. Kim, "Fast digital methods for adiabatic state preparation", arXiv:2004.04164, (2020).
[132] Haoya Li, Hongkang Ni, and Lexing Ying, "On efficient quantum block encoding of pseudo-differential operators", arXiv:2301.08908, (2023).
[133] Elise Fressart, Michel Nowak, and Nicole Spillane, "Quantum Domain Decomposition for Preconditioning the Finite Element Method", arXiv:2605.26090, (2026).
[134] Pierre-Antoine Bernard and Nathan Wiebe, "Analytical Angle-Finding and Series Expansions for Quantum Signal Processing via Orthogonal Polynomial Theory", arXiv:2605.05321, (2026).
[135] Keita Kanno, Kazumasa Ueno, Hayato Higuchi, Morimasa Okamoto, Yuya Yoshizuru, Ryoya Ishimaru, Towa Takagi, and Kentaro Sakamoto, "Explicit Quantum Circuit Simulation of Nonlinear 1-Dimensional Fluid with Carleman-linearized Boltzmann Method", arXiv:2606.12770, (2026).
[136] Srushti Patil and Nina Glaser, "Efficient targeting of arbitrary excited states with quantum inverse power iteration through filtering polynomials", arXiv:2606.28255, (2026).
[137] Alexander M. Dalzell, Jianqiang Li, and Yuan Su, "Faster quantum linear system solver beyond the condition number", arXiv:2607.07691, (2026).
The above citations are from Crossref's cited-by service (last updated successfully 2026-08-10 14:46:22) and SAO/NASA ADS (last updated successfully 2026-08-10 14:46:27). The list may be incomplete as not all publishers provide suitable and complete citation data.
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.
Pingback: Optimal polynomial based quantum eigenstate filtering - Swiss Quantum Hub