Prerequisite Knowledge Review for Quantum Computing

Quantum computing sits at the intersection of linear algebra, quantum mechanics, and computational complexity theory, and fluency in the specialized applications of these fields to quantum information processing is non-negotiable for advancing beyond introductory material. This chapter assumes you have already mastered the core definitions and basic theorems of these three domains, and instead focuses on the nuanced ways their concepts manifest in quantum computing contexts, the common misconceptions that trip up even experienced researchers, and the edge cases that are rarely covered in standard textbooks. By the end of this chapter, you will be able to recognize and avoid the most frequent pitfalls that hinder progress in quantum algorithm design, error correction, and hardware development, and you will have consolidated your foundational knowledge through targeted, quantum-specific derivation exercises. For readers using the digital edition, interactive self-assessment quizzes and dynamic visualizations are embedded throughout to reinforce key concepts; print edition readers can refer to the included cheat sheet for quick reference to core definitions and formulas.

Linear Algebra for Quantum Computing: Beyond Standard Textbook Definitions

While linear algebra is a well-trodden field for most readers of this book, its application to quantum computing introduces subtle constraints and conventions that diverge from classical uses in signal processing, machine learning, or classical physics. We focus here on the three linear algebra constructs most critical for quantum information: Hilbert spaces, tensor products, and matrix decomposition methods, with explicit attention to quantum-specific use cases and common errors.

Hilbert Spaces: Completeness and Its Non-Negotiable Role in Quantum Information

In quantum computing, all quantum states are defined as vectors in a finite-dimensional complex Hilbert space $\mathcal{H}$, a complete inner product space equipped with the standard Hermitian inner product $\langle \phi | \psi \rangle$ for $|\phi\rangle, |\psi\rangle \in \mathcal{H}$. The completeness property of Hilbert spaces—every Cauchy sequence of vectors converges to a vector within the space—is often glossed over in introductory linear algebra courses, but it is a foundational requirement for quantum mechanics: it guarantees that the total probability of all possible measurement outcomes sums exactly to 1, a non-negotiable physical constraint.

For a single qubit, the relevant Hilbert space is $\mathbb{C}^2$, the space of 2-dimensional complex vectors. For $n$ qubits, the joint Hilbert space is the $n$-fold tensor product of $\mathbb{C}^2$ with itself, a $2^n$-dimensional space we will formalize in the next section. A common misconception among new quantum computing practitioners is that any set of linearly independent vectors can serve as a valid basis for a quantum state’s Hilbert space. This is false: a basis must span the entire Hilbert space, meaning any vector in the space can be written as a linear combination of basis vectors. For example, the set $\{|0\rangle, |+\rangle = (|0\rangle + |1\rangle)/\sqrt{2}\}$ is linearly independent, but it only spans a 2-dimensional subspace of $\mathbb{C}^2$ if we restrict to real coefficients; with complex coefficients, it actually spans the full space, but the set $\{|0\rangle, |+\rangle, |1\rangle\}$ is linearly dependent, and cannot form a basis. The critical edge case arises when working with subspaces of a larger Hilbert space, such as the logical subspace of a quantum error-correcting code: if the logical subspace is not complete (i.e., not a closed subspace of the full physical Hilbert space), measurement probabilities will not sum to 1, leading to unphysical results. We will revisit this constraint in Chapter 7 when designing stabilizer codes.

Another frequent error is conflating the Hilbert space of a quantum system with the space of its measurement outcomes. The measurement outcomes for an $n$-qubit system in the computational ($Z$) basis are the $2^n$ bitstrings of length $n$, which form an orthonormal basis for the $n$-qubit Hilbert space, but the Hilbert space itself contains all possible superpositions of these bitstrings, not just the basis states themselves.

Tensor Products: The Algebraic Backbone of Multi-Qubit Systems

