Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle
arXiv:2205.06261 · doi:10.22331/q-2022-09-20-811
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 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 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.
23 pages + 4 figures + 10 page appendix (added background information on algebraic geometry; publication in Quantum)
References in corpus (7)
- Quantum algorithm for solving linear systems of equations
- A Grand Unification of Quantum Algorithms
- Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
- An area law for 2D frustration-free spin systems
- Quantum advantage for noisy channel discrimination
- Quantum Hypothesis Testing with Group Structure
- Outer factorizations in one and several variables
Cited by in corpus (18)
- Hybrid Oscillator-Qubit Quantum Processors: Instruction Set Architectures, Abstract Machine Models, and Applications
- Nearly-optimal state preparation for quantum simulations of lattice gauge theories
- Quantum Regularized Least Squares
- Derivative Pricing using Quantum Signal Processing
- Quantum state preparation for multivariate functions
- Single-shot Quantum Signal Processing Interferometry
- Block encoding bosons by signal processing
- On multivariate polynomials achievable with quantum signal processing
- Comment on "Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle"
- Infinite quantum signal processing for arbitrary Szegő functions
- Encoding of linear kinetic plasma problems in quantum circuits via data compression
- Modular quantum signal processing in many variables
- Topological Signal Processing on Quantum Computers for Higher-Order Network Analysis
- Scalable Quantum Computational Science: A Perspective from Block-Encodings and Polynomial Transformations
- Parallel Quantum Signal Processing Via Polynomial Factorization
- Quantum Signal Processing and Quantum Singular Value Transformation on
- An adversary bound for quantum signal processing
- Quantum Framework for Simulating Linear PDEs with Robin Boundary Conditions