Single quantum querying of a database

Barbara M. Terhal*, John A. Smolin

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

42 Citations (Scopus)


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
Issue number3
Publication statusPublished - 1998
Externally publishedYes


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

Cite this