On a register of n qubits (N = 2^n amplitudes), Grover's inversion about the mean replaces every amplitude a by 2m - a, where m is the mean of all N amplitudes. As a matrix this is
where |s\rangle is the uniform state (every amplitude 1/\sqrt N) and \delta_{ij} is 1 when i = j and 0 otherwise. For n = 2 every diagonal entry is -0.5 and every other entry 0.5.
A chip cannot apply a 2^n \times 2^n matrix directly; it runs circuits. Write diffusion_circuit(n) that returns a circuit, a list of gates applied from left to right, whose matrix is D. The chip knows four gates:
("h", q),("x", q),("z", q): the Hadamard gate H=\tfrac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}, X=\begin{pmatrix}0&1\\1&0\end{pmatrix} or Z=\mathrm{diag}(1,-1) on qubitq;("mcz",): the multi-controlled Z on all n qubits, which multiplies the amplitude of the single basis state |11\dots1\rangle (index N-1) by -1 and leaves every other amplitude alone (for n = 1 it is just Z).
Qubit 0 is the leftmost bit: in 3 qubits, |011\rangle is index 3. Any global phase is accepted: a circuit whose matrix is -D (or e^{i\phi}D) counts as correct, because it acts on every state in the same way up to a global phase.
The setup gives circuit_matrix(n, gates), which returns the matrix of a circuit as a list of rows, so you can test with Run: print(circuit_matrix(2, diffusion_circuit(2))).
Examples
Input: n = 1
Output: a circuit whose matrix is [[0, 1], [1, 0]] up to a global phase
Explanation: with N = 2, D has 2/2 - 1 = 0 on the diagonal and 1 elsewhere.
Input: n = 2
Output: a circuit whose matrix is, up to a global phase,
[[-0.5, 0.5, 0.5, 0.5], [0.5, -0.5, 0.5, 0.5], [0.5, 0.5, -0.5, 0.5], [0.5, 0.5, 0.5, -0.5]]
Constraints
1 <= n <= 6- each test is judged by building the circuit's matrix and comparing it with D (tolerance
1e-6, any global phase)
Goals
- Write the inversion about the mean as the matrix 2|s><s| - I
- Build it from Hadamard, X and one multi-controlled Z gate
- Recognise that a circuit equal up to a factor -1 is the same operation