Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:3NH6NBIQrecord.jsonopen to challenge →
read the original 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.
This paper has not been read by Pith yet.
Forward citations
Cited by 24 Pith papers
-
A Machine-Verified Proof of a Quantum-Optimization Conjecture
A Lean 4 machine-verified proof establishes that depth-p QAOA on the ring of disagrees attains approximation ratio (2p+1)/(2p+2) exactly.
-
Faster quantum linear system solver beyond the condition number
Two quantum linear system solvers are presented with query complexity independent of the condition number, scaling instead with an effective condition number or a solution-norm ratio.
-
Unbiased Hamiltonian Simulation by Reversing Trotter Error Dynamics
PTER removes Trotter errors in quantum Hamiltonian simulation via quasi-probabilistic reversal of the error dynamics, producing unbiased results with constant overhead.
-
Explicit Quantum Circuit Simulation of Nonlinear 1-Dimensional Fluid with Carleman-linearized Boltzmann Method
Explicit quantum-circuit simulation of nonlinear 1D fluid via second-order Carleman-linearized Boltzmann equation and QSVD Taylor ODE solver, with logarithmic scaling analysis.
-
Tightening energy-based boson truncation bound using Monte Carlo-assisted methods
Monte Carlo-assisted tightening of the energy-based boson truncation bound substantially reduces volume dependence in (1+1)D scalar field theory and (2+1)D U(1) gauge theory.
-
Tightening energy-based boson truncation bound using Monte Carlo-assisted methods
A Monte Carlo-assisted analytic method tightens energy-based bounds on boson truncation errors, substantially reducing the volume dependence of the required cutoff in scalar and gauge theories.
-
Constrained Optimal Polynomials for Quantum Linear System Solvers
Constrained Uniform Polynomial (CUP) and Constrained Adaptive Polynomial (CAP) solvers achieve lower error than standard QSVT and Chebyshev methods in noise-limited regimes by optimizing accuracy versus block-encoding...
-
Nonisothermal global-pressure exactness in fractured multiphase flow with aperture feedback
A new mixed saturation-temperature compatibility condition is derived for exact global-pressure equivalence in nonisothermal multiphase fractured flow, with numerical benchmarks confirming regimes where exactness hold...
-
Random dilation superchannel
Presents a poly-complexity quantum circuit implementing the random dilation superchannel for parallel channel queries, with approximate sequential extension, a no-go theorem for exact sequential dilation, and an appli...
-
Probabilistic quantum algorithm for Lyapunov equations and matrix inversion
Probabilistic quantum algorithm prepares mixed states proportional to Lyapunov equation solutions and matrix inverses using oracles for input matrices and a deterministic stopping rule.
-
Polynomial time constructive decision algorithm for multivariable quantum signal processing
A polynomial-time classical decision algorithm exactly characterizes which multivariable Laurent polynomial pairs are realizable by M-QSP and supplies a constructive implementation when the answer is yes.
-
A shortcut to an optimal quantum linear system solver
The paper gives a QLSS with query complexity (1+O(ε))κ ln(2√2/ε) using one kernel reflection when ||x|| is known, or O(κ log(1/ε)) overall, with explicit bound 56κ + 1.05κ ln(1/ε).
-
Fixing Divergence in Carleman Linearization via Analytical Continuation
A Möbius conformal map and regularized incomplete beta function fix the long-time divergence of Carleman linearization for logistic, KPP-Fisher, and phase-field equations.
-
Quantum algorithm for solving differential equations using SLAC derivatives
Presents LCU block-encodings for SLAC derivative operators, applies Shannon wavelets and preconditioning, and obtains O(d n^3 α^(k) log(1/ε)) gate complexity for d-dimensional PDEs via QLSA.
-
Fault-Tolerant Resource Comparison of Qudit and Qubit Encodings for Diagonal Quadratic Operators
Qudit encodings for quadratic diagonal evolutions require exponentially stronger synthesis advantages than qubits to win asymptotically in product formulas but can yield constant-factor savings in LCU at low d.
-
Nonisothermal global-pressure exactness in fractured multiphase flow with aperture feedback
Constrained optimal polynomials (CUP and CAP) reduce quantum linear system solver errors under noise by jointly optimizing approximation accuracy and block-encoding normalization, outperforming standard QSVT and Cheby...
-
Phase-Stable Hologram Updates for Large-Scale Neutral-Atom Array Reconfiguration
WPGS algorithm enforces inter-frame phase continuity in holographic tweezers to suppress refresh-induced atom loss and speed up updates for large neutral-atom arrays.
-
Implementing Hamiltonian Renormalization Group Flow on Quantum Computers with VAPOR
VAPOR is a variational quantum algorithm that finds RG fixed points for naively discretized operators in a symmetry-restricted SU(2) Yang-Mills toy model by decomposing into Pauli strings.
-
Quantum algorithm for solving differential equations using SLAC derivatives
Efficient quantum block-encodings of SLAC first-order derivative and Laplacian operators are built with LCU, state preparation, wavelet multi-scale transforms, and preconditioning to solve PDEs via QLSA with analyzed ...
-
Fault-Tolerant Resource Comparison of Qudit and Qubit Encodings for Diagonal Quadratic Operators
The paper derives explicit finite-d break-even synthesis costs for qudit vs. qubit encodings of diagonal quadratic operators in product-formula and LCU simulations, identifying low-d regions where qudits yield savings.
-
Tightening energy-based boson truncation bound using Monte Carlo-assisted methods
New analytic and Monte Carlo-assisted method tightens energy-based boson truncation bounds, reducing volume dependence in (1+1)D scalar and (2+1)D U(1) gauge theories.
-
Quantum simulation of massive Thirring and Gross--Neveu models for arbitrary number of flavors
Quantum simulation methods for Thirring and Gross-Neveu fermionic models with arbitrary flavors, including gate complexity bounds and ground-state preparation up to 20 qubits.
-
Unitaria: Quantum Linear Algebra via Block Encodings
Unitaria is a new open-source Python library that provides a high-level, composable interface for block encodings in quantum computing, enabling automatic circuit generation and classical simulation-based verification.
-
PyEncode: An Open-Source Library for Structured Quantum State Preparation
PyEncode supplies verified Qiskit circuits and gate-count predictors for exact amplitude encoding of sparse, step, square, Walsh, Fourier, geometric, Hamming, staircase, Dicke, and polynomial vectors.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.