# Quantum Computing 3 -- Multiple qubits

Already with a single qubit you can perform complicated operations, because you can make arbitrary superpositions of the two basis states. However, it only becomes interesting when you have a memory register with many qubits available. Now, operations such as the CNOT gate, linking multiple qubits, are also possible. In this way, qubits can be entangled with each other, so that their states are correlated with each other and can no longer be considered separately. This entanglement provides a new way to store information and perform calculations, which is not possible with a classical computer.

Two qubit states

We consider a system of two qubits. If both qubits are measured, there can be in one of four possible states. These basis states $| 00 \rangle$, $| 01 \rangle$, $| 10 \rangle$ and $| 11 \rangle$ result mathematically as tensor product of the single basis states:

\begin{aligned} |00\rangle = |0\rangle \otimes |0\rangle &\equiv \left( \begin{array}{c} 1 \\ 0 \end{array} \right) \otimes \left( \begin{array}{c} 1 \\ 0 \end{array} \right) = \left( \begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \end{array} \right) \\ |01\rangle = |0\rangle \otimes |1\rangle &\equiv \left( \begin{array}{c} 1 \\ 0 \end{array} \right) \otimes \left( \begin{array}{c} 0 \\ 1 \end{array} \right) = \left( \begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \end{array} \right) \\ |10\rangle = |1\rangle \otimes |0\rangle &\equiv \left( \begin{array}{c} 0 \\ 1 \end{array} \right) \otimes \left( \begin{array}{c} 1 \\ 0 \end{array} \right) = \left( \begin{array}{c} 0 \\ 0 \\ 1 \\ 0 \end{array} \right) \\ |11\rangle = |1\rangle \otimes |1\rangle &\equiv \left( \begin{array}{c} 0 \\ 1 \end{array} \right) \otimes \left( \begin{array}{c} 0 \\ 1 \end{array} \right) = \left( \begin{array}{c} 0 \\ 0 \\ 0 \\ 1 \end{array} \right) \end{aligned} The general state $| \psi \rangle$ of the quantum system can be represented as a superposition of base states and thus corresponds to a four-dimensional vector: $|\psi\rangle = \alpha |00 \rangle + \beta |01\rangle + \gamma |10\rangle + \delta |11\rangle \equiv \left( \begin{array}{c} \alpha \\ \beta \\ \gamma \\ \delta \end{array} \right) \in \mathbb{C}^4$ If this state is normalized (i.e. $| \alpha | ^ 2 + | \beta | ^ 2 + | \gamma | ^ 2 + | \delta | ^ 2 = 1$), then the absolute squares $| \alpha | ^ 2, | \beta | ^ 2, | \gamma | ^ 2$ and $| \delta | ^ 2$ correspond to the probabilities to measure the respective state.

$|\psi\rangle \equiv \left( \begin{array}{c} \alpha \\ \beta \\ \gamma \\ \delta \end{array} \right) \stackrel{\text{measurement}}{\longrightarrow} |\psi'\rangle = \begin{cases} |00\rangle & \text{with probability } |\alpha|^2 \\ |01\rangle & \text{with probability } |\beta|^2 \\ |10\rangle & \text{with probability } |\gamma|^2 \\ |11\rangle & \text{with probability } |\delta|^2 \end{cases}$

Separable and entangled states

The state $| \psi \rangle$ of a two-qubit system is called separable if the two qubits do not depend on each other. In this case, the state can be written as a tensor product of individual states: $|\psi\rangle = |\psi_1\rangle \otimes |\psi_2\rangle = (\alpha_1 |0\rangle + \beta_1 |1\rangle) \otimes (\alpha_2 |0\rangle + \beta_2 |1\rangle) \equiv \left( \begin{array}{c} \alpha_1 \\ \beta_1 \end{array} \right) \otimes \left( \begin{array}{c} \alpha_2 \\ \beta_2 \end{array} \right) = \left( \begin{array}{c} \alpha_1 \alpha_2 \\ \alpha_1 \beta_2 \\ \beta_1 \alpha_2 \\ \beta_1 \beta_2 \end{array} \right)$ It is therefore possible to specify separately the states $| \psi_1 \rangle$ and $| \psi_2 \rangle$ of the first and second qubit. In particular, the basis states $|00\rangle, |01\rangle, |10\rangle$ and $|11\rangle$ are separable.

In the general case, however, the quantum state can not be separated because the qubits depend on each other. In this case there is an entangled state or an entanglement. This is indicated by the fact that the measurements of different qubits provide random outcomes, but the results are correlated with each other. A special case are maximum entangled states, in which the measurement result of the first qubit completely defines the state of the second qubit.

Bell state

Is the state $|\psi\rangle = \frac{1}{\sqrt{2}} (|00\rangle + |11\rangle)$ separable or entangled?

When measuring both qubits, the states $| 00 \rangle$ and $| 11 \rangle$ result with equal probability, so that at the end both qubits must be in the same basis state. Whether the one qubit assumes the state $| 0 \rangle$ or $| 1 \rangle$ is not set in advance and depends on the other qubit. Thus, the two qubits can no longer be considered separately and there is no decomposition in the form $| \psi \rangle = | \psi_1 \rangle \otimes | \psi_2 \rangle$. Futhermore, the state $|\psi\rangle$ is maximum entangled, since a measurement of a single qubit determines the state of the other qubit.

