Structured quantum search in NP-complete problems using the cumulative density of states
arXiv:quant-ph/0109087 · doi:10.1103/PhysRevA.83.014302
Abstract
In the multitarget Grover algorithm, we are given an unstructured N-element list of objects S_i containing a T-element subset tau and function f, called an oracle, such that f(S_i)=1 if S_i is in tau, otherwise f(S_i) = 0. By using quantum parallelism, an element of tau can be retrieved in O(sqrt(N/T)) steps, compared to O(N/T) for any classical algorithm. It is shown here that in combinatorial optimization problems with N=4^M, the density of states can be used in conjunction with the multitarget Grover algorithm to construct a sequence of oracles that structure the search so that the optimum state is obtained with certainty in O(log(N)) steps.
arXiv comment5 pages, 2 figures. Revised to include numerical example. Submitted to PRL
References in corpus (11)
- Quantum Mechanics helps in searching for a needle in a haystack
- Elementary gates for quantum computation
- The Security of Practical Quantum Key Distribution
- Quantum Interferometric Optical Lithography: Exploiting Entanglement to Beat The Diffraction Limit
- Quantum computing with trapped ions
- Grover Algorithm with zero theoretical failure rate
- Nonlinear interactions with an ultrahigh flux of broadband entangled photons
- On Arbitrary Phases in Quantum Amplitude Amplification
- Nested quantum search and NP-complete problems
- Lifetime measurements of the 5d states of rubidium
- An Exponentially Fast Quantum Search Algorithm