Product Decomposition of Periodic Functions in Quantum Signal Processing

Jeongwan Haah

doi:10.22331/q-2019-10-07-190

Product Decomposition of Periodic Functions in Quantum Signal Processing

Microsoft Quantum and Microsoft Research, Redmond, Washington, USA

Published:	2019-10-07, volume 3, page 190
Eprint:	arXiv:1806.10236v4
Doi:	https://doi.org/10.22331/q-2019-10-07-190
Citation:	Quantum 3, 190 (2019).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Updated after initial publication: This publication was updated to version v4 after the initial publication. The authors left the following comment on the arXiv:

22 pages, (v2) numerical experiment result, clarifications and minor fixes, (v3) removed the need of distinguishing real roots from nonreal ones, and elaborated the error analysis (v4) footnote added. An implementation available at this https URL

Abstract

We consider an algorithm to approximate complex-valued periodic functions $f(e^{i\theta})$ as a matrix element of a product of $SU(2)$-valued functions, which underlies so-called quantum signal processing. We prove that the algorithm runs in time $\mathcal O(N^3 \mathrm{polylog}(N/\epsilon))$ under the random-access memory model of computation where $N$ is the degree of the polynomial that approximates $f$ with accuracy $\epsilon$; previous efficiency claim assumed a strong arithmetic model of computation and lacked numerical stability analysis.

► BibTeX data

@article{Haah2019product,
  doi = {10.22331/q-2019-10-07-190},
  url = {https://doi.org/10.22331/q-2019-10-07-190},
  title = {Product {D}ecomposition of {P}eriodic {F}unctions in {Q}uantum {S}ignal {P}rocessing},
  author = {Haah, Jeongwan},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {3},
  pages = {190},
  month = oct,
  year = {2019}
}

► References

[1] G. H. Low and I. L. Chuang, ``Optimal Hamiltonian simulation by quantum signal processing,'' Phys. Rev. Lett. 118, 010501 (2017), arXiv:1606.02685.
https://doi.org/10.1103/PhysRevLett.118.010501
arXiv:1606.02685

[2] G. H. Low, T. J. Yoder, and I. L. Chuang, ``Methodology of resonant equiangular composite quantum gates,'' Phys. Rev. X 6, 041067 (2016), arXiv:1603.03996.
https://doi.org/10.1103/PhysRevX.6.041067
arXiv:1603.03996

[3] G. H. Low and I. L. Chuang, ``Hamiltonian simulation by Qubitization,'' Quantum 3, 163 (2019), arXiv:1610.06546.
https://doi.org/10.22331/q-2019-07-12-163
arXiv:1610.06546

[4] A. Gilyén, Y. Su, G. H. Low, and N. Wiebe, ``Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics,'' in STOC 2019 Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (2019) pp. 193–204, arXiv:1806.01838.
https://doi.org/10.1145/3313276.3316366
arXiv:1806.01838

[5] A. M. Childs and N. Wiebe, ``Hamiltonian simulation using linear combinations of unitary operations,'' Quantum Information and Computation 12, 901–924 (2012), arXiv:1202.5822.
arXiv:1202.5822

[6] D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, ``Exponential improvement in precision for simulating sparse Hamiltonians,'' in Proceedings of the 46th ACM Symposium on Theory of Computing (STOC) (2014) pp. 283–292, arXiv:1312.1414.
https://doi.org/10.1145/2591796.2591854
arXiv:1312.1414

[7] A. M. Childs, D. Maslov, Y. Nam, N. J. Ross, and Y. Su, ``Toward the first quantum simulation with quantum speedup,'' Proceedings of the National Academy of Sciences 115, 9456–9461 (2018), arXiv:1711.10980.
https://doi.org/10.1073/pnas.1801723115
arXiv:1711.10980

[8] J. Haah, M. Hastings, R. Kothari, and G. H. Low, ``Quantum algorithm for simulating real time evolution of lattice hamiltonians,'' in 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) (2018) pp. 350–360.
https://doi.org/10.1109/FOCS.2018.00041

[9] A. W. Harrow, A. Hassidim, and S. Lloyd, ``Quantum algorithm for solving linear systems of equations,'' Phys. Rev. Lett. 15, 150502 (2009), arXiv:0811.3171.
https://doi.org/10.1103/PhysRevLett.103.150502
arXiv:0811.3171

