License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.18
URN: urn:nbn:de:0030-drops-74893
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7489/
Go to the corresponding LIPIcs Volume Portal

Dohotaru, Catalin ; Høyer, Peter

Controlled Quantum Amplification

pdf-format:
LIPIcs-ICALP-2017-18.pdf (0.5 MB)

Abstract

We propose a new framework for turning quantum search algorithms that decide into quantum algorithms for finding a solution. Consider we are given an abstract quantum search algorithm A that can determine whether a target g exists or not. We give a general construction of another operator U that both determines and finds the target, whenever one exists. Our amplification method at most doubles the cost over using A, has little overhead, and works by controlling the evolution of A. This is the first known general framework to the open question of turning abstract quantum search algorithms into quantum algorithms for finding a solution.

We next apply the framework to random walks. We develop a new classical algorithm and a new quantum algorithm for finding a unique marked element. Our new random walk finds a unique marked element using H update operations and 1/eps checking operations. Here H is the hitting time, and eps is the probability that the stationary distribution of the walk is in the marked state. Our classical walk is derived via quantum arguments. Our new quantum algorithm finds a unique marked element using H^(1/2) update operations and 1/eps^(1/2) checking operations, up to logarithmic factors. This is the first known quantum algorithm being simultaneously quadratically faster in both parameters. We also show that the framework can simulate Grover's quantum search algorithm, amplitude amplification, Szegedy's quantum walks, and quantum interpolated walks.

BibTeX - Entry

@InProceedings{dohotaru_et_al:LIPIcs:2017:7489,
  author =	{Catalin Dohotaru and Peter H\oyer},
  title =	{{Controlled Quantum Amplification}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{18:1--18:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7489},
  URN =		{urn:nbn:de:0030-drops-74893},
  doi =		{10.4230/LIPIcs.ICALP.2017.18},
  annote =	{Keywords: Quantum algorithms, quantum walks, random walks, quantum search}
}

Keywords: Quantum algorithms, quantum walks, random walks, quantum search
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

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