Skip to main content

NOTICE: Due to a lapse in annual appropriations, most of this website is not being updated. Learn more.

Form submissions will still be accepted but will not receive responses at this time. Sections of this site for programs using non-appropriated funds (such as NVLAP) or those that are excepted from the shutdown (such as CHIPS and NVD) will continue to be updated.

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

Published

Author(s)

Isabel M. Beichl, Stephen Bullock, David Song

Abstract

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 .
Citation
Journal of Research (NIST JRES) - Research
Report Number
Research
Volume
112
Issue
6

Keywords

Deutsch's algorithm, quantum computation

Citation

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], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=150002 (Accessed October 13, 2025)

Issues

If you have any questions about this publication or are having problems accessing it, please contact [email protected].

Created October 31, 2007, Updated October 12, 2021
Was this page helpful?