Two-qubit gates

The state of the two-qubit system can also be manipulated with quantum gates, which are now represented by unitary $4 \times 4$ matrices. The application of a gate $U$ corresponds to the matrix mutiplication with the four-dimensional state vector: \begin{aligned} U &\equiv \left(\begin{array}{cccc} u_{11} & u_{12} & u_{13} & u_{14} \\ u_{21} & u_{22} & u_{23} & u_{24} \\ u_{31} & u_{32} & u_{33} & u_{34} \\ u_{41} & u_{42} & u_{43} & u_{44} \end{array} \right) \in \mathbb{C}^{4\times4}, \quad |\psi\rangle \equiv \left(\begin{array}{c} \alpha \\ \beta \\ \gamma \\ \delta \end{array} \right) \in \mathbb{C}^4\\ U |\psi\rangle &\equiv \left(\begin{array}{cccc} u_{11} & u_{12} & u_{13} & u_{14} \\ u_{21} & u_{22} & u_{23} & u_{24} \\ u_{31} & u_{32} & u_{33} & u_{34} \\ u_{41} & u_{42} & u_{43} & u_{44} \end{array} \right) \cdot \left(\begin{array}{c} \alpha \\ \beta \\ \gamma \\ \delta \end{array} \right) = \left( \begin{array}{c} \alpha u_{11} + \beta u_{12} + \gamma u_{13} + \delta u_{14} \\ \alpha u_{21} + \beta u_{22} + \gamma u_{23} + \delta u_{24} \\ \alpha u_{31} + \beta u_{32} + \gamma u_{33} + \delta u_{34} \\ \alpha u_{41} + \beta u_{42} + \gamma u_{43} + \delta u_{44} \end{array} \right) \end{aligned}

Single-qubit gates

The single-qubit gates that we have come to know so far can also be transferred to the two-qubit system. Let $U$ be such a one-qubit gate then one can now define two-qubit operators $U_1 = U \otimes I$ and $U_2 = I \otimes U$, each corresponding to the application of $U$ to the first or second qubit. The new operators are defined by their effect on the base states \begin{aligned} U_1 |ij\rangle &= (U \otimes I)|ij\rangle = (U|i\rangle)\otimes|j\rangle\\ U_2 |ij\rangle &= (I \otimes U)|ij\rangle = |i \rangle \otimes (U |j\rangle) \end{aligned} where $i,j \in \{0,1\}$. Using this rule, the matrix representation of this operators can also be derived: \begin{aligned} U &= \left( \begin{array}{cc} a & b \\ c & d \end{array} \right) \in \mathbb{C}^{2 \times 2} \\ U_1 &= U \otimes I \equiv \left( \begin{array}{cccc} a & 0 & b & 0 \\ 0 & a & 0 & b \\ c & 0 & d & 0 \\ 0 & c & 0 & d \end{array} \right) \\ U_2 &= I \otimes U \equiv \left( \begin{array}{cccc} a & b & 0 & 0 \\ c & d & 0 & 0 \\ 0 & 0 & a & b \\ 0 & 0 & c & d \end{array} \right) \end{aligned}

Controlled NOT (CNOT)

Besides single-qubit operations, we also need additional operations that can link the two qubits together and create an entanglement. An example of such an operation is the Controlled-NOT gate (CNOT), which can be described by the following matrix:

$\text{CNOT} = \left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array} \right) \qquad \begin{array}{c|c} |\psi\rangle & \text{CNOT} |\psi\rangle \\ \hline |00\rangle & |00\rangle \\ |01\rangle & |01\rangle \\ |10\rangle & |11\rangle \\ |11\rangle & |10\rangle \end{array}$ The first qubit is called control bit and the second bit target bit. In the diagram, the target bit is marked with a cross and is connected with a line to the control bit. The CNOT gate applies a NOT operation (X-gate) to the target bit if and only if the control bit is in the state $| 1 \rangle$.

Using the CNOT gate and the Hadamard gate, the Bell state can be generated from an initial state $| 00 \rangle$: $\text{CNOT} \cdot (H \otimes I) \cdot |00\rangle = \text{CNOT} \cdot \frac{1}{\sqrt{2}}(|00\rangle + |10\rangle) = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$

Note by Markus Michelmann
2 years, 6 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

Thanks for the notes! I appreciate the pictures especially, clearly you put quite some work into this. Actually, I was looking into this stuff before (inspired by codeforces Q# competition), and I just wanted to share this article too for anyone looking into this stuff https://www.scottaaronson.com/democritus/lec9.html, because it offers a pretty different way of looking at it that I found complimentary and interesting

- 2 years, 6 months ago

Thanks for the encouragement. I always try to summarize the essence of the topic in these notes without going too much into detail. Of course, these notes are not a substitute for a complete lecture or textbook. But it's hard to find a textbook that will allow beginners getting in quantum computing and to write some own programs. That's why I find this article by Scott Aaronson particularly interesting and will take a closer look at it again. Thanks!

- 2 years, 6 months ago