Product Decomposition of Periodic Functions in Quantum Signal Processing

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.

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 https://github.com/microsoft/Quantum-NC

References in corpus (4)

• Quantum algorithm for solving linear systems of equations
• Toward the first quantum simulation with quantum speedup
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Faster integer multiplication using short lattice vectors

Cited by in corpus (51)

• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Near-optimal ground state preparation
• Efficient phase-factor evaluation in quantum signal processing
• Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices
• Quantum algorithm for simulating real time evolution of lattice Hamiltonians
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Time-marching based quantum solvers for time-dependent linear differential equations
• On the energy landscape of symmetric quantum signal processing
• Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm
• Hybridized Methods for Quantum Simulation in the Interaction Picture
• Realization of quantum signal processing on a noisy quantum computer
• Two-Unitary Decomposition Algorithm and Open Quantum System Simulation
• Efficient quantum amplitude encoding of polynomial functions
• Random circuit block-encoded matrix and a proposal of quantum LINPACK benchmark
• Quantum advantage for computations with limited space
• Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle
• Quantum Phase Processing and its Applications in Estimating Phase and Entropies
• Quantum algorithms from fluctuation theorems: Thermal-state preparation
• Linear-depth quantum circuits for loading Fourier approximations of arbitrary functions
• Amplitude Estimation from Quantum Signal Processing
• Hybrid Oscillator-Qubit Quantum Processors: Instruction Set Architectures, Abstract Machine Models, and Applications
• Stable factorization for phase factors of quantum signal processing
• Fragmented imaginary-time evolution for early-stage quantum signal processors
• Quantum Signal Processing for simulating cold plasma waves
• On efficient quantum block encoding of pseudo-differential operators
• Derivative Pricing using Quantum Signal Processing
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• End-to-end resource analysis for quantum interior point methods and portfolio optimization
• Infinite quantum signal processing
• Quantum algorithm for the advection-diffusion equation and the Koopman-von Neumann approach to nonlinear dynamical systems
• Signal processing techniques for efficient compilation of controlled rotations in trapped ions
• Simulation of linear non-Hermitian boundary-value problems with quantum singular value transformation
• Quantum Hypothesis Testing with Group Structure
• Halving the Cost of Quantum Algorithms with Randomization
• Single-shot Quantum Signal Processing Interferometry
• Complementary polynomials in quantum signal processing
• On multivariate polynomials achievable with quantum signal processing
• Nearly-frustration-free ground state preparation
• Quantum phase estimation based filtering: performance analysis and application to low-energy spectral calculation
• Modular quantum signal processing in many variables
• Quantum circuits for partial differential equations in Fourier space
• Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
• Heisenberg-limited adaptive gradient estimation for multiple observables
• Parallel Quantum Signal Processing Via Polynomial Factorization
• Quantum advantage in temporally flat measurement-based quantum computation
• Scalable Quantum Computational Science: A Perspective from Block-Encodings and Polynomial Transformations
• Revisiting fixed-point quantum search: proof of the quasi-Chebyshev lemma
• Explicit decoders using fixed-point amplitude amplification based on QSVT
• Quantum Merlin-Arthur proof systems for synthesizing quantum states
• An adversary bound for quantum signal processing