1 Search Results for "Dohotaru, Catalin"

Document
DOI: 10.4230/LIPIcs.ICALP.2017.18
Controlled Quantum Amplification

Authors: Catalin Dohotaru and Peter Høyer

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

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.
Cite as

Catalin Dohotaru and Peter Høyer. Controlled Quantum Amplification. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 18:1-18:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dohotaru_et_al:LIPIcs.ICALP.2017.18,
  author =	{Dohotaru, Catalin and H{\o}yer, Peter},
  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 =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.18},
  URN =		{urn:nbn:de:0030-drops-74893},
  doi =		{10.4230/LIPIcs.ICALP.2017.18},
  annote =	{Keywords: Quantum algorithms, quantum walks, random walks, quantum search}
}
  • Refine by Author
  • 1 Dohotaru, Catalin
  • 1 Høyer, Peter

  • Refine by Classification

  • Refine by Keyword
  • 1 Quantum algorithms
  • 1 quantum search
  • 1 quantum walks
  • 1 random walks

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact