- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review A

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Randomization accelerating series-truncated quantum algorithms

Yue Wang and Qi Zhao*

  • Department of Computer Science, School of Computing and Data Science, University of Hong Kong, Pokfulam Road, Hong Kong, China

  • *Contact author: zhaoqi@cs.hku.hk
PDF

Phys. Rev. A 113, 042423 – Published 9 April, 2026

DOI: https://doi.org/10.1103/5bbv-wr5n

Abstract

Quantum algorithms typically demand prohibitively complex circuits to solve practical problems. Previous studies have shown that classical randomness can accelerate some specific quantum algorithms. In this work, we introduce the randomized truncated series (RTS), which enables all quantum algorithms relying on truncated series approximations to enjoy such acceleration. RTS offers twofold accelerations: it quadratically suppresses truncation errors and allows continuous adjustment of the effective truncation order. By leveraging random mixing between two quantum circuits, RTS ensures that their probabilistic combination accurately realizes the desired algorithm, while significantly reducing the average circuit size. We demonstrate the versatility of RTS through concrete applications. Our results shed light on a path toward practical quantum advantage.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (58)

  1. S. Lloyd, Universal quantum simulators, Science 273, 1073 (1996).
  2. G. H. Low and I. L. Chuang, Hamiltonian simulation by qubitization, Quantum 3, 163 (2019).
  3. G. H. Low, Quantum signal processing by single-qubit dynamics, Ph.D. thesis, Massachusetts Institute of Technology (2017).
  4. 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, 090502 (2015).
  5. A. M. Childs, A. Ostrander, and Y. Su, Faster quantum simulation by randomization, Quantum 3, 182 (2019).
  6. A. M. Childs and Y. Su, Nearly optimal lattice simulation by product formulas, Phys. Rev. Lett. 123, 050503 (2019).
  7. Q. Zhao, Y. Zhou, A. F. Shaw, T. Li, and A. M. Childs, Hamiltonian simulation with random inputs, Phys. Rev. Lett. 129, 270502 (2022).
  8. D. W. Berry, A. M. Childs, A. Ostrander, and G. Wang, Quantum algorithm for linear differential equations with exponentially improved dependence on precision, Commun. Math. Phys. 356, 1057 (2017).
  9. J.-P. Liu, H. Ø. Kolden, H. K. Krovi, N. F. Loureiro, K. Trivisa, and A. M. Childs, Efficient quantum algorithm for dissipative nonlinear differential equations, Proc. Natl. Acad. Sci. USA 118, e2026805118 (2021).
  10. D. An and L. Lin, Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm, ACM Trans. Quantum Comput. 3, 1 (2022).
  11. D. An, J.-P. Liu, D. Wang, and Q. Zhao, A theory of quantum differential equation solvers: Limitations and fast-forwarding, Commun. Math. Phys. 406, 189 (2025).
  12. H. Krovi, Improved quantum algorithms for linear and nonlinear differential equations, Quantum 7, 913 (2023).
  13. D. Fang, L. Lin, and Y. Tong, Time-marching based quantum solvers for time-dependent linear differential equations, Quantum 7, 955 (2023).
  14. A. Gilyén, Y. Su, G. H. Low, and N. Wiebe, in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (2019), pp. 193–204.
  15. C. Sünderhauf, Generalized quantum singular value transformation, arXiv:2312.00723.
  16. J. M. Martyn, Z. M. Rossi, A. K. Tan, and I. L. Chuang, Grand unification of quantum algorithms, PRX Quantum 2, 040203 (2021).
  17. D. A. Lidar and H. Wang, Calculating the thermal rate constant with exponential speedup on a quantum computer, Phys. Rev. E 59, 2429 (1999).
  18. G. Ortiz, J. E. Gubernatis, E. Knill, and R. Laflamme, Quantum algorithms for fermionic simulations, Phys. Rev. A 64, 022319 (2001).
  19. D. Wecker, B. Bauer, B. K. Clark, M. B. Hastings, and M. Troyer, Gate-count estimates for performing quantum chemistry on small quantum computers, Phys. Rev. A 90, 022305 (2014).
  20. R. Babbush, C. Gidney, D. W. Berry, N. Wiebe, J. McClean, A. Paler, A. Fowler, and H. Neven, Encoding electronic spectra in quantum circuits with linear T complexity, Phys. Rev. X 8, 041015 (2018).
  21. 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, 011044 (2018).
  22. S. McArdle, S. Endo, A. Aspuru-Guzik, S. C. Benjamin, and X. Yuan, Quantum computational chemistry, Rev. Mod. Phys. 92, 015003 (2020).
  23. P. C. S. Costa, S. Jordan, and A. Ostrander, Quantum algorithm for simulating the wave equation, Phys. Rev. A 99, 012323 (2019).
  24. J. Haah, M. B. Hastings, R. Kothari, and G. H. Low, Quantum algorithm for simulating real time evolution of lattice Hamiltonians, SIAM J. Comput. 52, FOCS18-250 (2023).
  25. K. Mizuta and K. Fujii, Optimal Hamiltonian simulation for time-periodic systems, Quantum 7, 962 (2023).
  26. P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput. 26, 1484 (1997).
  27. X. Li, X. Yin, N. Wiebe, J. Chun, G. K. Schenter, M. S. Cheung, and J. Mülmenstädt, Potential quantum advantage for simulation of fluid dynamics, Phys. Rev. Res. 7, 013036 (2025).
  28. A. Ameri, E. Ye, P. Cappellaro, H. Krovi, and N. F. Loureiro, Quantum algorithm for the linear Vlasov equation with collisions, Phys. Rev. A 107, 062412 (2023).
  29. N. Linden, A. Montanaro, and C. Shao, Quantum vs. classical algorithms for solving the heat equation, Commun. Math. Phys. 395, 601 (2022).
  30. D. Herman, C. Googin, X. Liu, A. Galda, I. Safro, Y. Sun, M. Pistoia, and Y. Alexeev, Quantum computing for Finance, Nat. Rev. Phys. 5, 450 (2023).
  31. D. Stilck França and R. Garcia-Patron, Limitations of optimization algorithms on noisy quantum devices, Nat. Phys. 17, 1221 (2021).
  32. Y. Zhou, E. M. Stoudenmire, and X. Waintal, What limits the simulation of quantum computers? Phys. Rev. X 10, 041038 (2020).
  33. E. Campbell, Random compiler for fast Hamiltonian simulation, Phys. Rev. Lett. 123, 070503 (2019).
  34. K. Wan, M. Berta, and E. T. Campbell, Randomized quantum algorithm for statistical phase estimation, Phys. Rev. Lett. 129, 030503 (2022).
  35. Y. Yang, B.-N. Lu, and Y. Li, Accelerated quantum Monte Carlo with mitigated error on noisy quantum computer, PRX Quantum 2, 040361 (2021).
  36. P. Zeng, J. Sun, L. Jiang, and Q. Zhao, Simple and high-precision Hamiltonian simulation by compensating Trotter error with linear combination of unitary operations, PRX Quantum 6, 010359 (2025).
  37. E. Granet and H. Dreyer, Hamiltonian dynamics on digital quantum computers without discretization error, npj Quantum Inf. 10, 82 (2024).
  38. C.-H. Cho, D. W. Berry, and M.-H. Hsieh, Doubling the order of approximation via the randomized product formula, Phys. Rev. A 109, 062431 (2024).
  39. E. Campbell, Shorter gate sequences for quantum computing by mixing unitaries, Phys. Rev. A 95, 042306 (2017).
  40. M. B. Hastings, Turning gate synthesis errors into incoherent errors, Quantum Inf. Comput. 17, 488 (2017).
  41. M. Reiher, N. Wiebe, K. M. Svore, D. Wecker, and M. Troyer, Elucidating reaction mechanisms on quantum computers, Proc. Natl. Acad. Sci. USA 114, 7555 (2017).
  42. 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. USA 115, 9456 (2018).
  43. R. Kothari, Efficient algorithms in quantum query complexity, Ph.D. thesis, University of Waterloo (2014).
  44. D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, in Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing (2014), pp. 283–292.
  45. A. M. Childs and N. Wiebe, Hamiltonian simulation using linear combinations of unitary operations, Quantum Inf. Comput. 12, 901 (2012).
  46. 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 (2017).
  47. M. Abramowitz, I. A. Stegun, and R. H. Romer, Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables (U.S. Department of Commerce, 1988).
  48. D. Nagaj, P. Wocjan, and Y. Zhang, Fast amplification of QMA, Quantum Inf. Comput. 9, 1053 (2009).
  49. R. D. Somma and S. Boixo, Spectral gap amplification, SIAM J. Comput. 42, 593 (2013).
  50. D. W. Berry, High-order quantum algorithm for solving linear differential equations, J. Phys. A: Math. Theor. 47, 105301 (2014).
  51. J.-P. Liu and L. Lin, Dense outputs from quantum simulations, J. Comput. Phys. 514, 113213 (2024).
  52. J. Jiang, X. Sun, S.-H. Teng, B. Wu, K. Wu, and J. Zhang, Optimal space-depth trade-off of cnot circuits in quantum logic synthesis, in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SIAM, Philadelphia, PA, 2020), pp. 213–229.
  53. D. An, J.-P. Liu, and L. Lin, Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost, Phys. Rev. Lett. 131, 150603 (2023).
  54. D. An, A. M. Childs, and L. Lin, Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters, Commun. Math. Phys. 407, 19 (2026).
  55. G. H. Low and Y. Su, Quantum eigenvalue processing, SIAM J. Comput. 55, 135 (2026).
  56. G. H. Low and N. Wiebe, Hamiltonian simulation in the interaction picture, arXiv:1805.00675.
  57. L. Clinton, T. Cubitt, B. Flynn, F. M. Gambetta, J. Klassen, A. Montanaro, S. Piddock, R. A. Santos, and E. Sheridan, Towards near-term quantum simulation of materials, Nat. Commun. 15, 211 (2024).
  58. J. M. Martyn and P. Rall, Halving the cost of quantum algorithms with randomization, npj Quantum Inf. 11, 47 (2025).

Outline

Information

Phys. Rev. A 113, 042423– Published 9 April, 2026
  • Received 4 September 2024
  • Revised 12 March 2026
  • Accepted 20 March 2026
Crossmark - Check for updates button

©2026 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation