Superfast quantum algorithms for coin weighing and binary search problems

Authors:
  • BTBarbara M. Terhal
    Barbara M. Terhal
  • JSJohn A. Smolin
    John A. Smolin

Abstract
We present a class of superfast quantum algorithms 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 linear hashing codes and our quantum-mechanical method.