[10] A. Shamir, ``Factoring numbers in $O(\log n)$ arithmetic steps,'' Information Processing Letters 8, 28–31 (1979).
https://doi.org/10.1016/0020-0190(79)90087-5

[11] A. Schönhage, ``On the power of random access machines,'' in Automata, Languages and Programming. ICALP 1979. Lecture Notes in Computer Science,, Vol. 71, edited by M. H.A. (Springer, Berlin, Heidelberg, 1979) pp. 520–529.
https://doi.org/10.1007/3-540-09510-1_42

[12] J. Qian and C. A. Wang, ``How much precision is needed to compare two sums of square roots of integers?'' Information Processing Letters 100, 194 – 198 (2006).
https://doi.org/10.1016/j.ipl.2006.05.002

[13] Q. Cheng, X. Meng, C. Sun, and J. Chen, ``Bounding the sum of square roots via lattice reduction,'' Math. Comp. 79, 1109–1122 (2010), arXiv:0905.4487.
https://doi.org/10.1090/S0025-5718-09-02304-7
arXiv:0905.4487

[14] G. H. Low and I. L. Chuang, ``Hamiltonian simulation by uniform spectral amplification,'' arXiv:1707.05391.
arXiv:1707.05391

[15] V. Y. Pan, ``Optimal and nearly optimal algorithms for approximating polynomial zeros,'' Computers & Mathematics with Applications 31, 97 – 138 (1996).
https://doi.org/10.1016/0898-1221(96)00080-6

[16] G. U. Ramos, ``Roundoff error analysis of the fast fourier transform,'' Mathematics of Computation 25, 757–768 (1971).
https://doi.org/10.2307/2004342

[17] D. Harvey and J. van der Hoeven, ``Faster integer multiplication using short lattice vectors,'' Open Book Series 2, 293–310 (2019), arXiv:1802.07932.
https://doi.org/10.2140/obs.2019.2.293
arXiv:1802.07932

[18] D. E. Knuth, The Art of Computer Programming, 3rd ed., Vol. 2 (Addison-Wesley, 1998).

[19] 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 (2015) pp. 792–809, arXiv:1501.01715.
https://doi.org/10.1109/FOCS.2015.54
arXiv:1501.01715

[20] A. M. Childs, ``On the relationship between continuous- and discrete-time quantum walk,'' Commun. Math. Phys. 294, 581–603 (2010), arXiv:0810.0312.
https://doi.org/10.1007/s00220-009-0930-1
arXiv:0810.0312

[21] D. W. Berry and A. M. Childs, ``Black-box hamiltonian simulation and unitary implementation,'' Quantum Information and Computation 12 (2012), arXiv:0910.4157.
arXiv:0910.4157

[22] J. P. Boyd, ``The rate of convergence of fourier coefficients for entire functions of infinite order with application to the weideman-cloot sinh-mapping for pseudospectral computations on an infinite interval,'' Journal of Computational Physics 110, 360 – 372 (1994).
https://doi.org/10.1006/jcph.1994.1032

[23] M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions (National Bureau of Standards, 1964).

[24] A. M. Childs, R. Kothari, and R. D. Somma, ``Quantum algorithm for systems of linear equations with exponentially improved dependence on precision,'' SIAM Journal on Computing 46, 1920–1950 (2017), arXiv:1511.02306.
https://doi.org/10.1137/16M1087072
arXiv:1511.02306

[25] L. K. Grover, ``A fast quantum mechanical algorithm for database search,'' in Proceedings, 28th Annual ACM Symposium on the Theory of Computing (STOC) (1996) pp. 212–219, arXiv:quant-ph/9605043.
https://doi.org/10.1145/237814.237866
arXiv:quant-ph/9605043

Cited by

[1] Jeongwan Haah, Matthew B. Hastings, Robin Kothari, and Guang Hao Low, "Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians", SIAM Journal on Computing 52 6, FOCS18-250 (2023).

[2] Rahul Sarkar and Theodore J. Yoder, "Density theorems with applications in quantum signal processing", Journal of Computational and Applied Mathematics 430, 115243 (2023).

[3] Yulong Dong and Lin Lin, "Random circuit block-encoded matrix and a proposal of quantum LINPACK benchmark", Physical Review A 103 6, 062412 (2021).

[4] Abhishek Rajput, Alessandro Roggero, and Nathan Wiebe, "Hybridized Methods for Quantum Simulation in the Interaction Picture", Quantum 6, 780 (2022).

