Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics

Abstract

Quantum computing is powerful because unitary operators describing the time-evolution of a quantum system have exponential size in terms of the number of qubits present in the system. We develop a new "Singular value transformation" algorithm capable of harnessing this exponential advantage, that can apply polynomial transformations to the singular values of a block of a unitary, generalizing the optimal Hamiltonian simulation results of Low and Chuang. The proposed quantum circuits have a very simple structure, often give rise to optimal algorithms and have appealing constant factors, while usually only use a constant number of ancilla qubits. We show that singular value transformation leads to novel algorithms. We give an efficient solution to a certain "non-commutative" measurement problem and propose a new method for singular value estimation. We also show how to exponentially improve the complexity of implementing fractional queries to unitaries with a gapped spectrum. Finally, as a quantum machine learning application we show how to efficiently implement principal component regression. "Singular value transformation" is conceptually simple and efficient, and leads to a unified framework of quantum algorithms incorporating a variety of quantum speed-ups. We illustrate this by showing how it generalizes a number of prominent quantum algorithms, including: optimal Hamiltonian simulation, implementing the Moore-Penrose pseudoinverse with exponential precision, fixed-point amplitude amplification, robust oblivious amplitude amplification, fast QMA amplification, fast quantum OR lemma, certain quantum walk results and several quantum machine learning algorithms. In order to exploit the strengths of the presented method it is useful to know its limitations too, therefore we also prove a lower bound on the efficiency of singular value transformation, which often gives optimal bounds.

arXiv comment67 pages, 1 figure

References in corpus (18)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum algorithm for solving linear systems of equations
• Quantum principal component analysis
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Search via Quantum Walk
• Fixed-point quantum search with an optimal number of queries
• A different kind of quantum search
• Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
• On Arbitrary Phases in Quantum Amplitude Amplification
• The methodology of resonant equiangular composite quantum gates
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• Product Decomposition of Periodic Functions in Quantum Signal Processing
• Operator Lipschitz Functions
• Approximating Fractional Time Quantum Evolution
• On preparing ground states of gapped Hamiltonians: An efficient Quantum Lovász Local Lemma

Cited by in corpus (257)

