Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision
Why is this work in the frame?
A frame that forgets how it found something cannot be audited. These are the routes that admitted this work.
No Canadian affiliation. An affiliation-only frame — the usual design — would never have seen this work. It is one of the works that make the case for inverting the frame.
Machine scores (provisional)
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
- Teacher spread
- 0.261 · how far apart the two teachers sit on this one work
- Validation status
score_only:v0-immature-baseline· verbatim from the scoring run: score_only means the number may rank works, and no category label ships from it
Abstract
Harrow, Hassidim, and Lloyd [Phys. Rev. Lett., 103 (2009), 150502] showed that for a suitably specified $N \times N$ matrix $A$ and an $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 ${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.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
The record
- Venue
- SIAM Journal on Computing
- Topic
- Quantum Computing Algorithms and Architecture
- Field
- Computer Science
- Canadian institutions
- —
- Funders
- Army Research OfficeAir Force Office of Scientific ResearchCanadian Institute for Advanced ResearchIntelligence Advanced Research Projects ActivityNational Science Foundation
- Keywords
- Quantum algorithmQuantum phase estimation algorithmMathematicsQuantum algorithm for linear systems of equationsAlgorithmState (computer science)Operator (biology)QuantumSeries (stratigraphy)PolynomialMatrix (chemical analysis)Chebyshev filterState vectorQuantum Fourier transformMathematical analysisQuantum mechanicsQuantum error correctionPhysicsQuantum processQuantum dynamics
- Has abstract in OpenAlex
- yes