Develops a quantum algorithm for linear matrix differential equations with query complexity O~(ν L t / ε) that is nearly optimal and yields polynomial to exponential speedups for open quantum system simulation.
hub Canonical reference
Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
Canonical reference. 89% of citing Pith papers cite this work as background.
23
Pith papers citing it
505
external citations · Crossref
Background
89% of classified citations
abstract
Harrow, Hassidim, and Lloyd showed that for a suitably specified $N \times N$ matrix $A$ and $N$-dimensional vector $\vec{b}$, there is a quantum algorithm that outputs a quantum state proportional to the solution of the linear system of equations $A\vec{x}=\vec{b}$. If $A$ is sparse and well-conditioned, their algorithm runs in time $\mathrm{poly}(\log N, 1/\epsilon)$, where $\epsilon$ is the desired precision in the output state. We improve this to an algorithm whose running time is polynomial in $\log(1/\epsilon)$, exponentially improving the dependence on precision while keeping essentially the same dependence on other parameters. Our algorithm is based on a general technique for implementing any operator with a suitable Fourier or Chebyshev series representation. This allows us to bypass the quantum phase estimation algorithm, whose dependence on $\epsilon$ is prohibitive.
hub tools
citation-role summary
background 8
method 1
citation-polarity summary
representative citing papers
Quantum signal processing angles admit closed-form expressions via orthogonal polynomial theory, allowing O(log(1/ε)) gate block-encodings of smooth functions through Hermite expansions and full characterization of SU(1,1)-QSP polynomials by roots.
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.
New scalable QRAM simulator reveals post-selection constraints on error filtration and produces refined near-deterministic performance criteria.
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 classical polynomial-time algorithm for optimized sampling of lottery tickets in neural networks removes the exponential dependence on data dimension from prior classical approaches.
A quantum multi-level framework achieves near-optimal query complexity for q-Tsallis entropy estimation for q>1 and a speedup for q<1 over classical methods.
Quantum algorithms achieve polylog(N) complexity for high-dimensional linear SDEs by amplitude-encoding the solution and noise via Dyson series or Euler-Maruyama approximations plus quantum linear systems 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.
A dual Fourier-PSF and contour-PSF framework resolves the smoothness-sparsity trade-off for efficient quantum simulation of singular and holomorphic matrix functions.
Cobble is a domain-specific language for quantum block encodings that compiles high-level matrix expressions to optimized circuits using analyses and quantum singular value transformation, achieving 2.6x-25.4x speedups over unoptimized baselines on benchmarks.
Analytical Pauli-string coefficients plus multistage state refinement let tensor networks find low eigenstates of million-dimensional Laplacians with high fidelity on 20 qubits.
The paper proposes an eigenstate filtering (EF) variant of quantum inverse power iteration (QIPI) that uses symmetric QSVT polynomials to robustly target excited states, showing better convergence than Chebyshev or Fourier approaches on H2, LiH, and BeH2.
Develops a threshold-regularized Moore-Penrose pseudoinverse formulation of PGM with hybrid classical-quantum circuit implementation using block-encoding for stable discrimination in ill-conditioned and rank-deficient ensembles.
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.
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 LCNU-plus-embedding data loading for any polynomial Carleman-linearized autonomous system and applies it to the 3D LBE, yielding Ns ~ O(α²Q²) terms and explicit T-gate resource estimates for two solvers.
The Eclipse Qrisp BlockEncoding interface provides high-level programming abstractions for block-encodings, enabling easier implementation of quantum algorithms such as QSVT, matrix inversion, and Hamiltonian simulation.
CBMD decomposes non-Hermitian evolution operators into Hermitian LCU terms via a matrix residue theorem, matching known optimal query bounds and offering a route to polynomial matrix functions.
Human-AI collaboration expanded a meta-idea on rational approximation into sign-embedding quantum algorithms for matrix problems, with humans retaining final judgment on routes and refinements.
Quantum algorithms for element-wise polynomial matrix transforms achieve exponential space reduction in polynomial degree with corrections to prior constructions.
A hybrid quantization scheme enables efficient switching between first- and second-quantization in quantum circuits for molecular systems, claiming up to three orders of magnitude fewer ground-state preparations for 2-RDM measurements.
Hybrid quantum interior point methods for linear programming have no practical runtime advantage over classical solvers like HiGHS on realistic instances because their quantum lower bounds already exceed classical performance under optimistic assumptions.
citing papers explorer
-
Efficient quantum algorithm for linear matrix differential equations and applications to open quantum systems
Develops a quantum algorithm for linear matrix differential equations with query complexity O~(ν L t / ε) that is nearly optimal and yields polynomial to exponential speedups for open quantum system simulation.
-
Analytical Angle-Finding and Series Expansions for Quantum Signal Processing via Orthogonal Polynomial Theory
Quantum signal processing angles admit closed-form expressions via orthogonal polynomial theory, allowing O(log(1/ε)) gate block-encodings of smooth functions through Hermite expansions and full characterization of SU(1,1)-QSP polynomials by roots.
-
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.
-
Refined Criteria for QRAM Error Suppression via Efficient Large-Scale QRAM Simulator
New scalable QRAM simulator reveals post-selection constraints on error filtration and produces refined near-deterministic performance criteria.
-
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/ε).
-
Winning Lottery Tickets in Neural Networks via a Quantum-Inspired Classical Algorithm
A classical polynomial-time algorithm for optimized sampling of lottery tickets in neural networks removes the exponential dependence on data dimension from prior classical approaches.
-
Quantum Multi-Level Estimation of Functionals of Discrete Distributions
A quantum multi-level framework achieves near-optimal query complexity for q-Tsallis entropy estimation for q>1 and a speedup for q<1 over classical methods.
-
Quantum algorithm for solving high-dimensional linear stochastic differential equations via amplitude encoding of the noise term
Quantum algorithms achieve polylog(N) complexity for high-dimensional linear SDEs by amplitude-encoding the solution and noise via Dyson series or Euler-Maruyama approximations plus quantum linear systems solvers.
-
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.
-
A Unified Poisson Summation Framework for Generalized Quantum Matrix Transformations
A dual Fourier-PSF and contour-PSF framework resolves the smoothness-sparsity trade-off for efficient quantum simulation of singular and holomorphic matrix functions.
-
Cobble: Compiling Block Encodings for Quantum Computational Linear Algebra
Cobble is a domain-specific language for quantum block encodings that compiles high-level matrix expressions to optimized circuits using analyses and quantum singular value transformation, achieving 2.6x-25.4x speedups over unoptimized baselines on benchmarks.
-
Efficient Pauli-decomposition and multistage state-refinement for tensor network based differential equation solver
Analytical Pauli-string coefficients plus multistage state refinement let tensor networks find low eigenstates of million-dimensional Laplacians with high fidelity on 20 qubits.
-
Efficient targeting of arbitrary excited states with quantum inverse power iteration through filtering polynomials
The paper proposes an eigenstate filtering (EF) variant of quantum inverse power iteration (QIPI) that uses symmetric QSVT polynomials to robustly target excited states, showing better convergence than Chebyshev or Fourier approaches on H2, LiH, and BeH2.
-
Robust Pretty Good Measurement via Hybrid Classical-Quantum Pseudoinverse Approximation and Circuit-Level Realization
Develops a threshold-regularized Moore-Penrose pseudoinverse formulation of PGM with hybrid classical-quantum circuit implementation using block-encoding for stable discrimination in ill-conditioned and rank-deficient ensembles.
-
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.
-
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 Data Loading for Carleman Linearized Systems: Application to the Lattice-Boltzmann Equation
Presents LCNU-plus-embedding data loading for any polynomial Carleman-linearized autonomous system and applies it to the 3D LBE, yielding Ns ~ O(α²Q²) terms and explicit T-gate resource estimates for two solvers.
-
Block-encodings as programming abstractions: The Eclipse Qrisp BlockEncoding Interface
The Eclipse Qrisp BlockEncoding interface provides high-level programming abstractions for block-encodings, enabling easier implementation of quantum algorithms such as QSVT, matrix inversion, and Hamiltonian simulation.
-
Quantum Simulation of Non-Hermitian Special Functions and Dynamics via Contour-based Matrix Decomposition
CBMD decomposes non-Hermitian evolution operators into Hermitian LCU terms via a matrix residue theorem, matching known optimal query bounds and offering a route to polynomial matrix functions.
-
From Meta Idea to Advanced Mathematical Discovery -- Human-AI Co-Discovery of Sign-Embedding Quantum Algorithms
Human-AI collaboration expanded a meta-idea on rational approximation into sign-embedding quantum algorithms for matrix problems, with humans retaining final judgment on routes and refinements.
-
Quantum element-wise transforms
Quantum algorithms for element-wise polynomial matrix transforms achieve exponential space reduction in polynomial degree with corrections to prior constructions.
-
Optimizing Quantum Chemistry Simulations with a Hybrid Quantization Scheme
A hybrid quantization scheme enables efficient switching between first- and second-quantization in quantum circuits for molecular systems, claiming up to three orders of magnitude fewer ground-state preparations for 2-RDM measurements.
-
Practical lower bounds for hybrid quantum interior point methods in linear programming
Hybrid quantum interior point methods for linear programming have no practical runtime advantage over classical solvers like HiGHS on realistic instances because their quantum lower bounds already exceed classical performance under optimistic assumptions.