[5] Andreea-Iulia Lefterovici, Michael Perk, Debora Ramacciotti, Antonio F. Rotundo, Shawn E. Skelton, and Martin Steinbach, "Beyond Asymptotic Scaling: Comparing Functional Quantum Linear Solvers", IEEE Transactions on Quantum Engineering 7, 1 (2026).

[6] Zane M. Rossi and Isaac L. Chuang, "Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle", Quantum 6, 811 (2022).

[7] Jiasu Wang, Yulong Dong, and Lin Lin, "On the energy landscape of symmetric quantum signal processing", Quantum 6, 850 (2022).

[8] S. E. Skelton, 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) 150 (2024) ISBN:979-8-3315-4137-8.

[9] Patrick Rall and Bryce Fuller, "Amplitude Estimation from Quantum Signal Processing", Quantum 7, 937 (2023).

[10] Nikitas Stamatopoulos and William J. Zeng, "Derivative Pricing using Quantum Signal Processing", Quantum 8, 1322 (2024).

[11] Lorenzo Laneve and Stefan Wolf, "On multivariate polynomials achievable with quantum signal processing", Quantum 9, 1641 (2025).

[12] Lin Lin and Yu Tong, "Near-optimal ground state preparation", Quantum 4, 372 (2020).

[13] Yuan Liu, Shraddha Singh, Kevin C. Smith, Eleanor Crane, John M. Martyn, Alec Eickbusch, Alexander Schuckert, Richard D. Li, Jasmine Sinanan-Singh, Micheline B. Soley, Takahiro Tsunoda, Isaac L. Chuang, Nathan Wiebe, and Steven M. Girvin, "Hybrid Oscillator-Qubit Quantum Processors: Instruction Set Architectures, Abstract Machine Models, and Applications", PRX Quantum 7 1, 010201 (2026).

[14] Lin Lin, Volume 7: Invited Lectures: Sections 15–20 57 (2026) ISBN:978-1-61197-872-8.

[15] Mudassir Moosa, Thomas W Watts, Yiyou Chen, Abhijat Sarma, and Peter L McMahon, "Linear-depth quantum circuits for loading Fourier approximations of arbitrary functions", Quantum Science and Technology 9 1, 015002 (2024).

[16] Hongkang Ni and Lexing Ying, "Fast Phase Factor Finding for Quantum Signal Processing", SIAM Journal on Scientific Computing 48 4, B651 (2026).

[17] S S Gayathri, R. Kumar, and Samiappan Dhanalakshmi, "Efficient Floating-point Division Quantum Circuit using Newton-Raphson Division", Journal of Physics: Conference Series 2335 1, 012058 (2022).

[18] Hugo Delavenne, François Le Gall, Yupan Liu, and Masayuki Miyamoto, "Quantum Merlin-Arthur proof systems for synthesizing quantum states", Quantum 9, 1688 (2025).

[19] Pablo A. M. Casares, Yanbing Zhou, Utkarsh Azad, Stepan Fomichev, Jack S. Baker, Chen Ling, Debasish Banerjee, Alain Delgado, and Juan Miguel Arrazola, "Quantum algorithms to identify optically detected magnetic resonance-active defects for quantum sensing applications", Physical Review A 113 5, 052454 (2026).

[20] Guang Hao Low and Isaac L. Chuang, "Hamiltonian Simulation by Qubitization", Quantum 3, 163 (2019).

[21] Zoe Holmes, Gopikrishnan Muraleedharan, Rolando D. Somma, Yigit Subasi, and Burak Şahinoğlu, "Quantum algorithms from fluctuation theorems: Thermal-state preparation", Quantum 6, 825 (2022).

[22] Danial Motlagh and Nathan Wiebe, "Generalized Quantum Signal Processing", PRX Quantum 5 2, 020368 (2024).

[23] S E Skelton, "von Neumann measurement and quantum phase estimation of block-encoded Hamiltonians", Quantum Science and Technology 11 3, 035014 (2026).

[24] Kaito Wada, Naoki Yamamoto, and Nobuyuki Yoshioka, "Heisenberg-Limited Adaptive Gradient Estimation for Multiple Observables", PRX Quantum 6 2, 020308 (2025).

[25] 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).

