Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

A Quantum Algorithm Detecting Concentrated Maps



Isabel M. Beichl, Stephen Bullock, David Song


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 .
Journal of Research (NIST JRES) - Research
Report Number


Deutsch's algorithm, quantum computation


Beichl, I. , Bullock, S. and Song, D. (2007), A Quantum Algorithm Detecting Concentrated Maps, Journal of Research (NIST JRES), National Institute of Standards and Technology, Gaithersburg, MD, [online], (Accessed November 28, 2023)
Created October 31, 2007, Updated October 12, 2021