How can you decompose Grover's diffusion operator into gates?

Question

I know how Grover's diffusion operator works ($U_s = 2|sranglelangle s|-I$) with the inversion around the mean. However, I want to implement it in simpler gates, to use the algorithm. How can I do this ?

BrockenDuck · Accepted Answer

Grover's diffusion operator can be implemented with H, X and a controlled Z gate. I will show this mathematically. Since $|srangle = |+rangle^{otimes n} $ :
$$
U_s = 2|sranglelangle s|-I = H^{otimes n}(2|0ranglelangle0|-I)H^{otimes n}
$$
We know have the H gate which appeared. We now know that we will have to apply the Hadamard gate to every qubit at the beginning and the end of Grover's diffusion operator. We will only work with $2|0ranglelangle 0|-I$. $|0ranglelangle0|$ is the outer product of the first basic state. It is a matrix filled with 0s only (0, 0) is filled with a 1. $I$ Is the identity matrix.
$$
2|0ranglelangle 0|-I = 2
begin {bmatrix}
1 & 0 & cdots & 0 
0 & 0 & cdots & 0 
vdots & vdots & ddots & 0
0  & 0 & 0 & 0
end {bmatrix}
-
I = 
begin {bmatrix}
2 & 0 & cdots & 0 
0 & 0 & cdots & 0 
vdots & vdots & ddots & 0
0  & 0 & 0 & 0
end {bmatrix} -
begin {bmatrix}
1 & 0 & cdots & 0 
0 & 1 & cdots & 0 
vdots & vdots & ddots & 0
0  & 0 & 0 & 1
end {bmatrix}
=
begin {bmatrix}
1 & 0 & cdots & 0 
0 & -1 & cdots & 0 
vdots & vdots & ddots & 0
0  & 0 & 0 & -1
end {bmatrix}
$$
We now have the matrix which represents $2|0ranglelangle 0|-I$. It flips the phase of every state apart from $|0cdots0rangle$. If we apply a global phase of $-1$ (which can be ignored), we only have to flip the phase of $|0cdots0rangle$.
$$
begin {bmatrix}
1 & 0 & cdots & 0 
0 & -1 & cdots & 0 
vdots & vdots & ddots & 0
0  & 0 & 0 & -1
end {bmatrix}
= -1
begin {bmatrix}
-1 & 0 & cdots & 0 
0 & 1 & cdots & 0 
vdots & vdots & ddots & 0
0  & 0 & 0 & 1
end {bmatrix} = -1 X^{otimes n}
begin {bmatrix}
1 & 0 & cdots & 0 & 0 
0 & 1 & cdots & 0 & 0 
vdots & vdots & ddots & 0 & 0 
0 & 0 & 0 & 1 & 0 
0 & 0 & 0 & 0 & -1 
end {bmatrix} X^{otimes n}
$$
We can transform the matrix by applying the X gate to every qubit to only have to flip the phase of $|1cdots1rangle$ state. However, this matrix is only a controlled Z operation with all the qubits except the last one as control.
There we have it : Grover's diffusion operator with only H gates , X gates and a controlled Z gate. This paper describes a slightly different way to do it with a toffoli (CCNOT) gate but the method has the same complexity (I think). I hope this answered your question.

How can you decompose Grover's diffusion operator into gates?

One Answer

Add your own answers!

Ask a Question