# 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.