0
$\begingroup$

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:

enter image description here

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.

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ 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 $\endgroup$
    – glS ♦
    Jul 3, 2021 at 11:09
  • 1
    $\begingroup$ I have just edited your question in order to be in line with requirements on formatting as mentioned by gIS. $\endgroup$
    – Martin Vesely
    Jul 4, 2021 at 20:45
  • 1
    $\begingroup$ @gIS: I have just edited the question to follow formatting requirements. As Rafael is a new user, I think a small help is necessary. :-) $\endgroup$
    – Martin Vesely
    Jul 4, 2021 at 20:48

1 Answer 1

Reset to default
2
$\begingroup$

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

You can also find some additional information about the paper in this thread.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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 ? $\endgroup$
    – Pritam Sinha
    Jul 4, 2021 at 7:31
  • $\begingroup$ @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. $\endgroup$
    – Martin Vesely
    Jul 4, 2021 at 17:04
  • 1
    $\begingroup$ 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. $\endgroup$
    – Pritam Sinha
    Jul 5, 2021 at 15:23

Your Answer

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

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