5
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.