License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2012.636
URN: urn:nbn:de:0030-drops-34261
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3426/
Go to the corresponding LIPIcs Volume Portal

Ambainis, Andris

Variable time amplitude amplification and quantum algorithms for linear algebra problems

pdf-format:
42.pdf (0.5 MB)

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 =	{636--647},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{Christoph D{\"u}rr and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3426},
  URN =		{urn:nbn:de:0030-drops-34261},
  doi =		{10.4230/LIPIcs.STACS.2012.636},
  annote =	{Keywords: quantum computing, quantum algorithms, amplitude amplification, linear equations}
}

Keywords: quantum computing, quantum algorithms, amplitude amplification, linear equations
Collection: 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Issue Date: 2012
Date of publication: 24.02.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI