# How to build and visualize circuit from matrix?

In paper Efficient quantum algorithm for solving travelling salesman problem: An IBM quantum experience, the authors use gate $$U_j$$ and its decomposition $$U_j = \begin{pmatrix} \mathrm{e}^{ia} & 0 & 0 & 0 \\ 0 & \mathrm{e}^{ib} & 0 & 0 \\ 0 & 0 & \mathrm{e}^{ic} & 0 \\ 0 & 0 & 0 & \mathrm{e}^{id} \\ \end{pmatrix}= \begin{pmatrix} 1 & 0 \\ 0 & \mathrm{e}^{i(c-a)} \end{pmatrix} \otimes \begin{pmatrix} \mathrm{e}^{ia} & 0 \\ 0 & \mathrm{e}^{ib} \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & \mathrm{e}^{i(d+c-a-b)} \\ \end{pmatrix}.$$ Note that they denote exponent $$d+c-a-b$$ by $$x$$ in the paper.

Then they present implementation of controlled version of $$U_j$$ with this circuit:

and also provide QASM code

cu1 ( c−a ) x , y ;
u1 ( a ) x ;
cu1 ( b−a ) x , z ;
ccx x , y , z ;
cu1 ( ( d−c+a−b ) / 2 ) x , z ;
ccx x , y , z ;
cu1 ( ( d−c+a−b ) / 2 ) x , y ;
cu1 ( ( d−c+a−b ) / 2 ) x , z ;


I am so confused about this. Can someone explain how the matrix, the image and the code connect to each other? It seems that each describe different circuit.

• please try to make your question more focused, and ask a single question per post. You can open different posts to ask different questions. See quantumcomputing.stackexchange.com/help/how-to-ask. Also, try to avoid screenshots of text as much as possible, as those are hardly searchable, and provide links to show where your information is from
– glS
Jul 3 at 11:09
• I have just edited your question in order to be in line with requirements on formatting as mentioned by gIS. Jul 4 at 20:45
• @gIS: I have just edited the question to follow formatting requirements. As Rafael is a new user, I think a small help is necessary. :-) Jul 4 at 20:48

Firstly, you might be interested in paper Elementary gates for quantum computation explaining how complex gates can be decomposed to simpler ones. This would allow you understand how the matrix $$U_j$$ is decomposed.

Before we proceeed further, we have to define gate $$U1$$ used on IBM Q computer: $$U1(\lambda)= \begin{pmatrix} 1 & 0 \\ 0 & e^{i\lambda} \end{pmatrix}$$

While the authors present matrix $$U_j$$, the implementation of acutal gate in the figure is its controlled version. Therefore, is it a little bit different.

The controlled version of the first matrix in the decomposition correspond to the first gate in the picture. On IBM Q, it is controlled $$U1$$ gate with $$\lambda = c-a$$.

The second gate is composed of global phase gate with angle $$a$$ and $$U1$$ gate with angle $$b-a$$. The global phase $$e^a$$ is simply factored out of the matrix which leaves you with $$e^a\text{diag}(1;e^{b-a})$$. So controlled version of this gate is implemented with $$U1$$ having $$\lambda = a$$ applied on the control qubit and no gate (or rather identity gate $$I$$) applied on the target qubit. This is the controlled global phase gate. Then it is followed by controlled $$U1$$ with angle $$b-a$$.

The last matrix in the decomposition is controlled $$U1$$ gate described by 4x4 matrix $$\begin{pmatrix}I & O \\ O & U1\end{pmatrix},$$ where $$I$$ is identity matrix 2x2 and $$O$$ is zero matrix 2x2. Since the whole $$U_j$$ has to be controlled, the last gate is controlled controlled $$U1$$ (or double controlled $$U1$$) implemented with last three gates in the figure. However, this part seems a little bit strange in the original paper and I think it is wrong. According to the lemma 6.1 in the paper linked above, it is possible to construct double controlled gate with CNOT gates and gates $$V$$ and $$V^\dagger$$ such that $$V^2 = U$$. In this case $$U = U1(a)$$, therefore $$V = U1(a/2)$$ and $$V^\dagger = U1(-a/2)$$. The reason is that $$U1$$ is a kind of a rotation, so $$V^2=VV=U1(a/2)U1(a/2)=U1(a)$$ and inverse to $$U1(a)$$ is $$U1(-a)$$. You can check all this by direct calculation.

Also note that exponent in the last matrix is wrong. It should be $$d-c+a-b$$. You can check this by calculating right side of the equation. As the matrices are presented in the paper, it is impossible to arrive back to $$U_j$$ on the left side.

With the decomposition provided in the question, lemma 6.1 I mentioned and correction to the exponent, the correct code for controlled version of $$U_j$$ should be

\\first matrix
u1(c-a) x,y;
\\second matrix
u1(a) x;
cu1(b-a) x,z;
\\third matrix (with lemma 6.1)
cu1((d-c+a-b)/2) y,z;
cx x,y;
cu1(-(d-c+a-b)/2) y,z;
cx x,y;
cu1((d-c+a-b)/2) x,z;


Finally, I would list all mistakes in the paper:

• the exponent $$x$$ should be $$d-c+a-b$$, not $$d+c-a-b$$
• there should not be Toffoli gates but CNOTs on qubits $$x$$ and $$y$$
• there should be sign minus before parameter of $$U1$$ on seventh row
• no Toffoli gate should be in the circuit diagram and $$U(x)$$ should be double controlled gate

• Thanks for the reply. I was so confused about this. 2 question plz: I feel that $U(b-a)$ gate came we take out $e^{ia}$ part from the second matrix. right ? 1) When you said the last four gates in the figure- 2 Toffolis and 2 controlled $U_{1}$. Which 2 $U_{1}$. Bcoz if I see the code and figure the 2 doesn't match up. 2) And also in the code its saying controlled $U(x)$, its different in figure ? Jul 4 at 7:31
• @Rafael: I more elaborated and edited my answer. Please note that there is a lot of mistakes in the paper you are strugling with. I rememberd my confusions when I firstly saw it. I found some my notes and tried to do my best to explain how the correct decomposition of $U_j$ should look like, I also added corrected QASM code. Hope this help. And sorry, I did also some mistakes in my first version of the answer. Jul 4 at 17:04
• Thanks for the detailed explanation and also clearing my doubt. I was so confused, I see you were also confused when you saw it. After your explanation I tried to do the matrix tensor and multiplication by hand and I got exactly the same matrix as $CU_{j}$. Now all of it make senses. Thank you for your effort to help. Jul 5 at 15:23