We consider an arbitrary mapping for , some number of quantum bits. Using calls to a classical oracle evaluating and an classical bit data store, it is possible to determine whether is one-to-one. For some radian angle , we say is -concentrated iff for some fixed and any . This manuscript presents a quantum algorithm that distinguishes a -concentrated from a one-to-one in calls to a quantum oracle function with high probability. For rad., the quantum algorithm outperforms a classical analog on average, with maximal outperformance at rad. Thus, the constructions generalize Deutsch¿s algorithm, in that quantum outperformance is robust for (slightly) nonconstant .
, Bullock, S.
and Song, D.
A Quantum Algorithm Detecting Concentrated Maps, Journal of Research (NIST JRES), National Institute of Standards and Technology, Gaithersburg, MD, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=150002
(Accessed November 28, 2023)