LIPIcs.STACS.2012.636.pdf
- Filesize: 496 kB
- 12 pages
Document
Variable time amplitude amplification and quantum algorithms for linear algebra problems
Author
-
Part of:
Volume:
29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2012-02-24
Cite As Get BibTex
Andris Ambainis. Variable time amplitude amplification and quantum algorithms for linear algebra problems. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 636-647, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
https://doi.org/10.4230/LIPIcs.STACS.2012.636
Abstract
Quantum amplitude amplification is a method of increasing a success probability of an algorithm from a small epsilon>0 to Theta(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(k^2 log N) to O(k log^3 k log N) where k 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.
Subject Classification
Keywords
- quantum computing
- quantum algorithms
- amplitude amplification
- linear equations
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads