{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T01:05:32Z","timestamp":1774659932593,"version":"3.50.1"},"reference-count":57,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2022,9,20]],"date-time":"2022-09-20T00:00:00Z","timestamp":1663632000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Co-design Center for Quantum Advantage","award":["DE-SC0012704"],"award-info":[{"award-number":["DE-SC0012704"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"Recent work shows that quantum signal processing (QSP) and its multi-qubit lifted version, quantum singular value transformation (QSVT), unify and improve the presentation of most quantum algorithms. QSP\/QSVT characterize the ability, by alternating ans\u00e4tze, to obliviously transform the singular values of subsystems of unitary matrices by polynomial functions; these algorithms are numerically stable and analytically well-understood. That said, QSP\/QSVT require consistent access to a s<\/mml:mi>i<\/mml:mi>n<\/mml:mi>g<\/mml:mi>l<\/mml:mi>e<\/mml:mi><\/mml:math> oracle, saying nothing about computing joint properties<\/mml:mtext><\/mml:mrow><\/mml:math> of two or more oracles; these can be far cheaper to determine given an ability to pit oracles against one another coherently. This work introduces a corresponding theory of QSP over multiple variables: M-QSP. Surprisingly, despite the non-existence of the fundamental theorem of algebra for multivariable polynomials, there exist necessary and sufficient conditions under which a desired s<\/mml:mi>t<\/mml:mi>a<\/mml:mi>b<\/mml:mi>l<\/mml:mi>e<\/mml:mi><\/mml:math> multivariable polynomial transformation is possible. Moreover, the classical subroutines used by QSP protocols survive in the multivariable setting for non-obvious reasons, and remain numerically stable and efficient. Up to a well-defined conjecture, we give proof that the family of achievable multivariable transforms is as loosely constrained as could be expected. The unique ability of M-QSP to o<\/mml:mi>b<\/mml:mi>l<\/mml:mi>i<\/mml:mi>v<\/mml:mi>i<\/mml:mi>o<\/mml:mi>u<\/mml:mi>s<\/mml:mi>l<\/mml:mi>y<\/mml:mi><\/mml:math> approximate joint functions<\/mml:mtext><\/mml:mrow><\/mml:math> of multiple variables coherently leads to novel speedups incommensurate with those of other quantum algorithms, and provides a bridge from quantum algorithms to algebraic geometry.<\/jats:p>","DOI":"10.22331\/q-2022-09-20-811","type":"journal-article","created":{"date-parts":[[2022,9,20]],"date-time":"2022-09-20T10:33:04Z","timestamp":1663669984000},"page":"811","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":27,"title":["Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle"],"prefix":"10.22331","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7718-654X","authenticated-orcid":false,"given":"Zane M.","family":"Rossi","sequence":"first","affiliation":[{"name":"Department of Physics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA"}]},{"given":"Isaac L.","family":"Chuang","sequence":"additional","affiliation":[{"name":"Department of Physics, Department of Electrical Engineering and Computer Science, and Co-Design Center for Quantum Advantage, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA"}]}],"member":"9598","published-online":{"date-parts":[[2022,9,20]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Andr\u00e1s Gily\u00e9n, Yuan Su, Guang Hao Low, and Nathan Wiebe. ``Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics''. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (2019).","DOI":"10.1145\/3313276.3316366"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Patrick Rall. ``Faster coherent quantum algorithms for phase, energy, and amplitude estimation''. Quantum 5, 566 (2021).","DOI":"10.22331\/q-2021-10-19-566"},{"key":"2","unstructured":"John M. Martyn, Yuan Liu, Zachary E. Chin, and Isaac L. Chuang. ``Efficient fully-coherent Hamiltonian simulation'' (2021). arXiv:2110.11327."},{"key":"3","doi-asserted-by":"publisher","unstructured":"John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang. ``Grand unification of quantum algorithms''. PRX Quantum 2, 040203 (2021).","DOI":"10.1103\/PRXQuantum.2.040203"},{"key":"4","unstructured":"Seth Lloyd, Bobak T. Kiani, David R. M. Arvidsson-Shukur, Samuel Bosch, Giacomo De Palma, William M. Kaminsky, Zi-Wen Liu, and Milad Marvian. ``Hamiltonian singular value transformation and inverse block encoding'' (2021). arXiv:2104.01410."},{"key":"5","unstructured":"Andr\u00e1s Gily\u00e9n and Alexander Poremba. ``Improved quantum algorithms for fidelity estimation'' (2022). arXiv:2203.15993."},{"key":"6","doi-asserted-by":"publisher","unstructured":"Andr\u00e1s Gily\u00e9n, Seth Lloyd, Iman Marvian, Yihui Quek, and Mark M Wilde. ``Quantum algorithm for petz recovery channels and pretty good measurements''. Physical Review Letters 128, 220502 (2022).","DOI":"10.1103\/PhysRevLett.128.220502"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Zane M Rossi and Isaac L Chuang. ``Quantum hypothesis testing with group structure''. Physical Review A 104, 012425 (2021).","DOI":"10.1103\/PhysRevA.104.012425"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Nai-Hui Chia, Andr\u00e1s Gily\u00e9n, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang. ``Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning''. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Page 387\u2013400. STOC 2020New York, NY, USA (2020). Association for Computing Machinery.","DOI":"10.1145\/3357713.3384314"},{"key":"9","unstructured":"Alex Lombardi, Fermi Ma, and Nicholas Spooner. ``Post-quantum zero knowledge, revisited (or: How to do quantum rewinding undetectably)'' (2021). arXiv:2111.12257."},{"key":"10","doi-asserted-by":"publisher","unstructured":"G. H. Low, T. J. Yoder, and I. L. Chuang. ``Methodology of resonant equiangular composite quantum gates''. Phys. Rev. X 6, 041067 (2016).","DOI":"10.1103\/PhysRevX.6.041067"},{"key":"11","doi-asserted-by":"publisher","unstructured":"G. H. Low and I. L. Chuang. ``Optimal Hamiltonian simulation by quantum signal processing''. Phys. Rev. Lett. 118, 010501 (2017).","DOI":"10.1103\/PhysRevLett.118.010501"},{"key":"12","doi-asserted-by":"publisher","unstructured":"G. H. Low and I. L. Chuang. ``Hamiltonian simulation by qubitization''. Quantum 3, 163 (2019).","DOI":"10.22331\/q-2019-07-12-163"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Jeongwan Haah. ``Product decomposition of periodic functions in quantum signal processing''. Quantum 3, 190 (2019).","DOI":"10.22331\/q-2019-10-07-190"},{"key":"14","unstructured":"Rui Chao, Dawei Ding, Andras Gilyen, Cupjin Huang, and Mario Szegedy. ``Finding angles for quantum signal processing with machine precision'' (2020). arXiv:2003.02831."},{"key":"15","doi-asserted-by":"publisher","unstructured":"Yulong Dong, Xiang Meng, K. Birgitta Whaley, and Lin Lin. ``Efficient phase-factor evaluation in quantum signal processing''. Phys. Rev. A 103 (2021).","DOI":"10.1103\/physreva.103.042419"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum algorithm for linear systems of equations''. Phys. Rev. Lett. 103 (2009).","DOI":"10.1103\/physrevlett.103.150502"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Peter W Shor. ``Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer''. SIAM review 41, 303\u2013332 (1999).","DOI":"10.1137\/S0097539795293172"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Richard P Feynman. ``Simulating physics with computers''. In Feynman and computation. Pages 133\u2013153. CRC Press (2018).","DOI":"10.1007\/BF02650179"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Jintai Ding and Bo-Yin Yang. ``Multivariate public key cryptography''. In Post-quantum cryptography. Pages 193\u2013241. Springer (2009).","DOI":"10.1007\/978-0-387-36946-4"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Scott Aaronson and Paul Christiano. ``Quantum money from hidden subspaces''. In Proceedings of the forty-fourth annual ACM symposium on theory of computing. Pages 41\u201360. (2012).","DOI":"10.48550\/arXiv.1203.4740"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Anurag Anshu, Itai Arad, and David Gosset. ``An area law for 2d frustration-free spin systems''. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Pages 12\u201318. (2022).","DOI":"10.1145\/3519935.3519962"},{"key":"22","unstructured":"Rahul Sarkar and Theodore J. Yoder. ``Density theorems with applications in quantum signal processing'' (2022). arXiv:2111.07182."},{"key":"23","unstructured":"Jiasu Wang, Yulong Dong, and Lin Lin. ``On the energy landscape of symmetric quantum signal processing'' (2021). arXiv:2110.04993."},{"key":"24","doi-asserted-by":"publisher","unstructured":"Joran Van Apeldoorn, Andr\u00e1s Gily\u00e9n, Sander Gribling, and Ronald de Wolf. ``Quantum SDP-solvers: Better upper and lower bounds''. Quantum 4, 230 (2020).","DOI":"10.48550\/arXiv.1705.01843"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Lin Lin and Yu Tong. ``Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems''. Quantum 4, 361 (2020).","DOI":"10.22331\/q-2020-11-11-361"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Patrick Rall. ``Quantum algorithms for estimating physical quantities using block encodings''. Phys. Rev. A 102, 022408 (2020).","DOI":"10.1103\/PhysRevA.102.022408"},{"key":"27","doi-asserted-by":"publisher","unstructured":"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''. Phys. Rev. A 104, 032422 (2021).","DOI":"10.1103\/PhysRevA.104.032422"},{"key":"28","doi-asserted-by":"publisher","unstructured":"J. Geronimo and Hugo Woerdeman. ``Positive extensions, Fej\u00e9r-Riesz factorization and autoregressive filters in two variables''. Ann. Math. 160, 839\u2013906 (2004).","DOI":"10.4007\/annals.2004.160.839"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Murray Marshall. ``Positive polynomials and sums of squares''. Number 146 in Mathematical surveys and monographs. Am. Math. Soc. (2008).","DOI":"10.1090\/surv\/146"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Bogdan Dumitrescu. ``Positive trigonometric polynomials and signal processing applications''. Springer. Switzerland (2007).","DOI":"10.1007\/978-3-319-53688-0"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Michael Dritschel and Hugo Woerdeman. ``Outer factorizations in one and several variables''. Trans. Am. Math. Soc. 357, 4661\u20134679 (2005).","DOI":"10.48550\/arXiv.math\/0403099"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Jeffrey S Geronimo and Hugo Woerdeman. ``Two variable orthogonal polynomials on the bicircle and structured matrices''. SIAM journal on matrix analysis and applications 29, 796\u2013825 (2007).","DOI":"10.1137\/060662472"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Michael A. Dritschel and James Rovnyak. ``The operator Fej\u00e9r-Riesz theorem''. Pages 223\u2013254. Springer Basel. Basel (2010).","DOI":"10.1007\/978-3-0346-0347-8_14"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Robin Hartshorne. ``Algebraic geometry''. Volume 52. Springer New York, NY. (2013).","DOI":"10.1007\/978-1-4757-3849-0"},{"key":"35","unstructured":"William Fulton. ``Algebraic curves: An introduction to algebraic geometry''. Addison-Wesley. (1969). url: dept.math.lsa.umich.edu\/ wfulton\/CurveBook.pdf."},{"key":"36","doi-asserted-by":"publisher","unstructured":"George Polya and Gabor Szeg\u00f6. ``Problems and theorems in analysis II''. Springer. Berlin (1998).","DOI":"10.1007\/978-3-642-61905-2"},{"key":"37","doi-asserted-by":"publisher","unstructured":"F. Grenez. ``Design of linear or minimum-phase FIR filters by constrained Chebyshev approximation''. Signal Process. 5, 325\u2013332 (1983).","DOI":"10.1016\/0165-1684(83)90091-9"},{"key":"38","unstructured":"E. Remez. ``Sur le calcul effectif des polynomes dapproximation de Tchebichef''. C. R. Acad. Sci. Paris 199, 337\u2013340 (1934)."},{"key":"39","doi-asserted-by":"publisher","unstructured":"J. McClellan, T. Parks, and L. Rabiner. ``A computer program for designing optimum FIR linear phase digital filters''. IEEE trans. audio electroacoust. 21, 506\u2013526 (1973).","DOI":"10.1109\/TAU.1973.1162525"},{"key":"40","doi-asserted-by":"publisher","unstructured":"Jeffrey S Geronimo and Hugo J Woerdeman. ``Two-variable polynomials: intersecting zeros and stability''. IEEE Trans. Circuits Syst. I: Regular Papers 53, 1130\u20131139 (2006).","DOI":"10.1109\/TCSI.2005.862180"},{"key":"41","doi-asserted-by":"publisher","unstructured":"Anatolii Grinshpan, Dmitry S Kaliuzhnyi-Verbovetskyi, Victor Vinnikov, and Hugo J Woerdeman. ``Stable and real-zero polynomials in two variables''. Multidimens. Syst. Signal Process. 27, 1\u201326 (2016).","DOI":"10.1007\/s11045-014-0286-3"},{"key":"42","doi-asserted-by":"publisher","unstructured":"Rudolf Lidl and Ch. Wells. ``Chebyshev polynomials in several variables.''. Journal f\u00fcr die reine und angewandte Mathematik 255, 104\u2013111 (1972).","DOI":"10.1515\/crll.1972.255.104"},{"key":"43","doi-asserted-by":"publisher","unstructured":"Charles F Dunkl and Yuan Xu. ``Orthogonal polynomials of several variables''. Number 155 in Encyclopedia of mathematics and its applications. Cambridge University Press. (2014).","DOI":"10.1017\/CBO9781107786134"},{"key":"44","doi-asserted-by":"publisher","unstructured":"RJ Beerends. ``Chebyshev polynomials in several variables and the radial part of the Laplace-Beltrami operator''. Trans. Am. Math. Soc. 328, 779\u2013814 (1991).","DOI":"10.2307\/2001804"},{"key":"45","doi-asserted-by":"publisher","unstructured":"Zane M Rossi, Jeffery Yu, Isaac L Chuang, and Sho Sugiura. ``Quantum advantage for noisy channel discrimination''. Phys. Rev. A 105, 032401 (2022).","DOI":"10.1103\/PhysRevA.105.032401"},{"key":"46","doi-asserted-by":"crossref","unstructured":"Camille Jordan. ``Essai sur la g\u00e9om\u00e9trie \u00e0 $ n $ dimensions''. Bulletin de la Soci\u00e9t\u00e9 math\u00e9matique de France 3, 103\u2013174 (1875).","DOI":"10.24033\/bsmf.90"},{"key":"47","doi-asserted-by":"publisher","unstructured":"DJ Newman and HS Shapiro. ``Jackson\u2019s theorem in higher dimensions''. In On Approximation Theory\/\u00dcber Approximationstheorie. Pages 208\u2013219. Springer (1964).","DOI":"10.1007\/978-3-0348-4131-3_20"},{"key":"48","doi-asserted-by":"publisher","unstructured":"David L Ragozin. ``Polynomial approximation on compact manifolds and homogeneous spaces''. Trans. Am. Math. Soc. 150, 41\u201353 (1970).","DOI":"10.1090\/S0002-9947-1970-0410210-0"},{"key":"49","doi-asserted-by":"publisher","unstructured":"Lloyd Trefethen. ``Multivariate polynomial approximation in the hypercube''. Proc. Am. Math. Soc. 145, 4837\u20134844 (2017).","DOI":"10.1090\/proc\/13623"},{"key":"50","doi-asserted-by":"publisher","unstructured":"TW Parks and James McClellan. ``Chebyshev approximation for nonrecursive digital filters with linear phase''. IEEE Transactions on circuit theory 19, 189\u2013194 (1972).","DOI":"10.1109\/TCT.1972.1083419"},{"key":"51","doi-asserted-by":"publisher","unstructured":"GA Watson. ``A multiple exchange algorithm for multivariate Chebyshev approximation''. SIAM J. Numer. Anal. 12, 46\u201352 (1975).","DOI":"10.1137\/0712004"},{"key":"52","doi-asserted-by":"publisher","unstructured":"Hugo J Woerdeman, Jeffrey S Geronimo, and Glaysar Castro. ``A numerical algorithm for stable 2D autoregressive filter design''. Signal Processing 83, 1299\u20131308 (2003).","DOI":"10.1016\/S0165-1684(03)00057-4"},{"key":"53","doi-asserted-by":"publisher","unstructured":"Yvan Hachez and Hugo J Woerdeman. ``Approximating sums of squares with a single square''. Linear Algebra Appl. 399, 187\u2013201 (2005).","DOI":"10.1016\/j.laa.2004.10.005"},{"key":"54","doi-asserted-by":"publisher","unstructured":"Mario Szegedy. ``Quantum speed-up of Markov chain based algorithms''. In 45th Annual IEEE symposium on foundations of computer science. Pages 32\u201341. IEEE (2004).","DOI":"10.1109\/FOCS.2004.53"},{"key":"55","doi-asserted-by":"publisher","unstructured":"Chris Marriott and John Watrous. ``Quantum Arthur\u2013Merlin games''. Comput. Complex. 14, 122\u2013152 (2005).","DOI":"10.1007\/s00037-005-0194-x"},{"key":"56","doi-asserted-by":"publisher","unstructured":"Daniel Nagaj, Pawel Wocjan, and Yong Zhang. ``Fast amplification of QMA''. Quantum Info. Comput. 9, 1053\u20131068 (2009).","DOI":"10.26421\/QIC9.11-12-8"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-09-20-811\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2022,9,20]],"date-time":"2022-09-20T10:33:21Z","timestamp":1663670001000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-09-20-811\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,20]]},"references-count":57,"URL":"https:\/\/doi.org\/10.22331\/q-2022-09-20-811","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,20]]},"article-number":"811"}}