Grover's Algorithm and its relation to complexity classes?

Question

I am getting confused about Grover's algorithm and it's connection to complexity classes.

The Grover's algorithm finds and element $k$ in a database of $N=2^n$ (such that $f(k)=1$) of elements with $$\sim \sqrt{N}=2^{n/2}$$ calls to the oracle.

So we have the following problem:

Problem: Find a $k$ in the database such that $f(k)=1$

Now I am aware that this is not a desision problem and thus our normal definitions of complexity class $\text{P}$, $\text{NP}$ etc don't really apply. But I am curious to know how we would define the complexity class in such a case - and weather it is done with respect to $N$ or $n$?

Furthermore the Grover's algorithm can be used as a subroutine. I have read in several places that the Grover's algorithm does not change the complexity class a problem - is there a heuristic way to see this.

Answer 1

Summary

• There is a theory of complexity of search problems (also known as relation problems). This theory includes classes called FP, FNP, and FBQP which are effectively about solving search problems with different sorts of resources.
• From search problems, you can also define decision problems, which allows you to relate search problems to the usual classes P, NP, and BQP.
• Whether you consider the search version of the decision version of the problem, the way that you consider the input to the Unstructured Search problem will determine what upper bounds you can put on its complexity.

The complexity of relation problems

As you note, Grover's problem solves a search problem, which in the complexity literature is sometimes also known as a relation problem. That is, it is a problem of the following sort:

The structure of a general search problem.
Given an input $x$ and a binary relation $R$, find a $y$ such that $R(x,y)$ holds.

The complexity classes FP and FNP are defined in terms of such problems, where in particular one is interested in the case where $y$ has length at most a polynomial function of the length of $x$, and where the relation $R(x,y)$ can itself be computed in an amount of time bounded by some polynomial in the length of $(x,y)$.

In particular: the example of the 'database search' problem for which Grover's Search is usually applied can be described as follows.

Unstructured Search.
Given an input oracle $\mathcal O: \mathcal H_2^{\otimes m+1} \!\to \mathcal H_2^{\otimes m+1}$ such that $\mathcal O \lvert a \rangle \lvert b \rangle = \lvert a \rangle \lvert b \oplus f(a) \rangle$ for some function $f: \{0,1\}^m \to \{0,1\}$, find a $y$ such that $\mathcal O \lvert y \rangle \lvert 0 \rangle = \lvert y \rangle \lvert 1 \rangle$.

Here, the oracle itself is the input to the problem: it plays the role of $x$, and the relation which we are computing is $$ R(\mathcal O,y) \;\;\equiv\;\; \Bigl[\mathcal O \lvert y \rangle \lvert 0 \rangle = \lvert y \rangle \lvert 1 \rangle\Bigr] \;\;\equiv\;\; \Bigl[ f(y) = 1 \Bigr].$$

Suppose that, instead of an oracle, we are provided with a specific input $x$ which describes how the function $f$ is to be computed, we can then consider which complexity class this problem belongs to. As pyramids indicates, the appropriate complexity class we obtain depends on how the input is provided.

• Suppose that the input function is provided as an database (as the problem is sometimes described), where each entry to the database has some length $\ell$. If $n$ is the length of the string $x$ used to describe the entire database, then the database has $N = n\big/\ell$ entries. It is then possible to exhaustively search the entire database by querying each of the $N$ entries in sequence, and stop if we find an entry $y$ such that $f(y) = 1$. Supposing that each query to the database takes something like $O(\log N) \subseteq O(\log n)$ time, this procedure halts in time $O(N \log N) \subseteq O(n \log n)$, so that the problem is in FP.

  Assuming that the database-lookup can be done in coherent superposition, Grover's algorithm allows this problem is in FBQP. However, as FP ⊆ FBQP, the classical exhaustive search also proves that this problem is in FBQP. All that we obtain (up to log factors) is a quadratic speed-up due to a savings in the number of database queries.
  
  

