4
$\begingroup$

I recently asked this question on Grover's algorithm, and I am still fairly confused about the whole thing. Consider the following snippet from this post (written by DIDIx13) which for convenience I will reproduce here:

If you throw away the problem structure, and just consider the space of $2^n$ possible solutions, then even a quantum computer needs about $\sqrt{2^n}$ steps to find the correct one (using Grover's algorithm) If a quantum polynomial time algorithm for a $\text{NP}$-complete problem is ever found, it must exploit the problem structure in some way.

The first line emphasis one place where I am confused: Grover's algorithm finds a solution amongst $2^n$ solutions to a problem - this is not a decisions problem alone and as mentioned in my question linked above means we cannot assign it a complexity class.

That said Grover's algorithm can be used to solve decision problems (there seems to be a lot of talk on related questions about "SAT") - but I have yet seen a simple example of such an application.

Thus my question is: Does there exist a simple example of Grover's algorithm solving a decision problem? (even better if you can provide one where the classical search is in $NP$ and another in $P$)

$\endgroup$

1 Answer 1

3
$\begingroup$

Take the problem of 3-SAT. There is some $f(x)$ which gives outputs 0 or 1. We generally think of the case where the outputs 1 are rare, and hard to find.

PROBLEM: Determine if there is an $x$ that satisfies $f(x)=1$.

(3-SAT has a certain structure to the way the variables are evaluated based on conjunctive normal form, but that's not so important right now).

This problem is known to be NP-complete: as much as we believe NP and P are distinct, we believe this problem cannot be solved efficiently. But Grover's does help us because it gives us a square root speed-up; it searches for the items where the answer is 1.

I'm not sure if you're asking for a specific example of an $f(x)$, but one of the issues is that this complexity classification is about scaling: you need a family of functions for different sized inputs. 3-SAT is one such class. Perhaps my answer here supplies the sorts of examples you were after?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.