9

This is part of Simon Algorithm (Initial state + some Oracle function) There is a post that explains how to interpret circuits (How to interpret a quantum circuit as a matrix?), but I'm not sure how to apply to the following circuit.

Circuit built with IMB plataform

The first part, both Hadamard to first and second qubit:

$M_1 = H \otimes H \otimes I \otimes I$

Then, first Controlled NOT:

How can I apply a matrix to the first and second qubit if I have $M_1$ that is a 16x16 matrix. I know I could have applied $H$ to the first qubit and then do a tensor product with $I$ (third qubit), and the result, multiply by $CX$. But then I have the second $CX$ which is applied to the first qubit and 4th qubit.

Symbol $\otimes$ is a tensor product.

Martin Vesely
  • 15,244
  • 4
  • 32
  • 75

1 Answers1

10

Note: $I_k$ is unit matrix and $O_k$ is the zero matrix of order $k$ in the following text.

First step of the algorithm is $H \otimes H \otimes I_2 \otimes I_2$ as you mentioned.

A controlled gate $U$ with $n$ qubits between the control qubit and the target qubit can expressed as a matrix

$$ CU_{n} = \begin{pmatrix} I_{\frac{N}{2}} & O_{\frac{N}{2}} \\ O_{\frac{N}{2}} & I_{\frac{N}{4}} \otimes U \end{pmatrix}, $$

where $N = 2^{n + 2}$ (you can check that for $n=0$ and $U=X$ you will get CNOT matrix).

Now, how to apply this on CNOT acting on $q_{2}$ and controlled with $q_{0}$. In this case $n=1$ and $U=X$. Hence $N=2^{1+2}=8$ and CNOT in the second step of algorithm can be written as $$ CX_{1} = \begin{pmatrix} I_{4} & O_{4} \\ O_{4} & I_{2} \otimes X \end{pmatrix} $$

After that there is a $I$ gate on qubit $q_{3}$, so the second step of the algoritm can be written as $CX_{1} \otimes I_{2}$.

Third step is CNOT gate with two qubits between control and target qubits ($N=2^{2+2} = 16$) hence its matrix is

$$ CX_{2} = \begin{pmatrix} I_{8} & O_{8} \\ O_{8} & I_{4} \otimes X \end{pmatrix} $$

Fourth step is simply $I_2 \otimes CNOT \otimes I_2$.

Fifth step is $I_2 \otimes CX_{1}$ (i.e. similarly as in the second step but matrices in Kronecker product are switched).

You can check that all matrices describing each step is 16x16. Now, you can multiply them all together to get final matrix representation of the algorithm.

Martin Vesely
  • 15,244
  • 4
  • 32
  • 75