  
|
     
|
Applicable Algebra in Engineering, Communication and Computing
ISSN: 0938-1279 (printed version)
ISSN: 1432-0622 (electronic version)
Abstract Volume 10 Issue 4/5 (2000) pp 311-338
Nested Quantum Search and NP-Hard Problems
Nicolas J. Cerf (1)(2), Lov K. Grover (3), Colin P. Williams (2)
(1) Ecole Polytechnique, CP 165, Université Libre de Bruxelles, 1050 Bruxelles, Belgium
(2) Quantum Computing Technologies Group, Section 367, Jet Propulsion Laboratory, California Institute of Technology, Pasadena, CA 91109, USA
(3) 3C-404A Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ 07974, USA (e-mail: ncerf@ulb.ac.be, Colin.P.Williams@jpl.nasa.gov)
Received: August 17, 1998; revised version: December 1, 1999
Abstract. 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.
Key words: Quantum computation, Quantum algorithms, Combinatorial search problems, NP-hard problems.
Article in PDF format (194 KB)
Online publication: May 12, 2000
LINK Helpdesk
© Springer-Verlag Berlin Heidelberg 2000