Structured quantum search in NP-complete problems using the cumulative density of states

Details Structured quantum search in NP-complete problems using the cumulative density of states Structured quantum search in NP-complete problems using the cumulative density of states

2001-09-18

arxiv.org/abs/quant-ph/0109087v2

Physics

Quantum Physics

5 pages, 2 figures. Revised to include numerical example. Submitted to PRL

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Structured quantum search in NP-complete problems using the cumulative density of states does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Structured quantum search in NP-complete problems using the cumulative density of states, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Structured quantum search in NP-complete problems using the cumulative density of states will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-622251