Single quantum querying of a database

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. © 1998 The American Physical Society.