Single quantum querying of a database

Barbara M. Terhal, John A. Smolin

Research output: Contribution to journalArticleScientificpeer-review

45 Citations (Scopus)

Abstract

We present a class of fast quantum algorithms, based on Bernstein and Vazirani’s parity problem, that retrieves the entire contents of a quantum database [Formula Presented] in a single query. The class includes binary search problems and coin-weighing problems. We compare the efficiency of these quantum algorithms with the classical algorithms that are bounded by the classical information-theoretic bound. We show the connection between classical algorithms based on several compression codes and our quantum-mechanical method.

Original languageEnglish
Pages (from-to)1822-1826
Number of pages5
JournalPhysical Review A - Atomic, Molecular, and Optical Physics
Volume58
Issue number3
DOIs
Publication statusPublished - 1998
Externally publishedYes

Fingerprint

Dive into the research topics of 'Single quantum querying of a database'. Together they form a unique fingerprint.

Cite this