ISSN:
1432-0622
Keywords:
Key words: Quantum computation, Quantum algorithms, Combinatorial search problems, NP-hard problems.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
,
Technology
Notes:
Abstract. A quantum algorithm is known that solves an unstructured search problem in a number of iterations of order , 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 , with a constant α 〈 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 α 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s002000050134
Permalink