Oracles with Costs

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 certa...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2015-11
Main Authors: Kimmel, Shelby, Cedric Yen-Yu Lin, Han-Hsuan, Lin
Format: Article
Language:English
Subjects:
Algorithms
Black boxes
Cost analysis
Model testing
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422
DOI:10.48550/arxiv.1502.02174