arXiv preprint ·
An Optimal Quantum Linear Systems Algorithm
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
In the quantum linear systems problem (QLSP), we are given query access to a $d$-sparse $N\times N$ matrix $A$ with condition number $κ$, and the ability to prepare a quantum state proportional to a vector $\vec b$. The goal is to output an $ε$-approximation to the quantum state proportional to the solution $\vec x$ of $A\vec{x}=\vec{b}$. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities $O(κd\log(1/ε))$ and $κ\sqrt d(κd/ε)^{o(1)}$, while the best known lower bounds were $Ω(κ\log(1/ε))$ and $Ω(κ\sqrt d)$. We improve these bounds and show that the complexity of the QLSP is $Θ(κ\sqrt d\log(1/ε))$. We also resolve an open problem of Berry and Childs by showing that any $N\times N$ unitary can be implemented with bounded error using $O(\sqrt N)$ queries to its matrix entries.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Native implementation of the machine-learned Skala exchange-correlation functional in CP2K: Unified one-centre reconstruction for molecular and condensed-phase calculations
Dynamical resource theory of time-reversal symmetry breaking
Tensor-Engineered Van der Waals NbOCl2 Resonant Metasurface for Polarization-entangled Bell State Generation
Transverse momentum as the counter-diabatic generator in bent waveguide couplers
The equivalence of topological indices for $\mathrm{U}(1)\rtimes\mathbb{Z}_2$-symmetric quantum spin chains
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.