We’re rewarding the question askers & reputations are being recalculated! Read more.
2 deleted 4 characters in body
source | link

As this seems a recurring question, let me repeat my answer from Physics.SE:


This seems to be a common misunderstanding about Grover's algorithm. It is not about querying a magically encoded database. Rather, you have an efficiently computable function $f(x)\in\{0,1\}$ and you want to find some $x_0$ for which $f(x_0)=1$. Since you know how to realize $f(x)$ (i.e., you have a circuit), you can run $f$ on a quantum computer and use Grover to find such an $x_0$. This function can be seen as returning entries of a "database", which is encoded in a specific function, though I don't particularly like this picture.

The relevance is in the fact that a large number of interesting problems (namely, the class NP) are such that solutions might be hard to find, but they are easy to verify. Thus, Grover gives a square-root speed-up on any brute-force method to solve such a problem (i.e., any method which does not make use of any special structural property of $f$).


This seems to be a common misunderstanding about Grover's algorithm. It is not about querying a magically encoded database. Rather, you have an efficiently computable function $f(x)\in\{0,1\}$ and you want to find some $x_0$ for which $f(x_0)=1$. Since you know how to realize $f(x)$ (i.e., you have a circuit), you can run $f$ on a quantum computer and use Grover to find such an $x_0$. This function can be seen as returning entries of a "database", which is encoded in a specific function, though I don't particularly like this picture.

The relevance is in the fact that a large number of interesting problems (namely, the class NP) are such that solutions might be hard to find, but they are easy to verify. Thus, Grover gives a square-root speed-up on any brute-force method to solve such a problem (i.e., any method which does not make use of any special structural property of $f$).

Differently speaking, Grover's algorithm is not, I repeat not, about searching Harry Potter books or the like. It is about speeding up finding solutions of unstructured NP problems (or problems where one does not know the structure), i.e. where the validity of a solution can be checked. This is often called a "search problem", but is has nothing to do with "databases" as we would usually think of them, and is thus not applicable to Harry Potter.

As this seems a recurring question, let me repeat my answer from Physics.SE:


This seems to be a common misunderstanding about Grover's algorithm. It is not about querying a magically encoded database. Rather, you have an efficiently computable function $f(x)\in\{0,1\}$ and you want to find some $x_0$ for which $f(x_0)=1$. Since you know how to realize $f(x)$ (i.e., you have a circuit), you can run $f$ on a quantum computer and use Grover to find such an $x_0$. This function can be seen as returning entries of a "database", which is encoded in a specific function, though I don't particularly like this picture.

The relevance is in the fact that a large number of interesting problems (namely, the class NP) are such that solutions might be hard to find, but they are easy to verify. Thus, Grover gives a square-root speed-up on any brute-force method to solve such a problem (i.e., any method which does not make use of any special structural property of $f$).


Differently speaking, Grover's algorithm is not, I repeat not, about searching Harry Potter or the like. It is about speeding up finding solutions of unstructured NP problems (or problems where one does not know the structure), i.e. where the validity of a solution can be checked. This is often called a "search problem", but is has nothing to do with "databases" as we would usually think of them, and is thus not applicable to Harry Potter.

As this seems a recurring question, let me repeat my answer from Physics.SE:

This seems to be a common misunderstanding about Grover's algorithm. It is not about querying a magically encoded database. Rather, you have an efficiently computable function $f(x)\in\{0,1\}$ and you want to find some $x_0$ for which $f(x_0)=1$. Since you know how to realize $f(x)$ (i.e., you have a circuit), you can run $f$ on a quantum computer and use Grover to find such an $x_0$. This function can be seen as returning entries of a "database", which is encoded in a specific function, though I don't particularly like this picture.

The relevance is in the fact that a large number of interesting problems (namely, the class NP) are such that solutions might be hard to find, but they are easy to verify. Thus, Grover gives a square-root speed-up on any brute-force method to solve such a problem (i.e., any method which does not make use of any special structural property of $f$).

Differently speaking, Grover's algorithm is not, I repeat not, about searching Harry Potter books or the like. It is about speeding up finding solutions of unstructured NP problems (or problems where one does not know the structure), i.e. where the validity of a solution can be checked. This is often called a "search problem", but is has nothing to do with "databases" as we would usually think of them, and is thus not applicable to Harry Potter.

1
source | link

As this seems a recurring question, let me repeat my answer from Physics.SE:


This seems to be a common misunderstanding about Grover's algorithm. It is not about querying a magically encoded database. Rather, you have an efficiently computable function $f(x)\in\{0,1\}$ and you want to find some $x_0$ for which $f(x_0)=1$. Since you know how to realize $f(x)$ (i.e., you have a circuit), you can run $f$ on a quantum computer and use Grover to find such an $x_0$. This function can be seen as returning entries of a "database", which is encoded in a specific function, though I don't particularly like this picture.

The relevance is in the fact that a large number of interesting problems (namely, the class NP) are such that solutions might be hard to find, but they are easy to verify. Thus, Grover gives a square-root speed-up on any brute-force method to solve such a problem (i.e., any method which does not make use of any special structural property of $f$).


Differently speaking, Grover's algorithm is not, I repeat not, about searching Harry Potter or the like. It is about speeding up finding solutions of unstructured NP problems (or problems where one does not know the structure), i.e. where the validity of a solution can be checked. This is often called a "search problem", but is has nothing to do with "databases" as we would usually think of them, and is thus not applicable to Harry Potter.