Superfast quantum algorithms for coin weighing and binary search problems
Barbara M. Terhal, John A. Smolin · arXiv (Cornell University) · 1997
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.