The tensor product is the mathematical operation that combines the Hilbert spaces of individual quantum systems into the joint Hilbert space of the composite system. For two Hilbert spaces $\mathcal{H}_A$ and $\mathcal{H}_B$ with dimensions $d_A$ and $d_B$, the tensor product space $\mathcal{H}_A \otimes \mathcal{H}_B$ has dimension $d_A d_B$, and its elements are finite linear combinations of elementary tensors $|\psi_A\rangle \otimes |\psi_B\rangle$, where $|\psi_A\rangle \in \mathcal{H}_A$ and $|\psi_B\rangle \in \mathcal{H}_B$. For $n$ qubits, the joint Hilbert space is $(\mathbb{C}^2)^{\otimes n}$, with dimension $2^n$, a fact we will prove in the exercises at the end of this chapter.

A state $|\psi\rangle \in \mathcal{H}_A \otimes \mathcal{H}_B$ is called separable (or unentangled) if it can be written as a single elementary tensor $|\psi_A\rangle \otimes |\psi_B\rangle$. If no such decomposition exists, the state is entangled. Entanglement is a uniquely quantum phenomenon with no classical analog, and it is the primary resource for most quantum advantages in communication and computation. A common misconception is that entangled states are “more complicated” or “less physical” than separable states; in reality, almost all pure states in a bipartite Hilbert space are entangled: the set of separable states is a measure-zero subset of the full state space, as visualized in the diagram below.

```mermaid graph LR A[4-Dimensional Two-Qubit Hilbert Space] --> B[Separable States<br/>(3D Manifold, Measure Zero)] A --> C[Entangled States<br/>(Full Space Complement)] B --> D[Example: (|00⟩ + |01⟩)/√2] C --> E[Example: (|00⟩ + |11⟩)/√2] classDef space fill:#c9daf8,stroke:#333,stroke-width:2px classDef separable fill:#d5e8d4,stroke:#333,stroke-width:2px classDef entangled fill:#f8cecc,stroke:#333,stroke-width:2px class A space class B separable class C entangled class D,E fill:#fff,stroke:#333 ```

For bipartite pure states, the Schmidt decomposition—a direct application of the singular value decomposition (SVD) to the state’s coefficient matrix—provides a canonical form that makes entanglement easy to characterize. For any $|\psi\rangle \in \mathcal{H}_A \otimes \mathcal{H}_B$, we can write: $$|\psi\rangle = \sum_{i=1}^{r} s_i |u_i\rangle_A \otimes |v_i\rangle_B$$ where $s_i > 0$

are the Schmidt coefficients, $r$ is the Schmidt rank (the number of non-zero coefficients), and $\{|u_i\rangle_A\}$ and $\{|v_i\rangle_B\}$ are orthonormal sets of states in $\mathcal{H}_A$ and $\mathcal{H}_B$ respectively. The Schmidt rank is a direct measure of bipartite entanglement for pure states: a state is separable if and only if $r=1$, and maximally entangled if $r = \min(d_A, d_B)$. For the Bell state $|\Phi^+\rangle = (|00\rangle + |11\rangle)/\sqrt{2}$, the coefficient matrix in the computational basis is $\begin{pmatrix} 1/\sqrt{2} & 0 \\ 0 & 1/\sqrt{2} \end{pmatrix}$, whose singular values are both $1/\sqrt{2}$, so $r=2$, confirming it is maximally entangled. A common misconception is that the Schmidt decomposition is unique: it is unique up to degeneracy of the Schmidt coefficients. If two Schmidt coefficients are equal, any unitary rotation within the corresponding degenerate subspace yields an equally valid Schmidt decomposition. For example, the state $(|00\rangle + |01\rangle + |10\rangle + |11\rangle)/2$ has Schmidt coefficients $[1/\sqrt{2}, 1/\sqrt{2}]$, so its Schmidt bases are not unique. The entanglement entropy $S(\rho_A) = -\text{Tr}(\rho_A \log \rho_A)$, where $\rho_A = \text{Tr}_B(|\psi\rangle\langle\psi|)$