Ambainis, Andris
Variable time amplitude amplification and quantum algorithms for linear algebra problems
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.
BibTeX  Entry
@InProceedings{ambainis:LIPIcs:2012:3426,
author = {Andris Ambainis},
title = {{Variable time amplitude amplification and quantum algorithms for linear algebra problems}},
booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
pages = {636647},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897354},
ISSN = {18688969},
year = {2012},
volume = {14},
editor = {Christoph D{\"u}rr and Thomas Wilke},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3426},
URN = {urn:nbn:de:0030drops34261},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2012.636},
annote = {Keywords: quantum computing, quantum algorithms, amplitude amplification, linear equations}
}
2012
Keywords: 

quantum computing, quantum algorithms, amplitude amplification, linear equations 
Seminar: 

29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Related Scholarly Article: 


Issue date: 

2012 
Date of publication: 

2012 