• Suppose that the input function is described succinctly, by a polynomial-time algorithm that takes a specification $x \in \{0,1\}^n$ and an argument $y \in \{0,1\}^m$ and computes $\mathcal O : \mathcal H_2^{m+1} \!\to \mathcal H_2^{m+1}\!$ on a standard basis state $\lvert y \rangle\lvert b \rangle$, where $m$ may be much larger than $\Omega(\log n)$. An example would be where $x$ specifies the CNF form of some boolean function $f: \{0,1\}^m \to \{0,1\}$ for $m \in O(n)$, in which case we may efficiently evaluate $f(y)$ on an input $y \in \{0,1\}^m$ and thereby efficiently evaluate $\mathcal O$ on standard basis states. This puts the problem in FNP.

  Given a procedure to evaluate $f(y)$ from $(x,y)$ in time $O(p(n))$ for $n = \lvert x \rvert$, Grover's algorithm solves the problem of Unstructured Search for $\mathcal O$ in time $O(p(n) \sqrt{2^m})$ $\subseteq O(p(n) \sqrt{2^n})$. This is not polynomial in $n$, and so does not suffice to put this problem in FBQP: we only obtain a quadratic speedup — though this is still a potentially huge savings of computation time, assuming that the advantage provided by Grover's algorithm is not lost to the overhead required for fault-tolerant quantum computation.
  
  

In both cases, the complexity is determined in terms of the length $n$ of the string $x$ *which specifies how to compute the oracle $\mathcal O$. In the case that $x$ represents a look-up table, we have $N = n\big/\ell$, in which case the performance as a function of $N$ is similar to the performance as a function of $n$; but in the case that $x$ succinctly specifies $\mathcal O$, and $N \in O(2^{n/2})$, the big-picture message that Grover's solves the problem in $O(\sqrt N)$ queries obscures the finer-grained message that this algorithm is still exponential-time for a quantum computer.

Decision complexity from relation problems

There is a straightforward way to get decision problems from relation problems, which is well-known from the theory of NP-complete problems: to turn the search problem to a question of the existence of a valid solution.

The decision version of a general search problem.
Given an input $x$ and an binary relation $R$, determine whether $\exists y: R(x,y)$ holds.

The complexity class NP can essentially be defined in terms of such problems, when the relationship $R$ is efficiently computable: the most famous NP-complete problems (CNF-SAT, HAMCYCLE, 3-COLOURING) are about the mere existence of a valid solution to an efficiently verifiable relationship problem. This switch from producing solutions to simply asserting the existence of solutions is also what allows us to describe versions of integer factorisation which are in BQP (by asking whether there exist non-trivial factors, rather than asking for the values of non-trivial factors).

In the case of Unstructured Search, again which complexity class best describes the problem depends on how the input is structured. Determining whether there exists a solution to a relationship problem may be reduced to finding and verifying a solution to that problem. Thus in the case that the input is a string $x$ specifying the oracle as a look-up table, the problem of unstructured search is in P; and more generally if $x$ specifies an efficient means of evaluating the oracle, the problem is in NP. It is also possible that there is a way of determining whether there exists a solution to Unstructured Search which does so without actually finding a solution, though it is not clear in general how to do so in a way which would provide an advantage over actually finding a solution.

Oracle complexity

I have conspicuously been shifting from talking about the oracle $\mathcal O$, to ways that an input $x$ can be used to specify (and evaluate) the oracle $\mathcal O$. But of course, the main way in which we consider Grover's algorithm is as an oracle result in which evaluating the oracle takes a single time-step and requires no speficiation. How do we consider the complexity of the problem in this case?

In this case, we are dealing with a relativised model of computation, in which evaluating this one specific oracle $\mathcal O$ (which, remember, is the input to the problem) is a primitive operation. This oracle is defined on all input sizes: to consider the problem for searching on strings of length $n$, you must specify that you are considering how the oracle $\mathcal O$ acts on inputs of length $n$, which again would be done by considering the length of a boolean string $x$ taken as input. In this case, the way in which we would present the problem might be as follows.

Unstructured Search relative to Oracle $\mathcal O$.
Given an input $x = 11\cdots 1$ of length $n$,

• find a $y \in \{0,1\}^n$ (relation problem) or

• determine whether there exists a $y \in \{0,1\}^n$ (decision problem)

such that $\mathcal O \lvert y \rangle \lvert 0 \rangle = \lvert y \rangle \lvert 1 \rangle$.

This problem is in $\mathsf{NP}^{\mathcal O}$ (for the decision problem) or $\mathsf{FNP}^{\mathcal O}$ (for the relation problem), depending on which version of the problem you wish to consider. Because Grover's algorithm is not a polynomial-time algorithm, this problem is not known to be in $\mathsf{BQP}^{\mathcal O}$ or $\mathsf{FBQP}^{\mathcal O}$. In fact, we can say something stronger, as we will soon see.

The reason why I brushed over the actual, oracle-based description of Unstructured Search was in order to touch on your point of complexity, and in particular to touch on the question of input size. The complexity of problems are largely governed by how the inputs are specified: as a succinct specification (in the case of how a function is specified in CNF-SAT), as an explicit specification (in the case of a look-up table for a function), or even as an integer specified in unary, i.e. as the length of a string of 1s as above (as in "Unstructured Search relative to Oracle $\mathcal O$" above).

As we can see from the latter case, if we treat the input only as an oracle, the situation looks a bit un-intuitive, and it certainly makes it impossible to talk about the ways that the "database" can be realised. But one virtue of considering the relativised version of the problem, with an actual oracle, is that we can prove things which otherwise we have no idea how to prove. If we could prove that the decision version of the succinct unstructured search problem was in BQP, then we would stand to realise an enormous breakthrough in practical computation; and if we could prove that the decision problem was not actually in BQP, then we would have shown that P ≠ PSPACE, which would be an enormous breakthrough in computational complexity. We don't know how to do either. But for the relativised problem, we can show that there are oracles $\mathcal O$ for which the decision version of "Unstructured Search relative to $\mathcal O$" is in $\mathsf{NP}^{\mathcal O}$ but not in $\mathsf{BQP}^{\mathcal O}$. This allows us to show that while quantum computing is potentially powerful, there are reasons to expect that BQP probably doesn't contain NP, and that the relation version of Unstructured Search in particular is unlikely to be contained in FBQP without imposing strong constraints on how the input is represented.

Answer 2

