2
$\begingroup$

I wonder about the effectiveness of the Grover algorithm in real life. In particular, if I think of a number in $\{0,...,2^n -1\}$, is it possible to build a "real" machine that guesses my number (with high probability) in $\sim \sqrt{2^n}$ steps ?

By a "machine", I mean some kind of big box or any complicated device (a particle accelerator, if you desire) that could contain, for example, $n$ entangled qbits, combined with a screen and a two-key keyboard ("yes" and "no") such that

1) the screen displays some number in $\{0,...,2^n -1\}$ and the sentence "is this your number?"

2) the machine waits for a human user to press either of the two keys of the keyboard

3) the machine repeats steps 1), 2) for about $\sqrt{2^n}$ times

4) the screen displays some number in $\{0,...,2^n -1\}$ and the sentence "this is your number".

EDIT : I know the Grover algorithm, the problem I have is about the "nature" of the oracle.

$\endgroup$
  • 1
    $\begingroup$ Particle accelerator? I doubt that particle accelerators have anything to do with this - I'd think you'd be looking for a quantum computer. $\endgroup$ – David Z Sep 19 '17 at 16:23
  • $\begingroup$ It was a "joke". I mean any device, as big and complicated as you would want. Anyhow, if I can say that I know approximately what a quantum algorithm is, I sure don't know what a quantum computer, a particle accelerator, or even a particle are. I'll edit my post. $\endgroup$ – Plop Sep 19 '17 at 16:30
  • $\begingroup$ a related question on quantumcomputing.SE $\endgroup$ – glS Aug 20 '19 at 20:34
2
$\begingroup$

This seems to be a common misunderstanding about Grover's algorithm. It is not about querying a "magic" black box function. 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$.

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$).

$\endgroup$
  • $\begingroup$ About the first four lines, if you have a "physical" circuit (I mean, an assembly, in real life, of tiny bits of "quantum hardware") that can "compute" a function $f$, isn't it faster to analyse the circuit that to run it on a quantum computer ? Besides, the person who built the circuit is you, right ? $\endgroup$ – Plop Sep 20 '17 at 8:26
  • $\begingroup$ About the following lines, I'm not sure what you mean. Do you mean that for a (some) NP problem, it is possible to build an efficient quantum circuit that "computes" a function $f$ defined over the set of all possible (and possibly wrong) outputs such that $f(x) = 1$ if and only if $x$ is a valid solution ? If yes, I don't see how it is possible to build such a circuit without knowing beforehand the valid solutions, and if it is, I don't know if it is possible to build a circuit that could work for any instance. $\endgroup$ – Plop Sep 20 '17 at 8:31
  • $\begingroup$ @Plop There are many cases where checking a solution to a problem is easy, but finding a solution is (potentially) hard -- graph coloring, 3-SAT, factoring, ... For such problems, $f(x)$ checks the correctness of a solution $x$, and is thus easy to compute. Yet, finding a solution $x_0$ is hard, even if you know everything about $f$ and you built it yourself. $\endgroup$ – Norbert Schuch Sep 20 '17 at 9:18
  • $\begingroup$ Ok I agree that even if I built $f$ myself, it could still be hard to find a solution. But I still don't understand what you mean : assume we have and NP problem, that is, a problem for which no efficient algorithm is known to find a solution, but such that there is an efficient algorithm, that, given a guess, checks if it is a valid answer. Can you tell me what you would do ? On what $f$ would you use Grover's algorithm ? Thanks for your replies, by the way. $\endgroup$ – Plop Sep 20 '17 at 9:42
  • $\begingroup$ @Plop You encode the proof into $x$, and $f(x)$ is the function which checks the proof. For graph coloring, e.g., $x$ would be a string of colors, and $f(x)$ would check if all assignements are satisfied (which can be done with AND, OR, and NOT gates). $\endgroup$ – Norbert Schuch Sep 20 '17 at 11:38
0
$\begingroup$

No, you can't run Grover's algorithm against a person pressing "no" or "yes" keys when prompted "is this your number?".

Grover's algorithm requires the ability to query under superposition, without decoherence. Humans don't support this kind of operation. We're too large and hot and wet and generally decohering all over the place.

$\endgroup$
  • $\begingroup$ Can you give me some details ? I don't understand why the last lines prove your claim. Assuming humans did not decohere, would the algorithm work ? (Maybe "pressing keys" would not make sense anymore, I don't know ?) And your claim is only half-satisfying to me : I wonder about the possibility of building a machine, maybe based on Grover's algorithm, maybe not, maybe on some more complicated algorithm. $\endgroup$ – Plop Sep 20 '17 at 8:34
  • $\begingroup$ It's really really not possible to make a human that doesn't decohere. For example, they wouldn't be able to think. Thinking creates waste heat. Waste heat counts as a measurement. The oracle in Grover's algorithm has to be queryable under superposition, and humans simply aren't capable of that. $\endgroup$ – Craig Gidney Sep 20 '17 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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