文章基本信息

标题：Oracles with Costs
本地全文：下载
作者：Shelby Kimmel ; Cedric Yen-Yu Lin ; Han-Hsuan Lin 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：44
页码：1-26
DOI：10.4230/LIPIcs.TQC.2015.1
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Quantum Algorithms; Query Complexity; Amplitude Amplification