Superfast quantum algorithms for coin weighing and binary search problems
Authors:
- Barbara M. TerhalBTBarbara M. Terhal
- John A. SmolinJSJohn A. Smolin
Preprint
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.