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.STACS.2014.482
URN: urn:nbn:de:0030-drops-44813
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4481/
Go to the corresponding LIPIcs Volume Portal

Kothari, Robin

An optimal quantum algorithm for the oracle identification problem

pdf-format:
39.pdf (0.6 MB)

Abstract

In the oracle identification problem, we are given oracle access to an unknown N-bit string x promised to belong to a known set C of size M and our task is to identify x. We present a quantum algorithm for the problem that is optimal in its dependence on N and M. Our algorithm considerably simplifies and improves the previous best algorithm due to Ambainis et al. Our algorithm also has applications in quantum learning theory, where it improves the complexity of exact learning with membership queries, resolving a conjecture of Hunziker et al.

The algorithm is based on ideas from classical learning theory and a new composition theorem for solutions of the filtered gamma_2-norm semidefinite program, which characterizes quantum query complexity. Our composition theorem is quite general and allows us to compose quantum algorithms with input-dependent query complexities without incurring a logarithmic overhead for error reduction. As an application of the composition theorem, we remove all log factors from the best known quantum algorithm for Boolean matrix multiplication.

BibTeX - Entry

@InProceedings{kothari:LIPIcs:2014:4481,
  author =	{Robin Kothari},
  title =	{{An optimal quantum algorithm for the oracle identification problem}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{482--493},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Ernst W. Mayr and Natacha Portier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4481},
  URN =		{urn:nbn:de:0030-drops-44813},
  doi =		{10.4230/LIPIcs.STACS.2014.482},
  annote =	{Keywords: quantum algorithms, quantum query complexity, oracle identification}
}

Keywords: quantum algorithms, quantum query complexity, oracle identification
Collection: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Issue Date: 2014
Date of publication: 05.03.2014

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