How to decompose 8x8 Unitary Matrix into tensor product of three phased gate?

Question

Our goal is decompose 8x8 unitary matrices $U_j$ to extend the Solving TSP with Quantum Phase estimation

$U_j = \begin{pmatrix} e^{ia}& 0& 0& 0& 0& 0& 0&0 \\ 0& e^{ib}& 0& 0& 0& 0& 0&0 \\ 0& 0& e^{ic}& 0& 0& 0& 0&0 \\ 0& 0& 0& e^{id}& 0& 0& 0&0 \\ 0& 0& 0& 0& e^{ie}& 0& 0&0 \\ 0& 0& 0& 0& 0& e^{if}& 0&0 \\ 0& 0& 0& 0& 0& 0& e^{ig}&0 \\ 0& 0& 0& 0& 0& 0& 0&e^{ih} \end{pmatrix}$

Since, we are using QPE to solve TSP Problem, we must decompose unitary matrix $U_j$ into the tensor product of three phased gate with three degree of freedom $i,j,k$

$P_1 = \begin{pmatrix} 1 & 0 \\ 0 & e^{ii} \end{pmatrix}, \quad P_2 = \begin{pmatrix} 1 & 0 \\ 0 & e^{ij} \end{pmatrix}, \quad P_3 = \begin{pmatrix} 1 & 0 \\ 0 & e^{ik} \end{pmatrix}$

We have the result of tensor product of three phased gate $P_1 \otimes P_2 \otimes P_3$:

$P_1 \otimes P_2 \otimes P_3 = \begin{pmatrix} 1& 0& 0& 0& 0& 0& 0&0 \\ 0& e^{ik}& 0& 0& 0& 0& 0&0 \\ 0& 0& e^{ij}& 0& 0& 0& 0&0 \\ 0& 0& 0& e^{i(k+j)}& 0& 0& 0&0 \\ 0& 0& 0& 0& e^{ii}& 0& 0&0 \\ 0& 0& 0& 0& 0& e^{i(k+i)}& 0&0 \\ 0& 0& 0& 0& 0& 0& e^{i(i+j)}&0 \\ 0& 0& 0& 0& 0& 0& 0&e^{i(k+j+i)} \end{pmatrix}$

And then taking the global phase factor $e^{il}$.Equating $U_j = e^{il}\ P_1 \otimes P_2 \otimes P_3$ :

$e^{il} \ P_1 \otimes P_2 \otimes P_3 = \begin{pmatrix} e^{il}& 0& 0& 0& 0& 0& 0&0 \\ 0& e^{i(k+l)}& 0& 0& 0& 0& 0&0 \\ 0& 0& e^{i(l+j)}& 0& 0& 0& 0&0 \\ 0& 0& 0& e^{i(k+j+l)}& 0& 0& 0&0 \\ 0& 0& 0& 0& e^{i(i+l)}& 0& 0&0 \\ 0& 0& 0& 0& 0& e^{i(k+i+l)}& 0&0 \\ 0& 0& 0& 0& 0& 0& e^{i(i+j+l)}&0 \\ 0& 0& 0& 0& 0& 0& 0&e^{i(k+j+i+l)} \end{pmatrix} $

We obtain eight nontrivial conditions, one for each diagonal entry.

• $e^{ia} = e^{il} $ so $a = l$
• $e^{ib} = e^{i(l+k)}$ so $k = b - a$
• $e^{ic} = e^{i(l+j)}$ so $j = c - a$
• $e^{id} = e^{i(l+k+j)}$ so $d = b + c - a$
• $e^{ie} = e^{i(l+i)}$ so $i = e - a$
• $e^{if} = e^{i(l+k+i)}$ so $f = b + e - a$
• $e^{ig} = e^{i(l+i+j)}$ so $g = e + c - a$
• $e^{ih} = e^{i(l+i+j+k)}$ so $h = e + c + b - 2a$

We replace these values back into the unitary matrix $U_j = e^{il}\ P_1 \otimes P_2 \otimes P_3$

$U_j = \begin{pmatrix} e^{ia}& 0& 0& 0& 0& 0& 0&0 \\ 0& e^{ib}& 0& 0& 0& 0& 0&0 \\ 0& 0& e^{ic}& 0& 0& 0& 0&0 \\ 0& 0& 0& e^{i(b+c-a)}& 0& 0& 0&0 \\ 0& 0& 0& 0& e^{ie}& 0& 0&0 \\ 0& 0& 0& 0& 0& e^{i(b+e-a)}& 0&0 \\ 0& 0& 0& 0& 0& 0& e^{i(e+c-a)}&0 \\ 0& 0& 0& 0& 0& 0& 0&e^{i(e+c+b-2a)} \end{pmatrix}$

We are struggling in constructing controlled-controlled-phased-gate to satisfy and cancel out the 4th, 6th, 7th, 8th entries, since some body said "You have 4 degrees of freedom (3 phases from the tensor product of phase gates plus the global phase) and 8 entries of the 8×8 matrix. Hence, you need to add 4 controlled-controlled-phase gates, one for each of the extra entries that you could not fix with the tensor product of three phase gates"

For example: $e^{i(b+c-a)}$ transform into $e^d$ when element-wise with controlled-controlled-phased gate.

Based on our understanding, controlled-controlled-phased gate has a form:

$CCZ = \begin{pmatrix} 1& 0& 0& 0& 0& 0& 0&0 \\ 0& 1& 0& 0& 0& 0& 0&0 \\ 0& 0& 1& 0& 0& 0& 0&0 \\ 0& 0& 0& 1& 0& 0& 0&0 \\ 0& 0& 0& 0& 1& 0& 0&0 \\ 0& 0& 0& 0& 0& 1& 0&0 \\ 0& 0& 0& 0& 0& 0& 1&0 \\ 0& 0& 0& 0& 0& 0& 0&-1 \end{pmatrix}$

The method I mentioned above works fine with 4x4 Unitary Matrices, but when extend into 8x8 unitary matrix, I wonder:

• How can 4 controlled-controlled-phased gates can cancel out the 4,6,7,8 entries since only the 8th enty in controlled-conttrolled-phased gate changes?

• How can we construct 4 controlled-controlled-phased gate to satisfy our matrix conditions?

• Is there any method for decomposing 8x8 unitary matrices into phased-gate to implement quantum phase estimation?

Thanks for your response!

Answer 1

You need controlled-controlled-phase gates with an arbitrary phase, $$ \left(\begin{array}{ccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & e^{i\phi} \end{array}\right). $$ If you don't have this directly, you'll want to decompose it in terms of more elementrary gates in the same way that the toffoli gate can be decomposed.

Also remember that you can use bit flip gates to move the phase onto a different diagonal element to give you all the freedom you need.

Another trick is the use the two-qubit controlled-phase as well - minimise the number of three-qubit gates you need!