The Tensor Product
Roll two dice and count the outcomes: not 6 + 6 = 12, but
6 \times 6 = 36, because every face of the first die can pair with every
face of the second. Whenever two systems are truly independent — each free to be in
any of its own states, in every combination — the number of joint possibilities multiplies.
The tensor product is the linear-algebra operation that captures exactly this, and
it is the reason a handful of qubits can hold an astronomical amount of state.
Combining an m-dimensional space V with an
n-dimensional space W by tensor product gives a
space whose dimension is the product:
\dim(V \otimes W) = (\dim V)(\dim W).
Its basis is
every pairing e_i \otimes f_j of a basis vector of
V with one of W.
The four two-qubit basis states
Take two qubits. The first has basis \{|0\rangle, |1\rangle\}, and so does
the second. Pair them every possible way — first choice down the side, second along the top — and
you get 2 \times 2 = 4 combined basis states, written by just
concatenating the labels: |0\rangle \otimes |1\rangle = |01\rangle.
Computing it: the Kronecker product
On coordinates, the tensor product is carried out by the Kronecker product:
multiply every entry of the first vector by the whole of the second, and stack the results.
\begin{bmatrix} a \\ b \end{bmatrix} \otimes \begin{bmatrix} c \\ d \end{bmatrix} = \begin{bmatrix} a\begin{bmatrix} c \\ d \end{bmatrix} \\[4pt] b\begin{bmatrix} c \\ d \end{bmatrix} \end{bmatrix} = \begin{bmatrix} ac \\ ad \\ bc \\ bd \end{bmatrix}.
Two 2-vectors give a 4-vector — 2 \times 2 = 4, as promised. As a check,
|0\rangle \otimes |1\rangle is
\begin{bmatrix} 1 \\ 0 \end{bmatrix} \otimes \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \end{bmatrix} = |01\rangle,
the second of the four basis vectors — precisely the "01" cell in the grid above. The same rule
builds the Kronecker product of matrices: replace each entry A_{ij} by the
block A_{ij} B. It plays nicely with
matrix multiplication
through the mixed-product rule (A \otimes B)(C \otimes D) = (AC) \otimes (BD).
- combines independent systems; dimensions multiply:
\dim(V\otimes W) = \dim V \cdot \dim W;
- its basis is all products e_i \otimes f_j of the two bases;
- on coordinates it is the Kronecker product (each entry of the first scales a
whole copy of the second);
- a d-fold product of a 2-dimensional space
has dimension 2^d — exponential in the number of factors.
One qubit lives in a 2-dimensional space; tensoring
n of them gives dimension
\underbrace{2\times 2\times\cdots\times 2}_{n} = 2^{n}. That exponential is
staggering. At n = 300, the state space has
2^{300} \approx 10^{90} dimensions — more than the number of atoms in the
observable universe (about 10^{80}). No classical computer could even
store the list of amplitudes for 300 qubits, yet 300 physical qubits hold them effortlessly.
Simulating that growth on ordinary hardware is exactly the wall that quantum computers are built to
climb over.
Two traps. First, order matters and it is not ordinary multiplication:
v \otimes w and w \otimes v are generally
different vectors, and dimensions multiply, not add
(\mathbb{C}^2 \otimes \mathbb{C}^2 is 4-dimensional,
not 4 vectors of length 2). Second — and this is
the deep one — most vectors in V \otimes W cannot be
written as a single product v \otimes w at all. Those inseparable vectors,
like \tfrac{1}{\sqrt2}(|00\rangle + |11\rangle), are exactly the
entangled states — and they have no classical analogue whatsoever.