[26] Kevin J. Joven, Elin Ranjan Das, Joel Bierman, Aishwarya Majumdar, Masoud Hakimi Heris, and Yuan Liu, "Scalable quantum computational science: A perspective from block-encodings and polynomial transformations", APL Computational Physics 2 1, 010901 (2026).

[27] Muhammad Abdullah Ijaz and Muhammad Faryad, "Noise analysis of Grover and phase estimation algorithms implemented as quantum singular value transformations for a small number of noisy qubits", Scientific Reports 13 1, 20144 (2023).

[28] 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).

[29] Jasmine Sinanan-Singh, Gabriel L. Mintzer, Isaac L. Chuang, and Yuan Liu, "Single-shot Quantum Signal Processing Interferometry", Quantum 8, 1427 (2024).

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

[31] Yulong Dong, Lin Lin, and Yu Tong, "Ground-State Preparation and Energy Estimation on Early Fault-Tolerant Quantum Computers via Quantum Eigenvalue Transformation of Unitary Matrices", PRX Quantum 3 4, 040305 (2022).

[32] J.-T. Bu, Lei Zhang, Zhan Yu, Jing-Bo Wang, W.-Q. Ding, W.-F. Yuan, B. Wang, H.-J. Du, W.-J. Chen, L. Chen, J.-W. Zhang, J.-C. Li, F. Zhou, Xin Wang, and M. Feng, "Exploring the experimental limit of deep quantum signal processing using a trapped-ion simulator", Physical Review Applied 23 3, 034073 (2025).

[33] Yukun Zhang, Xiaoming Zhang, Jinzhao Sun, Heng Lin, Yifei Huang, Dingshun Lv, and Xiao Yuan, "Quantum Algorithms for Quantum Molecular Systems: A Survey", WIREs Computational Molecular Science 15 3, e70020 (2025).

[34] Koen Groenland, Freek Witteveen, Kareljan Schoutens, and Rene Gerritsma, "Signal processing techniques for efficient compilation of controlled rotations in trapped ions", New Journal of Physics 22 6, 063006 (2020).

[35] Yulong Dong, Lin Lin, Hongkang Ni, and Jiasu Wang, "Infinite quantum signal processing", Quantum 8, 1558 (2024).

[36] Yuki Ito, Hitomi Mori, Kazuki Sakamoto, and Keisuke Fujii, "Polynomial time constructive decision algorithm for multivariable quantum signal processing", Quantum 10, 2102 (2026).

[37] Lexing Ying, "Stable factorization for phase factors of quantum signal processing", Quantum 6, 842 (2022).

[38] Haoya Li, Hongkang Ni, and Lexing Ying, "On efficient quantum block encoding of pseudo-differential operators", Quantum 7, 1031 (2023).

[39] 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).

[40] Zheng Zhang and Minzhong Luo, Proceedings of the 23rd ACM International Conference on Computing Frontiers 133 (2026) ISBN:9798400725685.

[41] Eduard Grigoryan, Sachin Kumar, and Placido Rogério Pinheiro, "A Review on Models and Applications of Quantum Computing", Quantum Reports 7 3, 39 (2025).

[42] Youle Wang, "Resource-efficient quantum phase estimation by randomization", Quantum Science and Technology 10 3, 035036 (2025).

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

[44] Matthew Thibodeau and Bryan K. Clark, "Nearly-frustration-free ground state preparation", Quantum 7, 1084 (2023).

[45] Michel Alexis, Gevorg Mnatsakanyan, and Christoph Thiele, "Quantum signal processing and nonlinear Fourier analysis", Revista Matemática Complutense 37 3, 655 (2024).

[46] Yuta Kikuchi, Conor Mc Keever, Luuk Coopmans, Michael Lubasch, and Marcello Benedetti, "Realization of quantum signal processing on a noisy quantum computer", npj Quantum Information 9 1, 93 (2023).

[47] Bjorn K. Berntson and Christoph Sünderhauf, "Complementary Polynomials in Quantum Signal Processing", Communications in Mathematical Physics 406 7, 161 (2025).

[48] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing 193 (2019) ISBN:9781450367059.

[49] Ugnė Liaubaitė and S E Skelton, "Prospects of quantum error mitigation for quantum signal processing", Physica Scripta 100 12, 125119 (2025).

[50] John M. Martyn and Patrick Rall, "Halving the cost of quantum algorithms with randomization", npj Quantum Information 11 1, 47 (2025).

