Comparison of quantum oracles
Elham Kashefi, Adrian Kent, Vlatko Vedral, Konrad Banaszek · Physical Review A · 2002
A standard quantum oracle ${S}_{f}$ for a general function $f: {Z}_{N}\ensuremath{\rightarrow}{Z}_{N}$ is defined to act on two input states and return two outputs, with inputs $|i〉$ and $|j〉 (i,j\ensuremath{\in}{Z}_{N})$ returning outputs $|i〉$ and $|j\ensuremath{\bigoplus}f(i)〉.$ However, if f is known to be a one-to-one function, a simpler oracle, ${M}_{f},$ which returns $|f(i)〉$ given $|i〉,$ can also be defined. We consider the relative strengths of these oracles. We define a simple promise problem that minimal quantum oracles can solve exponentially faster than classical oracles, via an algorithm that cannot be naively adapted to standard quantum oracles. We show that ${S}_{f}$ can be constructed by invoking ${M}_{f}$ and ${(M}_{f}{)}^{\ensuremath{-}1}$ once each, while $\ensuremath{\Theta}(\sqrt{N})$ invocations of ${S}_{f}$ and/or ${(S}_{f}{)}^{\ensuremath{-}1}$ are required to construct ${M}_{f}.$