Grover's algorithm

by Fran├žois Schwarzentruber (you have some explanations below) $$\newcommand{\ket}[1]{\mid#1 \rangle}$$
























(*)






(**)



Qubits as cats

Qubits are here represented by cats. We have:
- 0 = dead cat = pictures where colors are inverted;
- 1 = alive cat.

The first qubit may be 0 (dead) or 1 (alive) . The second qubit may be 0 (dead) or 1 (alive) .

Superpositions as animations

A superposition is represented by cats that are changing over time with respect to the scalars in the superposition.


Examples:

is the superposition where the qubit is always at |1>.


is the superposition where the qubit is always at |0>.


may represent the superposition $$\frac 1 {\sqrt 2} (\ket 0 + \ket 1)$$ where the qubit is at |0> with probability 1/2 and at |1> with probability 1/2.


may represent the superposition $$\frac 1 2 \ket 0 + \frac {\sqrt 3} 2 \ket 1)$$ where the qubit is at |0> with probability 1/4 and at |1> with probability 3/4.


may represent the superposition $$\frac 1 2 (\ket {00} + \ket {01} + \ket {10} + \ket {11})$$ where all states |00>, |01>, |10> and |11> have probability 1/4.


is a Bell state: it may be the superposition $$\frac 1 {\sqrt 2} (\ket {00} + \ket {11})$$ where we have |00> with probability 1/2 and |11> with probability 1/2. There is entanglement.


If the scalar is negative, images are turned.

Example:
may represent the superposition -|1>.






Few words about Grover's algorithm

Grover's algorithm is solving the following problem. Let f be a function from {0, 1}^n to {0, 1}. Here n = 4. We pose N = 2^n. Here N = 16. There is a unique element x such that f(x) = 1. In our example, x is 0101 that is .


The aim is to find x without any knowledge on f. More precisely, the problem solved by Grover's algorithm is defined as follows:
- input: a black box Uf that computes f;
- output: x such that f(x) = 1.

Grover's starts with 0000, that is . Then we apply Hadamard gates in order to obtain a uniform superposition of all physical states. Then we apply the gate Uf. It preserves all physical states except |0101>. The state |0101> is mapped to -|0101>.


Examples:























Then D is the Grover diffusion operator that amplifies the unique state that has a negative scalar and put a positive scalar on it that is stricly greater in norm that the previous scalar. The other states are such that their probability are lower. In other words, the state |0101> is amplified. When we then apply again the Uf operator, we continue to negate the scalar of |0101> and the other scalars are kept equal. Then D continues to amply more and more the scalar of |0101> in norm. After some iterations of Uf and D, we may measure the qubits and obtain |0101> with a probability higher than 1/2: at (*) in the circuit the measure is ideal.


Warning: if we do too much iterations, then the probability is then again decreasing. For instance, (**) in the circuit is already too late.