Undergrad They physics of phase inversion in Grover's algorithm

[dreamspy]

How would this operator be implemented physically if we had a quantum computer?

In Grover's algorithm this magical operator is often called "phase inversion". Here is the operator from wiki:

https://wikimedia.org/api/rest_v1/media/math/render/svg/07fb23bffa787430b084971c6a108a8f6ff6c2b3

It’s an operator that does nothing to most of the states, except it inverts the phase of the states we’re looking for. (for all states x where f(x) = 1).

I assume we are using the feature of quantum mechanics that we can input a superposition of all possible states, and acting upon them all at the same time with our operators, then at the end, measuring the state of the system, giving us the state we're looking for with high probability (p > 1/2).

So I repeat my question:

How would this operator be implemented physically if we had a quantum computer?

Thanks
Frímann Kjerúlf
BSc Physics - University of Iceland

 

[PeterDonis]

Here is the operator from wiki:

You need to give a lot more context. Please give a link to the full article. Or, even better, to a textbook or peer-reviewed paper that discusses this operator.

 

[Strilanc]

The black box in Grover's algorithm depends on the problem you're trying to solve. But generally it's just a "solution checker" that checks if a given input is correct, hits the "is it correct?" bit with a Z gate, then uncomputes all the junk it created while doing that.

A simple example is searching for a 3-SAT solution. Suppose we want to find boolean values for x, y, and z that satisfy:

$$(x \lor y \lor z) \land (\lnot x \lor \lnot y \lor \lnot z) \land (\lnot x \lor y \lor \lnot z)$$

To check a solution, you need to check if each clause is satisfied then combine those answers into one big 'all clauses satisfied' answer. Which, combined with the Z gate and uncomputation, looks something like exactly this:

Of course this is a very simple case. In more complicated cases, like checking if the input encodes a valid proof of a theorem, the circuit can get very complicated. You would want to use a tool to generate the circuit, based on some C code or whatever.