[51] I. Novikau, E. A. Startsev, and I. Y. Dodin, "Quantum signal processing for simulating cold plasma waves", Physical Review A 105 6, 062444 (2022).

[52] Di Fang, Lin Lin, and Yu Tong, "Time-marching based quantum solvers for time-dependent linear differential equations", Quantum 7, 955 (2023).

[53] Akshay Patil, Abhishek Tiwari, Vivek Khaneja, and Nagendra Singh, Lecture Notes in Networks and Systems 1073, 287 (2025) ISBN:978-981-97-5702-2.

[54] Lorenzo Laneve, "An adversary bound for quantum signal processing", Quantum 10, 2025 (2026).

[55] Michael Lubasch, Yuta Kikuchi, Lewis Wright, and Conor Mc Keever, "Quantum circuits for partial differential equations in Fourier space", Physical Review Research 7 4, 043326 (2025).

[56] Santiago Cifuentes, Samson Wang, Thais L. Silva, Mario Berta, and Leandro Aolita, "Quantum Computational Complexity of Matrix Functions", PRX Quantum 7 2, 020364 (2026).

[57] Sam McArdle, András Gilyén, and Mario Berta, "Quantum State Preparation without Coherent Arithmetic", Physical Review Letters 136 24, 240603 (2026).

[58] I. Novikau and I. Joseph, "Quantum algorithm for the advection-diffusion equation and the Koopman-von Neumann approach to nonlinear dynamical systems", Computer Physics Communications 309, 109498 (2025).

[59] 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).

[60] Javier Gonzalez-Conde, Thomas W. Watts, Pablo Rodriguez-Grasa, and Mikel Sanz, "Efficient quantum amplitude encoding of polynomial functions", Quantum 8, 1297 (2024).

[61] I. Novikau, I.Y. Dodin, and E.A. Startsev, "Simulation of Linear Non-Hermitian Boundary-Value Problems with Quantum Singular-Value Transformation", Physical Review Applied 19 5, 054012 (2023).

[62] Guoqiong Yan, Yandong Pang, Hongcan Gu, Su Wu, Bin Li, Wen Liu, Hanjie Liu, Cong Liu, and Junbing Huang, "Detection of distorted interference pulses for UWFBG array based on odd function decomposition", Optical Fiber Technology 82, 103641 (2024).

[63] Patrick Rall, "Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation", Quantum 5, 566 (2021).

[64] Zane M. Rossi and Isaac L. Chuang, "Quantum hypothesis testing with group structure", Physical Review A 104 1, 012425 (2021).

[65] 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).

[66] Zane M. Rossi and Isaac L. Chuang, "Semantic embedding for quantum algorithms", Journal of Mathematical Physics 64 12, 122202 (2023).

[67] Nishchay Suri, Joseph Barreto, Stuart Hadfield, Nathan Wiebe, Filip Wudarski, and Jeffrey Marshall, "Two-Unitary Decomposition Algorithm and Open Quantum System Simulation", Quantum 7, 1002 (2023).

[68] Thais L. Silva, Márcio M. Taddei, Stefano Carrazza, and Leandro Aolita, "Fragmented imaginary-time evolution for early-stage quantum signal processors", Scientific Reports 13 1, 18258 (2023).

[69] Michael de Oliveira, Luís S. Barbosa, and Ernesto F. Galvão, "Quantum advantage in temporally flat measurement-based quantum computation", Quantum 8, 1312 (2024).

[70] Rei Sakuma, Kaito Wada, Shu Kanno, Kimberlee Keithley, Kenji Sugisaki, Takashi Abe, Hajime Nakamura, and Naoki Yamamoto, "Quantum-phase-estimation-based filtering: Performance analysis and application to low-energy spectral calculations", Physical Review A 113 1, 012602 (2026).

[71] Takeru Utsumi and Yoshifumi Nakata, "Explicit decoders using fixed-point amplitude amplification based on QSVT", Quantum 10, 2024 (2026).

[72] Jessica Lemieux, Bettina Heim, David Poulin, Krysta Svore, and Matthias Troyer, "Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm", Quantum 4, 287 (2020).

[73] Youle Wang, Lei Zhang, Zhan Yu, and Xin Wang, "Quantum phase processing and its applications in estimating phase and entropies", Physical Review A 108 6, 062413 (2023).

