Quantum bit (Ⅲ): From 1 to \(n\).
State space
We've seen that a qubit lives in a complex vector space of dimension 2, whose basis is given by \((\ket0, \ket1)\). Let's call this vector space \(E\). Now, how do we describe the state of 2 qubits? We introduce the tensor product of \(E\) with itself, denoted \(E\otimes E=E^{\otimes 2}\).
This is a vector space of dimension \(2\times2=4\), whose basis is: \[ \begin{alignat*}{1} (\ket0\otimes\ket0&=\ket{00}, \\ \ket0\otimes\ket1&=\ket{01}, \\ \ket1\otimes\ket0&=\ket{10},\\ \ket1\otimes\ket1&=\ket{11}) \end{alignat*} \]
Indices are often used to distinguish the space of each bit, for example, \(\ket0_A\otimes\ket0_B\). The symbol \(\otimes\) is often omitted: \(\ket0\ket0\)
We naturally extend the definition of the Hermitian inner product on \(E\) to \(E^{\otimes 2}\) in the following way: \[ \begin{alignat*}{1} (\bra{\varphi}_A\otimes\bra{\varphi'}_B)(\ket{\psi}_A\otimes\ket{\psi'}_B) &= \braket{\varphi}{\psi}\times \braket{\varphi'}{\psi'} \end{alignat*} \] This is simply the standard inner product in \(\mathbb{C}^4\).
The tensor product \(\otimes\) distributes over \(+\); If the first qubit is in state \(\ket{\psi}_A=\alpha\ket0+\beta\ket1\) and the second qubit is in state \(\ket{\psi}_B=\gamma\ket0+\nu\ket1\), then the joint state of the pair of qubits is \[ \begin{alignat*}{1} (\alpha\ket0+\beta\ket1)\otimes(\gamma\ket0+\nu\ket1) &= \alpha\gamma\ket0\otimes\ket0 + \alpha\nu\ket0\otimes\ket1 + \beta\gamma\ket1\otimes\ket0 + \beta\nu\ket1\ket1 \\ &= \alpha\gamma\ket{00} + \alpha\nu\ket{01} + \beta\gamma\ket{10} + \beta\nu\ket{11} \end{alignat*} \]
The above definitions are easily extended to describe \(n\) qubits in \(\underbrace{E\otimes E\otimes \dots\otimes E}_{n\text{ times}}=E^{\otimes n}\), whose dimension is \(2^n\) and a basis is: \[ \begin{alignat*}{1} (&\underbrace{\ket{00 \dots00}}_{n\text{ digits}}, \\ &\ket{00\dots 01}, \\ &\vdots \\ &\ket{11\dots 10}, \\ &\ket{11\dots 11}) \\ \end{alignat*} \] or, if we interpret above binary strings as binary representation of integers, \[ \begin{alignat*}{1} (&\ket{0}, \\ &\ket{1}, \\ &\vdots \\ &\ket{2^n-2}, \\ &\ket{2^n-1}) \\ \end{alignat*} \]
Entanglement
Where things get interesting is that any element of \(E^{\otimes 2}\) of norm 1, i.e. any normalized linear combination of the basis vectors, is a perfectly valid state; for example, consider: \[ \ket{\phi^+} = \frac{1}{\sqrt{2}}(\ket{00} + \ket{11}) \]
What's remarkable about this state is that it can't be factorized into a product of two states: one can't write \[ \ket{\phi^+} = \ket{\psi}_A\otimes\ket{\psi}_B \] It's a 2-qubit state that could be described as irreducible; there's no state vector to describe each one of the qubits separately in isolation from one another ( to describe the state of one qubit of the pair we need the concept of mixed state—as opposed to pure state—which we will see later on ). They are intrinsically linked. This is called entanglement, and it's a fundamental feature of the quantum world. This is what enables exponential speedup when running algorithms on a quantum computer, compared with a classical computer.
\(\ket{\phi^+}\) is one of the 4 Bell states, or EPR pairs, according to Einstein, Podolsky and Rosen who introduced them in their 1935 paper. Here's the full list: \[ \begin{alignat*}{1} \ket{\phi^+} = \frac{1}{\sqrt{2}}(\ket{00} + \ket{11}) \\ \ket{\phi^-} = \frac{1}{\sqrt{2}}(\ket{00} - \ket{11}) \\ \ket{\psi^+} = \frac{1}{\sqrt{2}}(\ket{01} + \ket{10}) \\ \ket{\psi^-} = \frac{1}{\sqrt{2}}(\ket{01} - \ket{10}) \end{alignat*} \] They form an orthonormal basis of \(E^{\otimes 2}\).
\(n\)-qubit Operators
If \(U,V\) are two unitary endomorphisms of \(E\), we can define the action of the endomorphism \(U\otimes V\) on \(E^{\otimes 2}\) by \[ U\otimes V(\ket{\psi}_A \otimes \ket{\psi}_B) = U\ket{\psi}_A\otimes V\ket{\psi}_B \] \(U\otimes V\) is unitary.
If we identify \(U\) and \(V\) with their respective matrices in the basis \((\ket0,\ket1)\), the matrix of \(U\otimes V\) is the tensor product of the 2 matrices, which is given block-wise by:
More generally, if the matrix \(U\) is square of size \(m\), the matrix tensor product is given by:
But conversely, an operator on 2 qubits is not necessarily the tensor product of 2 operators on 1 qubit; to be valid, it only needs to be unitary. For example, consider
This operator swaps qubit values. Its action cannot be described as the result of two operators being applied to each one of the qubits independently of one another.
Here are some examples of basic operators on 2 and 3 qubits. Controlled \(U\)-type operators apply the \(U\) operator to the target qubit iff the control qubit is 1.
| Nom | Circuit | Matrix |
|---|---|---|
| Controlled Not |  |
\( \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{bmatrix} \) |
| Swap |  |
\( \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix} \) |
| Controlled Z |  |
\( \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & -1 \\ \end{bmatrix} \) |
| Toffoli |  |
\( \begin{bmatrix} 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 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{bmatrix} \) |
| Fredkin (controlled swap) |  |
\( \begin{bmatrix} 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 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix} \) |