1
$\begingroup$

Here's the exact problem I'm having with Grover's search algorithm.. Given a function f:{0,...,N-1} -> {0,1}, Grover's problem is to find x such that f(x)=1, provided that there exists such x.

The phase inversion step: Invert the phase of the "key value".

So my question is, when we can already distinguish the key from the others, there is nothing to solve. Why do we need to solve the problem at all when we can already separate the key value? I am missing a point here but I don't understand what it is.

Many thanks for your help.

$\endgroup$
  • 1
    $\begingroup$ "we need to solve the problem" so that we can find the key value, rather than just being able to separate it. ​ ​ ​ ​ ​ ​ ​ Presumably, ​ ​ ​ " ​ Invert the phase of the "key value" ​ " ​ ​ ​ can somehow be done without already knowing the key value. ​ ​ ​ ​ ​ ​ ​ (I have no idea how that might be doable.) ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user12859 Jan 12 '18 at 9:31
  • 1
    $\begingroup$ Where did you find this phrase? You should probably give a reference, preferably a link if available. $\endgroup$ – Yuval Filmus Jan 12 '18 at 12:34
  • 1
    $\begingroup$ There is probably a quantum register containing the key (initially, a superposition of all keys), and this is what you need to invert the phase of. $\endgroup$ – Yuval Filmus Jan 12 '18 at 12:34
  • $\begingroup$ The phase inversion step "Invert the phase of the key value" is a bit unclear and circular. If the aim of the algorithm is to find the key value and uses the step "invert the phase of the key value" then the algorithm is begging the question. It's circular reasoning. I don't see how this is legitimate. $\endgroup$ – acevik Jan 13 '18 at 8:03
1
$\begingroup$

When computing the oracle in Grover's algorithm, you prepare a qubit entangled with the search register such that the qubit is ON in the parts of the superposition where the search register contains a satisfying solution and OFF in the other parts of the superposition. This is not hard to do: you just use any old circuit that would determine if a given input was a solution, and apply that to the search register.

By preparing the solution qubit, applying a Z gate to it, then uncomputing the solution qubit, you negate the parts of the superposition corresponding to solutions. Having that qubit available is not the same thing as finding a solution. For example, if you measured it you'd almost always get an OFF result and find that your search register contained a non-solution. But, by using the prepared qubit as a tool to negate the phase of the solution space, Grover's algorithm can set up a gradual rotation towards the solution space.

More information: http://algassert.com/post/1719

$\endgroup$

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.