Where is "quantum search" in the complexity hierarchy?

Question

Grover's algorithm is one of the most popular quantum algorithms that solves the problem of "quantum search." But what is this problem, and what are its characteristics.

When considering other famous problems, like integer factorization, they are organized into complexity classes. Integer factorization, for example, is believed to be in the NP-intermediate class (the class of problems in NP that are not in P or NP-complete). Of course, it isn't a decision problem, so it should actually be in TFNP.

But where in the complexity hierarchy does "quantum search" lie?

Answer 1

Grover's algorithm is best thought of as solving an oracle problem, using the square-root of the number of oracle calls that a classical computer would use.

Grover originally framed the problem as solving an NP problem in the square-root of the time of a classical machine. For example the oracle could be a particular instance of 3-SAT. If we believe in pretty standard computational complexity conjectures, it's unlikely that there's an algorithm that solves a 3-SAT problem on $n$ bits with less than $2^{n/{(1+\epsilon})}$ queries classically, but Grover's algorithm gives a quantum solution with only $2^{n/2}$ queries.

The question also refers to a "complexity hierarchy". Perhaps you meant the polynomial hierarchy? I haven't thought about it too much but I guess you could also change the oracle in Grover's algorithm to be somewhere in the polynomial hierarchy - for example, you could ask for a mate-in-$n$ moves in a sufficiently generalized version of Chess - I'm not sure whether or how Grover's speedup would apply to such a problem, though.