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

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?

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.