What do operations on single Qubits of Unfactorable Superpositions Do?

So suppose I have the following Quantum Circuit:

B ---- |xxxxxxx|------------------------

Which is a 2 input Controlled Gate (applying some gate of two choices to Qubit B, depending on the value of Qubit A) followed by a single Hadamard Gate acting on Qubit A.

Initially the Qubits are in states $$a_0\left| 0 \right> + a_1\left| 1 \right>$$ $$b_0\left| 0 \right> + b_1\left| 1 \right>$$ Respectively. So the combined system is in state

$$a_0 b_0 \left| 00 \right> +a_0 b_1 \left| 01 \right> + a_1 b_0 \left| 10 \right> + a_1 b_1 \left| 11 \right>$$

At the beginning.

After the application of the controlled Gate, the combined superposition can easily be in a state that CANNOT be factored into a tensor product of two states. Any superposition of the form

$$q_0 \left| 00 \right> +q_1 \left| 01 \right> + q_2 \left| 10 \right> + q_3 \left| 11 \right>$$

Where $q_0/q_1 \ne q_2/q_3$ for example couldn't be factored into a tensor product.

But now when we apply that Hadamard gate, it is applied onto a single Qubit. What is it doing then? Given that the "state" of a single qubit cannot be independently factored and considered, how does the hadamard gate now affect the state of system?

How this is different than:

Help on applying a Hadamard gate and CNOT to two single q-bits

In the linked question, we are dealing with a factorable state, that then is given a CNOT transform. That computation is obvious since the factorable state (post Hadamard) can be expressed as:

$$a_0\left| 0 \right> + a_1\left| 1 \right>$$ $$b_0\left| 0 \right> + b_1\left| 1 \right>$$

yielding superposition state:

$$a_0 b_0 \left| 00 \right> +a_0 b_1 \left| 01 \right> + a_1 b_0 \left| 10 \right> + a_1 b_1 \left| 11 \right>$$

Which can now be easily computed with the $4 \times 4$ CNOT operator.

In our question we go the other way. WE start off with teh application of a $4 \times 4$ controlled operator to generate an entangled superposition

$$q_0 \left| 00 \right> +q_1 \left| 01 \right> + q_2 \left| 10 \right> + q_3 \left| 11 \right>$$

And now am attempting to determine how the behavior of a gate acting on a SINGLE Qubit affects the whole superposition.

The link is irrelelvant here since our system is no longer factorable as a tensor product of independent superpositions.

What I'm asking can be summarized succinctly as: How can I write a single Qubit operator $O$ (given as a $2 \times 2$ matrix) as a multiQubit operator $O'$ (given as a $2^k \times 2^k$ matrix) that acts as the identity on all inputs except the first where it acts as $O$ traditionally would.

To that end, the question offers no hint of how to go about it.

Work so far

My intuition suggests given the system:

$$q_0 \left| 00 \right> +q_1 \left| 01 \right> + q_2 \left| 10 \right> + q_3 \left| 11 \right>$$

We can artificially believe that the first qubit is in the state

$$(q_0 + q_1) \left| 0 \right> + (q_2 + q_3) \left| 1 \right>$$

And that the entire superposition is in:

$$(q_0 + q_1) \frac{q_0}{q_0 + q_1}\left| 00 \right> +(q_0 + q_1) \frac{q_1}{q_0 + q_1} \left| 01 \right> + (q_2 + q_3) \frac{q_2}{q_2 + q_3} \left| 10 \right> + (q_2 + q_3) \frac{q_3}{q_2 + q_3} \left| 11 \right>$$

So when we apply the Hadamard to the Qubit we send:

$$(q_0 + q_1) \left| 0 \right> + (q_2 + q_3) \left| 1 \right>$$

To

$$\frac{q_0 + q_1+q_2 + q_3}{\sqrt{2}} \left| 0 \right> + \frac{q_0 + q_1-q_2 - q_3}{\sqrt{2}} \left| 1 \right>$$

And thus the entire system now is in:

