Product Decomposition of Periodic Functions in Quantum Signal Processing
arXiv:1806.10236 · doi:10.22331/q-2019-10-07-190
Abstract
We consider an algorithm to approximate complex-valued periodic functions as a matrix element of a product of -valued functions, which underlies so-called quantum signal processing. We prove that the algorithm runs in time under the random-access memory model of computation where is the degree of the polynomial that approximates with accuracy ; previous efficiency claim assumed a strong arithmetic model of computation and lacked numerical stability analysis.
arXiv comment22 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 (12)
- Quantum algorithm for solving linear systems of equations
- Hamiltonian Simulation by Qubitization
- Optimal Hamiltonian Simulation by Quantum Signal Processing
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Toward the first quantum simulation with quantum speedup
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- On the relationship between continuous- and discrete-time quantum walk
- Hamiltonian simulation with nearly optimal dependence on all parameters
- Exponential improvement in precision for simulating sparse Hamiltonians
- The methodology of resonant equiangular composite quantum gates
- Faster integer multiplication using short lattice vectors
- Bounding the Sum of Square Roots via Lattice Reduction
Cited by in corpus (52)
- Hamiltonian Simulation by Qubitization
- 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
- Amplitude Estimation from Quantum Signal Processing
- Linear-depth quantum circuits for loading Fourier approximations of arbitrary functions
- 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
- Fault-tolerant quantum algorithms for quantum molecular systems: A survey
- Derivative Pricing using Quantum Signal Processing
- On efficient quantum block encoding of pseudo-differential operators
- 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
- Single-shot Quantum Signal Processing Interferometry
- Halving the Cost of Quantum Algorithms with Randomization
- Complementary polynomials in quantum signal processing
- Nearly-frustration-free ground state preparation
- On multivariate polynomials achievable with quantum signal processing
- Quantum phase estimation based filtering: performance analysis and application to low-energy spectral calculation
- Modular quantum signal processing in many variables
- Heisenberg-limited adaptive gradient estimation for multiple observables
- Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
- Quantum circuits for partial differential equations in Fourier space
- Quantum advantage in temporally flat measurement-based quantum computation
- Parallel Quantum Signal Processing Via Polynomial Factorization
- Scalable Quantum Computational Science: A Perspective from Block-Encodings and Polynomial Transformations
- Revisiting fixed-point quantum search: proof of the quasi-Chebyshev lemma
- Quantum Merlin-Arthur proof systems for synthesizing quantum states
- An adversary bound for quantum signal processing
- Explicit decoders using fixed-point amplitude amplification based on QSVT