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.
National Institute of Standards and Technology, Gaithersburg, MD 20899.
Isabel
I
Beichl
Institute for Defense Analyses, Center for Computing Sciences, Bowie, MD 20715.
Stephen S
SS
Bullock
Korea Institute for Advanced Study, Seoul 130-722, Korea.
Daegene
D
Song
Deutsch-Jozsa algorithm; Deutsch’s algorithm; concentrated maps; one-to-one mappings; quantum computation; quantum oracle; roots of unity