$$\frac{q_0 + q_1+q_2 + q_3}{\sqrt{2}} \frac{q_0}{q_0 + q_1}\left| 00 \right> +\frac{q_0 + q_1+q_2 + q_3}{\sqrt{2}} \frac{q_1}{q_0 + q_1} \left| 01 \right> + \frac{q_0 + q_1-q_2 - q_3}{\sqrt{2}} \frac{q_2}{q_2 + q_3} \left| 10 \right> + \frac{q_0 + q_1-q_2 - q_3}{\sqrt{2}} \frac{q_3}{q_2 + q_3} \left| 11 \right>$$

But I'm not sure why I would rigorously believe this.

(Renormalize where necessary)

• I took another look and unmarked it as a duplicate. By the way: you could delete almost everything in the question except for the succinct summary in the part you just added, and it would probably be a much clearer. (Just keep some indication that you made an effort to find the solution yourself.) – David Z Apr 18 '16 at 9:26
• @DavidZ +1 for the fact that the question would be much more clear if most of it would be removed. – Norbert Schuch Apr 18 '16 at 12:07

Given that the "state" of a single qubit cannot be independently factored and considered, how does the hadamard gate now affect the state of system?

To apply a single-qubit operation $M$ to an n-qubit system you hit the system with $I \otimes M \otimes I \otimes ... \otimes I$. The position of $M$ within that tensor product determines which qubit you hit.

You can also use simple equivalent rules, like these:

1. Group the states by the uninvolved qubits.

$|\psi\rangle = a|00⟩ + b|01⟩ + c|10⟩ + d|11⟩$

$= \Big(a|0⟩ + c|1⟩\Big)|0⟩ + \Big(b|0⟩ + d|1⟩\Big)|1⟩$

2. Apply the operation within each group.

$H_0 |\psi\rangle = \Big(H(a|0⟩ + c|1⟩)\Big)|0⟩ + \Big(H(b|0⟩ + d|1⟩)\Big)|1⟩$

$= \Big(\frac{a+c}{\sqrt 2}|0⟩ + \frac{a-c}{\sqrt 2}|1⟩\Big)|0⟩ + \Big(\frac{b+d}{\sqrt 2}|0⟩ + \frac{b-d}{\sqrt 2}|1⟩\Big)|1⟩$

3. Ungroup

$=\frac{a+c}{\sqrt 2}|00⟩ + \frac{b+d}{\sqrt 2}|01⟩ + \frac{a-c}{\sqrt 2}|10⟩ + \frac{b-d}{\sqrt 2}|11⟩$

Sometimes it makes sense to just keep the grouping around. For example, when the system is spread across two parties you might as well keep it laid out in a grid where columns are the Alice groups and rows are the Bob groups. Gives you a kind of "matrix of amplitudes", which is convenient because Alice's operations correspond to left-multiplying that matrix and Bob's operations correspond to right-transpose-multiplying it.

• What if you want to applay a double-qubit operation M to an n-qubit system? Is there also a nice formula for that, just like for the single-qubit operation? – coolcat007 May 31 '16 at 1:44
• @coolcat007 The same idea applies: group by uninvolved qubits, operate separately on each group as if the other qubits weren't there, and ungroup. When applying an $m$-qubit operation to an $n$-qubit system, the grouping creates up to $2^{n-m}$ groups with each having up to $2^m$ amplitudes. – Craig Gidney May 31 '16 at 2:06
• Could you give me an example for the CNOT on qbit 3 and 6 in an n-qubit system? For example, when n = 8 – coolcat007 Jun 4 '16 at 15:07

How can I write a single Qubit operator $O$ (given as a $2\times 2$ matrix) as a multiQubit operator $O'$ (given as a $2^k \times 2^k$ matrix) that acts as the identity on all inputs except the first where it acts as $O$ traditionally would.

This has a very direct answer:

$$O' = O\otimes \underbrace{I_2 \otimes \cdots \otimes I_2}_{k-1\text{ factors}}$$

