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 <= theta <= pi 2, we say f(x) is. - concentrated if and only if e(2 pi if(x)/N) subset of e(i[psi 0-theta,psi 0+theta]) for some given psi(0) and any 0 <= x <= N - 1. We present a quantum algorithm that distinguishes theta-concentrated f(x) from a one-to-one f( x) in O(1) calls to a quantum oracle function U-f with high probability. For 0 < theta < 0.3301 rad, the quantum algorithm outperforms random (classical) evaluation of the function testing for dispersed values (on average). Maximal outperformance occurs theta = 1/2sin(-1) 1/pi approximate to 0.1620 rad.
Publisher
National Institute of Standards and Technology
ISSN
1044-677X
Volume
112
Issue
6
Page
307
Cite
J. Res. Natl. Inst. Stand. Technol. Vol. 112, No. 6, p. 307
Rights
The Journal of Research of the National Institute of Standards and Technology is a publication of the U.S. Government. The papers are in the public domain and are not subject to copyright in the United States. However, please pay special attention to the individual works to make sure there are no copyright restrictions indicated. Individual works may require securing other permissions from the original copyright holder.