Variable time amplitude amplification and quantum algorithms for linear algebra problems. (English) Zbl 1245.68084
Dürr, Christoph (ed.) et al., STACS 2012. 29th international symposium on theoretical aspects of computer science, Paris, France, February 29th – March 3rd, 2012. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-35-4). LIPIcs – Leibniz International Proceedings in Informatics 14, 636-647, electronic only (2012).
Summary: Quantum amplitude amplification is a method of increasing a success probability of an algorithm from a small \(\varepsilon>0\) to \(\varTheta(1)\) with less repetitions than classically. In this paper, we generalize quantum amplitude amplification to the case when parts of the algorithm that is being amplified stop at different times.
We then apply the new variable time amplitude amplification to give two new quantum algorithms for linear algebra problems. Our first algorithm is an improvement of Harrow et al. algorithm for solving systems of linear equations. We improve the running time of the algorithm from \(O(\varkappa^2 \log N)\) to \(O(\varkappa \log^3 \varkappa \log N)\) where \(\varkappa\) is the condition number of the system of equations. Our second algorithm tests whether a matrix \(A\) is singular or far from singular, faster then the previously known algorithms.
For the entire collection see [Zbl 1237.68016].
We then apply the new variable time amplitude amplification to give two new quantum algorithms for linear algebra problems. Our first algorithm is an improvement of Harrow et al. algorithm for solving systems of linear equations. We improve the running time of the algorithm from \(O(\varkappa^2 \log N)\) to \(O(\varkappa \log^3 \varkappa \log N)\) where \(\varkappa\) is the condition number of the system of equations. Our second algorithm tests whether a matrix \(A\) is singular or far from singular, faster then the previously known algorithms.
For the entire collection see [Zbl 1237.68016].
MSC:
| 68Q12 | Quantum algorithms and complexity in the theory of computing |
