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!