Nested quantum search and NP-hard problems

DOI10.1007/S002000050134MaRDI QIDQ1567563zbMATH OpenOpenAlexFDO

Authors N. J. Cerf, Lov K. Grover, Colin P. Williams

Publication date 21 June 2000

Published in Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/9806078

zbMATH Keywords

quantum algorithm

Mathematics Subject Classification ID

Quantum computation (81P68)

Abstract: A quantum algorithm is known that solves an unstructured search problem in a number of iterations of order $sqrtd$, 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}^{a}lpha$, 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.

Recommendations

• Solving NP-Complete Problems with Quantum Search
• scientific article; zbMATH DE number 1285153
• scientific article; zbMATH DE number 1149422
• A panoply of quantum algorithms
• Quantum-walk speedup of backtracking algorithms

Cited in

(14)

• Quantum partial search for uneven distribution of multiple target items
• Quantum algorithm for lexicographically minimal string rotation
• scientific article; zbMATH DE number 1929929 (Why is no real title available?)
• HIERARCHICAL QUANTUM SEARCH
• scientific article; zbMATH DE number 1530002 (Why is no real title available?)
• Using an \(A^\ast\)-based framework for decomposing combinatorial optimization problems to employ NISQ computers
• Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games
• Exponential-time quantum algorithms for graph coloring problems
• Universality, invariance, and the foundations of computational complexity in the light of the quantum computer
• Solving NP-Complete Problems with Quantum Search
• Mind the gap: achieving a super-Grover quantum speedup by jumping to the end
• Quantum optimization
• Quantum-walk speedup of backtracking algorithms
• The variational quantum eigensolver: a review of methods and best practices

This page was built for publication: Nested quantum search and NP-hard problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1567563)