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 language | English |
---|---|
Pages (from-to) | 1822-1826 |
Number of pages | 5 |
Journal | Physical Review A - Atomic, Molecular, and Optical Physics |
Volume | 58 |
Issue number | 3 |
DOIs | |
Publication status | Published - 1998 |
Externally published | Yes |