Physics – Quantum Physics
Scientific paper
1998-06-23
Phys.Rev. A61 (2000) 032303
Physics
Quantum Physics
18 pages RevTeX, 3 Postscript figures
Scientific paper
10.1103/PhysRevA.61.032303
A quantum algorithm is known that solves an unstructured search problem in a number of iterations of order $\sqrt{d}$, where $d$ is the dimension of the search space, whereas any classical algorithm necessarily scales as $O(d)$. It is shown here that an improved quantum search algorithm can be devised that exploits the structure of a tree search problem by nesting this standard search algorithm. The number of iterations required to find the solution of an average instance of a constraint satisfaction problem scales as $\sqrt{d^\alpha}$, with a constant $\alpha<1$ depending on the nesting depth and the problem considered. When applying a single nesting level to a problem with constraints of size 2 such as the graph coloring problem, this constant $\alpha$ is estimated to be around 0.62 for average instances of maximum difficulty. This corresponds to a square-root speedup over a classical nested search algorithm, of which our presented algorithm is the quantum counterpart.
Cerf Nicolas J.
Grover Lov K.
Williams Colin P.
No associations
LandOfFree
Nested quantum search and NP-complete problems 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 Nested quantum search and NP-complete problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nested quantum search and NP-complete problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-656232