The beta version of DROPS 2 is now publicly available! Check this page out at DROPS 2 now!


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.TQC.2015.1
URN: urn:nbn:de:0030-drops-55459
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5545/
Go to the corresponding LIPIcs Volume Portal

Kimmel, Shelby ; Lin, Cedric Yen-Yu ; Lin, Han-Hsuan

Oracles with Costs

pdf-format:
1.pdf (0.8 MB)

Abstract

While powerful tools have been developed to analyze quantum query complexity, there are still many natural problems that do not fit neatly into the black box model of oracles. We create a new model that allows multiple oracles with differing costs. This model captures more of the difficulty of certain natural problems. We test this model on a simple problem, Search with Two Oracles, for which we create a quantum algorithm that we prove is asymptotically optimal. We further give some evidence, using a geometric picture of Grover's algorithm, that our algorithm is exactly optimal.

BibTeX - Entry

@InProceedings{kimmel_et_al:LIPIcs:2015:5545,
  author =	{Shelby Kimmel and Cedric Yen-Yu Lin and Han-Hsuan Lin},
  title =	{{Oracles with Costs}},
  booktitle =	{10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)},
  pages =	{1--26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-96-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{44},
  editor =	{Salman Beigi and Robert Koenig},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5545},
  URN =		{urn:nbn:de:0030-drops-55459},
  doi =		{10.4230/LIPIcs.TQC.2015.1},
  annote =	{Keywords: Quantum Algorithms, Query Complexity, Amplitude Amplification}
}

Keywords: Quantum Algorithms, Query Complexity, Amplitude Amplification
Collection: 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)
Issue Date: 2015
Date of publication: 04.11.2015

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