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] Oleksandr Kyriienko, Annie E. Paine, and Vincent E. Elfving, "Solving nonlinear differential equations with differentiable quantum circuits", Physical Review A 103 5, 052416 (2021).
[2] Ruizhe Zhang, Guoming Wang, and Peter Johnson, "Computing Ground State Properties with Early Fault-Tolerant Quantum Computers", Quantum 6, 761 (2022).
[3] Lin Lin and Yu Tong, "Near-optimal ground state preparation", Quantum 4, 372 (2020).
[4] Zane M. Rossi and Isaac L. Chuang, "Semantic embedding for quantum algorithms", Journal of Mathematical Physics 64 12, 122202 (2023).
[5] Ajinkya Borle, Vincent Elfving, and Samuel J. Lomonaco, "Quantum approximate optimization for hard problems in linear algebra", SciPost Physics Core 4 4, 031 (2021).
[6] Jiasu Wang, Yulong Dong, and Lin Lin, "On the energy landscape of symmetric quantum signal processing", Quantum 6, 850 (2022).
[7] Lin Lin and Yu Tong, "Heisenberg-Limited Ground-State Energy Estimation for Early Fault-Tolerant Quantum Computers", PRX Quantum 3 1, 010318 (2022).
[8] 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).
[9] Shantanav Chakraborty, Aditya Morolia, and Anurudh Peduri, "Quantum Regularized Least Squares", Quantum 7, 988 (2023).
[10] 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).
[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] Yuan Su, Hsin-Yuan Huang, and Earl T. Campbell, "Nearly tight Trotterization of interacting electrons", Quantum 5, 495 (2021).
[13] Di Fang, Lin Lin, and Yu Tong, "Time-marching based quantum solvers for time-dependent linear differential equations", Quantum 7, 955 (2023).
[14] Hari Krovi, "Improved quantum algorithms for linear and nonlinear differential equations", Quantum 7, 913 (2023).
[15] Haoya Li, Hongkang Ni, and Lexing Ying, "On efficient quantum block encoding of pseudo-differential operators", Quantum 7, 1031 (2023).
[16] Alexandra. V Volosova, 2024 6th International Youth Conference on Radio Electronics, Electrical and Power Engineering (REEPE) 1 (2024) ISBN:979-8-3503-8289-1.
[17] Yulong Dong and Lin Lin, "Random circuit block-encoded matrix and a proposal of quantum LINPACK benchmark", Physical Review A 103 6, 062412 (2021).
[18] 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).
[19] 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).
[20] 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).
[21] 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).
[22] Changpeng Shao and Ashley Montanaro, "Faster Quantum-inspired Algorithms for Solving Linear Systems", ACM Transactions on Quantum Computing 3 4, 1 (2022).
[23] Daan Camps and Roel Van Beeumen, 2022 IEEE International Conference on Quantum Computing and Engineering (QCE) 104 (2022) ISBN:978-1-6654-9113-6.
[24] 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).
[25] 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).
[26] 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).
[27] 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).
[28] Yatian Wang, Hua Xiang, and Songling Zhang, "Quantum algorithm for matrix logarithm by integral formula", Quantum Information Processing 22 1, 76 (2023).
[29] 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).
[30] 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).
[31] 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).
[32] Zane M. Rossi and Isaac L. Chuang, "Quantum hypothesis testing with group structure", Physical Review A 104 1, 012425 (2021).
[33] 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).
[34] Matthew Thibodeau and Bryan K. Clark, "Nearly-frustration-free ground state preparation", Quantum 7, 1084 (2023).
[35] William J. Huggins and Jarrod R. McClean, "Accelerating Quantum Algorithms with Precomputation", Quantum 8, 1264 (2024).
[36] Nikitas Stamatopoulos and William J. Zeng, "Derivative Pricing using Quantum Signal Processing", Quantum 8, 1322 (2024).
[37] Samson Wang, Sam McArdle, and Mario Berta, "Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra", PRX Quantum 5 2, 020324 (2024).
[38] 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).
[39] Sevag Gharibian and François Le Gall, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing 19 (2022) ISBN:9781450392648.
[40] Zane M. Rossi and Isaac L. Chuang, "Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle", Quantum 6, 811 (2022).
[41] 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).
[42] 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).
[43] 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).
[44] 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.
[45] Yulong Dong, K. Birgitta Whaley, and Lin Lin, "A quantum hamiltonian simulation benchmark", npj Quantum Information 8 1, 131 (2022).
[46] 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).
[47] 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).
[48] John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang, "Grand Unification of Quantum Algorithms", PRX Quantum 2 4, 040203 (2021).
[49] Ronald de Wolf, "Quantum Computing: Lecture Notes", arXiv:1907.09415, (2019).
[50] Dong An, Jin-Peng Liu, Daochen Wang, and Qi Zhao, "A theory of quantum differential equation solvers: limitations and fast-forwarding", arXiv:2211.05246, (2022).
[51] András Gilyén and Alexander Poremba, "Improved Quantum Algorithms for Fidelity Estimation", arXiv:2203.15993, (2022).
[52] Kianna Wan and Isaac H. Kim, "Fast digital methods for adiabatic state preparation", arXiv:2004.04164, (2020).
[53] Dong An, Andrew M. Childs, and Lin Lin, "Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters", arXiv:2312.03916, (2023).
[54] 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).
[55] András Gilyén and Umesh Vazirani, "(Sub)Exponential advantage of adiabatic quantum computation with no sign problem", arXiv:2011.09495, (2020).
[56] Haoya Li, Hongkang Ni, and Lexing Ying, "On efficient quantum block encoding of pseudo-differential operators", arXiv:2301.08908, (2023).
The above citations are from Crossref's cited-by service (last updated successfully 2024-05-24 15:21:01) and SAO/NASA ADS (last updated successfully 2024-05-24 15:21:02). 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