It's easy enough to see how you might come up with this for the two-qubit case. Let's use the basis $(\lvert 00\rangle, \lvert 01\rangle, \lvert 10\rangle, \lvert 11\rangle)$, which is handy because these basis states are not entangled; they can be factored into a state for qubit 1 and a state for qubit 2. For example: $$\lvert 00\rangle = \lvert 0\rangle_1 \otimes \lvert 0\rangle_2$$ or alternatively $$\begin{pmatrix}1 \\ 0 \\ 0 \\ 0\end{pmatrix} = \begin{pmatrix}1 \\ 0\end{pmatrix}_1 \otimes \begin{pmatrix}1 \\ 0\end{pmatrix}_2$$ The operator $O'$ should act like $$O'\lvert 00\rangle = O'\bigl(\lvert 0\rangle_1\otimes\lvert 0\rangle_2\bigr) = \bigl(O\lvert 0\rangle_1\bigr)\otimes\bigl(\lvert 0\rangle_2\bigr)$$ or \begin{align} O'\begin{pmatrix}1 \\ 0 \\ 0 \\ 0\end{pmatrix} &= \left[O\begin{pmatrix}1 \\ 0\end{pmatrix}_1\right] \otimes \begin{pmatrix}1 \\ 0\end{pmatrix}_2 \\ &= \left[\begin{pmatrix}O_{11} & O_{12} \\ O_{21} & O_{22}\end{pmatrix}\begin{pmatrix}1 \\ 0\end{pmatrix}_1\right] \otimes \begin{pmatrix}1 \\ 0\end{pmatrix}_2 \\ &= \begin{pmatrix}O_{11} \\ O_{21}\end{pmatrix}\otimes\begin{pmatrix}1 \\ 0\end{pmatrix}_2 \\ &= \begin{pmatrix}O_{11} \\ 0 \\ O_{21} \\ 0\end{pmatrix} \end{align} Going through a similar procedure for each of the other three basis states, you find \begin{align} O'\begin{pmatrix}0 \\ 1 \\ 0 \\ 0\end{pmatrix} &= \begin{pmatrix}0 \\ O_{11} \\ 0 \\ O_{21}\end{pmatrix} & O'\begin{pmatrix}0 \\ 0 \\ 1 \\ 0\end{pmatrix} &= \begin{pmatrix}O_{12} \\ 0 \\ O_{22} \\ 0\end{pmatrix} & O'\begin{pmatrix}0 \\ 0 \\ 0 \\ 1\end{pmatrix} &= \begin{pmatrix}0 \\ O_{12} \\ 0 \\ O_{22}\end{pmatrix} \end{align} Putting these four columns together, you get the full matrix expression for $O'$: $$O' = \begin{pmatrix}O_{11} & 0 & O_{12} & 0 \\ 0 & O_{11} & 0 & O_{12} \\ O_{21} & 0 & O_{22} & 0 \\ 0 & O_{21} & 0 & O_{22}\end{pmatrix}$$ (check that this matrix reproduces the results derived above). This is, of course, just the tensor product of $O$ with the $2\times 2$ identity matrix, $O\otimes I_2$.

You could do the same calculation for three gates, or more, but it becomes increasingly tedious.

• This gave me enough of a hint to derive the correct formulation. I did the check and the operator you suggested instead applies a Hadamard transform to the second Qubit and not the first. If you replicate @Craig Gidney's procedure you end up with the matrix $$\frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1 \end{pmatrix}$$ – frogeyedpeas Apr 19 '16 at 2:54
• Which is the correct $O \otimes I_2$ as you suggested – frogeyedpeas Apr 19 '16 at 2:54
• @frogeyedpeas ah, I mixed up the definition of the tensor product. I've fixed it now. – David Z Apr 19 '16 at 9:27
• @DavidZ How does this work for a 2-qubit operator (Like CNOT) on for example qubit 2 and 4 in a 5-qubit system? Can you still use the tensor product or do you have to use different methods to perform such an operation? So a more general question: in an n-qubit system, say you have a transform involving m qubits that are not necessarily in order, how would you perform this? Do you need to use bubblesort using swap functions to get the qubits in the right order? – coolcat007 Jun 6 '16 at 21:50
• @coolcat007 You can still use tensor products, you might just have to write them a little differently. It's possible that the easiest way to actually figure out the matrix elements is to reorder your qubit basis, compute the tensor product, and undo the reordering. But you can do this all in the math; you don't have to implement a sorting algorithm in the quantum computer. Remember, the labeling of the qubits is arbitrary, assuming they're all mutually connected. – David Z Jun 6 '16 at 23:17