Preconditioned Quantum Linear System Algorithm
Top Cited Papers
Open Access
- 18 June 2013
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 110 (25), 250504
- https://doi.org/10.1103/physrevlett.110.250504
Abstract
We describe a quantum algorithm that generalizes the quantum linear system algorithm [Harrow et al., Phys. Rev. Lett. 103, 150502 (2009)] to arbitrary problem specifications. We develop a state preparation routine that can initialize generic states, show how simple ancilla measurements can be used to calculate many quantities of interest, and integrate a quantum-compatible preconditioner that greatly expands the number of problems that can achieve exponential speedup over classical linear systems solvers. To demonstrate the algorithm’s applicability, we show how it can be used to compute the electromagnetic scattering cross section of an arbitrary target exponentially faster than the best classical algorithm. DOI: http://dx.doi.org/10.1103/PhysRevLett.110.250504 © 2013 American Physical SocietyKeywords
Other Versions
This publication has 16 references indexed in Scilit:
- Quantum Algorithm for Data FittingPhysical Review Letters, 2012
- Quantum Algorithm for Linear Systems of EquationsPhysical Review Letters, 2009
- Preparation of many-body states for quantum simulationThe Journal of Chemical Physics, 2009
- Efficient Quantum Algorithms for Simulating Sparse HamiltoniansCommunications in Mathematical Physics, 2006
- Efficient state preparation for a register of quantum bitsPhysical Review A, 2006
- Preconditioning Techniques for Large Linear Systems: A SurveyJournal of Computational Physics, 2002
- A Priori Sparsity Patterns for Parallel Sparse Approximate Inverse PreconditionersSIAM Journal on Scientific Computing, 2000
- Parallel Preconditioning with Sparse Approximate InversesSIAM Journal on Scientific Computing, 1997
- On the Conditioning of Finite Element Equations with Highly Refined MeshesSIAM Journal on Numerical Analysis, 1989
- Simulating physics with computersInternational Journal of Theoretical Physics, 1982