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

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 June 2, 2023)
Created October 31, 2007, Updated October 12, 2021