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

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!


$$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.