Single quantum querying of a database
Abstract
Description
We present a class of fast quantum algorithms, based on Bernstein and Vazirani's parity problem, that retrieve the entire contents of a quantum database $Y$ in a single query. The class includes binary search problems and coin-weighing problems. Our methods far exceed the efficiency of classical algorithms which 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.
Replaced with expanded version, 6 pages revtex, 12 November 1997. Replaced again to fix small typographical errors, submitted to Phys. Rev. A
Replaced with expanded version, 6 pages revtex, 12 November 1997. Replaced again to fix small typographical errors, submitted to Phys. Rev. A