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.


1 Answer 1


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.

  • 1
    $\begingroup$ Thank you, very clear! So basically, in order to find the matrix representation of the algorithm, we need to know the generalized matrix of each gate. In this case, Hadamard and Controlled Not gates are easy to "expand", but I think other gates not. $\endgroup$ Commented Jan 22, 2020 at 15:35
  • 1
    $\begingroup$ @FelipeRojoAmadeo: You are welcome. This approach works for any controlled gate. Simply put any other gate instead of $X$ or $H$. $\endgroup$ Commented Jan 22, 2020 at 15:53
  • $\begingroup$ For SWAP I can't build CU_n matrix... If I apply a SWAP gate to q[0] and q[2], I can implement it as 3 CX gates: CX_02, CX2_0, and CX_02, with CX_xx as subindex, first for control qubit and the second one for target qubit. As you mentioned in your last comment, your approach is only for controlled gates, but no for other gates, right? $\endgroup$ Commented Jan 22, 2020 at 18:03
  • 2
    $\begingroup$ @FelipeRojoAmadeo: In case of swap gate, you can rewrite second CNOT (i.e. acting on $q_0$ and controlled by $q_2$) as $(H \otimes H) CNOT (H \otimes H)$. The CNOT acts on qubit $q_2$ and it is controlled by $q_0$. $H$'s are applied on $q_0$ and $q_2$. $\endgroup$ Commented Jan 23, 2020 at 5:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.