01035nas a2200181 4500008004100000020002200041022001400063245002300077210002300100260001500123300000900138490000700147520060100154100001900755700002400774700001900798856003600817 2015 eng d a978-3-939897-96-5 a1868-896900aOracles with Costs0 aOracles with Costs c2015/02/07 a1-260 v443 a 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.
1 aKimmel, Shelby1 aLin, Cedric, Yen-Yu1 aLin, Han-Hsuan uhttp://arxiv.org/abs/1502.02174