A Lean 4 machine-verified proof establishes that depth-p QAOA on the ring of disagrees attains approximation ratio (2p+1)/(2p+2) exactly.
hub Canonical reference
Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics
Canonical reference. 75% of citing Pith papers cite this work as background.
19
Pith papers citing it
498
external citations · Pith
Background
75% of classified citations
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.
hub tools
citation-role summary
background 6
method 2
citation-polarity summary
representative citing papers
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.
Explicit quantum-circuit simulation of nonlinear 1D fluid via second-order Carleman-linearized Boltzmann equation and QSVD Taylor ODE solver, with logarithmic scaling analysis.
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 normalization under uniform or moment-based spectral models.
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 application to exponentially improved channel storage-retrieval.
Probabilistic quantum algorithm prepares mixed states proportional to Lyapunov equation solutions and matrix inverses using oracles for input matrices and a deterministic stopping rule.
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.
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/ε).
A regularized function inserted into Carleman linearization, derived from a Möbius conformal map, removes the long-time divergence for logistic, KPP-Fisher, and phase-field models and supports an LCU quantum implementation.
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 Chebyshev-iteration solvers in numerical benchmarks.
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.
For diagonal quadratic evolutions, qubit encodings are asymptotically cheaper than qudit encodings in both Trotter and LCU settings, but small-dimension qudits can win under favorable synthesis or code-switching assumptions.
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.
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.
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.
PyEncode maps ten exact structured amplitude patterns plus SUM/PARTITION/TENSOR compositions and an MPS loader to verified Qiskit circuits with claimed poly(m) gate counts.
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 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.
citing papers explorer
-
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.
-
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.
-
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 normalization under uniform or moment-based spectral models.
-
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 application to exponentially improved channel storage-retrieval.
-
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 regularized function inserted into Carleman linearization, derived from a Möbius conformal map, removes the long-time divergence for logistic, KPP-Fisher, and phase-field models and supports an LCU quantum implementation.
-
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 Chebyshev-iteration solvers in numerical benchmarks.
-
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
For diagonal quadratic evolutions, qubit encodings are asymptotically cheaper than qudit encodings in both Trotter and LCU settings, but small-dimension qudits can win under favorable synthesis or code-switching assumptions.
-
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.
-
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.
-
PyEncode: An Open-Source Library for Structured Quantum State Preparation
PyEncode maps ten exact structured amplitude patterns plus SUM/PARTITION/TENSOR compositions and an MPS loader to verified Qiskit circuits with claimed poly(m) gate counts.
-
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.
- Unbiased Hamiltonian Simulation by Reversing Trotter Error Dynamics