1Department of Physics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
2Department of Physics, Department of Electrical Engineering and Computer Science, and Co-Design Center for Quantum Advantage, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
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ätze, 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 $single$ oracle, saying nothing about computing $textit{joint properties}$ 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 $stable$ 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 $obliviously$ approximate $textit{joint functions}$ 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.
Featured image: A figurative representation of the circuits considered in M-QSP; here the querent can successively apply their own unitary operations, interleaved among possibly both of two oracular unitary operations. The properties of such circuits, and the functions they achieve in the parameters of each oracle, are the primary focus of the theory of M-QSP.
Popular summary
This work takes the underlying intuition and mathematical foundation of the standard statement of QSP and investigates how they can be extended to a multivariable setting. I.e., if one wishes instead to coherently compute joint functions of multiple signals with alternating quantum circuit ansätze, what are the corresponding results from algebraic geometry necessary to constitute a useful theory of multivariable QSP/QSVT (M-QSP/M-QSVT)? In turn, the ability to compute joint functions can be shown to save query and gate complexity in comparison to multiple iterations of single-variable instances. To this end we provide a series of initial results showing that, up to a well-defined conjecture, the possible multivariable transformations with M-QSP/M-QSVT are as loosely constrained as could be expected.
In addition to demonstrating how a change of setting for QSP/QSVT can lead to a vastly extended family of quantum algorithms, this work also points toward a wide family of mathematical subfields and methods with the possibility of novel relevance to quantum information. This work promotes a new, bottom-up approach to understanding QSP/QSVT-like circuits, repurposing and extending powerful and seemingly unrelated mathematical techniques toward new physical intuition and computational possibilities.
► BibTeX data
► References
[1] András Gilyén, 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).
https://doi.org/10.1145/3313276.3316366
[2] Patrick Rall. “Faster coherent quantum algorithms for phase, energy, and amplitude estimation”. Quantum 5, 566 (2021).
https://doi.org/10.22331/q-2021-10-19-566
[3] John M. Martyn, Yuan Liu, Zachary E. Chin, and Isaac L. Chuang. “Efficient fully-coherent Hamiltonian simulation” (2021). arXiv:2110.11327.
arXiv:2110.11327
[4] John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang. “Grand unification of quantum algorithms”. PRX Quantum 2, 040203 (2021).
https://doi.org/10.1103/PRXQuantum.2.040203
[5] 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.
arXiv:2104.01410
[6] András Gilyén and Alexander Poremba. “Improved quantum algorithms for fidelity estimation” (2022). arXiv:2203.15993.
arXiv:2203.15993
[7] András Gilyén, 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).
https://doi.org/10.1103/PhysRevLett.128.220502
[8] Zane M Rossi and Isaac L Chuang. “Quantum hypothesis testing with group structure”. Physical Review A 104, 012425 (2021).
https://doi.org/10.1103/PhysRevA.104.012425
[9] Nai-Hui Chia, András Gilyén, 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–400. STOC 2020New York, NY, USA (2020). Association for Computing Machinery.
https://doi.org/10.1145/3357713.3384314
[10] Alex Lombardi, Fermi Ma, and Nicholas Spooner. “Post-quantum zero knowledge, revisited (or: How to do quantum rewinding undetectably)” (2021). arXiv:2111.12257.
arXiv:2111.12257
[11] G. H. Low, T. J. Yoder, and I. L. Chuang. “Methodology of resonant equiangular composite quantum gates”. Phys. Rev. X 6, 041067 (2016).
https://doi.org/10.1103/PhysRevX.6.041067
[12] G. H. Low and I. L. Chuang. “Optimal Hamiltonian simulation by quantum signal processing”. Phys. Rev. Lett. 118, 010501 (2017).
https://doi.org/10.1103/PhysRevLett.118.010501
[13] G. H. Low and I. L. Chuang. “Hamiltonian simulation by qubitization”. Quantum 3, 163 (2019).
https://doi.org/10.22331/q-2019-07-12-163
[14] 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
[15] 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
[16] Yulong Dong, Xiang Meng, K. Birgitta Whaley, and Lin Lin. “Efficient phase-factor evaluation in quantum signal processing”. Phys. Rev. A 103 (2021).
https://doi.org/10.1103/physreva.103.042419
[17] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. “Quantum algorithm for linear systems of equations”. Phys. Rev. Lett. 103 (2009).
https://doi.org/10.1103/physrevlett.103.150502
[18] Peter W Shor. “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”. SIAM review 41, 303–332 (1999).
https://doi.org/10.1137/S0097539795293172
[19] Richard P Feynman. “Simulating physics with computers”. In Feynman and computation. Pages 133–153. CRC Press (2018).
https://doi.org/10.1007/BF02650179
[20] Jintai Ding and Bo-Yin Yang. “Multivariate public key cryptography”. In Post-quantum cryptography. Pages 193–241. Springer (2009).
https://doi.org/10.1007/978-0-387-36946-4
[21] 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–60. (2012).
https://doi.org/10.48550/arXiv.1203.4740
[22] 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–18. (2022).
https://doi.org/10.1145/3519935.3519962
[23] Rahul Sarkar and Theodore J. Yoder. “Density theorems with applications in quantum signal processing” (2022). arXiv:2111.07182.
arXiv:2111.07182
[24] Jiasu Wang, Yulong Dong, and Lin Lin. “On the energy landscape of symmetric quantum signal processing” (2021). arXiv:2110.04993.
arXiv:2110.04993
[25] Joran Van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. “Quantum SDP-solvers: Better upper and lower bounds”. Quantum 4, 230 (2020).
https://doi.org/10.48550/arXiv.1705.01843
[26] Lin Lin and Yu Tong. “Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems”. Quantum 4, 361 (2020).
https://doi.org/10.22331/q-2020-11-11-361
[27] Patrick Rall. “Quantum algorithms for estimating physical quantities using block encodings”. Phys. Rev. A 102, 022408 (2020).
https://doi.org/10.1103/PhysRevA.102.022408
[28] 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).
https://doi.org/10.1103/PhysRevA.104.032422
[29] J. Geronimo and Hugo Woerdeman. “Positive extensions, Fejér-Riesz factorization and autoregressive filters in two variables”. Ann. Math. 160, 839–906 (2004).
https://doi.org/10.4007/annals.2004.160.839
[30] Murray Marshall. “Positive polynomials and sums of squares”. Number 146 in Mathematical surveys and monographs. Am. Math. Soc. (2008).
https://doi.org/10.1090/surv/146
[31] Bogdan Dumitrescu. “Positive trigonometric polynomials and signal processing applications”. Springer. Switzerland (2007).
https://doi.org/10.1007/978-3-319-53688-0
[32] Michael Dritschel and Hugo Woerdeman. “Outer factorizations in one and several variables”. Trans. Am. Math. Soc. 357, 4661–4679 (2005).
https://doi.org/10.48550/arXiv.math/0403099
[33] 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–825 (2007).
https://doi.org/10.1137/060662472
[34] Michael A. Dritschel and James Rovnyak. “The operator Fejér-Riesz theorem”. Pages 223–254. Springer Basel. Basel (2010).
https://doi.org/10.1007/978-3-0346-0347-8_14
[35] Robin Hartshorne. “Algebraic geometry”. Volume 52. Springer New York, NY. (2013).
https://doi.org/10.1007/978-1-4757-3849-0
[36] William Fulton. “Algebraic curves: An introduction to algebraic geometry”. Addison-Wesley. (1969). url: dept.math.lsa.umich.edu/ wfulton/CurveBook.pdf.
https://dept.math.lsa.umich.edu/~wfulton/CurveBook.pdf
[37] George Polya and Gabor Szegö. “Problems and theorems in analysis II”. Springer. Berlin (1998).
https://doi.org/10.1007/978-3-642-61905-2
[38] F. Grenez. “Design of linear or minimum-phase FIR filters by constrained Chebyshev approximation”. Signal Process. 5, 325–332 (1983).
https://doi.org/10.1016/0165-1684(83)90091-9
[39] E. Remez. “Sur le calcul effectif des polynomes dapproximation de Tchebichef”. C. R. Acad. Sci. Paris 199, 337–340 (1934).
[40] J. McClellan, T. Parks, and L. Rabiner. “A computer program for designing optimum FIR linear phase digital filters”. IEEE trans. audio electroacoust. 21, 506–526 (1973).
https://doi.org/10.1109/TAU.1973.1162525
[41] Jeffrey S Geronimo and Hugo J Woerdeman. “Two-variable polynomials: intersecting zeros and stability”. IEEE Trans. Circuits Syst. I: Regular Papers 53, 1130–1139 (2006).
https://doi.org/10.1109/TCSI.2005.862180
[42] 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–26 (2016).
https://doi.org/10.1007/s11045-014-0286-3
[43] Rudolf Lidl and Ch. Wells. “Chebyshev polynomials in several variables.”. Journal für die reine und angewandte Mathematik 255, 104–111 (1972).
https://doi.org/10.1515/crll.1972.255.104
[44] Charles F Dunkl and Yuan Xu. “Orthogonal polynomials of several variables”. Number 155 in Encyclopedia of mathematics and its applications. Cambridge University Press. (2014).
https://doi.org/10.1017/CBO9781107786134
[45] RJ Beerends. “Chebyshev polynomials in several variables and the radial part of the Laplace-Beltrami operator”. Trans. Am. Math. Soc. 328, 779–814 (1991).
https://doi.org/10.2307/2001804
[46] Zane M Rossi, Jeffery Yu, Isaac L Chuang, and Sho Sugiura. “Quantum advantage for noisy channel discrimination”. Phys. Rev. A 105, 032401 (2022).
https://doi.org/10.1103/PhysRevA.105.032401
[47] Camille Jordan. “Essai sur la géométrie à $ n $ dimensions”. Bulletin de la Société mathématique de France 3, 103–174 (1875).
[48] DJ Newman and HS Shapiro. “Jackson’s theorem in higher dimensions”. In On Approximation Theory/Über Approximationstheorie. Pages 208–219. Springer (1964).
https://doi.org/10.1007/978-3-0348-4131-3_20
[49] David L Ragozin. “Polynomial approximation on compact manifolds and homogeneous spaces”. Trans. Am. Math. Soc. 150, 41–53 (1970).
https://doi.org/10.1090/S0002-9947-1970-0410210-0
[50] Lloyd Trefethen. “Multivariate polynomial approximation in the hypercube”. Proc. Am. Math. Soc. 145, 4837–4844 (2017).
https://doi.org/10.1090/proc/13623
[51] TW Parks and James McClellan. “Chebyshev approximation for nonrecursive digital filters with linear phase”. IEEE Transactions on circuit theory 19, 189–194 (1972).
https://doi.org/10.1109/TCT.1972.1083419
[52] GA Watson. “A multiple exchange algorithm for multivariate Chebyshev approximation”. SIAM J. Numer. Anal. 12, 46–52 (1975).
https://doi.org/10.1137/0712004
[53] Hugo J Woerdeman, Jeffrey S Geronimo, and Glaysar Castro. “A numerical algorithm for stable 2D autoregressive filter design”. Signal Processing 83, 1299–1308 (2003).
https://doi.org/10.1016/S0165-1684(03)00057-4
[54] Yvan Hachez and Hugo J Woerdeman. “Approximating sums of squares with a single square”. Linear Algebra Appl. 399, 187–201 (2005).
https://doi.org/10.1016/j.laa.2004.10.005
[55] Mario Szegedy. “Quantum speed-up of Markov chain based algorithms”. In 45th Annual IEEE symposium on foundations of computer science. Pages 32–41. IEEE (2004).
https://doi.org/10.1109/FOCS.2004.53
[56] Chris Marriott and John Watrous. “Quantum Arthur–Merlin games”. Comput. Complex. 14, 122–152 (2005).
https://doi.org/10.1007/s00037-005-0194-x
[57] Daniel Nagaj, Pawel Wocjan, and Yong Zhang. “Fast amplification of QMA”. Quantum Info. Comput. 9, 1053–1068 (2009).
https://doi.org/10.26421/QIC9.11-12-8
Cited by
[1] Zhan Yu, Hongshun Yao, Mujin Li, and Xin Wang, “Power and limitations of single-qubit native quantum neural networks”, arXiv:2205.07848.
[2] Shantanav Chakraborty, Aditya Morolia, and Anurudh Peduri, “Quantum Regularized Least Squares”, arXiv:2206.13143.
The above citations are from SAO/NASA ADS (last updated successfully 2022-10-10 12:31:06). The list may be incomplete as not all publishers provide suitable and complete citation data.
On Crossref’s cited-by service no data on citing works was found (last attempt 2022-10-10 12:31:04).
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.