A Novel Approach to Quantum Heuristics for Structured Database Search
arXiv:quant-ph/0106152
Abstract
An algorithm for structured database searching is presented and used to solve the set partition problem. O(n) oracle calls are required in order to obtain a solution, but the probability that this solution is optimal decreases exponentially with problem size. Each oracle call is followed by a measurement, implying that it is necessary to maintain quantum coherence for only one oracle call at a time.
17 pages, 4 figures