A Quantum Algorithm Detecting Concentrated Maps

We consider an arbitrary mapping f: {0, …, N - 1} → {0, …, N - 1} for N = 2 (n) , n some number of quantum bits. Using N calls to a classical oracle evaluating f(x) and an N-bit memory, it is possible to determine whether f(x) is one-to-one. For some radian angle 0 ≤ θ ≤ π/2, we say f(x) is θ - concentrated if and only if [Formula: see text] for some given ψ 0 and any 0 ≤ x ≤ N - 1. We present a quantum algorithm that distinguishes a θ-concentrated f(x) from a one-to-one f(x) in O(1) calls to a quantum oracle function Uf with high probability. For 0 < θ < 0.3301 rad, the quantum algorithm outperforms random (classical) evaluation of the function testing for dispersed values (on average). Maximal outperformance occurs at [Formula: see text] rad.