[74] John M. Martyn, Zane M. Rossi, Kevin Z. Cheng, Yuan Liu, and Isaac L. Chuang, "Parallel Quantum Signal Processing Via Polynomial Factorization", Quantum 9, 1834 (2025).

[75] Lin Lin and Yu Tong, "Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems", Quantum 4, 361 (2020).

[76] Guanzhong Li, Shiguang Feng, and Lvzhou Li, "Revisiting fixed-point quantum search: proof of the quasi-Chebyshev lemma", Frontiers of Computer Science 20 10, 2010906 (2026).

[77] Sapthagiri Miriyala and Venkata Ramireddy Chirra, "From Quantum Algorithm Primitives to Design Patterns: A Unified Framework for NISQ and Fault‐Tolerant Regimes", Advanced Quantum Technologies 9 6, e70310 (2026).

[78] Dmitri Maslov, Jin-Sung Kim, Sergey Bravyi, Theodore J. Yoder, and Sarah Sheldon, "Quantum advantage for computations with limited space", Nature Physics 17 8, 894 (2021).

[79] 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).

[80] Zane M. Rossi, Jack L. Ceroni, and Isaac L. Chuang, "Modular quantum signal processing in many variables", Quantum 9, 1776 (2025).

[81] 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).

[82] John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang, "Grand Unification of Quantum Algorithms", PRX Quantum 2 4, 040203 (2021).

[83] Matic Petrič and René Zander, "Block-encodings as programming abstractions: The Eclipse Qrisp BlockEncoding Interface", arXiv:2604.18276, (2026).

[84] Takeru Utsumi, Yoshifumi Nakata, Qisheng Wang, and Ryuji Takagi, "Quantum algorithms for Uhlmann transformation", arXiv:2509.03619, (2025).

[85] Minh C. Tran, Andrew Y. Guo, Yuan Su, James R. Garrison, Zachary Eldredge, Michael Foss-Feig, Andrew M. Childs, and Alexey V. Gorshkov, "Locality and Digital Quantum Simulation of Power-Law Interactions", Physical Review X 9 3, 031006 (2019).

[86] Lorenzo Laneve, "Robust black-box quantum-state preparation via quantum signal processing", arXiv:2305.04705, (2023).

[87] Jeongwan Haah, Matthew B. Hastings, Robin Kothari, and Guang Hao Low, "Quantum algorithm for simulating real time evolution of lattice Hamiltonians", arXiv:1801.03922, (2018).

[88] Rui Chao, Dawei Ding, Andras Gilyen, Cupjin Huang, and Mario Szegedy, "Finding Angles for Quantum Signal Processing with Machine Precision", arXiv:2003.02831, (2020).

[89] Ivan Novikau and Ilon Joseph, "Quantum algorithm for the advection-diffusion equation and the Koopman-von Neumann approach to nonlinear dynamical systems", arXiv:2410.03985, (2024).

[90] Sean Greenaway, William Pol, and Sukin Sim, "A case study against QSVT: assessment of quantum phase estimation improved by signal processing techniques", arXiv:2404.01396, (2024).

[91] Lorenzo Laneve, "Quantum Signal Processing, Phase Extraction, and Proportional Sampling", arXiv:2303.11077, (2023).

[92] S. E. Skelton, "Mostly Harmless Methods for QSP-Processing with Laurent Polynomials", arXiv:2408.04321, (2024).

[93] Guang Hao Low, "Hamiltonian simulation with nearly optimal dependence on spectral norm", arXiv:1807.03967, (2018).

[94] Joran van Apeldoorn and András Gilyén, "Quantum algorithms for zero-sum games", arXiv:1904.03180, (2019).

[95] Haoya Li, Hongkang Ni, and Lexing Ying, "On efficient quantum block encoding of pseudo-differential operators", arXiv:2301.08908, (2023).

[96] Pierre-Antoine Bernard and Nathan Wiebe, "Analytical Angle-Finding and Series Expansions for Quantum Signal Processing via Orthogonal Polynomial Theory", arXiv:2605.05321, (2026).

[97] François Le Gall, Yupan Liu, and Qisheng Wang, "Space-bounded quantum state testing via space-efficient quantum singular value transformation", arXiv:2308.05079, (2023).

[98] Kunal Marwaha, "The QAOA on the ring of disagrees", arXiv:2606.29562, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-10 21:48:26) and SAO/NASA ADS (last updated successfully 2026-08-10 21:48:30). 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.