An adversary bound for quantum signal processing

Summarize this article with:
AbstractQuantum signal processing (QSP) and quantum singular value transformation (QSVT), have emerged as unifying frameworks in the context of quantum algorithm design. These techniques allow to carry out efficient polynomial transformations of matrices block-encoded in unitaries, involving a single ancilla qubit. Recent efforts try to extend QSP to the multivariate setting (M-QSP), where multiple matrices are transformed simultaneously. However, this generalization faces problems not encountered in the univariate counterpart: in particular, the class of polynomials achievable by M-QSP seems hard to characterize. In this work we borrow tools from query complexity, namely the state conversion problem and the adversary bound: we first recast QSP as a state conversion problem over the Hilbert space of square-integrable functions. We then show that the adversary bound for a state conversion problem in this space precisely identifies all and only the QSP protocols in the univariate case. Motivated by this first result, we extend the formalism to several variables: the existence of a feasible solution to the adversary bound implies the existence of a M-QSP protocol, and the computation of a protocol of minimal space is reduced to a rank minimization problem involving the feasible solution space of the adversary bound.Featured image: On the left, the process of constructing a QSP protocol (univariate or multivariate) using the adversary bound. On the right a visualization of $Q_\tau$, a convex space of feasible solutions to the adversary bound for constructing a desired parameterized quantum state $\tau(z)$. If $Q_\tau$ is non-empty, then a QSP protocol for $\tau(z)$ exists.Popular summaryQuantum signal processing is an important primitive in the quantum algorithmic literature. Roughly speaking, by alternating occurrences of a unitary that encodes some complex number $z$ (the "signal" operator) with operations $A_k$ that are independent of $z$ (the "processing" operators), the matrix product will contain a polynomial $P(z)$ in one of the entries, whose degree depends on the number of calls to the signal operator, and whose coefficients depend on the $A_k$ we choose. It turns out that we can make any possible polynomial $P(z)$ by choosing an appropriate sequence of processing operators. However, this is not clear when we have access to multiple signals $z_1, \ldots, z_m$ (the so-called multivariate quantum signal processing). This work uses the adversary bound — a convex optimization problem borrowed from quantum query complexity theory — to establish a necessary and sufficient condition for a given polynomial $P(z_1, \ldots, z_m)$ to admit a sequence of processing operators.► BibTeX data@article{Laneve2026adversarybound, doi = {10.22331/q-2026-03-13-2025}, url = {https://doi.org/10.22331/q-2026-03-13-2025}, title = {An adversary bound for quantum signal processing}, author = {Laneve, Lorenzo}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2025}, month = mar, year = {2026} }► References [1] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. ``Quantum Amplitude Amplification and Estimation''. Quantum Computation and Information 305, 53–74 (2002). https://doi.org/10.1090/conm/305/05215 [2] Dominic W Berry, Andrew M Childs, and Robin Kothari. ``Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters''. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. Pages 792–809. (2015). https://doi.org/10.1109/FOCS.2015.54 [3] Andrew M Childs and Nathan Wiebe. ``Hamiltonian simulation using linear combinations of unitary operations''. Quantum Information and Computation 12, 901–924 (2012). https://doi.org/10.26421/QIC12.11-12-1 [4] Dong An, Jin-Peng Liu, and Lin Lin. ``Linear Combination of Hamiltonian Simulation for Nonunitary Dynamics with Optimal State Preparation Cost''.
Physical Review Letters 131, 150603 (2023). https://doi.org/10.1103/PhysRevLett.131.150603 [5] Dong An, Andrew M. Childs, Lin Lin, and Lexing Ying. ``Laplace transform based quantum eigenvalue transformation via linear combination of Hamiltonian simulation'' (2024). arXiv:2411.04010. arXiv:2411.04010 [6] Michael A. Nielsen and Isaac L. Chuang. ``Quantum computation and quantum information: 10th anniversary edition''.
Cambridge University Press. Cambridge (2010). url: https://doi.org/10.1017/CBO9780511976667. https://doi.org/10.1017/CBO9780511976667 [7] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum Algorithm for Linear Systems of Equations''.
Physical Review Letters 103, 150502 (2009). https://doi.org/10.1103/PhysRevLett.103.150502 [8] Dorit Aharonov, Andris Ambainis, Julia Kempe, and Umesh Vazirani. ``Quantum walks on graphs''. In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing. Pages 50–59. STOC '01. Association for Computing Machinery (2001). https://doi.org/10.1145/380752.380758 [9] A Ambainis. ``Quantum walk algorithm for element distinctness''. In 45th Annual IEEE Symposium on Foundations of Computer Science. Pages 22–31. (2004). https://doi.org/10.1109/FOCS.2004.54 [10] Mario Szegedy. ``Quantum speed-up of Markov chain based algorithms''. In 45th Annual IEEE Symposium on Foundations of Computer Science. Pages 32–41. (2004). https://doi.org/10.1109/FOCS.2004.53 [11] Aleksandrs Belovs. ``Quantum Walks and Electric Networks'' (2013). arXiv:1302.3143. arXiv:1302.3143 [12] Simon Apers, András Gilyén, and Stacey Jeffery. ``A Unified Framework of Quantum Walk Search''.
In Leibniz International Proceedings in Informatics (LIPIcs). Volume 187 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021). https://doi.org/10.4230/LIPIcs.STACS.2021.6 [13] András Gilyén, Yuan Su, Guang Hao Low, and Nathan 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. ACM (2019). https://doi.org/10.1145/3313276.3316366 [14] Guang Hao Low and Isaac L Chuang. ``Hamiltonian Simulation by Uniform Spectral Amplification'' (2017). arXiv:1707.05391. arXiv:1707.05391 [15] Guang Hao Low and Isaac L. Chuang. ``Optimal Hamiltonian Simulation by Quantum Signal Processing''.
Physical Review Letters 118, 010501 (2017). https://doi.org/10.1103/PhysRevLett.118.010501 [16] Guang Hao Low. ``Quantum signal processing by single-qubit dynamics''. Thesis. Massachusetts Institute of Technology. (2017). url: https://dspace.mit.edu/handle/1721.1/115025. https://dspace.mit.edu/handle/1721.1/115025 [17] Guang Hao Low and Isaac L. Chuang. ``Hamiltonian Simulation by Qubitization''. Quantum 3, 163 (2019). https://doi.org/10.22331/q-2019-07-12-163 [18] John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang. ``A Grand Unification of Quantum Algorithms''. PRX Quantum 2, 40203 (2021). https://doi.org/10.1103/PRXQuantum.2.040203 [19] Dominic W. Berry, Danial Motlagh, Giacomo Pantaleoni, and Nathan Wiebe. ``Doubling the efficiency of Hamiltonian simulation via generalized quantum signal processing''. Physical Review A 110, 012612 (2024). https://doi.org/10.1103/PhysRevA.110.012612 [20] Jeongwan Haah. ``Product Decomposition of Periodic Functions in Quantum Signal Processing''. Quantum 3, 190 (2019). https://doi.org/10.22331/q-2019-10-07-190 [21] Rui Chao, Dawei Ding, Andras Gilyen, Cupjin Huang, and Mario Szegedy. ``Finding Angles for Quantum Signal Processing with Machine Precision'' (2020). arXiv:2003.02831. arXiv:2003.02831 [22] Yulong Dong, Xiang Meng, K Birgitta Whaley, and Lin Lin. ``Efficient phase-factor evaluation in quantum signal processing''. Physical Review A 103, 42419 (2021). https://doi.org/10.1103/PhysRevA.103.042419 [23] Lexing Ying. ``Stable factorization for phase factors of quantum signal processing''. Quantum 6, 842 (2022). https://doi.org/10.22331/q-2022-10-20-842 [24] Jiasu Wang, Yulong Dong, and Lin Lin. ``On the energy landscape of symmetric quantum signal processing''. Quantum 6, 850 (2022). https://doi.org/10.22331/q-2022-11-03-850 [25] 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, A2951–A2971 (2024). https://doi.org/10.1137/23M1598192 [26] Shuntaro Yamamoto and Nobuyuki Yoshioka. ``Robust Angle Finding for Generalized Quantum Signal Processing'' (2024). arXiv:2402.03016. arXiv:2402.03016 [27] Bjorn K. Berntson and Christoph Sünderhauf. ``Complementary Polynomials in Quantum Signal Processing''. Communications in Mathematical Physics 406, 161 (2025). https://doi.org/10.1007/s00220-025-05302-9 [28] Michel Alexis, Lin Lin, Gevorg Mnatsakanyan, Christoph Thiele, and Jiasu Wang. ``Infinite quantum signal processing for arbitrary Szegö functions'' (2024). arXiv:2407.05634. https://doi.org/10.1002/cpa.70007 arXiv:2407.05634 [29] Lorenzo Laneve. ``Generalized Quantum Signal Processing and Non-Linear Fourier Transform are equivalent'' (2025). arXiv:2503.03026. arXiv:2503.03026 [30] Hongkang Ni and Lexing Ying. ``Fast Phase Factor Finding for Quantum Signal Processing'' (2024). arXiv:2410.06409. arXiv:2410.06409 [31] Hongkang Ni, Rahul Sarkar, Lexing Ying, and Lin Lin. ``Inverse nonlinear fast Fourier transform on SU(2) with applications to quantum signal processing'' (2025). arXiv:2505.12615. arXiv:2505.12615 [32] John M. Martyn and Patrick Rall. ``Halving the cost of quantum algorithms with randomization''. npj Quantum Information 11, 47 (2025). https://doi.org/10.1038/s41534-025-01003-2 [33] John M. Martyn, Zane M. Rossi, Kevin Z. Cheng, Yuan Liu, and Isaac L. Chuang. ``Parallel Quantum Signal Processing Via Polynomial Factorization'' (2024). arXiv:2409.19043. https://doi.org/10.22331/q-2025-08-27-1834 arXiv:2409.19043 [34] 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, L012007 (2024). https://doi.org/10.1103/PhysRevResearch.6.L012007 [35] Zane M. Rossi, Jack L. Ceroni, and Isaac L. Chuang. ``Modular quantum signal processing in many variables''. Quantum 9, 1776 (2025). https://doi.org/10.22331/q-2025-06-18-1776 [36] Zane M. Rossi. ``A Solovay-Kitaev theorem for quantum signal processing'' (2025). arXiv:2505.05468. arXiv:2505.05468 [37] Zane M. Rossi and Isaac L. Chuang. ``Multivariable quantum signal processing (M-QSP): Prophecies of the two-headed oracle''. Quantum 6, 811 (2022). https://doi.org/10.22331/q-2022-09-20-811 [38] Hitomi Mori, Kaoru Mizuta, and Keisuke Fujii. ``Comment on "Multivariable quantum signal processing (M-QSP): Prophecies of the two-headed oracle"''. Quantum 8, 1512 (2024). https://doi.org/10.22331/q-2024-10-29-1512 [39] Yuki Ito, Hitomi Mori, Kazuki Sakamoto, and Keisuke Fujii. ``Polynomial time constructive decision algorithm for multivariable quantum signal processing'' (2024). arXiv:2410.02332. arXiv:2410.02332 [40] Balázs Németh, Blanka Kövér, Boglárka Kulcsár, Roland Botond Miklósi, and András Gilyén. ``On variants of multivariate quantum signal processing and their characterizations'' (2023). arXiv:2312.09072. arXiv:2312.09072 [41] Lorenzo Laneve and Stefan Wolf. ``On multivariate polynomials achievable with quantum signal processing''. Quantum 9, 1641 (2025). https://doi.org/10.22331/q-2025-02-20-1641 [42] Yonah Borns-Weil, Tahsin Saffat, and Zachary Stier. ``A Quantum Algorithm for Functions of Multiple Commuting Hermitian Matrices'' (2023). arXiv:2302.11139. arXiv:2302.11139 [43] Niladri Gomes, Hokiat Lim, and Nathan Wiebe. ``Multivariable QSP and Bosonic Quantum Simulation using Iterated Quantum Signal Processing'' (2024). arXiv:2408.03254. arXiv:2408.03254 [44] Peter Hoyer and Robert Spalek. ``Lower Bounds on Quantum Query Complexity'' (2005). arXiv:quant-ph/0509153. arXiv:quant-ph/0509153 [45] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. ``Quantum lower bounds by polynomials''. J. ACM 48, 778–797 (2001). https://doi.org/10.1145/502090.502097 [46] Andris Ambainis. ``Polynomial degree vs. quantum query complexity'' (2004). arXiv:quant-ph/0305028. arXiv:quant-ph/0305028 [47] Andris Ambainis. ``Quantum lower bounds by quantum arguments''. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing. Pages 636–643. STOC '00. Association for Computing Machinery (2000). https://doi.org/10.1145/335305.335394 [48] Robert Spalek. ``The Multiplicative Quantum Adversary''. In Proceedings of the 2008 IEEE 23rd Annual Conference on Computational Complexity. Pages 237–248. CCC '08. IEEE Computer Society (2008). https://doi.org/10.1109/CCC.2008.9 [49] Robert Spalek and Mario Szegedy. ``All quantum adversary methods are equivalent''. In Proceedings of the 32nd International Conference on Automata, Languages and Programming. Pages 1299–1311. ICALP'05. Springer-Verlag (2005). https://doi.org/10.1007/11523468_105 [50] Aleksandrs Belovs. ``Variations on Quantum Adversary'' (2015). arXiv:1504.06943. arXiv:1504.06943 [51] Peter Hoyer, Troy Lee, and Robert Spalek. ``Tight adversary bounds for composite functions'' (2006). arXiv:quant-ph/0509067. arXiv:quant-ph/0509067 [52] Ashley Montanaro and Changpeng Shao. ``Quantum and Classical Query Complexities of Functions of Matrices''. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing. Pages 573–584. STOC 2024. Association for Computing Machinery (2024). https://doi.org/10.1145/3618260.3649665 [53] Peter Hoyer, Troy Lee, and Robert Spalek. ``Negative weights make adversaries stronger''. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing. Pages 526–535. (2007). https://doi.org/10.1145/1250790.1250867 [54] Ben W. Reichardt. ``Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function''. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science. Pages 544–551. (2009). https://doi.org/10.1109/FOCS.2009.55 [55] Aleksandrs Belovs. ``A Direct Reduction from the Polynomial to the Adversary Method''. In Frédéric Magniez and Alex Bredariol Grilo, editors, 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024). Volume 310 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:15. Dagstuhl, Germany (2024). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.TQC.2024.11 [56] Andris Ambainis, Loïck Magnin, Martin Roetteler, and Jérémie Roland. ``Symmetry-assisted adversaries for quantum state generation''. In 2011 IEEE 26th Annual Conference on Computational Complexity. Pages 167–177. (2011). https://doi.org/10.1109/CCC.2011.24 [57] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, and Mario Szegedy. ``Quantum query complexity of state conversion''. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. Pages 344–353. (2011). https://doi.org/10.1109/FOCS.2011.75 [58] Aleksandrs Belovs and Duyal Yolcu. ``One-Way Ticket to Las Vegas and the Quantum Adversary'' (2023). arXiv:2301.02003. arXiv:2301.02003 [59] Aleksandrs Belovs, Stacey Jeffery, and Duyal Yolcu. ``Taming Quantum Time Complexity''. Quantum 8, 1444 (2024). https://doi.org/10.22331/q-2024-08-23-1444 [60] Lorenzo Laneve. ``Quantum signal processing over SU(N)'' (2024). arXiv:2311.03949. arXiv:2311.03949 [61] Xi Lu, Yuan Liu, and Hongwei Lin. ``Quantum Signal Processing and Quantum Singular Value Transformation on U(N)'' (2024). arXiv:2408.01439. arXiv:2408.01439 [62] Danial Motlagh and Nathan Wiebe. ``Generalized Quantum Signal Processing''. PRX Quantum 5, 020368 (2024). https://doi.org/10.1103/PRXQuantum.5.020368 [63] Christoph Sünderhauf. ``Generalized Quantum Singular Value Transformation'' (2023). arXiv:2312.00723. arXiv:2312.00723 [64] Abdulmtalb Hussen and Abdelbaset Zeyani. ``Fejer-Riesz Theorem and Its Generalization''. International Journal of Scientific and Research Publications (IJSRP) 11, 286–292 (2021). https://doi.org/10.29322/IJSRP.11.06.2021.p11437 [65] Jeffrey S. Geronimo and Hugo J. Woerdeman. ``Positive extensions, Fejér-Riesz factorization and autoregressive filters in two variables''. Annals of Mathematics 160, 839–906 (2004). https://doi.org/10.4007/ANNALS.2004.160.839 [66] Michael A. Dritschel. ``On Factorization of Trigonometric Polynomials''. Integral Equations and Operator Theory 49, 11–42 (2004). https://doi.org/10.1007/s00020-002-1198-4 [67] Walter Rudin. ``The extension problem for positive-definite functions''. Illinois Journal of Mathematics 7, 532–539 (1963). https://doi.org/10.1215/ijm/1255644960 [68] Michel Alexis, Gevorg Mnatsakanyan, and Christoph Thiele. ``Quantum signal processing and nonlinear Fourier analysis''. Revista Matemática Complutense 37, 655–694 (2024). https://doi.org/10.1007/s13163-024-00494-5 [69] Benjamin Recht, Weiyu Xu, and Babak Hassibi. ``Necessary and Sufficient Conditions for Success of the Nuclear Norm Heuristic for Rank Minimization''. In 2008 47th IEEE Conference on Decision and Control. Pages 3065–3070. (2008). https://doi.org/10.1109/CDC.2008.4739332 [70] Yulong Dong, Lin Lin, Hongkang Ni, and Jiasu Wang. ``Infinite quantum signal processing''. Quantum 8, 1558 (2024). https://doi.org/10.22331/q-2024-12-10-1558 [71] 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, 40305 (2022). https://doi.org/10.1103/PRXQuantum.3.040305 [72] John B. Conway. ``A Course in Functional Analysis''. Volume 96 of Graduate Texts in Mathematics. Springer. New York, NY (2007). https://doi.org/10.1007/978-1-4757-4383-8 [73] Ya-Ju Tsai. ``SU(2) non-linear Fourier transform''. PhD thesis. University of California Los Angeles. (2005).Cited byCould not fetch Crossref cited-by data during last attempt 2026-03-13 14:36:50: Could not fetch cited-by data for 10.22331/q-2026-03-13-2025 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-03-13 14:36:51: No response from ADS or unable to decode the received json data when getting the list of citing works.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. AbstractQuantum signal processing (QSP) and quantum singular value transformation (QSVT), have emerged as unifying frameworks in the context of quantum algorithm design. These techniques allow to carry out efficient polynomial transformations of matrices block-encoded in unitaries, involving a single ancilla qubit. Recent efforts try to extend QSP to the multivariate setting (M-QSP), where multiple matrices are transformed simultaneously. However, this generalization faces problems not encountered in the univariate counterpart: in particular, the class of polynomials achievable by M-QSP seems hard to characterize. In this work we borrow tools from query complexity, namely the state conversion problem and the adversary bound: we first recast QSP as a state conversion problem over the Hilbert space of square-integrable functions. We then show that the adversary bound for a state conversion problem in this space precisely identifies all and only the QSP protocols in the univariate case. Motivated by this first result, we extend the formalism to several variables: the existence of a feasible solution to the adversary bound implies the existence of a M-QSP protocol, and the computation of a protocol of minimal space is reduced to a rank minimization problem involving the feasible solution space of the adversary bound.Featured image: On the left, the process of constructing a QSP protocol (univariate or multivariate) using the adversary bound. On the right a visualization of $Q_\tau$, a convex space of feasible solutions to the adversary bound for constructing a desired parameterized quantum state $\tau(z)$. If $Q_\tau$ is non-empty, then a QSP protocol for $\tau(z)$ exists.Popular summaryQuantum signal processing is an important primitive in the quantum algorithmic literature. Roughly speaking, by alternating occurrences of a unitary that encodes some complex number $z$ (the "signal" operator) with operations $A_k$ that are independent of $z$ (the "processing" operators), the matrix product will contain a polynomial $P(z)$ in one of the entries, whose degree depends on the number of calls to the signal operator, and whose coefficients depend on the $A_k$ we choose. It turns out that we can make any possible polynomial $P(z)$ by choosing an appropriate sequence of processing operators. However, this is not clear when we have access to multiple signals $z_1, \ldots, z_m$ (the so-called multivariate quantum signal processing). This work uses the adversary bound — a convex optimization problem borrowed from quantum query complexity theory — to establish a necessary and sufficient condition for a given polynomial $P(z_1, \ldots, z_m)$ to admit a sequence of processing operators.► BibTeX data@article{Laneve2026adversarybound, doi = {10.22331/q-2026-03-13-2025}, url = {https://doi.org/10.22331/q-2026-03-13-2025}, title = {An adversary bound for quantum signal processing}, author = {Laneve, Lorenzo}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2025}, month = mar, year = {2026} }► References [1] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. ``Quantum Amplitude Amplification and Estimation''. Quantum Computation and Information 305, 53–74 (2002). https://doi.org/10.1090/conm/305/05215 [2] Dominic W Berry, Andrew M Childs, and Robin Kothari. ``Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters''. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. Pages 792–809. (2015). https://doi.org/10.1109/FOCS.2015.54 [3] Andrew M Childs and Nathan Wiebe. ``Hamiltonian simulation using linear combinations of unitary operations''. Quantum Information and Computation 12, 901–924 (2012). https://doi.org/10.26421/QIC12.11-12-1 [4] Dong An, Jin-Peng Liu, and Lin Lin. ``Linear Combination of Hamiltonian Simulation for Nonunitary Dynamics with Optimal State Preparation Cost''.
Physical Review Letters 131, 150603 (2023). https://doi.org/10.1103/PhysRevLett.131.150603 [5] Dong An, Andrew M. Childs, Lin Lin, and Lexing Ying. ``Laplace transform based quantum eigenvalue transformation via linear combination of Hamiltonian simulation'' (2024). arXiv:2411.04010. arXiv:2411.04010 [6] Michael A. Nielsen and Isaac L. Chuang. ``Quantum computation and quantum information: 10th anniversary edition''.
Cambridge University Press. Cambridge (2010). url: https://doi.org/10.1017/CBO9780511976667. https://doi.org/10.1017/CBO9780511976667 [7] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum Algorithm for Linear Systems of Equations''.
Physical Review Letters 103, 150502 (2009). https://doi.org/10.1103/PhysRevLett.103.150502 [8] Dorit Aharonov, Andris Ambainis, Julia Kempe, and Umesh Vazirani. ``Quantum walks on graphs''. In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing. Pages 50–59. STOC '01. Association for Computing Machinery (2001). https://doi.org/10.1145/380752.380758 [9] A Ambainis. ``Quantum walk algorithm for element distinctness''. In 45th Annual IEEE Symposium on Foundations of Computer Science. Pages 22–31. (2004). https://doi.org/10.1109/FOCS.2004.54 [10] Mario Szegedy. ``Quantum speed-up of Markov chain based algorithms''. In 45th Annual IEEE Symposium on Foundations of Computer Science. Pages 32–41. (2004). https://doi.org/10.1109/FOCS.2004.53 [11] Aleksandrs Belovs. ``Quantum Walks and Electric Networks'' (2013). arXiv:1302.3143. arXiv:1302.3143 [12] Simon Apers, András Gilyén, and Stacey Jeffery. ``A Unified Framework of Quantum Walk Search''.
In Leibniz International Proceedings in Informatics (LIPIcs). Volume 187 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021). https://doi.org/10.4230/LIPIcs.STACS.2021.6 [13] András Gilyén, Yuan Su, Guang Hao Low, and Nathan 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. ACM (2019). https://doi.org/10.1145/3313276.3316366 [14] Guang Hao Low and Isaac L Chuang. ``Hamiltonian Simulation by Uniform Spectral Amplification'' (2017). arXiv:1707.05391. arXiv:1707.05391 [15] Guang Hao Low and Isaac L. Chuang. ``Optimal Hamiltonian Simulation by Quantum Signal Processing''.
Physical Review Letters 118, 010501 (2017). https://doi.org/10.1103/PhysRevLett.118.010501 [16] Guang Hao Low. ``Quantum signal processing by single-qubit dynamics''. Thesis. Massachusetts Institute of Technology. (2017). url: https://dspace.mit.edu/handle/1721.1/115025. https://dspace.mit.edu/handle/1721.1/115025 [17] Guang Hao Low and Isaac L. Chuang. ``Hamiltonian Simulation by Qubitization''. Quantum 3, 163 (2019). https://doi.org/10.22331/q-2019-07-12-163 [18] John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang. ``A Grand Unification of Quantum Algorithms''. PRX Quantum 2, 40203 (2021). https://doi.org/10.1103/PRXQuantum.2.040203 [19] Dominic W. Berry, Danial Motlagh, Giacomo Pantaleoni, and Nathan Wiebe. ``Doubling the efficiency of Hamiltonian simulation via generalized quantum signal processing''. Physical Review A 110, 012612 (2024). https://doi.org/10.1103/PhysRevA.110.012612 [20] Jeongwan Haah. ``Product Decomposition of Periodic Functions in Quantum Signal Processing''. Quantum 3, 190 (2019). https://doi.org/10.22331/q-2019-10-07-190 [21] Rui Chao, Dawei Ding, Andras Gilyen, Cupjin Huang, and Mario Szegedy. ``Finding Angles for Quantum Signal Processing with Machine Precision'' (2020). arXiv:2003.02831. arXiv:2003.02831 [22] Yulong Dong, Xiang Meng, K Birgitta Whaley, and Lin Lin. ``Efficient phase-factor evaluation in quantum signal processing''. Physical Review A 103, 42419 (2021). https://doi.org/10.1103/PhysRevA.103.042419 [23] Lexing Ying. ``Stable factorization for phase factors of quantum signal processing''. Quantum 6, 842 (2022). https://doi.org/10.22331/q-2022-10-20-842 [24] Jiasu Wang, Yulong Dong, and Lin Lin. ``On the energy landscape of symmetric quantum signal processing''. Quantum 6, 850 (2022). https://doi.org/10.22331/q-2022-11-03-850 [25] 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, A2951–A2971 (2024). https://doi.org/10.1137/23M1598192 [26] Shuntaro Yamamoto and Nobuyuki Yoshioka. ``Robust Angle Finding for Generalized Quantum Signal Processing'' (2024). arXiv:2402.03016. arXiv:2402.03016 [27] Bjorn K. Berntson and Christoph Sünderhauf. ``Complementary Polynomials in Quantum Signal Processing''. Communications in Mathematical Physics 406, 161 (2025). https://doi.org/10.1007/s00220-025-05302-9 [28] Michel Alexis, Lin Lin, Gevorg Mnatsakanyan, Christoph Thiele, and Jiasu Wang. ``Infinite quantum signal processing for arbitrary Szegö functions'' (2024). arXiv:2407.05634. https://doi.org/10.1002/cpa.70007 arXiv:2407.05634 [29] Lorenzo Laneve. ``Generalized Quantum Signal Processing and Non-Linear Fourier Transform are equivalent'' (2025). arXiv:2503.03026. arXiv:2503.03026 [30] Hongkang Ni and Lexing Ying. ``Fast Phase Factor Finding for Quantum Signal Processing'' (2024). arXiv:2410.06409. arXiv:2410.06409 [31] Hongkang Ni, Rahul Sarkar, Lexing Ying, and Lin Lin. ``Inverse nonlinear fast Fourier transform on SU(2) with applications to quantum signal processing'' (2025). arXiv:2505.12615. arXiv:2505.12615 [32] John M. Martyn and Patrick Rall. ``Halving the cost of quantum algorithms with randomization''. npj Quantum Information 11, 47 (2025). https://doi.org/10.1038/s41534-025-01003-2 [33] John M. Martyn, Zane M. Rossi, Kevin Z. Cheng, Yuan Liu, and Isaac L. Chuang. ``Parallel Quantum Signal Processing Via Polynomial Factorization'' (2024). arXiv:2409.19043. https://doi.org/10.22331/q-2025-08-27-1834 arXiv:2409.19043 [34] 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, L012007 (2024). https://doi.org/10.1103/PhysRevResearch.6.L012007 [35] Zane M. Rossi, Jack L. Ceroni, and Isaac L. Chuang. ``Modular quantum signal processing in many variables''. Quantum 9, 1776 (2025). https://doi.org/10.22331/q-2025-06-18-1776 [36] Zane M. Rossi. ``A Solovay-Kitaev theorem for quantum signal processing'' (2025). arXiv:2505.05468. arXiv:2505.05468 [37] Zane M. Rossi and Isaac L. Chuang. ``Multivariable quantum signal processing (M-QSP): Prophecies of the two-headed oracle''. Quantum 6, 811 (2022). https://doi.org/10.22331/q-2022-09-20-811 [38] Hitomi Mori, Kaoru Mizuta, and Keisuke Fujii. ``Comment on "Multivariable quantum signal processing (M-QSP): Prophecies of the two-headed oracle"''. Quantum 8, 1512 (2024). https://doi.org/10.22331/q-2024-10-29-1512 [39] Yuki Ito, Hitomi Mori, Kazuki Sakamoto, and Keisuke Fujii. ``Polynomial time constructive decision algorithm for multivariable quantum signal processing'' (2024). arXiv:2410.02332. arXiv:2410.02332 [40] Balázs Németh, Blanka Kövér, Boglárka Kulcsár, Roland Botond Miklósi, and András Gilyén. ``On variants of multivariate quantum signal processing and their characterizations'' (2023). arXiv:2312.09072. arXiv:2312.09072 [41] Lorenzo Laneve and Stefan Wolf. ``On multivariate polynomials achievable with quantum signal processing''. Quantum 9, 1641 (2025). https://doi.org/10.22331/q-2025-02-20-1641 [42] Yonah Borns-Weil, Tahsin Saffat, and Zachary Stier. ``A Quantum Algorithm for Functions of Multiple Commuting Hermitian Matrices'' (2023). arXiv:2302.11139. arXiv:2302.11139 [43] Niladri Gomes, Hokiat Lim, and Nathan Wiebe. ``Multivariable QSP and Bosonic Quantum Simulation using Iterated Quantum Signal Processing'' (2024). arXiv:2408.03254. arXiv:2408.03254 [44] Peter Hoyer and Robert Spalek. ``Lower Bounds on Quantum Query Complexity'' (2005). arXiv:quant-ph/0509153. arXiv:quant-ph/0509153 [45] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. ``Quantum lower bounds by polynomials''. J. ACM 48, 778–797 (2001). https://doi.org/10.1145/502090.502097 [46] Andris Ambainis. ``Polynomial degree vs. quantum query complexity'' (2004). arXiv:quant-ph/0305028. arXiv:quant-ph/0305028 [47] Andris Ambainis. ``Quantum lower bounds by quantum arguments''. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing. Pages 636–643. STOC '00. Association for Computing Machinery (2000). https://doi.org/10.1145/335305.335394 [48] Robert Spalek. ``The Multiplicative Quantum Adversary''. In Proceedings of the 2008 IEEE 23rd Annual Conference on Computational Complexity. Pages 237–248. CCC '08. IEEE Computer Society (2008). https://doi.org/10.1109/CCC.2008.9 [49] Robert Spalek and Mario Szegedy. ``All quantum adversary methods are equivalent''. In Proceedings of the 32nd International Conference on Automata, Languages and Programming. Pages 1299–1311. ICALP'05. Springer-Verlag (2005). https://doi.org/10.1007/11523468_105 [50] Aleksandrs Belovs. ``Variations on Quantum Adversary'' (2015). arXiv:1504.06943. arXiv:1504.06943 [51] Peter Hoyer, Troy Lee, and Robert Spalek. ``Tight adversary bounds for composite functions'' (2006). arXiv:quant-ph/0509067. arXiv:quant-ph/0509067 [52] Ashley Montanaro and Changpeng Shao. ``Quantum and Classical Query Complexities of Functions of Matrices''. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing. Pages 573–584. STOC 2024. Association for Computing Machinery (2024). https://doi.org/10.1145/3618260.3649665 [53] Peter Hoyer, Troy Lee, and Robert Spalek. ``Negative weights make adversaries stronger''. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing. Pages 526–535. (2007). https://doi.org/10.1145/1250790.1250867 [54] Ben W. Reichardt. ``Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function''. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science. Pages 544–551. (2009). https://doi.org/10.1109/FOCS.2009.55 [55] Aleksandrs Belovs. ``A Direct Reduction from the Polynomial to the Adversary Method''. In Frédéric Magniez and Alex Bredariol Grilo, editors, 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024). Volume 310 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:15. Dagstuhl, Germany (2024). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.TQC.2024.11 [56] Andris Ambainis, Loïck Magnin, Martin Roetteler, and Jérémie Roland. ``Symmetry-assisted adversaries for quantum state generation''. In 2011 IEEE 26th Annual Conference on Computational Complexity. Pages 167–177. (2011). https://doi.org/10.1109/CCC.2011.24 [57] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, and Mario Szegedy. ``Quantum query complexity of state conversion''. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. Pages 344–353. (2011). https://doi.org/10.1109/FOCS.2011.75 [58] Aleksandrs Belovs and Duyal Yolcu. ``One-Way Ticket to Las Vegas and the Quantum Adversary'' (2023). arXiv:2301.02003. arXiv:2301.02003 [59] Aleksandrs Belovs, Stacey Jeffery, and Duyal Yolcu. ``Taming Quantum Time Complexity''. Quantum 8, 1444 (2024). https://doi.org/10.22331/q-2024-08-23-1444 [60] Lorenzo Laneve. ``Quantum signal processing over SU(N)'' (2024). arXiv:2311.03949. arXiv:2311.03949 [61] Xi Lu, Yuan Liu, and Hongwei Lin. ``Quantum Signal Processing and Quantum Singular Value Transformation on U(N)'' (2024). arXiv:2408.01439. arXiv:2408.01439 [62] Danial Motlagh and Nathan Wiebe. ``Generalized Quantum Signal Processing''. PRX Quantum 5, 020368 (2024). https://doi.org/10.1103/PRXQuantum.5.020368 [63] Christoph Sünderhauf. ``Generalized Quantum Singular Value Transformation'' (2023). arXiv:2312.00723. arXiv:2312.00723 [64] Abdulmtalb Hussen and Abdelbaset Zeyani. ``Fejer-Riesz Theorem and Its Generalization''. International Journal of Scientific and Research Publications (IJSRP) 11, 286–292 (2021). https://doi.org/10.29322/IJSRP.11.06.2021.p11437 [65] Jeffrey S. Geronimo and Hugo J. Woerdeman. ``Positive extensions, Fejér-Riesz factorization and autoregressive filters in two variables''. Annals of Mathematics 160, 839–906 (2004). https://doi.org/10.4007/ANNALS.2004.160.839 [66] Michael A. Dritschel. ``On Factorization of Trigonometric Polynomials''. Integral Equations and Operator Theory 49, 11–42 (2004). https://doi.org/10.1007/s00020-002-1198-4 [67] Walter Rudin. ``The extension problem for positive-definite functions''. Illinois Journal of Mathematics 7, 532–539 (1963). https://doi.org/10.1215/ijm/1255644960 [68] Michel Alexis, Gevorg Mnatsakanyan, and Christoph Thiele. ``Quantum signal processing and nonlinear Fourier analysis''. Revista Matemática Complutense 37, 655–694 (2024). https://doi.org/10.1007/s13163-024-00494-5 [69] Benjamin Recht, Weiyu Xu, and Babak Hassibi. ``Necessary and Sufficient Conditions for Success of the Nuclear Norm Heuristic for Rank Minimization''. In 2008 47th IEEE Conference on Decision and Control. Pages 3065–3070. (2008). https://doi.org/10.1109/CDC.2008.4739332 [70] Yulong Dong, Lin Lin, Hongkang Ni, and Jiasu Wang. ``Infinite quantum signal processing''. Quantum 8, 1558 (2024). https://doi.org/10.22331/q-2024-12-10-1558 [71] 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, 40305 (2022). https://doi.org/10.1103/PRXQuantum.3.040305 [72] John B. Conway. ``A Course in Functional Analysis''. Volume 96 of Graduate Texts in Mathematics. Springer. New York, NY (2007). https://doi.org/10.1007/978-1-4757-4383-8 [73] Ya-Ju Tsai. ``SU(2) non-linear Fourier transform''. PhD thesis. University of California Los Angeles. (2005).Cited byCould not fetch Crossref cited-by data during last attempt 2026-03-13 14:36:50: Could not fetch cited-by data for 10.22331/q-2026-03-13-2025 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-03-13 14:36:51: No response from ADS or unable to decode the received json data when getting the list of citing works.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.
