Nested Quantum Search and NP-Complete Problem
A quantum algorithm is known that solves an unstructured search problem in a number of iterations of order square-root of d, where d is the dimension of the search space, whereas any classical algorithm scales as O(d).
NP-complete problems quantum search algorithm tree↗