Complexity classes are generally defined with regard to the size of the input. The relevant sizes here are $n$ (the number of qubits on which you let Grover's algorithm operate) and a number you haven't mentioned yet, call it $m$, of bits needed to describe the subroutine generally referred to as the oracle. Typically, the oracle will be efficiently implemented in a way that scales polynomially in $n$, which is the case, for example, if you encode a typical boolean satisfiability problem in the oracle.

In any case, you do not get a gain in complexity class using Grover's algorithm: It takes exponentially many quantum operations, typically $m*2^{n/2}$, to solve a problem we could brute-force in exponentially many steps, typically $m*2^{n-1}$, on a classical computer anyways. This means that problems known (e.g. EXPTIME) or suspected (e.g. NP) to take exponential runtime will still require exponential runtime.

However, physicists like to appeal to the notion that this is still an exponential speed-up with no known (or indeed readily conceivable) classical equivalent. This is most apparent in the database example where the oracle function is a database lookup and Grover's algorithm can cause one to need many fewer lookups than there are data in the database. In this sense, there is still a significant advantage, although it is completely lost in the complexity class picture.

Answer 3

All counting is done in terms of $n$, the number of bits required to describe the input.

We define the class of problems $\text{NP}$ in the following way (or, this is one way to do it):

Let $f(x)$ be a function that accepts an input $x\in\{0,1\}^n$ and returns a single bit value 0 or 1. The task is that you have to find whether a given value of $x$ returns a 1. However, there is further structure to the problem: if $f(x)=1$, you are guaranteed that there exists a proof $p_x$ (of size $m\sim\text{poly}(n)$) such that a function $g(x,p_x)=1$ only if $f(x)=1$, and the function $g(x,p_x)$ is efficiently computable (i.e. it has a running time of $\text{poly}(n)$.

Let me give a few examples (perhaps these are what you were asking for here?):

• Parity: $f(x)$ answers the question 'is $x$ odd?'. This is so trivial (just take the least significant bit of $x$) that $f(x)$ is efficiently computed directly, and therefore a proof is unnecessary, $g(x,p_x)=f(x)$.

• Composite numbers: $f(x)$ answers the question 'is the decimal representation of $x$ a composite number?'. One possible proof in the yes direction (you only have to prove that direction) is to give a pair of factors. e.g. $x=72$, $p_x=(8,9)$. Then $g(x,p)$ simply involves multiplying together the factors and checking they are equal to $x$.

• Graph isomorphism: Given two graphs $G_1$ and $G_2$ (here $x$ contains the description of both graphs), $f(x)$ answers the question 'are the two graphs isomorphic?'. The proof $p_x$ is a permutation: a statement of how the vertices in $G_1$ map to those of $G_2$. The function $g(x,p_x)$ verifies that $p_x$ is a valid permutation, permutes the vertices of $G_1$ using the specified permutation, and verifies that the adjacency matrix is the same as that of $G_2$.

• Minesweeper: The old favourite game built into windows (and others) can be expressed like this. Imagine a minesweeper board that is partially uncovered, so some cells are unknown, and some cells have been uncovered to reveal how many mines are in the neighbouring cells. This is all built into the variable $x$. $f(x)$ asks the question 'is there a valid assignment of mines on the uncovered region?'. The proof, $p_x$ is simply one such assignment of mines. This is easily verified using $g(x,p_x)$ which simply ensures consistency with every known constraint.

All of these problems are in $\text{NP}$ because they fit the definition of an efficiently verifiable solution. Some of them are known to be in $\text{P}$ as well: we've already stated that odd testing is in $\text{P}$. Composite numbers also is, because it is efficient to check if a number is prime using AKS primality testing.

Graph isomorphism and minesweeper are not known to be in $\text{P}$. Indeed, minesweeper is known to be $\text{NP}$-complete, i.e. if it can be solved efficiently, every problem in $\text{NP}$ is in $\text{P}$. Many people suspect that $\text{P}\neq\text{NP}$, and hence Minesweeper would have instances which take longer than polynomial time to solve.

One possible way to solve an $\text{NP}$ problem is, for a fixed $x$, simply to test all possible proofs $p_x$ up to a maximum length $m=\text{poly}(n)$, and see if there's a satisfying solution, i.e. to search for a solution $g(x,p_x)=1$. Obviously, that takes time $O(2^m\text{poly}(m))$, as there are exponentially many items to search, each requiring a polynomial time to compute. This can be improved by implementing Grover's search: we just search for a solution $g(x,p_x)=1$ (i.e. the valid $p_x$ becomes the marked item), and this takes a time $O(2^{m/2}\text{poly}(m))$. This is massively faster, but does not change the assessment of whether the running time is polynomial or something worse; it has not become a polynomial time algorithm. For example, graph isomorphism would have to search over all possible permutations. Minesweeper would have to search over all possible assignments of mines on uncovered squares.

Of course, some of the time, additional structure in the problem permits different solutions that do not require the searching of all possible proofs. There, Grover's search is of less, or even no, use to us, but it might be that we can come up with a polynomial time algorithm in another way. For example, the case of composite testing: classically, finding the factors of a number appears to be hard: we can't do much better than testing all possible factors, so making use of that form of proof doesn't help much, but, as already mentioned, the question can be resolved efficiently via another route, AKS primality testing.

Answer 4

Forget about database. Grover's algorithm solves Boolean Satisfiability Problem, namely:

You have a boolean circuit with $n$ inputs and a single output. The circuit outputs $1$ for a single configuration of input bits, otherwise is outputs $0$. Find the configuration of input bits.

The problem is known to be NP-complete.