Comparison of quantum oracles

A standard quantum oracle $S_f$ for a general function $f:\hspace{0.5em}{Z}_N\to Z_N$ is defined to act on two input states and return two outputs, with inputs $|i〉$ and $|j〉\hspace{0.5em}(i,j\in Z_N)$ returning outputs $|i〉$ and $|j\oplus f\left(i\right)\mathrm{}〉.$ However, if f is known to be a one-to-one function, a simpler oracle, $M_f,$ which returns $|f\left(i\right)\mathrm{}〉$ 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{)}^{-1}$ once each, while $\Theta \left(\sqrt{N}\right)$ invocations of $S_f$ and/or ${(S}_f{)}^{-1}$ are required to construct $M_f.$