• Quantum Chemistry in the Age of Quantum Computing
• Hamiltonian Simulation by Qubitization
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Quantum computing for finance
• Near-optimal ground state preparation
• Computational advantage of quantum random sampling
• Quantum Algorithms for Simulating the Lattice Schwinger Model
• Noisy intermediate-scale quantum computers
• Drug design on quantum computers
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Improved quantum algorithms for linear and nonlinear differential equations
• A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance
• A randomized quantum algorithm for statistical phase estimation
• A Hardware-Aware Heuristic for the Qubit Mapping Problem in the NISQ Era
• Quantum SDP-Solvers: Better upper and lower bounds
• Product Decomposition of Periodic Functions in Quantum Signal Processing
• Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost
• Provably accurate simulation of gauge theories and bosonic systems
• Time-dependent unbounded Hamiltonian simulation with vector norm scaling
• Time-marching based quantum solvers for time-dependent linear differential equations
• Nearly tight Trotterization of interacting electrons
• On applications of quantum computing to plasma simulations
• On the energy landscape of symmetric quantum signal processing
• Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance
• General quantum algorithms for Hamiltonian simulation with applications to a non-Abelian lattice gauge theory
• Time complexity analysis of quantum algorithms via linear representations for nonlinear ordinary and partial differential equations
• An improved quantum-inspired algorithm for linear regression
• Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
• Hybridized Methods for Quantum Simulation in the Interaction Picture
• Simulating Open Quantum System Dynamics on NISQ Computers with Generalized Quantum Master Equations
• Thermal State Preparation via Rounding Promises
• Towards quantum advantage via topological data analysis
• Quantum Machine Learning for Finance
• Block-encoding structured matrices for data input in quantum computing
• Quantum Machine Learning in Drug Discovery: Applications in Academia and Pharmaceutical Industries
• Quantum Algorithm for Fidelity Estimation
• Trainability barriers and opportunities in quantum generative modeling
• Time-dependent Hamiltonian Simulation of Highly Oscillatory Dynamics and Superconvergence for Schrödinger Equation
• Efficient quantum amplitude encoding of polynomial functions
• Two-Unitary Decomposition Algorithm and Open Quantum System Simulation
• Towards Quantum Advantage in Financial Market Risk using Quantum Gradient Algorithms
• Quantum algorithm for persistent Betti numbers and topological data analysis
• Heisenberg-limited quantum phase estimation of multiple eigenvalues with few control qubits
• Quantum algorithms for Second-Order Cone Programming and Support Vector Machines
• On the complexity of quantum partition functions
• Quantum Computing for Fusion Energy Science Applications
• Quantum Resources Required to Block-Encode a Matrix of Classical Data
• FABLE: Fast Approximate Quantum Circuits for Block-Encodings
• New Quantum Algorithms for Computing Quantum Entropies and Distances
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Exact solution for the quantum and private capacities of bosonic dephasing channels
• Multivariate trace estimation in constant quantum depth
• Quantum Reinforcement Learning via Policy Iteration
• Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle
• Efficient quantum Gibbs samplers with Kubo--Martin--Schwinger detailed balance condition
• Quantum simulation of real-space dynamics
• Quantum algorithms from fluctuation theorems: Thermal-state preparation
• Simulating Effective QED on Quantum Computers
• Amplitude Estimation from Quantum Signal Processing
• An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation
• Stable factorization for phase factors of quantum signal processing
• Quantum Computing and Preconditioners for Hydrological Linear Systems
• Systems Architecture for Quantum Random Access Memory
• Selected topics of quantum computing for nuclear physics
• Quantum algorithm for Neighborhood Preserving Embedding
• Quantum Interior Point Methods for Semidefinite Optimization
• Quantum Natural Language Processing
• A quantum hamiltonian simulation benchmark
• Fragmented imaginary-time evolution for early-stage quantum signal processors
• Quantum Regularized Least Squares
• Szegedy Walk Unitaries for Quantum Maps
• Fast Quantum Algorithms for Trace Distance Estimation
• Time complexity analysis of quantum difference methods for linear high dimensional and multiscale partial differential equations
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• Improved Accuracy for Trotter Simulations Using Chebyshev Interpolation
• Perturbation theory with quantum signal processing
• An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic Optimization
• Quantum Pufferfish Privacy: A Flexible Privacy Framework for Quantum Systems
• A hybrid quantum-classical framework for computational fluid dynamics
• Circuit complexity of quantum access models for encoding classical data
• Tailoring Term Truncations for Electronic Structure Calculations Using a Linear Combination of Unitaries
• 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
• Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm
• Efficient algorithms for quantum information bottleneck
• Quantum algorithms for scientific computing
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications
• A comparative study of universal quantum computing models: towards a physical unification
• Quantum Optimization for Training Quantum Neural Networks
• Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
• Quantum algorithms for computing observables of nonlinear partial differential equations
• Variational quantum solver employing the PDS energy functional
• Fault-tolerant quantum computation of molecular observables
• Towards Perturbation Theory Methods on a Quantum Computer
• Quantum mean centering for block-encoding-based quantum algorithm
• Faster quantum chemistry simulations on a quantum computer with improved tensor factorization and active volume compilation
• Quantum algorithm for the advection-diffusion equation and the Koopman-von Neumann approach to nonlinear dynamical systems
• Optimal Hamiltonian simulation for time-periodic systems
• Quantum-accelerated constraint programming
• Double-bracket quantum algorithms for diagonalization
• Quantum differential equation solvers: limitations and fast-forwarding
• Efficient and precise quantum simulation of ultra-relativistic quark-nucleus scattering
• Complementarity and the unitarity of the black hole $S$-matrix
• Efficient Unitary T-designs from Random Sums
• Observation of a non-Hermitian supersonic mode on a trapped-ion quantum computer
• Quantum Langevin Dynamics for Optimization
• Efficient unitary designs and pseudorandom unitaries from permutations
• Benchmarking universal quantum gates via channel spectrum
• Quantum Next Generation Reservoir Computing: An Efficient Quantum Algorithm for Forecasting Quantum Dynamics
• Quantum simulation of colour in perturbative quantum chromodynamics
• Hamiltonian simulation for low-energy states with optimal time dependence
• Explicit Quantum Circuit for Simulating the Advection-Diffusion-Reaction Dynamics
• Signal processing techniques for efficient compilation of controlled rotations in trapped ions
• Implementing smooth functions of a Hermitian matrix on a quantum computer
• Quantum state preparation for multivariate functions
• Parallel Quantum Algorithm for Hamiltonian Simulation
• On proving the robustness of algorithms for early fault-tolerant quantum computers
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• Improved amplitude amplification strategies for the quantum simulation of classical transport problems
• Probing spectral features of quantum many-body systems with quantum simulators
• Quantum simulation of discrete linear dynamical systems and simple iterative methods in linear algebra via Schrodingerisation
• Universal resources for quantum computing
• Faster spectral density calculation using energy moments
• Solving the Hele-Shaw flow using the Harrow-Hassidim-Lloyd algorithm on superconducting devices: A study of efficiency and challenges
• QRAM: A Survey and Critique
• Toward Mixed Analog-Digital Quantum Signal Processing: Quantum AD/DA Conversion and the Fourier Transform
• Succinct Description and Efficient Simulation of Non-Markovian Open Quantum Systems
• Time-dependent Hamiltonian Simulation via Magnus Expansion: Algorithm and Superconvergence
• A multiple-circuit approach to quantum resource reduction with application to the quantum lattice Boltzmann method
• Halving the Cost of Quantum Algorithms with Randomization
• Double-bracket quantum algorithms for quantum imaginary-time evolution
• Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems
• Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era
• An invitation to the sample complexity of quantum hypothesis testing
• Quantum and classical query complexities of functions of matrices
• End-to-end complexity for simulating the Schwinger model on quantum computers
• Quantum Computation of Electronic Structure with Projector Augmented-Wave Method and Plane Wave Basis Set
• Block encoding bosons by signal processing
• Quantum Algorithm For Estimating Eigenvalue
• Explicit block encodings of boundary value problems for many-body elliptic operators
• A Universal Quantum Circuit Design for Periodical Functions
• Estimating Gibbs partition function with quantumClifford sampling
• Resource Analysis of Low-Overhead Transversal Architectures for Reconfigurable Atom Arrays
• Quantum algorithms for matrix geometric means
• Complementary polynomials in quantum signal processing
• TE-PAI: Exact Time Evolution by Sampling Random Circuits
• Polynomial Time Quantum Gibbs Sampling for Fermi-Hubbard Model at any Temperature
• A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation
• Optimal exact quantum algorithm for the promised element distinctness problem
• Lower bound for simulation cost of open quantum systems: Lipschitz continuity approach
• Randomized semi-quantum matrix processing
• Quantum Algorithms for the Pathwise Lasso
• Solving lattice gauge theories using the quantum Krylov algorithm and qubitization
• Molecular Properties from Quantum Krylov Subspace Diagonalization
• On Quantum Circuits for Discrete Graphical Models
• On multivariate polynomials achievable with quantum signal processing
• Quantum Algorithm for Estimating Betti Numbers Using Cohomology Approach
• Nearly-frustration-free ground state preparation
• Comment on "Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle"
• Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth
• Lindblad engineering for quantum Gibbs state preparation under the eigenstate thermalization hypothesis
• Infinite quantum signal processing for arbitrary Szegő functions
• Hamiltonian Learning via Shadow Tomography of Pseudo-Choi States
• Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems
• Quantum phase estimation based filtering: performance analysis and application to low-energy spectral calculation
• Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions
• An efficient quantum parallel repetition theorem and applications
• Ladder Operator Block-Encoding
• A comparison of three ways to measure time-dependent densities with quantum simulators
• Modular quantum signal processing in many variables
• Encoding of linear kinetic plasma problems in quantum circuits via data compression
• Optimal Low-Depth Quantum Signal-Processing Phase Estimation
• Average-Case Verification of the Quantum Fourier Transform Enables Worst-Case Phase Estimation
• Double-bracket algorithm for quantum signal processing without post-selection
• Efficient Gaussian State Preparation in Quantum Circuits
• Estimating Eigenenergies from Quantum Dynamics: A Unified Noise-Resilient Measurement-Driven Approach
• Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
• Heisenberg-limited adaptive gradient estimation for multiple observables
• Readout Error Mitigation for Mid-Circuit Measurements and Feedforward
• Quantum eigenvalue processing
• QKAN: quantum Kolmogorov-Arnold networks with applications in machine learning and multivariate state preparation
• Hybrid Quantum-Classical Algorithm For Robust Optimization via Stochastic-Gradient Online Learning
• Quantum algorithms for linear and non-linear fractional reaction-diffusion equations
• Time-Efficient Quantum Entropy Estimator via Samplizer
• Short-time quantum Fourier transform processing
• Parallelization techniques for quantum simulation of fermionic systems
• Systematic many-fermion Hamiltonian input scheme and spectral calculations on quantum computers
• Lower Bounds for Unitary Property Testing with Proofs and Advice
• Hardware-efficient quantum phase estimation via local control
• Parameterized quantum comb and simpler circuits for reversing unknown qubit-unitary operations
• Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding
• Multidimensional Electrical Networks and their Application to Exponential Speedups for Graph Problems
• Quantum bounds for compiled XOR games and $d$-outcome CHSH games
• Optimal Coherent Quantum Phase Estimation via Tapering
• High-precision and low-depth quantum algorithm design for eigenstate problems
• Estimating QSVT angles for matrix inversion with large condition numbers
• Quantum Calculation for Two-Stream Instability and Advection Test of Vlasov-Maxwell Equations: Numerical Evaluation of Hamiltonian Simulation
• Quantum state preparation via piecewise QSVT
• Parallel Quantum Signal Processing Via Polynomial Factorization
• Provable quantum speedups for computing persistence in topological data analysis
• Quantum implicit representation of vortex filaments in turbulence
• Universal Hamiltonian simulators in one and two dimensions
• On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
• On the Trotter Error in Many-body Quantum Dynamics with Coulomb Potentials
• A quantum algorithm for linear autonomous differential equations via Padé approximation
• Measurement Schemes for Quantum Linear Equation Solvers
• Quantum linear system algorithm with optimal queries to initial state preparation
• Quantum natural gradient with thermal-state initialization
• TrackHHL: A Quantum Computing Algorithm for Track Reconstruction at the LHCb
• Discrete Superconvergence Analysis for Quantum Magnus Algorithms of Unbounded Hamiltonian Simulation
• Learning the structure of any Hamiltonian from minimal assumptions
• Space-Efficient Quantum Error Reduction without log Factors
• Controlled Gate Networks: Theory and Application to Eigenvalue Estimation
• Quantized Markov Chain Couplings that Prepare Qsamples
• Two exact quantum signal processing results
• Solving coupled Non-linear Schrödinger Equations via Quantum Imaginary Time Evolution
• Energy-saving fast-forward scaling
• On the commutator scaling in Hamiltonian simulation with multi-product formulas
• Lower bounds for quantum-inspired classical algorithms via communication complexity
• Towards Practical Quantum Phase Estimation: A Modular, Scalable, and Adaptive Approach
• Simple and efficient end-to-end quantum thermal and ground state preparation
• Quantum algorithms based on quantum trajectories
• Warm-Start Variational Quantum Policy Iteration
• End-to-End Quantum Algorithm for Topology Optimization in Structural Mechanics
• Revisiting fixed-point quantum search: proof of the quasi-Chebyshev lemma
• Error analysis of quantum operators written as a linear combination of permutations
• When Quantum and Classical Models Disagree: Learning Beyond Minimum Norm Least Square
• Classical optimization with imaginary time block encoding on quantum computers: The MaxCut problem
• Sub-quadratic scalable approximate linear converter using multi-plane light conversion with low-entropy mode mixers
• Explicit decoders using fixed-point amplitude amplification based on QSVT
• Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs
• Quantum Merlin-Arthur proof systems for synthesizing quantum states
• Nonlinear path-following via the asymptotic numerical method on a quantum processor
• Post-Moore Technologies for Plasma Simulation: A Community Roadmap
• Natural gradient and parameter estimation for quantum Boltzmann machines
• An adversary bound for quantum signal processing
• Quantum Algorithm For Solving Nonlinear Algebraic Equations
• Co-Designing Spectral Transformation Oracles with Hybrid Oscillator-Qubit Quantum Processors: From Algorithms to Compilation
• QAFE${}^2$: Quantum accelerated multiscale finite element analysis
• Optimal Hamiltonian recognition of unknown quantum dynamics
• Quantum-Efficient Reinforcement Learning Solutions for Last-Mile On-Demand Delivery
• Resilience-Runtime Tradeoff Relations for Quantum Algorithms
• Quantum Signal Processing and Quantum Singular Value Transformation on $U(N)$
• Quantum Imaginary-Time Evolution with Polynomial Resources in Evolution Time
• Quantum Simulation of Nuclear Dynamics in First Quantization
• Quantum Computation
• Hybrid Quantum-Classical Clustering for Preparing a Prior Distribution of Eigenspectrum
• Determining Molecular Ground State with Quantum Imaginary Time Evolution using Broken-Symmetry Wave Function
• Quantum Simulation-Based Optimization for Cooling System Design
• Quantum oracles for the finite element method
• On the query complexity of unitary channel certification
• Quantum memory assisted observable estimation
• Spectral quantum algorithm for passive scalar transport in shear flows
• Quantum-Stable Robust Principal Component Analysis: Theory and Evidence from NISQ Regimes
• Operator-Level Quantum Acceleration of Non-Logconcave Sampling