Simultaneously Query-Optimal Quantum Linear-System Algorithm

arXiv:2609.33686 · quant-ph · Submitted 2026-09-27 · Read on arXiv

quant-ph

Submitted: 2026-09-27

Updated: 2026-09-27

Terminology

• Query Complexity — 8× in this paper · explained in 2 episodes
• Accuracy — 5× in this paper · explained in 1 episode
• Adiabatic Evolution — 5× in this paper · explained in 2 episodes
• Ancilla Qubits — 4× in this paper · explained in 1 episode
• Trace — 4× in this paper · explained in 2 episodes
• Block Encoding — 2× in this paper · explained in 4 episodes
• Verification — 2× in this paper · explained in 2 episodes
• Alignment — 1× in this paper · explained in 1 episode
• Hilbert Space — 1× in this paper · explained in 2 episodes
• Sparsity — 1× in this paper · explained in 4 episodes
• Spectral Gap — 1× in this paper · explained in 5 episodes
• Trace Distance — 1× in this paper · explained in 3 episodes

Sources

• Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm
• Elfs, transducers and quantum walks
• Quantum Lower Bounds by Polynomials
• Quantum algorithm for time-dependent differential equations using Dyson series
• Quantum algorithm for linear differential equations with exponentially improved dependence on precision
• Space-Efficient Quantum Error Reduction without log Factors
• Taming Quantum Time Complexity
• The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver
• Optimal scaling quantum linear systems solver via discrete adiabatic theorem
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• Query-Optimal and Gate-Efficient Lindbladian Simulation
• Time-Dependent Hamiltonian Simulation with Optimal Query Complexity
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• High-precision quantum algorithms for partial differential equations
• Quantum Regularized Least Squares
• A shortcut to an optimal quantum linear system solver
• Faster quantum linear system solver beyond the condition number
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Quantum algorithm for solving linear systems of equations

Related papers

• Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
• Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
• Polynomial-time classical and quantum simulation of quantum impurity models
• Theory of quantum-enhanced interferometry with general Markovian light sources
• A convergent hierarchy of spectral gap certificates for qubit Hamiltonians
• Universal Bound and Phase Transition in Many-Body Fermionic Non-Gaussianity