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.

Publication Details
Publication Type
Journal Article
Year of Publication
2015
Volume
44
Number of Pages
1–26
ISSN Number
1868-8969
DOI
10.4230/LIPIcs.TQC.2015.1
URL
http://arxiv.org/abs/1502.02174
Journal
10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)
Contributors
Groups
Date Published
02/2015