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

$newcommand{bra}[1]{left<#1right|} newcommand{ket}[1]{left|#1right>}$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(aket{0} + bket{1}right)ket{11} = aket{011} + bket{111} ket{111} rightarrow left(cket{0} + dket{1}right)ket{11} = cket{011} + dket{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(aket{011} + bket{111}right) bra{011} + left(cket{011} + dket{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(aket{011} + bket{111}right) bra{000} + left(cket{011} + dket{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} + bket{111}bra{000} + cket{000}bra{111} + dket{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 aket{000}+bket{111}$ and $ket{111} rightarrow cket{000}+dket{111}$. All other states are left alone. Therefore, eqref{7} and eqref{1} are equal.