Oracles with Costs
Oracles with Costs
复制标题
有成本的预言机
DOI：
10.4230/lipics.tqc.2015.1
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Han
中科院分区：
文献类型：
--
作者：
S. Kimmel;Cedric Yen;Han
虽然已经开发出强大的工具来分析量子查询的复杂性，但仍然有许多自然问题不能完全适合oracle的黑盒模型。我们创建了一个新的模型，允许不同成本的多个oracle。这个模型更多地抓住了某些自然问题的难度。我们在一个简单的问题上测试了这个模型，用两个oracle搜索，为此我们创建了一个量子算法，我们证明了它是渐近最优的。我们进一步用格罗弗算法的几何图给出了一些证据，证明我们的算法是完全最优的。
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.