Decomposition of any 2-level matrix into single qubit and CNOT gates

Question

I saw an example which takes a 2 level matrix. Which is a $8\times8$ matrix that acts non trivially only on 2 levels of only states $|000\rangle$ and $|111\rangle$. The way they do it is by using a gray code from $|000\rangle$ to $|111\rangle$ and then shifting $|000\rangle$ to $|011\rangle$ and performing the $U$ operation only on the most left qubit conditional on the two $|11\rangle$ qubits to the right.

The thing I am trying to do, is to show that in the end this is equivalent to the original $U$ operation of $8\times 8$ matrix. How can I show their equivalency?

What I was trying to do is, to take the $U$ acting on the left hand side qubit and tensor product it with two identity matrices acting on the two other qubits. But this doesn't yeild the original $U$ ($8\times 8$ matrix). What did I get wrong here?

And how do you actually prove that the original $8\times 8$ matrix operation $U$ acting only on states $|000\rangle$ and $|011\rangle$ can be translated by a small $U$ matrix acting only on the most left qubit plus CNOT gates. How can I show it? It would be even preferred to show it by using matrix manipulation of sorts to get the original $8\times 8$ matrix. Or even some intuition would be good as well. Thanks!

Answer 1

$\newcommand{\bra}[1]{\left<#1\right|} \newcommand{\ket}[1]{\left|#1\right>}$Consider the following linear operator:

$$ U = \left[ \begin{matrix} a & 0 & 0 & 0 & 0 & 0 & 0 & c\\ 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\\ b & 0 & 0 & 0 & 0 & 0 & 0 & d\\ \end{matrix} \right] \tag{1}\label{1} $$

This is a 2-level matrix, acting non-trivially only on states $\ket{000}$ and $\ket{111}$. You are asking to show that this can be decomposed into the following 3 steps:

• Step 1: Permute the computational basis states such that $\ket{000}$ becomes $\ket{011}$ but $\ket{111}$ remains $\ket{111}$.
• Step 2: Apply a single qubit gate on the first qubit if the second and third qubits are 1.
• Step 3: Undo step 1.

To prove that this is possible, we can write the unitary operator for each step, multiply them together and see that the result is equal to $U$.

Step 1: This can be given the following representation:

$$ S = \underbrace{\ket{011}\bra{000} + \ket{000}\bra{001} + \ket{001}\bra{011}}_{\text{permutation of Gray codes}} + \\ + \underbrace{\ket{010}\bra{010} + \ket{100}\bra{100} + \ket{101}\bra{101} + \ket{110}\bra{110} + \ket{111}\bra{111}}_{\text{trivial action}}\tag{2}\label{2}$$

This is just a permutation of the computational basis states. Its main purpose is to ensure that $\ket{000}$ becomes $\ket{110}$ but $\ket{111}$ remains $\ket{111}$. There are also the transitions $\ket{001} \rightarrow \ket{000}$ and $\ket{011} \rightarrow \ket{001}$ which I think only serve the purpose of more efficient circuit design because they allow an implementation which uses only CNOT gates without any additional working qubits. This is explained in Nielsen & Chuang 10th edition on pages 192-193.

Step 2: We condition the single qubit gate's action on the second and third qubits being 1. There are only 2 states of this form: $\ket{011}$ and $\ket{111}$. Consider how a single qubit operation on the first qubit acts on these states:

$$ \ket{011} \rightarrow \left(a\ket{0} + b\ket{1}\right)\ket{11} = a\ket{011} + b\ket{111}\\ \ket{111} \rightarrow \left(c\ket{0} + d\ket{1}\right)\ket{11} = c\ket{011} + d\ket{111} \tag{3}\label{3} $$

All other states are left alone. Now we can write the full action of this single qubit gate as:

$$ \bar{U} = \underbrace{\left(a\ket{011} + b\ket{111}\right) \bra{011} + \left(c\ket{011} + d\ket{111}\right) \bra{111}}_{\text{action of single qubit gate}} + \\ + \underbrace{\ket{000}\bra{000} + \ket{001}\bra{001} + \ket{010}\bra{010} + \ket{100}\bra{100} + \ket{101}\bra{101} + \ket{110}\bra{110}}_{\text{trivial action}} \tag{4}\label{4} $$

Step 3: We just need to undo step 1., which means that we need to take the $S$ unitary's inverse, which is its Hermitian conjugate:

$$ S^{\dagger} = \underbrace{\ket{000}\bra{011} + \ket{001}\bra{000} + \ket{011}\bra{001}}_{\text{undoing permutation of Gray codes}} + \\ + \underbrace{\ket{010}\bra{010} + \ket{100}\bra{100} + \ket{101}\bra{101} + \ket{110}\bra{110} + \ket{111}\bra{111}}_{\text{trivial action}}\tag{5}\label{5}$$

We want to show that $S^{\dagger}\bar{U}S=U$. Calculating $\bar{U}S$, we get:

$$ \bar{U}S = \left(a\ket{011} + b\ket{111}\right) \bra{000} + \left(c\ket{011} + d\ket{111}\right) \bra{111} + \\ + \ket{000}\bra{001} + \ket{001}\bra{011} + \ket{010}\bra{010} + \ket{100}\bra{100} + \ket{101}\bra{101} + \ket{110}\bra{110} \tag{6}\label{6} $$

Left multiplying this by $S^{\dagger}$ yields:

$$ S^{\dagger}\bar{U}S = \underbrace{a \ket{000}\bra{000} + b\ket{111}\bra{000} + c\ket{000}\bra{111} + d\ket{111}\bra{111}}_{\text{non-trivial action}} + \\ + \underbrace{\ket{001}\bra{001} + \ket{010}\bra{010} + \ket{011}\bra{011} + \ket{100}\bra{100} + \ket{101}\bra{101} + \ket{110}\bra{110}}_{\textrm{trivial action}} \tag{7}\label{7} $$

Now compare \eqref{7} with \eqref{1}. By inspection we can see that they yield the same result for each computational basis states. In particular, $\ket{000} \rightarrow a\ket{000}+b\ket{111}$ and $\ket{111} \rightarrow c\ket{000}+d\ket{111}$. All other states are left alone. Therefore, \eqref{7} and \eqref{1} are equal.