Chapter 1: Mathematical Foundations for Quantum Computing

Chapter Guide: The underlying language of quantum computing is linear algebra and complex analysis. This chapter selects the three most essential and irreplaceable mathematical toolkits — complex numbers, vector spaces, and linear operators — to lay the mathematical groundwork for the rigorous formulation of quantum states, quantum gates, and quantum measurement. Readers do not need any background in quantum mechanics; familiarity with complex numbers from high school mathematics and basic college-level linear algebra will suffice. Our expository strategy proceeds from the concrete to the abstract, from the familiar to the novel: we first review complex numbers and render them geometric, then naturally extend real vector spaces to the complex field, and finally introduce the linear operators that describe quantum evolution.

---

1.1 Complex Numbers & Euler’s Formula

1.1.1 Basic Construction of Complex Numbers

We begin with the simplest algebraic observation: the equation $x^2 + 1 = 0$ has no solution in the real numbers $\mathbb{R}$. No matter what real number $x$ we choose, $x^2$ is always non-negative, so $x^2 + 1$ is always greater than zero. To remedy this “defect,” mathematicians introduced an entirely new number, called the imaginary unit, denoted $i$, with the defining property

$$i^2 = -1$$

This is not “derived” from the real numbers but is a creative definition. Once we accept the existence of $i$, we can construct a complex number:

$$z = a + bi, \quad a, b \in \mathbb{R}$$

where $a$ is called the real part, denoted $\text{Re}(z) = a$; $b$ is called the imaginary part, denoted $\text{Im}(z) = b$. When $b = 0$, $z$ reduces to a real number; when $a = 0$ and $b \neq 0$, $z$ is purely imaginary. The set of all complex numbers is denoted $\mathbb{C}$.

Every complex number $z = a + bi$ can be placed in one-to-one correspondence with a point $(a, b)$ on the complex plane: the horizontal axis represents the real part, and the vertical axis represents the imaginary part. For example, the complex number $z = 3 + 2i$ corresponds to the point $(3, 2)$ on the complex plane, located in the first quadrant. The complex number $z = -1 - 2i$ corresponds to the point $(-1, -2)$, located in the third quadrant. This method of visualizing algebraic objects as geometric points is key to understanding the essence of complex number operations.

1.1.2 Arithmetic Operations and Conjugation

Addition and subtraction of complex numbers are performed component-wise on the real and imaginary parts, much like vector component operations:

$$(a + bi) + (c + di) = (a + c) + (b + d)i$$

Geometrically, this corresponds to the parallelogram law for two vectors on the complex plane. For instance, $(1 + i) + (2 - i) = 3$; geometrically, this means adding the position vectors of points $(1, 1)$ and $(2, -1)$ to obtain the point $(3, 0)$.

Multiplication makes use of $i^2 = -1$ and expands as follows:

$$(a + bi)(c + di) = ac + adi + bci + bdi^2 = (ac - bd) + (ad + bc)i$$

This formula may appear somewhat cumbersome at first glance, but it becomes very intuitive when expressed in polar coordinates.

Division is the operation among complex arithmetic that requires the most technique. To compute $\frac{a + bi}{c + di}$, we need to introduce the complex conjugate. Given $z = a + bi$, its conjugate is defined as

$$z^* = \overline{z} = a - bi$$

The geometric meaning of the conjugate is a mirror reflection of the complex number across the real axis: the real part remains unchanged, and the imaginary part flips sign. A crucially important property is $zz^* = (a + bi)(a - bi) = a^2 + b^2$, which is always a non-negative real number, equal to $|z|^2$.

Using this property, complex division can be accomplished by “rationalizing the denominator”:

$$\frac{a + bi}{c + di} = \frac{(a + bi)(c - di)}{(c + di)(c - di)} = \frac{(ac + bd) + (bc - ad)i}{c^2 + d^2}$$

The denominator becomes the real number $c^2 + d^2$, and the entire expression splits cleanly into real and imaginary parts.

Example 1.1: Compute $\displaystyle\frac{1 + 2i}{3 - i}$.

Multiply numerator and denominator by the denominator’s conjugate $3 + i$:

$$\frac{(1 + 2i)(3 + i)}{(3 - i)(3 + i)} = \frac{3 + i + 6i + 2i^2}{9 + 1} = \frac{3 + 7i - 2}{10} = \frac{1 + 7i}{10} = 0.1 + 0.7i$$

Thus, $\frac{1 + 2i}{3 - i} = 0.1 + 0.7i$. As a check, we can multiply $0.1 + 0.7i$ by $3 - i$: $(0.1 + 0.7i)(3 - i) = 0.3 - 0.1i + 2.1i - 0.7i^2 = 0.3 + 2.0i + 0.7 = 1 + 2i$, which matches the original numerator.

1.1.3 Polar Representation and Modulus

Beyond the rectangular form $z = a + bi$, complex numbers can also be represented in polar coordinates. This representation reveals the geometric essence of complex multiplication and division. On the complex plane, the distance from the point $(a, b)$ to the origin is called the modulus or absolute value:

$$r = |z| = \sqrt{a^2 + b^2}$$

The angle that the point makes with the positive real axis is called the argument:

$$\theta = \arg(z) = \arctan\left(\frac{b}{a}\right)$$

(When $a < 0$, one must adjust by $\pm\pi$ according to the quadrant to ensure the angle falls in the correct half-plane.) A complex number can then be written as

$$z = r(\cos\theta + i\sin\theta)$$

This is the trigonometric form of a complex number. For example, $z = 1 + i$ has modulus $\sqrt{2}$ and argument $\pi/4$ (i.e., $45^\circ$), so $1 + i = \sqrt{2}(\cos\pi/4 + i\sin\pi/4)$.

1.1.4 Derivation of Euler’s Formula

Euler’s formula is the bridge connecting the exponential function to trigonometric functions, and one of the most astonishing identities in all of mathematics:

$$e^{i\theta} = \cos\theta + i\sin\theta$$

We shall derive this remarkable identity rigorously from Taylor series, which is one of the core derivations readers are expected to master.

First, recall the Taylor expansions of three functions about $x = 0$ (convergent for all real $x$):

$$\begin{aligned} e^x &= 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!} + \cdots \\ \cos x &= 1 - \frac{x^2}{2!} + \frac{x^4}{4!} - \frac{x^6}{6!} + \cdots \\ \sin x &= x - \frac{x^3}{3!} + \frac{x^5}{5!} - \frac{x^7}{7!} + \cdots \end{aligned}$$

Now substitute $i\theta$ for $x$ in $e^x$. This is mathematically legitimate because the power series of the exponential function converges on the entire complex plane (a property of entire functions):

$$\begin{aligned} e^{i\theta} &= 1 + (i\theta) + \frac{(i\theta)^2}{2!} + \frac{(i\theta)^3}{3!} + \frac{(i\theta)^4}{4!} + \frac{(i\theta)^5}{5!} + \cdots \\ &= 1 + i\theta + \frac{i^2\theta^2}{2!} + \frac{i^3\theta^3}{3!} + \frac{i^4\theta^4}{4!} + \frac{i^5\theta^5}{5!} + \cdots \end{aligned}$$

Using the cyclic powers of $i$: $i^2 = -1$, $i^3 = -i$, $i^4 = 1$, $i^5 = i$, and so on:

$$e^{i\theta} = 1 + i\theta - \frac{\theta^2}{2!} - i\frac{\theta^3}{3!} + \frac{\theta^4}{4!} + i\frac{\theta^5}{5!} - \cdots$$

Now separate the real part (terms without $i$) and the imaginary part (terms with $i$):

$$e^{i\theta} = \underbrace{\left(1 - \frac{\theta^2}{2!} + \frac{\theta^4}{4!} - \frac{\theta^6}{6!} + \cdots\right)}_{= \cos\theta} + i\underbrace{\left(\theta - \frac{\theta^3}{3!} + \frac{\theta^5}{5!} - \frac{\theta^7}{7!} + \cdots\right)}_{= \sin\theta}$$

The series in parentheses are precisely the Taylor expansions of $\cos\theta$ and $\sin\theta$, respectively. We thus obtain Euler’s formula:

$$e^{i\theta} = \cos\theta + i\sin\theta$$

Combining this with the polar representation, any complex number can be written in the compact exponential form:

$$z = r e^{i\theta}$$

Euler’s identity is the special case when $\theta = \pi$:

$$e^{i\pi} + 1 = 0$$

It ties together five of the most important constants in mathematics — $0$, $1$, $e$, $i$, $\pi$ — in a breathtakingly concise relationship, celebrated as “the most beautiful formula in mathematics.” The beauty of this formula lies not only in its simplicity but also in how it reveals the profound inner connection among exponential functions, trigonometric functions, and imaginary numbers.

1.1.5 Geometric Meaning of Complex Multiplication: Rotation and Scaling

The true power of Euler’s formula lies in revealing the geometric essence of complex multiplication, which is one of the reasons complex numbers appear so frequently in quantum computing.

Let $z_1 = r_1 e^{i\theta_1}$ and $z_2 = r_2 e^{i\theta_2}$. Their product is

$$z_1 \cdot z_2 = r_1 r_2 \, e^{i(\theta_1 + \theta_2)}$$

This equation tells us: when multiplying two complex numbers, their moduli multiply ($r_1 r_2$) and their arguments add ($\theta_1 + \theta_2$). This geometric rule is remarkably elegant.

In particular, multiplying by $e^{i\theta}$ has the effect of: preserving the modulus while rotating counterclockwise by an angle $\theta$. For example:

• $e^{i\pi/2} = i$: multiplying by $i$ is equivalent to a $90^\circ$ counterclockwise rotation
• $e^{i\pi} = -1$: multiplying by $-1$ is equivalent to a $180^\circ$ rotation
• $e^{i\pi/4} = \frac{\sqrt{2}}{2}(1 + i)$: a $45^\circ$ rotation
• $e^{i\cdot 0} = 1$: a $0^\circ$ rotation, i.e., the identity operation

If $|z| \neq 1$, scaling accompanies the rotation. For instance, $2e^{i\pi/3}$ rotates the target complex number by $60^\circ$ and magnifies it by a factor of 2. If $|z| < 1$, the effect is a shrinking.

Geometric interpretation example: Multiply $z = 1 + i$ by $w = \sqrt{2}e^{i\pi/4}$.

First, $z = 1 + i$ has modulus $\sqrt{1^2 + 1^2} = \sqrt{2}$ and argument $\arctan(1) = \pi/4$. Meanwhile, $w = \sqrt{2}e^{i\pi/4}$ has modulus $\sqrt{2}$ and argument $\pi/4$. By the multiplication rule, the product has modulus $\sqrt{2} \cdot \sqrt{2} = 2$ and argument $\pi/4 + \pi/4 = \pi/2$. Hence

$$z \cdot w = 2e^{i\pi/2} = 2i$$

Direct algebraic verification: $(1 + i)(1 + i) = 1 + 2i + i^2 = 1 + 2i - 1 = 2i$, which agrees. This example clearly demonstrates the dual effect of complex multiplication: rotation (from $\pi/4$ to $\pi/2$) and scaling (from $\sqrt{2}$ to $2$).

1.1.6 Why Quantum Mechanics Needs Complex Numbers

In classical physics, almost all observable quantities — position, momentum, energy, temperature — can be described by real numbers. But quantum mechanics is fundamentally different: the evolution of a quantum state involves phase, and phase must be represented by complex numbers. The wave function $\psi(x, t)$ of a quantum state is itself a complex-valued function.

Complex phases play a central role in quantum interference. When two probability amplitudes are added, their relative phase determines whether the resulting probability is enhanced (constructive interference) or canceled (destructive interference). Without complex numbers, this wave-like behavior cannot be described. While classical wave interference can be described with real sine functions, the “probability amplitude” in quantum mechanics is a more fundamental concept that must be complex.

Rotation operations on the complex plane also correspond directly to the transformations that quantum gates apply to qubits — for example, the phase gate applies a rotation to a particular basis state on the complex plane. The $Y$ and $Z$ Pauli matrices are, in essence, rotation operations on the complex plane.

Moreover, the fundamental equation of quantum mechanics — the Schrödinger equation — explicitly contains the imaginary unit $i$:

$$i\hbar\frac{\partial\psi}{\partial t} = \hat{H}\psi$$

The left-hand side of the equation explicitly features $i$, which means that even if the initial condition is real-valued, time evolution will naturally generate an imaginary part. Complex numbers are not a “decoration” of quantum mechanics but an inseparable part of its structure.

Summary:

• The complex number $z = a + bi$ extends the real number field; $i^2 = -1$ is its defining cornerstone; the set of all complex numbers is denoted $\mathbb{C}$
• Among the four arithmetic operations, addition and subtraction proceed component-wise, multiplication requires expanding $i^2 = -1$, and division relies on the complex conjugate $z^* = a - bi$
• Polar form $z = r(\cos\theta + i\sin\theta)$ is the geometric language for describing complex numbers, where $r = |z|$ is the modulus and $\theta = \arg(z)$ is the argument
• Euler’s formula $e^{i\theta} = \cos\theta + i\sin\theta$ can be rigorously derived from the Taylor expansions of the exponential, cosine, and sine functions
• Complex multiplication = moduli multiply + arguments add, i.e., a composition of rotation and scaling; multiplying by $e^{i\theta}$ is equivalent to a rotation by angle $\theta$
• Quantum mechanics fundamentally requires complex numbers to describe indispensable phase information and the interference behavior of probability amplitudes

Connection to Quantum Computing: The state of a qubit is a unit vector in a complex vector space. The general state of a single qubit is $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$, where $\alpha, \beta \in \mathbb{C}$ and $|\alpha|^2 + |\beta|^2 = 1$. The relative phase between the complex numbers $\alpha$ and $\beta$ directly determines the probability distribution of measurement outcomes and is the mathematical root of quantum parallelism and quantum interference. Euler’s formula provides the most compact exponential form for describing the rotation operations of quantum gates; for example, the single-qubit phase gate $R_z(\theta) = e^{-i\theta Z/2}$ explicitly uses the complex exponential.

---

1.2 Vector Spaces & Hilbert Spaces

1.2.1 From $\mathbb{R}^n$ to $\mathbb{C}^n$: Generalizing Vector Spaces

In elementary linear algebra, we are familiar with the real vector space $\mathbb{R}^n$, where vectors such as $\mathbf{v} = (v_1, v_2, \ldots, v_n)^T$ consist of $n$ real components and support addition and scalar multiplication. For example, the vector $(1, 2, 3)^T$ in $\mathbb{R}^3$ can represent a point in three-dimensional space or a directed line segment from the origin.

In quantum computing, the components of vectors must be complex numbers. This is not an arbitrary choice but a necessity, because the amplitudes (probability amplitudes) of quantum states are inherently complex, as discussed in the previous section. This brings us to the complex vector space $\mathbb{C}^n$: an $n$-dimensional complex vector is an ordered $n$-tuple of complex numbers

$$\mathbf{v} = \begin{pmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{pmatrix}, \quad v_k \in \mathbb{C}$$

Vector addition proceeds component-wise:

$$\begin{pmatrix} v_1 \\ v_2 \end{pmatrix} + \begin{pmatrix} w_1 \\ w_2 \end{pmatrix} = \begin{pmatrix} v_1 + w_1 \\ v_2 + w_2 \end{pmatrix}$$

Scalar multiplication allows scaling by complex numbers:

$$c \cdot \begin{pmatrix} v_1 \\ v_2 \end{pmatrix} = \begin{pmatrix} c v_1 \\ c v_2 \end{pmatrix}, \quad c \in \mathbb{C}$$

Note that the scalar $c$ here can be any complex number, including purely imaginary numbers like $2i$ or general complex numbers like $1 + i$. For example:

$$(1 + i)\begin{pmatrix} 1 \\ i \end{pmatrix} = \begin{pmatrix} 1 + i \\ i + i^2 \end{pmatrix} = \begin{pmatrix} 1 + i \\ -1 + i \end{pmatrix}$$

A rigorous definition of a vector space must satisfy eight axioms: commutativity of addition, associativity of addition, existence of a zero vector, existence of additive inverses, associativity of scalar multiplication, distributivity of scalar multiplication over vector addition, distributivity of scalar multiplication over scalar addition, and the identity element $1\mathbf{v} = \mathbf{v}$. These axioms ensure that vector operations behave in accordance with our geometric intuition. In quantum computing, we almost always work in $\mathbb{C}^n$, so these axioms are automatically satisfied.

1.2.2 Linear Independence, Basis, and Dimension

A set of vectors $\{\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_m\}$ is called linearly independent if the equation

$$c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \cdots + c_m\mathbf{v}_m = \mathbf{0}$$

has only the trivial solution $c_1 = c_2 = \cdots = c_m = 0$. Intuitively, no vector can be “expressed” in terms of the others; each vector contributes a “new direction.”

If a set of linearly independent vectors can “span” (i.e., represent through linear combinations) the entire space, that set is called a basis for the space. The number of vectors in a basis is called the dimension of the space. The dimension of a space is unique and does not depend on the choice of basis.

The standard basis of $\mathbb{C}^n$ consists of $n$ vectors:

$$\mathbf{e}_1 = \begin{pmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix}, \quad \mathbf{e}_2 = \begin{pmatrix} 0 \\ 1 \\ \vdots \\ 0 \end{pmatrix}, \quad \ldots, \quad \mathbf{e}_n = \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 1 \end{pmatrix}$$

Any $\mathbf{v} \in \mathbb{C}^n$ can be uniquely expressed as

$$\mathbf{v} = v_1\mathbf{e}_1 + v_2\mathbf{e}_2 + \cdots + v_n\mathbf{e}_n$$

where the coefficient $v_k$ is precisely the $k$-th component of the vector. This representation is unique — given a basis, each vector has one and only one way of being written as a linear combination of the basis vectors.

1.2.3 Inner Products and Bra-ket Notation

To discuss the “length” of a vector and the “angle” between vectors, we need the inner product. In $\mathbb{R}^n$, the inner product is the dot product: $\mathbf{u} \cdot \mathbf{v} = u_1 v_1 + u_2 v_2 + \cdots + u_n v_n$. In $\mathbb{C}^n$, however, the definition requires adjustment — we must take the conjugate of one vector, otherwise $\langle\mathbf{v}, \mathbf{v}\rangle$ might not be a non-negative real number (for instance, if $\mathbf{v} = (1, i)^T$, a naive dot product gives $1 \cdot 1 + i \cdot i = 0$, which clearly cannot serve as a squared length).

Dirac notation, also known as bra-ket notation, is a notation system tailor-made for the inner product in quantum mechanics. It was invented by physicist Paul Dirac in 1939 and has become the standard language of quantum computing and quantum information.

We begin with the familiar column vector and progressively introduce this notation:

• Ket: $|\psi\rangle$ denotes a column vector. The symbol "$\rangle$" resembles half of an angle bracket, suggesting a “closed” column vector.
• Bra: $\langle\phi|$ denotes a row vector, the “conjugate transpose” of some ket.

The concrete correspondence is as follows. If

$$|\psi\rangle = \begin{pmatrix} \alpha_1 \\ \alpha_2 \\ \vdots \\ \alpha_n \end{pmatrix}$$

then the corresponding bra is

$$\langle\psi| = \begin{pmatrix} \alpha_1^* & \alpha_2^* & \cdots & \alpha_n^* \end{pmatrix}$$

That is, going from ket to bra requires two operations: transpose (column to row) and complex conjugation (star each component).

The inner product $\langle\phi|\psi\rangle$ is defined as the matrix product of a bra and a ket:

$$\langle\phi|\psi\rangle = \begin{pmatrix} \beta_1^* & \beta_2^* & \cdots & \beta_n^* \end{pmatrix} \begin{pmatrix} \alpha_1 \\ \alpha_2 \\ \vdots \\ \alpha_n \end{pmatrix} = \sum_{k=1}^n \beta_k^* \alpha_k$$

Note that it is the components of the first vector (the bra) that receive the conjugation. This guarantees that $\langle\psi|\psi\rangle = \sum_k |\alpha_k|^2$ is a non-negative real number, allowing us to define length.

Example 1.2: Let $|\psi\rangle = \begin{pmatrix} 1 \\ i \end{pmatrix}$ and $|\phi\rangle = \begin{pmatrix} 2 \\ 1+i \end{pmatrix}$. Compute $\langle\phi|\psi\rangle$.

First, write the bra:

$\langle\phi| = \begin{pmatrix} 2^* & (1+i)^* \end{pmatrix} = \begin{pmatrix} 2 & 1-i \end{pmatrix}$

Then perform the matrix multiplication:

$\langle\phi|\psi\rangle = 2 \cdot 1 + (1-i) \cdot i = 2 + i - i^2 = 2 + i + 1 = 3 + i$

The result is a complex number. If we swap the order to compute $\langle\psi|\phi\rangle$:

$\langle\psi| = \begin{pmatrix} 1 & -i \end{pmatrix}, \quad \langle\psi|\phi\rangle = 1 \cdot 2 + (-i)(1+i) = 2 - i - i^2 = 3 - i$

Note that $\langle\psi|\phi\rangle = \langle\phi|\psi\rangle^*$, which is a general property of the inner product.

From the inner product we can define the norm, i.e., the length of a vector:

$$\|\psi\| = \sqrt{\langle\psi|\psi\rangle} = \sqrt{\sum_k |\alpha_k|^2}$$

This is formally identical to the Euclidean length formula in $\mathbb{R}^n$, except that each component is now squared in modulus. We can also define the angle between two non-zero vectors:

$$\cos\theta = \frac{|\langle\phi|\psi\rangle|}{\|\phi\| \cdot \|\psi\|}$$

When $\langle\phi|\psi\rangle = 0$, the two vectors are said to be orthogonal. Orthogonality means the two vectors are geometrically “perpendicular,” with no overlapping “component.”

1.2.4 Hilbert Space: A Complete Inner Product Space

A Hilbert space is the stage on which quantum mechanics unfolds. Its rigorous definition is a “complete inner product space,” where “completeness” is a concept from analysis meaning that the space has no “holes” — the limit of any Cauchy sequence still lies within the space.

For the purposes of quantum computing, this abstract concept admits an eminently practical simplification:

A finite-dimensional Hilbert space is simply $\mathbb{C}^n$ equipped with the standard inner product.

This is because finite-dimensional spaces are automatically complete. The quantum systems covered in this book (finite numbers of qubits) all operate in finite-dimensional spaces, so the reader may intuitively regard a Hilbert space as “a complex vector space with an inner product, in which one can discuss length and angle.”

An orthonormal basis is a set of basis vectors that are pairwise orthogonal and each have norm 1. The standard basis $\{\mathbf{e}_1, \ldots, \mathbf{e}_n\}$ of $\mathbb{C}^n$ is an orthonormal basis because

$$\langle\mathbf{e}_j|\mathbf{e}_k\rangle = \delta_{jk} = \begin{cases} 1 & j = k \\ 0 & j \neq k \end{cases}$$

where $\delta_{jk}$ is the Kronecker delta. The advantage of an orthonormal basis is that the components of any vector can be read off directly through inner products: $v_k = \langle\mathbf{e}_k|\mathbf{v}\rangle$.

1.2.5 $\mathbb{C}^2$: The Simplest Qubit Space

The most fundamental unit of information in quantum computing is the quantum bit or qubit, whose state space is precisely the two-dimensional complex vector space $\mathbb{C}^2$. This stands in sharp contrast to the classical bit: the state space of a classical bit consists of only two discrete points $\{0, 1\}$, whereas the state space of a qubit is a continuous two-dimensional complex vector space.

The standard orthonormal basis of $\mathbb{C}^2$ is customarily denoted

$$|0\rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \quad |1\rangle = \begin{pmatrix} 0 \\ 1 \end{pmatrix}$$

This uses the same symbols $0$ and $1$ as classical bits, but the meaning is entirely different: a classical bit can only take the value $0$ or $1$, whereas a qubit can exist in a superposition of both:

$$|\psi\rangle = \alpha|0\rangle + \beta|1\rangle = \begin{pmatrix} \alpha \\ \beta \end{pmatrix}, \quad \alpha, \beta \in \mathbb{C}$$

Because a global phase (an overall factor of $e^{i\phi}$) does not affect physical observations (since probabilities depend only on squared moduli), we customarily require states to be normalized:

$$\langle\psi|\psi\rangle = |\alpha|^2 + |\beta|^2 = 1$$

This means that a quantum state is a unit vector in Hilbert space, lying on the “unit sphere.”

Example 1.3: Verify that $|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) = \begin{pmatrix} 1/\sqrt{2} \\ 1/\sqrt{2} \end{pmatrix}$ is normalized.

$\langle+|+\rangle = \left(\frac{1}{\sqrt{2}}\right)^2 + \left(\frac{1}{\sqrt{2}}\right)^2 = \frac{1}{2} + \frac{1}{2} = 1$

Verification passed. $|+\rangle$ is an important quantum state representing an equal-probability superposition of $|0\rangle$ and $|1\rangle$.

Another important state is $|-\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$, which is orthogonal to $|+\rangle$: $\langle+|-\rangle = \frac{1}{2}(1 - 1) = 0$. The set $\{|+\rangle, |-\rangle\}$ forms another orthonormal basis for $\mathbb{C}^2$.

Geometrically, the state space of a qubit corresponds to the three-dimensional unit sphere — the Bloch sphere. The north pole of the Bloch sphere is $|0\rangle$, the south pole is $|1\rangle$, and the points on the equator correspond to various equal-weight superposition states. This geometric representation will be discussed in detail in later chapters.

Summary:

• Quantum computing uses the complex vector space $\mathbb{C}^n$, the natural complex generalization of the real vector space $\mathbb{R}^n$, where scalar multiplication can involve any complex number
• The core structures of a vector space: addition, scalar multiplication, linear independence, basis, dimension; the standard basis of $\mathbb{C}^n$ has $n$ vectors
• Bra-ket notation $|\psi\rangle$ / $\langle\phi|$ is the standard language of quantum mechanics; the inner product $\langle\phi|\psi\rangle = \sum_k \beta_k^*\alpha_k$ defines length and angle
• Hilbert space = complete inner product space; in the finite-dimensional case it is simply $\mathbb{C}^n$ with the standard inner product
• $\mathbb{C}^2$, with $\{|0\rangle, |1\rangle\}$ as its standard basis, is the state space of a single qubit; a qubit can be in a superposition state but must be normalized

Connection to Quantum Computing: Quantum states are normalized vectors in a Hilbert space. The joint state space of $n$ qubits is the $2^n$-dimensional Hilbert space $\mathbb{C}^{2^n}$, which is the mathematical root of the exponential parallelism of quantum computing — $n$ classical bits can represent only one of $2^n$ states, whereas $n$ qubits can simultaneously be in a superposition of all $2^n$ basis states. Bra-ket notation makes the expression of quantum states, inner products, and operators extremely compact and is an essential tool for reading the quantum computing literature. For example, the famous Bell state $\frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$ is precisely a normalized vector in $\mathbb{C}^4$.

---

1.3 Linear Operators & Matrix Representation

1.3.1 Definition of a Linear Operator

On a vector space, we are interested in maps that preserve the linear structure. Such maps are called linear operators. Rigorously, a linear operator $T$ is a map satisfying the following two conditions:

$$T(\alpha|v\rangle + \beta|w\rangle) = \alpha T|v\rangle + \beta T|w\rangle$$

for all vectors $|v\rangle, |w\rangle$ and all scalars $\alpha, \beta$. In other words, $T$ “respects” the structure of addition and scalar multiplication — applying a linear combination and then mapping is the same as mapping first and then taking the same linear combination. This property guarantees that $T$ does not destroy the algebraic structure of the vector space.

Example 1.4: Verify that $T\begin{pmatrix}x \\ y\end{pmatrix} = \begin{pmatrix}2x \\ x+y\end{pmatrix}$ is linear.

Let $\mathbf{v} = (x_1, y_1)^T$ and $\mathbf{w} = (x_2, y_2)^T$:

$T(\alpha\mathbf{v} + \beta\mathbf{w}) = T\begin{pmatrix}\alpha x_1 + \beta x_2 \\ \alpha y_1 + \beta y_2\end{pmatrix} = \begin{pmatrix}2(\alpha x_1 + \beta x_2) \\ (\alpha x_1 + \beta x_2) + (\alpha y_1 + \beta y_2)\end{pmatrix}$

Expand and regroup:

$= \begin{pmatrix}2\alpha x_1 + 2\beta x_2 \\ \alpha(x_1 + y_1) + \beta(x_2 + y_2)\end{pmatrix} = \alpha\begin{pmatrix}2x_1 \\ x_1+y_1\end{pmatrix} + \beta\begin{pmatrix}2x_2 \\ x_2+y_2\end{pmatrix} = \alpha T\mathbf{v} + \beta T\mathbf{w}$

Hence $T$ is a linear operator. As a counterexample, $T\begin{pmatrix}x \\ y\end{pmatrix} = \begin{pmatrix}x^2 \\ y\end{pmatrix}$ is not linear because $T(2\mathbf{v}) = (4x^2, 2y)^T \neq 2(x^2, y)^T = 2T\mathbf{v}$.

1.3.2 Matrix Representation: The One-to-One Correspondence Between Operators and Matrices

A fundamental theorem of linear algebra tells us: in a finite-dimensional space, once a basis is chosen, each linear operator uniquely corresponds to a matrix, and vice versa. This correspondence is the bridge that converts abstract “operators” into computable “matrices” in quantum computing.

Concretely, let $\{|e_1\rangle, \ldots, |e_n\rangle\}$ be the standard basis of $\mathbb{C}^n$. The result of applying an operator $T$ to a basis vector $|e_j\rangle$ is still a vector in $\mathbb{C}^n$ and can therefore be expanded as a linear combination of the basis vectors:

$$T|e_j\rangle = \sum_{i=1}^n A_{ij}|e_i\rangle$$

The coefficients $A_{ij}$ form an $n \times n$ matrix $A = (A_{ij})$, which is the matrix representation of $T$ in this basis. Note that the column index $j$ corresponds to the input basis vector and the row index $i$ to the output coefficient — this is the standard convention for matrix representations.

Example 1.5: What is the matrix of $T\begin{pmatrix}x \\ y\end{pmatrix} = \begin{pmatrix}2x \\ x+y\end{pmatrix}$ given above?

Compute the action of $T$ on each basis vector:

$$T|1\rangle = T\begin{pmatrix}0 \\ 1\end{pmatrix} = \begin{pmatrix}0 \\ 1\end{pmatrix}$$

Taking these results as the columns of the matrix (because $T|0\rangle$ gives the first column as the components of the result vector), we obtain:

$$A = \begin{pmatrix} 2 & 0 \\ 1 & 1 \end{pmatrix}$$

Verification: $A\begin{pmatrix}x \\ y\end{pmatrix} = \begin{pmatrix}2x + 0y \\ x + y\end{pmatrix} = \begin{pmatrix}2x \\ x+y\end{pmatrix}$, which matches the definition of $T$. This verification is important: it confirms that the matrix $A$ does correctly encode the operator $T$.

1.3.3 Special Matrix Types

In quantum computing, three categories of matrices are especially important. Understanding their properties and physical significance is key to mastering quantum gates and quantum measurement.

Identity Matrix and Diagonal Matrices

The identity matrix $I_n$ (often abbreviated $I$) is the square matrix with ones on the diagonal and zeros elsewhere:

$$I = \begin{pmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{pmatrix}$$

It corresponds to the “do nothing” identity operator: $I|\psi\rangle = |\psi\rangle$ for all $|\psi\rangle$. In quantum circuits, the identity gate is usually not drawn explicitly but is indispensable in mathematical derivations.

A diagonal matrix has non-zero entries only on the main diagonal: $D = \text{diag}(d_1, d_2, \ldots, d_n)$. The action of a diagonal matrix on a basis vector $|e_k\rangle$ simply scales it by $d_k$: $D|e_k\rangle = d_k|e_k\rangle$. Thus, the basis vectors of a diagonal matrix are its eigenvectors, and the diagonal entries are the corresponding eigenvalues.

Hermitian Matrices

The conjugate transpose of a matrix $A$, also called the Hermitian conjugate, is denoted $A^\dagger$ (read “A dagger”) and is defined as: first take the transpose, then take the complex conjugate of each entry. That is, $(A^\dagger)_{ij} = A_{ji}^*$.

If $A^\dagger = A$, then $A$ is called a Hermitian matrix.

Core property: The eigenvalues of a Hermitian matrix are all real numbers. Proof: Let $A|\psi\rangle = \lambda|\psi\rangle$. Then

$\langle\psi|A|\psi\rangle = \lambda\langle\psi|\psi\rangle$

At the same time,

$\langle\psi|A|\psi\rangle = \langle\psi|A^\dagger|\psi\rangle = (\langle\psi|A|\psi\rangle)^* = \lambda^*\langle\psi|\psi\rangle$

Therefore $\lambda = \lambda^*$, i.e., $\lambda$ is a real number.

In quantum mechanics, observables — quantities that can be measured, such as energy, spin, and position — correspond to Hermitian operators / Hermitian matrices, whose eigenvalues are the possible measurement outcomes. Since measurement outcomes must be real numbers, the real-eigenvalue property of Hermitian matrices perfectly satisfies this physical requirement.

Example 1.6: Verify that $H = \begin{pmatrix} 3 & 1+i \\ 1-i & 2 \end{pmatrix}$ is Hermitian.

First take the transpose: $H^T = \begin{pmatrix} 3 & 1-i \\ 1+i & 2 \end{pmatrix}$

Then take the conjugate: $H^\dagger = \begin{pmatrix} 3^* & (1-i)^* \\ (1+i)^* & 2^* \end{pmatrix} = \begin{pmatrix} 3 & 1+i \\ 1-i & 2 \end{pmatrix} = H$

Thus $H$ is a Hermitian matrix. One can verify that its eigenvalues are real (approximately $4.3$ and $0.7$).

Unitary Matrices

If $U^\dagger U = UU^\dagger = I$, i.e., $U^\dagger = U^{-1}$ (the conjugate transpose equals the inverse), then $U$ is called a unitary matrix.

Core property: Unitary transformations preserve the inner product. For any $|\psi\rangle, |\phi\rangle$:

$$\langle U\phi|U\psi\rangle = \langle\phi|U^\dagger U|\psi\rangle = \langle\phi|I|\psi\rangle = \langle\phi|\psi\rangle$$

In particular, unitary transformations preserve the norm: $\|U|\psi\rangle\| = \|\psi\|$. This means that if $|\psi\rangle$ is a unit vector (a normalized quantum state), then $U|\psi\rangle$ is also a unit vector.

In quantum mechanics, quantum gates correspond to unitary transformations — they map normalized quantum states to other normalized quantum states, guaranteeing that the total probability remains 1. Every step of unitary evolution in quantum computation is reversible, a fact reflected in the invertibility of unitary matrices.

Hermitian vs. Unitary comparison:

Property	Hermitian Matrix $H$	Unitary Matrix $U$
Definition	$H^\dagger = H$	$U^\dagger U = I$
Eigenvalues	Real	Modulus 1 (can be written $e^{i\theta}$)
Physical meaning	Observable (measurement outcomes)	Quantum gate (state evolution)
Preserves what?	—	Inner product / norm / probability conservation
Typical examples	Pauli $X, Y, Z$ (also unitary)	Hadamard gate, phase gate, CNOT

1.3.4 Pauli Matrices

In operations on a single qubit ($\mathbb{C}^2$), the four Pauli matrices are the most fundamental and frequently used matrices. Named after physicist Wolfgang Pauli, they play central roles in quantum gates, quantum measurement, and quantum error correction.

Symbol	Name	Matrix Form	Type
$\sigma_0$ or $I$	Identity	$\displaystyle\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$	Both Hermitian and unitary
$\sigma_x$ or $X$	Pauli-X / NOT Gate	$\displaystyle\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$	Both Hermitian and unitary
$\sigma_y$ or $Y$	Pauli-Y	$\displaystyle\begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}$	Both Hermitian and unitary
$\sigma_z$ or $Z$	Pauli-Z / Phase Flip Gate	$\displaystyle\begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$	Both Hermitian and unitary

Let us understand their physical actions one by one:

• $I$ (Identity): Does nothing. $I|0\rangle = |0\rangle$, $I|1\rangle = |1\rangle$. It does not change the state in any basis.

• $X$ (NOT Gate / Pauli-X): Swaps $|0\rangle$ and $|1\rangle$, i.e., $X|0\rangle = |1\rangle$, $X|1\rangle = |0\rangle$. It is the quantum analogue of the classical NOT gate and corresponds to a rotation by $\pi$ about the $x$-axis on the Bloch sphere.

• $Z$ (Phase Flip Gate / Pauli-Z): Leaves $|0\rangle$ unchanged and attaches a minus sign to $|1\rangle$: $Z|0\rangle = |0\rangle$, $Z|1\rangle = -|1\rangle$. Note that $-|1\rangle$ and $|1\rangle$ represent the same physical state up to a global phase (which does not affect measurement), but $Z$ changes the relative phase when $|1\rangle$ is part of a superposition. $Z$ corresponds to a rotation by $\pi$ about the $z$-axis on the Bloch sphere.

• $Y$ (Pauli-Y): Can be regarded as a combination of $X$ and $Z$ ($Y = iXZ$), corresponding to a rotation by $\pi$ about the $y$-axis on the Bloch sphere. Its effect is $Y|0\rangle = i|1\rangle$, $Y|1\rangle = -i|0\rangle$.

Verifying unitarity: Taking $\sigma_x$ as an example, we verify that it is unitary:

$\sigma_x^\dagger = \begin{pmatrix} 0^* & 1^* \\ 1^* & 0^* \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} = \sigma_x$

$\sigma_x^\dagger \sigma_x = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = I$

Thus $\sigma_x$ is unitary. The other three can be verified similarly. It is noteworthy that all Pauli matrices are simultaneously Hermitian ($\sigma^\dagger = \sigma$) and unitary ($\sigma^\dagger\sigma = I$). This dual property allows them to serve both as observables (measurement operators) and as quantum gates (evolution operators).

Example 1.7: Compute the effect of $Z$ acting on the superposition state $|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$.

$Z|+\rangle = \frac{1}{\sqrt{2}}(Z|0\rangle + Z|1\rangle) = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) = |-\rangle$

Here $|-\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$ is another superposition state orthogonal to $|+\rangle$. The $Z$ gate transforms $|+\rangle$ into $|-\rangle$, which is equivalent to a $180^\circ$ rotation in the $x$-$y$ plane of the Bloch sphere. Applying $Z$ again to $|-\rangle$ returns it to $|+\rangle$: $Z^2 = I$.

1.3.5 Basic Rules of Matrix Operations

Matrix multiplication is used extensively in quantum computing. For $2 \times 2$ matrices $A = (a_{ij})$ and $B = (b_{ij})$, the $(i, j)$ entry of the product is:

$$(AB)_{ij} = \sum_{k=1}^2 a_{ik}b_{kj}$$

i.e., “row times column.” Written out explicitly:

$$AB = \begin{pmatrix} a_{11}b_{11} + a_{12}b_{21} & a_{11}b_{12} + a_{12}b_{22} \\ a_{21}b_{11} + a_{22}b_{21} & a_{21}b_{12} + a_{22}b_{22} \end{pmatrix}$$

Matrix multiplication does not generally satisfy the commutative law: $AB \neq BA$. This is a key distinction between quantum mechanics and classical mechanics — the order of operators (the sequence of operations) carries physical meaning. For example:

$\sigma_x \sigma_z = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$

$\sigma_z \sigma_x = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix} = -\sigma_x\sigma_z$

Interestingly, $\sigma_x \sigma_z = -\sigma_z \sigma_x$ — the Pauli matrices anticommute. This property finds important applications in quantum error correction, fermion simulation, and quantum random walks.

The Pauli matrices also satisfy the famous algebraic relations:

$\sigma_x\sigma_y = i\sigma_z, \quad \sigma_y\sigma_z = i\sigma_x, \quad \sigma_z\sigma_x = i\sigma_y$

and the square identities: $\sigma_x^2 = \sigma_y^2 = \sigma_z^2 = I$.

Summary:

• Linear operators $T$ preserve the linear structure: $T(\alpha|v\rangle + \beta|w\rangle) = \alpha T|v\rangle + \beta T|w\rangle$; this is the fundamental constraint on quantum evolution
• Once a basis is chosen, operators and matrices are in one-to-one correspondence; matrix multiplication corresponds to operator composition (note the order: $AB$ means “do $B$ first, then $A$”)
• Hermitian matrices $H^\dagger = H$: eigenvalues are real, corresponding to observables (measurement operators)
• Unitary matrices $U^\dagger U = I$: preserve inner product / norm, corresponding to quantum gates (evolution operators)
• Pauli matrices $\{I, X, Y, Z\}$ are the most fundamental set of operators on $\mathbb{C}^2$, all simultaneously Hermitian and unitary; they anticommute and satisfy $X^2 = Y^2 = Z^2 = I$
• Matrix multiplication is generally non-commutative; operator order corresponds to the physical sequence of operations

Connection to Quantum Computing: The entire framework of quantum computing rests on three mathematical pillars — and this chapter happens to cover all three:

1. Complex numbers (Section 1.1): the amplitudes of quantum states are complex numbers; the phase $e^{i\theta}$ drives quantum interference
2. Hilbert space (Section 1.2): quantum states are normalized vectors in a Hilbert space; bra-ket notation is the standard language
3. Linear operators (Section 1.3): quantum gates are unitary operators, observables are Hermitian operators; their eigenvalues correspond respectively to “evolved states” and “possible measurement outcomes”

The Pauli matrices $X, Y, Z$, together with the identity $I$, form the “alphabet” of all single-qubit operations — any single-qubit unitary gate can be composed from them (with appropriate phase rotations). For example, the Hadamard gate $H = \frac{1}{\sqrt{2}}(X + Z)$ is a superposition of $X$ and $Z$. This is the mathematical starting point for understanding quantum circuits and quantum algorithms. Subsequent chapters will build on this foundation by introducing the postulates of quantum mechanics and formally establishing the theoretical framework of quantum computing.

---

Next Chapter Preview: Having mastered complex numbers, vector spaces, and linear operators, Chapter 2 will introduce the core postulates of quantum mechanics — including quantum state evolution (the Schrodinger equation), the projection postulate for measurement, and the tensor product structure of composite systems — thereby completing the transition from “mathematical tools” to “quantum theory” and laying the physical foundation for subsequent study of quantum algorithms and quantum information theory.

1.4 Inner Products, Norms & Orthogonality

In Section 1.2, we introduced the basic concepts of vector spaces and Hilbert spaces and learned the ket $|v\rangle$ and bra $\langle v|$ of Dirac notation. These symbols are not merely compact notation; they embody a profound mathematical structure — the inner product. This section begins with the familiar dot product in the complex vector space $\mathbb{C}^n$, generalizes the inner product to arbitrary abstract vector spaces, and builds from it rigorous definitions of norm and orthogonality. These concepts are the central pillars of quantum mechanical formalism: the “length” of a quantum state, the “angle” between different states, and the calculation of measurement probabilities all depend on the inner product structure. Understanding the inner product is not only the foundation for the subsequent study of eigenvalue problems and spectral decomposition but also a crucial step in mastering the superposition principle of quantum states and the measurement postulate. Without an inner product structure, a vector space is merely an abstract algebraic object; once endowed with an inner product, the space acquires a rich geometric structure including metrics, angles, and projections.

Definition and Basic Properties of the Inner Product

Recall the ket $|v\rangle \in \mathbb{C}^n$ we defined in Section 1.2, written in component form as:

$$|v\rangle = \begin{pmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{pmatrix}$$

The corresponding bra $\langle v|$ is the conjugate transpose of that vector:

$$\langle v| = \begin{pmatrix} v_1^* & v_2^* & \cdots & v_n^* \end{pmatrix}$$

In $\mathbb{C}^n$, the inner product of two vectors $|v\rangle$ and $|w\rangle$ is defined as:

$$\langle v | w \rangle = \sum_{i=1}^{n} v_i^* w_i$$

This is a complex number. For example, if $|v\rangle = \begin{pmatrix} 1 \\ i \end{pmatrix}$ and $|w\rangle = \begin{pmatrix} 2 \\ 1+i \end{pmatrix}$, then:

$$\langle v | w \rangle = 1^* \cdot 2 + (-i) \cdot (1+i) = 2 - i(1+i) = 2 - i - i^2 = 3 - i$$

Here one must pay special attention to the role of the complex conjugate: the inner product takes the conjugate of the first vector, and this is to guarantee positive definiteness (see below). If the definition lacked this conjugation, then for a vector such as $|v\rangle = \begin{pmatrix} 1 \\ i \end{pmatrix}$, we would have $\langle v | v \rangle = 1 + i^2 = 0$, violating the requirement of positive definiteness. Introducing the complex conjugate yields $\langle v | v \rangle = 1 + (-i)(i) = 2 > 0$, thereby ensuring a sound mathematical structure. This point is especially important in quantum mechanics, because the normalization of quantum states directly depends on a positive-definite inner product.

From $\mathbb{C}^n$, we can abstractly define an inner product on an arbitrary complex vector space $V$. An inner product is a map $\langle \cdot | \cdot \rangle: V \times V \rightarrow \mathbb{C}$ satisfying the following three basic properties:

First, conjugate symmetry: For any $|v\rangle, |w\rangle \in V$,

$$\langle v | w \rangle = \langle w | v \rangle^*$$

This property guarantees that $\langle v | v \rangle$ is a real number, because $\langle v | v \rangle = \langle v | v \rangle^*$. When $v = w$, the result of the inner product is the inner product of the vector with itself and must be a real number. This is a prerequisite for defining the norm, since the norm is required to be a non-negative real number. Conjugate symmetry also implies that if the inner product is a pure real number, swapping the order of the two vectors does not affect the result; if the inner product is a complex number, swapping the order yields its complex conjugate.

Second, linearity in the second argument: For any $|v\rangle, |w\rangle, |u\rangle \in V$ and any complex numbers $\alpha, \beta \in \mathbb{C}$,

$$\langle v | \alpha w + \beta u \rangle = \alpha \langle v | w \rangle + \beta \langle v | u \rangle$$

Note that the inner product is antilinear in the first argument: $\langle \alpha v | w \rangle = \alpha^* \langle v | w \rangle$. This is consistent with the behavior of a bra as a row vector in matrix multiplication and with the linearity properties of the bra as an element of the dual space in quantum mechanics. Physically, linearity ensures that the inner product calculation for a superposition of quantum states can be decomposed according to the superposition principle.

Third, positive definiteness: For any non-zero vector $|v\rangle \neq 0$,

$$\langle v | v \rangle > 0$$

and $\langle v | v \rangle = 0$ if and only if $|v\rangle = 0$. This property is crucial: it allows us to define the “length” of a vector and rules out the possibility of any vector other than the zero vector having zero length. Positive definiteness is directly related to the probability interpretation in quantum mechanics: the inner product of a quantum state with itself must be positive to guarantee the positivity of probabilities. If non-zero vectors were allowed to have zero length, the probability interpretation would lose its mathematical foundation.

Norm and Distance

From the inner product we can naturally define the norm, i.e., the “length” or “magnitude” of a vector:

$$\| |v\rangle \| = \sqrt{\langle v | v \rangle}$$

For vectors in $\mathbb{C}^n$, this gives:

$$\| |v\rangle \| = \sqrt{\sum_{i=1}^{n} |v_i|^2}$$

where $|v_i|^2 = v_i^* v_i$ is the squared modulus of the complex number $v_i$. For example, computing the norm of $|v\rangle = \begin{pmatrix} 1 \\ i \end{pmatrix}$:

$$\| |v\rangle \| = \sqrt{1^* \cdot 1 + (-i) \cdot i} = \sqrt{1 + 1} = \sqrt{2}$$

If $\| |v\rangle \| = 1$, then $|v\rangle$ is called a unit vector. The way to normalize an arbitrary non-zero vector is to divide it by its norm:

$$|\hat{v}\rangle = \frac{|v\rangle}{\| |v\rangle \|}$$

The normalized vector satisfies $\langle \hat{v} | \hat{v} \rangle = 1$. In quantum mechanics, a quantum state must be normalized, which corresponds to the physical requirement that the total probability is 1. For example, normalizing $|v\rangle$ above gives:

$$|\hat{v}\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ i \end{pmatrix}$$

Verification: $\langle \hat{v} | \hat{v} \rangle = \frac{1}{2}(1 \cdot 1 + (-i) \cdot i) = \frac{1}{2}(1+1) = 1$.

From the norm we can derive two important inequalities. The Cauchy-Schwarz inequality states:

$$|\langle v | w \rangle| \leq \| |v\rangle \| \cdot \| |w\rangle \|$$

with equality if and only if the two vectors are linearly dependent. The triangle inequality states:

$$\| |v\rangle + |w\rangle \| \leq \| |v\rangle \| + \| |w\rangle \|$$

These two inequalities are very useful in analyzing the superposition and evolution of quantum states, for instance in bounding the fidelity between two quantum states. A direct corollary of the Cauchy-Schwarz inequality is that for normalized quantum states, the squared modulus of the inner product satisfies $|\langle v | w \rangle|^2 \leq 1$, which guarantees that probabilities in the Born rule never exceed 1. In addition, we can define the “angle” $\theta$ between two non-zero vectors by $\cos\theta = |\langle v | w \rangle| / (\|v\| \|w\|)$. When two quantum states are orthogonal, $\theta = 90^\circ$, meaning they are “perpendicular,” completely distinguishable states.

Orthogonality and Orthonormal Bases

Two vectors $|v\rangle$ and $|w\rangle$ are said to be orthogonal if their inner product is zero:

$$\langle v | w \rangle = 0$$

Orthogonality means the two vectors are in some sense “perpendicular.” In quantum mechanics, orthogonal states have an extremely important physical meaning: they represent physically distinct states that can be unambiguously told apart. If two quantum states are orthogonal, a measurement can never simultaneously yield non-zero probabilities for both states. This property is part of the foundation of quantum measurement theory: orthogonal states correspond to mutually exclusive measurement outcomes.

A set of vectors $\{|e_1\rangle, |e_2\rangle, \ldots, |e_n\rangle\}$ forms an orthogonal basis if they are pairwise orthogonal and linearly independent. If, further, each basis vector is a unit vector:

$$\langle e_i | e_j \rangle = \delta_{ij} = \begin{cases} 1 & i = j \\ 0 & i \neq j \end{cases}$$

then it is called an orthonormal basis, where $\delta_{ij}$ is the Kronecker delta. The computational basis $|0\rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$ and $|1\rangle = \begin{pmatrix} 0 \\ 1 \end{pmatrix}$ mentioned in Section 1.2 is an orthonormal basis for $\mathbb{C}^2$, because:

$$\langle 0 | 0 \rangle = 1, \quad \langle 1 | 1 \rangle = 1, \quad \langle 0 | 1 \rangle = 0$$

The importance of an orthonormal basis lies in how dramatically it simplifies the expansion of vectors and the calculation of inner products. In an orthonormal basis, the components of a vector can be obtained directly through inner products: if $|v\rangle = \sum_i v_i |e_i\rangle$, then $v_i = \langle e_i | v \rangle$. The inner product of any two vectors can also be written as the sum of products of corresponding components: $\langle v | w \rangle = \sum_i v_i^* w_i$. This simplicity makes the orthonormal basis the preferred basis representation in quantum computing.

For any set of linearly independent vectors, one can construct an orthonormal basis through the Gram-Schmidt orthogonalization process. The core idea of this process is to iteratively subtract from each vector its projection onto the already-constructed orthogonal vectors. Taking two dimensions as an example, given two linearly independent vectors $|a\rangle$ and $|b\rangle$, the construction proceeds as follows:

First, let $|e_1\rangle = |a\rangle / \| |a\rangle \|$. Then construct $|b'\rangle = |b\rangle - \langle e_1 | b \rangle |e_1\rangle$, which amounts to subtracting from $|b\rangle$ its component along the direction of $|e_1\rangle$. Finally, normalize: $|e_2\rangle = |b'\rangle / \| |b'\rangle \|$. One can verify that $\langle e_1 | e_2 \rangle = 0$ and both are unit vectors. This process generalizes to spaces of arbitrary dimension and is a universal algorithm for constructing orthonormal bases.

Projection Operators

In Section 1.3 we learned about linear operators and matrix representations. Now, using the inner product structure, we can define a particularly important type of operator — the projection operator. Given a normalized vector $|v\rangle$, define:

$$P_v = |v\rangle \langle v|$$

This operator projects an arbitrary vector $|w\rangle$ onto the one-dimensional subspace spanned by $|v\rangle$:

$$P_v |w\rangle = |v\rangle \langle v | w \rangle = (\langle v | w \rangle) |v\rangle$$

The result is a vector parallel to $|v\rangle$ whose coefficient is precisely the inner product $\langle v | w \rangle$. This coefficient has a profound physical meaning in quantum mechanics: its squared modulus $|\langle v | w \rangle|^2$ gives the probability that the quantum state $|w\rangle$ collapses to $|v\rangle$ upon measurement. The projection operator thus serves as a bridge connecting the mathematical inner product to the physical measurement probability.

Taking $\mathbb{C}^2$ as an example, let $|v\rangle = |0\rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$. Then the matrix representation of the projection operator is:

$$P_0 = |0\rangle \langle 0| = \begin{pmatrix} 1 \\ 0 \end{pmatrix} \begin{pmatrix} 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}$$

Similarly, $P_1 = |1\rangle \langle 1| = \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}$. It is easy to verify that $P_0^2 = P_0$ and $P_1^2 = P_1$, which is the characteristic property of a projection operator: projecting again does not change the result, i.e., $P_v^2 = P_v$. Moreover, projection operators are Hermitian operators: $P_v^\dagger = P_v$. These two properties — idempotence and Hermiticity — are the necessary and sufficient conditions for a projection operator.

If $\{|e_i\rangle\}$ is an orthonormal basis, then for any vector $|\psi\rangle$ we have the expansion:

$$|\psi\rangle = \sum_i \langle e_i | \psi \rangle |e_i\rangle$$

This is called the completeness relation. The corresponding operator form is:

$$\sum_i |e_i\rangle \langle e_i| = I$$

where $I$ is the identity operator. This identity is ubiquitous in quantum computing and is an important tool for performing basis transformations and deriving formulas. For example, inserting the completeness relation on either side of an arbitrary operator $A$: $A = I A I = \sum_{i,j} |e_i\rangle \langle e_i| A |e_j\rangle \langle e_j| = \sum_{i,j} A_{ij} |e_i\rangle \langle e_j|$, where $A_{ij} = \langle e_i| A |e_j\rangle$ is precisely the matrix element of $A$ in the orthonormal basis. The completeness relation can also be used to expand a state in a new basis: $|\psi\rangle = I |\psi\rangle = \sum_i |e_i\rangle \langle e_i | \psi \rangle$, which is the abstract vector-space analogue of a Fourier expansion.

Let us examine one more explicit example to consolidate the calculation of inner products. Consider the quantum state $|\psi\rangle = \frac{1}{2}\begin{pmatrix} 1 \\ \sqrt{3} \end{pmatrix}$ and compute its norm:

$$\| |\psi\rangle \| = \sqrt{\frac{1}{4}(1 + 3)} = \sqrt{1} = 1$$

The state is already normalized. Now compute its inner product with $|0\rangle$: $\langle 0 | \psi \rangle = \frac{1}{2}$, so the probability of measuring $|0\rangle$ is $|\langle 0 | \psi \rangle|^2 = \frac{1}{4}$. Similarly, the probability of measuring $|1\rangle$ is $\frac{3}{4}$. The two probabilities sum to 1, satisfying the normalization condition. This example clearly shows how the inner product directly connects mathematical calculation to physical measurement outcomes.

From a geometric perspective, the inner product can also be used to define the angle between two vectors. For non-zero vectors $|v\rangle$ and $|w\rangle$, the angle $\theta$ satisfies:

$$\cos \theta = \frac{|\langle v | w \rangle|}{\| |v\rangle \| \| |w\rangle \|}$$

The Cauchy-Schwarz inequality guarantees that the right-hand side does not exceed 1. When $\theta = 0$, the two vectors are parallel; when $\theta = \pi/2$, they are orthogonal. In quantum mechanics, orthogonal states correspond to perfectly distinguishable measurement outcomes, while parallel states represent the same physical state (differing only by an overall phase).

Summary:

This section built up the mathematical framework required by quantum mechanics, starting from the definition of the inner product. The inner product $\langle v | w \rangle$ generalizes the dot product on a complex vector space to an abstract vector space. Its three properties — conjugate symmetry, linearity in the second argument, and positive definiteness — guarantee that the norm $\| |v\rangle \| = \sqrt{\langle v | v \rangle}$ is well defined. The concept of orthogonality allows us to define orthonormal bases, and the projection operator $P_v = |v\rangle \langle v|$ provides an explicit operation for projecting onto a one-dimensional subspace. The completeness relation $\sum_i |e_i\rangle \langle e_i| = I$ shows that an orthonormal basis suffices to represent any vector in the space, providing the mathematical guarantee for expanding quantum states in different bases. The Cauchy-Schwarz and triangle inequalities, derived from the inner product, furnish basic constraints on relations among vectors.

Connection to Quantum Computing:

The inner product is the mathematical root of the probability interpretation in quantum mechanics. The normalization condition $\langle \psi | \psi \rangle = 1$ for quantum states directly corresponds to the physical conservation of total probability. The squared modulus of the inner product between two states, $|\langle \phi | \psi \rangle|^2$, gives the Born rule probability of obtaining a particular measurement outcome. Orthogonal states $\langle \phi | \psi \rangle = 0$ mean the two quantum states can be perfectly distinguished — a measurement can never simultaneously yield non-zero probabilities for both orthogonal states. Orthonormal bases constitute the set of possible measurement outcomes, and projection operators are the central mathematical objects of the quantum measurement postulate: the spectral decomposition of a measurement operator is precisely built from a family of projection operators. Thus, every concept in this section directly underpins the description of qubit states and the mathematical formalism of quantum measurement, forming the foundation for understanding quantum algorithms and quantum information theory. From quantum gate operations to quantum error correction, from quantum state tomography to quantum machine learning, the inner product structure is everywhere.

---

1.5 Eigenvalues & Eigenvectors

In Section 1.3, we studied linear operators and matrix representations and became familiar with concrete operator examples such as the Pauli matrices. This section delves into the eigenstructure of linear operators — eigenvalues and eigenvectors. For quantum mechanics, this is the most crucial section: the possible measurement outcomes of a quantum observable correspond to the eigenvalues of a Hermitian operator, and the state of the system after measurement collapses to the corresponding eigenvector. The spectral theorem will reveal the profound symmetries of the eigenstructure of Hermitian and unitary operators, laying the cornerstone for the mathematical formalism of quantum mechanics. Mastering the content of this section is an essential prerequisite for understanding quantum measurement, quantum evolution, and quantum error-correcting codes. The eigenvalue problem is not only a central topic of linear algebra but also the key link connecting abstract mathematics to physically measurable quantities.

The Characteristic Equation

Given a linear operator $A$ acting on a vector space $V$, if there exists a non-zero vector $|v\rangle$ and a scalar $\lambda$ such that:

$$A |v\rangle = \lambda |v\rangle$$

then $\lambda$ is called an eigenvalue of $A$, and $|v\rangle$ is the corresponding eigenvector. The meaning of this equation is very intuitive: eigenvectors are those vectors that, under the action of the operator $A$, are merely stretched or compressed (multiplied by a scalar $\lambda$) while their direction remains unchanged. Physically, this means that eigenvectors represent states that remain “stable” under the operation described by that operator. For instance, if $A$ describes a rotation operation, then vectors along the rotation axis are eigenvectors with eigenvalue 1 (since their length does not change).

Rewrite the equation as $(A - \lambda I)|v\rangle = 0$, where $I$ is the identity operator. A necessary and sufficient condition for a non-zero solution to exist is that the operator $(A - \lambda I)$ be singular, i.e.:

$$\det(A - \lambda I) = 0$$

This is called the characteristic equation. The left-hand side is a polynomial in $\lambda$, called the characteristic polynomial. For an $n \times n$ matrix, the characteristic polynomial is of degree $n$, so there are $n$ eigenvalues (counting multiplicities). Eigenvalues can be real or complex, simple or repeated roots, depending on the specific structure of the matrix.

Consider the example of a $2 \times 2$ matrix:

$$A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$$

Its characteristic polynomial is:

$$\det\begin{pmatrix} a-\lambda & b \\ c & d-\lambda \end{pmatrix} = (a-\lambda)(d-\lambda) - bc = \lambda^2 - (a+d)\lambda + (ad-bc) = 0$$

The coefficient $(a+d)$ is the trace of the matrix, and $(ad-bc)$ is the determinant. This yields important properties of eigenvalues: the sum of the eigenvalues equals the trace, and the product of the eigenvalues equals the determinant. This provides a convenient way to verify eigenvalue calculations.

Explicit Calculation: The Pauli $Z$ Matrix

Let us compute the eigenvalues and eigenvectors of the Pauli $Z$ matrix introduced in Section 1.3:

$$Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$$

The characteristic equation is:

$$\det\begin{pmatrix} 1-\lambda & 0 \\ 0 & -1-\lambda \end{pmatrix} = (1-\lambda)(-1-\lambda) = 0$$

Solving yields two eigenvalues: $\lambda_1 = 1$ and $\lambda_2 = -1$. Verification: the trace is $1 + (-1) = 0$, equal to the sum of the eigenvalues; the determinant is $1 \times (-1) - 0 = -1$, equal to the product of the eigenvalues.

For $\lambda_1 = 1$, solve $(Z - I)|v\rangle = 0$:

$$\begin{pmatrix} 0 & 0 \\ 0 & -2 \end{pmatrix} \begin{pmatrix} v_1 \\ v_2 \end{pmatrix} = 0 \implies v_2 = 0$$

Thus the normalized eigenvector is $|e_1\rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix} = |0\rangle$.

For $\lambda_2 = -1$, solve $(Z + I)|v\rangle = 0$:

$$\begin{pmatrix} 2 & 0 \\ 0 & 0 \end{pmatrix} \begin{pmatrix} v_1 \\ v_2 \end{pmatrix} = 0 \implies v_1 = 0$$

The normalized eigenvector is $|e_2\rangle = \begin{pmatrix} 0 \\ 1 \end{pmatrix} = |1\rangle$.

Notice that the eigenvectors of the $Z$ matrix are precisely the computational basis $|0\rangle$ and $|1\rangle$. This is no coincidence: the Pauli $Z$ matrix in quantum mechanics corresponds to a spin measurement along the $z$-axis, and its eigenvalues $\pm 1$ represent the spin-up and spin-down measurement outcomes, respectively. The eigenvectors are the final states to which the system collapses after measurement. This correspondence is a direct manifestation of the quantum measurement postulate.

The Spectral Theorem: Diagonalization of Hermitian Operators

We now arrive at the core content of this section — the spectral theorem. In quantum mechanics, operators representing observables are all Hermitian operators, i.e., those satisfying $H = H^\dagger$ (as defined in Section 1.3). The spectral theorem tells us that Hermitian operators possess a series of elegant properties, which endow quantum measurement with a clear physical meaning. Understanding the spectral theorem is key to mastering the mathematical structure of quantum mechanics.

Property 1: The eigenvalues of a Hermitian operator are all real.

The proof proceeds as follows. Let $H$ be a Hermitian operator, $H|v\rangle = \lambda |v\rangle$, with $|v\rangle \neq 0$. Consider $\langle v| H |v\rangle$:

On the one hand, from the eigenvalue equation:

$$\langle v| H |v\rangle = \langle v| (\lambda |v\rangle) = \lambda \langle v | v \rangle = \lambda \| |v\rangle \|^2$$

On the other hand, from the Hermitian property $H = H^\dagger$:

$$\langle v| H |v\rangle = \langle v| H^\dagger |v\rangle = (H |v\rangle)^\dagger |v\rangle = (\lambda |v\rangle)^\dagger |v\rangle = \lambda^* \langle v | v \rangle = \lambda^* \| |v\rangle \|^2$$

Comparing the two expressions, since $\| |v\rangle \|^2 \neq 0$, we have $\lambda = \lambda^*$, i.e., $\lambda \in \mathbb{R}$. This conclusion is of paramount importance: the results of quantum measurements must be real numbers, and the real eigenvalues of Hermitian operators guarantee precisely this. If eigenvalues were complex, measurement results would be complex, contradicting the physical fact that we can only read real values from experiments. This proof also demonstrates how the inner product structure, combined with the Hermitian property of the operator, yields a profound physical conclusion.

Property 2: Eigenvectors corresponding to distinct eigenvalues are mutually orthogonal.

Let $H|v\rangle = \lambda |v\rangle$ and $H|w\rangle = \mu |w\rangle$, with $\lambda \neq \mu$. Consider $\langle w| H |v\rangle$:

$$\langle w| H |v\rangle = \lambda \langle w | v \rangle$$

At the same time:

$$\langle w| H |v\rangle = \langle w| H^\dagger |v\rangle = (H|w\rangle)^\dagger |v\rangle = \mu^* \langle w | v \rangle = \mu \langle w | v \rangle$$

The last step uses the fact that $\mu$ is real. Hence:

$$(\lambda - \mu)\langle w | v \rangle = 0$$

Since $\lambda \neq \mu$, we must have $\langle w | v \rangle = 0$, i.e., the two eigenvectors are orthogonal. This means that the eigenvectors of a Hermitian operator naturally form an orthogonal basis. Combined with normalization, they form an orthonormal basis, which is the mathematical guarantee that “after measurement the system is in a certain eigenstate” in the quantum measurement postulate. Orthogonality guarantees that different measurement outcomes are distinguishable, which is the foundation of quantum measurement theory.

Property 3: A Hermitian operator admits a spectral decomposition.

For a Hermitian operator $H$ in a finite-dimensional space, let its eigenvalues be $\lambda_1, \lambda_2, \ldots, \lambda_n$ (repetitions allowed) with corresponding normalized eigenvectors $|e_1\rangle, |e_2\rangle, \ldots, |e_n\rangle$. The spectral theorem asserts:

$$H = \sum_{i=1}^{n} \lambda_i |e_i\rangle \langle e_i|$$

This is the spectral decomposition. It expresses the operator $H$ as a weighted sum of projection operators, with the eigenvalues as weights. This decomposition is of fundamental importance in quantum mechanics, because it represents an abstract operator in a form that can be directly mapped to physical measurements. Each projection operator $|e_i\rangle \langle e_i|$ corresponds to a possible measurement outcome, and the weight $\lambda_i$ is the numerical value of that outcome.

Explicit Calculation: Spectral Decomposition of the Pauli $X$ Matrix

Let us verify the spectral decomposition of the Pauli $X$ matrix:

$$X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$$

The characteristic equation is $\det\begin{pmatrix} -\lambda & 1 \\ 1 & -\lambda \end{pmatrix} = \lambda^2 - 1 = 0$, so the eigenvalues are $\lambda_1 = 1$, $\lambda_2 = -1$.

For $\lambda_1 = 1$, solve $(X - I)|v\rangle = 0$:

$$\begin{pmatrix} -1 & 1 \\ 1 & -1 \end{pmatrix} \begin{pmatrix} v_1 \\ v_2 \end{pmatrix} = 0 \implies v_1 = v_2$$

Normalizing gives $|+\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 1 \end{pmatrix}$.

For $\lambda_2 = -1$, solve $(X + I)|v\rangle = 0$:

$$\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} v_1 \\ v_2 \end{pmatrix} = 0 \implies v_1 = -v_2$$

Normalizing gives $|-\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ -1 \end{pmatrix}$.

Verify orthogonality: $\langle + | - \rangle = \frac{1}{2}(1 \cdot 1 + 1 \cdot (-1)) = 0$, indeed orthogonal.

Now perform the spectral decomposition:

$$X = (+1)|+\rangle \langle +| + (-1)|-\rangle \langle -|$$

Compute the matrices of the projection operators:

$$|+\rangle \langle +| = \frac{1}{2}\begin{pmatrix} 1 \\ 1 \end{pmatrix}\begin{pmatrix} 1 & 1 \end{pmatrix} = \frac{1}{2}\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}$$ $$|-\rangle \langle -| = \frac{1}{2}\begin{pmatrix} 1 \\ -1 \end{pmatrix}\begin{pmatrix} 1 & -1 \end{pmatrix} = \frac{1}{2}\begin{pmatrix} 1 & -1 \\ -1 & 1 \end{pmatrix}$$

Therefore:

$$X = \frac{1}{2}\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix} - \frac{1}{2}\begin{pmatrix} 1 & -1 \\ -1 & 1 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$$

Verification holds. The states $|+\rangle$ and $|-\rangle$ are called the $X$ basis or Hadamard basis and are widely used in quantum computing for constructing superposition states. For example, the action of the Hadamard gate $H$ transforms the computational basis to the $X$ basis.

Eigenvalues of Unitary Operators

In Section 1.3 we defined unitary operators: those satisfying $U^\dagger U = U U^\dagger = I$. Unitary operators describe the time evolution of quantum states, and their eigenvalues have a special property. Let $U|v\rangle = \lambda |v\rangle$. Then:

$$\langle v| U^\dagger U |v\rangle = \langle v | v \rangle = \| |v\rangle \|^2$$

At the same time:

$$\langle v| U^\dagger U |v\rangle = (U|v\rangle)^\dagger (U|v\rangle) = (\lambda |v\rangle)^\dagger (\lambda |v\rangle) = \lambda^* \lambda \langle v | v \rangle = |\lambda|^2 \| |v\rangle \|^2$$

Therefore $|\lambda|^2 = 1$, i.e., the eigenvalues of a unitary operator are complex numbers of modulus 1, which can be written as $e^{i\theta}$ with $\theta \in \mathbb{R}$. For example, the phase gate $P(\theta) = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\theta} \end{pmatrix}$ has eigenvalues $1$ and $e^{i\theta}$. This property guarantees that unitary evolution does not alter the normalization condition of quantum states. The phase $\theta$ plays a central role in quantum interference phenomena, where different phases can lead to constructive or destructive interference.

Let us examine one more non-Pauli example to deepen our understanding. Consider the Hermitian matrix:

$$H = \begin{pmatrix} 3 & 1 \\ 1 & 3 \end{pmatrix}$$

The characteristic equation is $\det\begin{pmatrix} 3-\lambda & 1 \\ 1 & 3-\lambda \end{pmatrix} = (3-\lambda)^2 - 1 = \lambda^2 - 6\lambda + 8 = 0$. Solving yields $\lambda_1 = 4$, $\lambda_2 = 2$. For $\lambda_1 = 4$, the eigenvector satisfies $-v_1 + v_2 = 0$, normalized to $|e_1\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 1 \end{pmatrix}$. For $\lambda_2 = 2$, the eigenvector satisfies $v_1 + v_2 = 0$, normalized to $|e_2\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ -1 \end{pmatrix}$. Verify orthogonality: $\langle e_1 | e_2 \rangle = 0$. The spectral decomposition is $H = 4|e_1\rangle \langle e_1| + 2|e_2\rangle \langle e_2|$. This example illustrates that any Hermitian matrix can be diagonalized by finding its eigenvector basis, which is the foundation of quantum measurement theory: if we measure the system using the physical quantity corresponding to $H$, the possible outcomes are 4 or 2, with probabilities determined by the projection of the system state onto $|e_1\rangle$ and $|e_2\rangle$.

Regarding degenerate eigenvalues: when a Hermitian operator has repeated eigenvalues, the eigenvectors belonging to that eigenvalue are not unique but span a subspace. For instance, the identity operator $I$ has all eigenvalues equal to 1, and any vector is an eigenvector. In such cases, we may arbitrarily choose an orthonormal basis within that subspace. Degeneracy reflects symmetries of the quantum system: when the system possesses a certain symmetry, different quantum states may have the same energy eigenvalue. Handling degeneracy requires additional conserved quantities or symmetries to determine a suitable basis.

The concepts of eigenvalues and eigenvectors can also be generalized to differential operators in function spaces. For example, the position operator $\hat{x}$ and the momentum operator $\hat{p} = -i\hbar \frac{d}{dx}$ in quantum mechanics are operators in infinite-dimensional spaces. The “eigenvectors” of the position operator are Dirac delta functions $\delta(x - x_0)$, with corresponding eigenvalues being the position coordinate $x_0$; the eigenvectors of the momentum operator are plane waves $e^{ipx/\hbar}$, with corresponding eigenvalues being the momentum $p$. Although strictly speaking these objects do not belong to the Hilbert space, the framework of rigged Hilbert spaces can make the mathematics rigorous. This perspective reveals the universality of the eigenvalue problem: it is not merely a property of finite-dimensional matrices but a fundamental structure of all linear operators.

Summary:

This section systematically studied the eigenstructure of linear operators, starting from the eigenvalue equation $A|v\rangle = \lambda |v\rangle$. The spectral theorem reveals three core properties of Hermitian operators: eigenvalues are real, eigenvectors corresponding to distinct eigenvalues are mutually orthogonal, and the operator can be decomposed as $H = \sum_i \lambda_i |e_i\rangle \langle e_i|$. We also proved that the eigenvalues of a unitary operator must be complex numbers of modulus 1 of the form $e^{i\theta}$. Through explicit calculations for the Pauli $Z$ and $X$ matrices, we verified these abstract theorems on concrete operators and demonstrated how to construct spectral decompositions and verify the results. The eigenvalue problem not only provides the “fingerprint” of an operator but furnishes the complete mathematical framework for quantum measurement theory.

Connection to Quantum Computing:

The spectral theorem is the mathematical cornerstone of the quantum measurement postulate. In quantum mechanics, every physical observable corresponds to a Hermitian operator $H$, and its possible measurement outcomes are precisely the real eigenvalues $\lambda_i$ of $H$. After measurement, the quantum state collapses to the corresponding eigenvector $|e_i\rangle$. The projection operators $|e_i\rangle \langle e_i|$ in the spectral decomposition $H = \sum_i \lambda_i |e_i\rangle \langle e_i|$ directly give the probability of obtaining measurement outcome $\lambda_i$: if the system is in state $|\psi\rangle$, the probability of measuring $\lambda_i$ is $\langle \psi| (|e_i\rangle \langle e_i|) |\psi\rangle = |\langle e_i | \psi \rangle|^2$, which is precisely the Born rule. The eigenvalues $e^{i\theta}$ of unitary operators correspond to the phase factors accumulated during quantum evolution and play a key role in quantum interference and quantum algorithms. Thus, the content of this section is an indispensable theoretical foundation for understanding quantum measurement, quantum gate operations, and quantum algorithms. From quantum simulation to quantum chemistry calculations, from quantum optimization to quantum machine learning, solving eigenvalue problems is a core computational task.

1.6 Tensor Products & Composite Systems

In the preceding sections, we studied the mathematical description of a single qubit, whose state space is the two-dimensional Hilbert space $\mathbb{C}^2$. Real quantum computers, however, contain multiple qubits, and the state space of the entire system is no longer simply $\mathbb{C}^2$ but a much larger space constructed via the tensor product. The tensor product is the mathematical language for describing multi-body quantum systems and the necessary path to understanding quantum entanglement, a core quantum characteristic. This section builds on the vector spaces of Section 1.2 and the linear operators of Section 1.3 to systematically introduce the definition of the tensor product, its matrix representation (the Kronecker product), and the distinction between separable and entangled states. The tensor product is the key mathematical tool that takes quantum computing from single qubits to multiple qubits, from theory to practical application. Without the tensor product, we could not describe the joint state of multiple qubits, nor understand those core phenomena of quantum computing that transcend classical computational capabilities.

Definition of the Tensor Product

Given two vector spaces $V$ and $W$ with dimensions $\dim(V) = m$ and $\dim(W) = n$, their tensor product $V \otimes W$ is a new vector space whose dimension is:

$$\dim(V \otimes W) = \dim(V) \cdot \dim(W) = m \cdot n$$

For vectors $|v\rangle \in V$ and $|w\rangle \in W$, their tensor product is denoted $|v\rangle \otimes |w\rangle$, often abbreviated as $|v\rangle |w\rangle$ or $|v w\rangle$. The tensor product differs from the direct sum: the dimension of a direct sum space is the sum of the dimensions, while the dimension of a tensor product space is the product of the dimensions. This exponential growth is the mathematical root of the enormous computational power of quantum computing. For example, a two-qubit system requires a four-dimensional space to describe, three qubits require eight dimensions, and one hundred qubits require $2^{100}$ dimensions — a number far exceeding the total number of atoms in the universe. It is precisely this exponentially growing state space that enables quantum systems to encode and process information volumes that classical computers cannot simulate.

The tensor product satisfies the distributive law with respect to addition and scalar multiplication:

$$|v\rangle \otimes (\alpha |w_1\rangle + \beta |w_2\rangle) = \alpha (|v\rangle \otimes |w_1\rangle) + \beta (|v\rangle \otimes |w_2\rangle)$$ $$(\alpha |v_1\rangle + \beta |v_2\rangle) \otimes |w\rangle = \alpha (|v_1\rangle \otimes |w\rangle) + \beta (|v_2\rangle \otimes |w\rangle)$$

In general, however, $(|v_1\rangle + |v_2\rangle) \otimes (|w_1\rangle + |w_2\rangle) \neq |v_1\rangle \otimes |w_1\rangle + |v_2\rangle \otimes |w_2\rangle$. The correct expansion should contain four terms, reflecting the richness of the tensor product state space structure.

The Basis of a Two-Qubit System

Consider the most important case for quantum computing: $V = W = \mathbb{C}^2$. Let $\{|0\rangle, |1\rangle\}$ be the computational basis of $\mathbb{C}^2$. A natural basis for $\mathbb{C}^2 \otimes \mathbb{C}^2 = \mathbb{C}^4$ consists of the following four basis vectors:

$$|00\rangle = |0\rangle \otimes |0\rangle = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix}, \quad |01\rangle = |0\rangle \otimes |1\rangle = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix}$$ $$|10\rangle = |1\rangle \otimes |0\rangle = \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \end{pmatrix}, \quad |11\rangle = |1\rangle \otimes |1\rangle = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix}$$

where the column vector form follows from the concrete construction of the tensor product: if $|v\rangle = \begin{pmatrix} v_1 \\ v_2 \end{pmatrix}$ and $|w\rangle = \begin{pmatrix} w_1 \\ w_2 \end{pmatrix}$, then:

$$|v\rangle \otimes |w\rangle = \begin{pmatrix} v_1 w_1 \\ v_1 w_2 \\ v_2 w_1 \\ v_2 w_2 \end{pmatrix}$$

For example:

$$|0\rangle \otimes |0\rangle = \begin{pmatrix} 1 \cdot 1 \\ 1 \cdot 0 \\ 0 \cdot 1 \\ 0 \cdot 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix}$$

Verification of $|0\rangle \otimes |1\rangle$:

$$|0\rangle \otimes |1\rangle = \begin{pmatrix} 1 \cdot 0 \\ 1 \cdot 1 \\ 0 \cdot 0 \\ 0 \cdot 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix}$$

These four basis vectors form an orthonormal basis for $\mathbb{C}^4$, satisfying $\langle ij | kl \rangle = \delta_{ik}\delta_{jl}$. A general two-qubit state can be expanded in this basis:

$$|\psi\rangle = \alpha_{00}|00\rangle + \alpha_{01}|01\rangle + \alpha_{10}|10\rangle + \alpha_{11}|11\rangle$$

where the complex coefficients satisfy the normalization condition $|\alpha_{00}|^2 + |\alpha_{01}|^2 + |\alpha_{10}|^2 + |\alpha_{11}|^2 = 1$. A normalized vector in this four-dimensional complex vector space is a two-qubit quantum state. Notably, one overall phase among the four complex coefficients can be ignored, so a pure state of two qubits is actually described by six real parameters — far more than the two binary parameters of two classical bits.

Matrix Tensor Product: The Kronecker Product

Operators can also be combined via the tensor product. Given an $m \times m$ matrix $A$ and an $n \times n$ matrix $B$, their Kronecker product $A \otimes B$ is an $(mn) \times (mn)$ block matrix:

$$A \otimes B = \begin{pmatrix} a_{11}B & a_{12}B & \cdots & a_{1m}B \\ a_{21}B & a_{22}B & \cdots & a_{2m}B \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1}B & a_{m2}B & \cdots & a_{mm}B \end{pmatrix}$$

That is, each element $a_{ij}$ of $A$ is replaced by $a_{ij}B$. The Kronecker product satisfies the following important properties:

$$(A \otimes B)(|v\rangle \otimes |w\rangle) = (A|v\rangle) \otimes (B|w\rangle)$$

and:

$$(A \otimes B)(C \otimes D) = (AC) \otimes (BD)$$

The first property says that a tensor product operator acting on a tensor product state is equivalent to each operator acting on its respective subsystem. This accords with physical intuition: if two subsystems evolve independently, the overall evolution is the tensor product of the individual evolutions. The second property guarantees that multi-step evolution can proceed by sequential matrix multiplication.

Explicit Calculation: $2 \times 2$ Kronecker Product

Let us compute a concrete example. Take the Pauli $Z$ matrix and the Pauli $X$ matrix:

$$Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}, \quad X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$$

Compute $Z \otimes X$:

$$Z \otimes X = \begin{pmatrix} 1 \cdot X & 0 \cdot X \\ 0 \cdot X & (-1) \cdot X \end{pmatrix} = \begin{pmatrix} X & 0 \\ 0 & -X \end{pmatrix}$$

Expanded as a $4 \times 4$ matrix:

$$Z \otimes X = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & -1 \\ 0 & 0 & -1 & 0 \end{pmatrix}$$

Let us verify how this matrix acts on the tensor product state $|0\rangle \otimes |+\rangle$, where $|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$.

First compute $(Z \otimes X)(|0\rangle \otimes |+\rangle)$. Using the property of the Kronecker product, this equals $(Z|0\rangle) \otimes (X|+\rangle) = |0\rangle \otimes |+\rangle$, because $Z|0\rangle = |0\rangle$ ($|0\rangle$ is an eigenvector of $Z$ with eigenvalue $+1$) and $X|+\rangle = |+\rangle$ ($|+\rangle$ is an eigenvector of $X$ with eigenvalue $+1$; see Section 1.5).

Verify with matrix multiplication: $|0\rangle \otimes |+\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 1 \\ 0 \\ 0 \end{pmatrix}$.

$$(Z \otimes X) \cdot \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 1 \\ 0 \\ 0 \end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & -1 \\ 0 & 0 & -1 & 0 \end{pmatrix} \begin{pmatrix} 1 \\ 1 \\ 0 \\ 0 \end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 1 \\ 0 \\ 0 \end{pmatrix}$$

Verification holds. This shows that $|0\rangle \otimes |+\rangle$ is an eigenvector of $Z \otimes X$ with eigenvalue $+1$.

Now compute $X \otimes Z$:

$$X \otimes Z = \begin{pmatrix} 0 \cdot Z & 1 \cdot Z \\ 1 \cdot Z & 0 \cdot Z \end{pmatrix} = \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & -1 \\ 1 & 0 & 0 & 0 \\ 0 & -1 & 0 & 0 \end{pmatrix}$$

Note that the tensor product does not generally satisfy the commutative law: $Z \otimes X \neq X \otimes Z$. This is consistent with physical intuition about quantum systems: a $Z$ operation on the first qubit and an $X$ operation on the second qubit is different from an $X$ operation on the first qubit and a $Z$ operation on the second qubit. Different ordering of operations leads to different physical results. This non-commutativity is the mathematical embodiment of why quantum gate operations cannot be freely reordered.

The Controlled-NOT (CNOT) Matrix

One of the most important two-qubit gates in quantum computing is the Controlled-NOT gate, or CNOT. Its physical meaning is: if the first qubit (the control) is in the $|1\rangle$ state, apply the $X$ gate (i.e., flip) to the second qubit (the target); if the control is in the $|0\rangle$ state, leave the target unchanged. The CNOT gate is one of the fundamental gates for achieving universal quantum computation. Without the CNOT gate, single-qubit gates alone cannot realize arbitrary quantum computations, because single-qubit gates can only operate on each qubit independently and cannot establish correlations between qubits.

Using the projection operators $P_0 = |0\rangle \langle 0| = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}$ and $P_1 = |1\rangle \langle 1| = \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}$ introduced in Section 1.4, the CNOT gate can be compactly expressed as:

$$\text{CNOT} = P_0 \otimes I + P_1 \otimes X$$

where $I$ is the $2 \times 2$ identity matrix. The physical meaning of this expression is very clear: when the control is 0 (projected onto $P_0$), the target remains unchanged ($I$); when the control is 1 (projected onto $P_1$), the target is flipped ($X$). This method of expressing conditional operations using projection operators can be generalized to more complex multi-controlled gates.

Let us expand this expression:

$$P_0 \otimes I = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} \otimes \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix}$$ $$P_1 \otimes X = \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix} \otimes \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$$

Adding these yields the $4 \times 4$ matrix of the CNOT gate:

$$\text{CNOT} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$$

Verify the action of the CNOT gate on the basis states:

• $\text{CNOT}|00\rangle = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}\begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} = |00\rangle$ (control is 0, target unchanged)
• $\text{CNOT}|01\rangle = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}\begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix} = |01\rangle$ (control is 0, target unchanged)
• $\text{CNOT}|10\rangle = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}\begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} = |11\rangle$ (control is 1, target flipped)
• $\text{CNOT}|11\rangle = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}\begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \end{pmatrix} = |10\rangle$ (control is 1, target flipped)

This is perfectly consistent with the definition of the CNOT gate. It is worth noting that the CNOT gate itself is a unitary matrix, satisfying $\text{CNOT}^\dagger \cdot \text{CNOT} = I$, which guarantees that the normalization condition of the quantum state is preserved after evolution.

Separable States and Entangled States

In multi-body quantum systems, state vectors fall into two categories. A separable state can be written as a single tensor product:

$$|\psi\rangle = |a\rangle \otimes |b\rangle$$

For example, $|0\rangle \otimes |+\rangle$ is a separable state. In such states, the properties of the two subsystems are “independent”: a measurement on one subsystem does not immediately affect the other. The measurement statistics of separable states can be described by classical probability theory. Any composite system in classical physics can be regarded as a statistical mixture of separable states.

However, not all states are separable. An entangled state is one that cannot be written as a single tensor product. The most classic example is the Bell state:

$$|\Phi^+\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$$

Let us verify that this is an entangled state. Suppose it can be decomposed as $|a\rangle \otimes |b\rangle$, where $|a\rangle = \alpha|0\rangle + \beta|1\rangle$ and $|b\rangle = \gamma|0\rangle + \delta|1\rangle$. Expanding:

$$|a\rangle \otimes |b\rangle = \alpha\gamma|00\rangle + \alpha\delta|01\rangle + \beta\gamma|10\rangle + \beta\delta|11\rangle$$

To match $\frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$, we need $\alpha\delta = 0$ and $\beta\gamma = 0$, but also $\alpha\gamma = \beta\delta = 1/\sqrt{2} \neq 0$, which is impossible. Hence $|\Phi^+\rangle$ cannot be decomposed as a single tensor product; it is an entangled state. The existence of entangled states is one of the most fundamental differences between quantum mechanics and classical physics.

Entangled states exhibit non-classical correlation properties: even if two qubits are spatially far apart, measuring one instantaneously affects the state of the other. Einstein called this “spooky action at a distance.” It is important to emphasize that this correlation cannot be used for superluminal communication, because measurement outcomes are random, and the two parties must compare results via a classical channel to discover the correlation. Entanglement is a core resource for quantum computing and quantum communication; quantum teleportation, superdense coding, and quantum error correction all depend on the manipulation of entangled states. We will develop the theory and applications of entanglement in detail in Section 3.3. Bell states are not only theoretically important but have been prepared and verified in numerous experiments and are among the most fundamental resource states in quantum information science.

Let us further examine how the tensor product manifests in a three-qubit system. The computational basis for three qubits is $|000\rangle, |001\rangle, \ldots, |111\rangle$, eight basis vectors in total, spanning the $\mathbb{C}^8$ space. A general pure state is:

$$|\psi\rangle = \sum_{i,j,k \in \{0,1\}} \alpha_{ijk} |ijk\rangle$$

The normalization condition requires $\sum |\alpha_{ijk}|^2 = 1$. This exponential growth means that describing the quantum state of $n$ qubits requires $2^n$ complex amplitudes, and even moderately sized quantum systems already far exceed the simulation capacity of classical computers. This is the precise mathematical root of the enormous computational potential of quantum computing: quantum systems naturally operate in an exponentially large space.

For three-qubit systems, we can also construct more complex entangled states. For example, the Greenberger-Horne-Zeilinger state (GHZ state):

$$|\text{GHZ}\rangle = \frac{1}{\sqrt{2}}(|000\rangle + |111\rangle)$$

This state is also entangled, and its entanglement structure is more complex than that of the two-qubit Bell state. In multi-body quantum systems, the forms and measures of entanglement constitute a rich field of study involving concepts such as entanglement entropy and entanglement spectrum. These tools play important roles in quantum error correction and quantum many-body physics.

The concept of the tensor product can also be generalized to two subsystems of different dimensions. For example, a composite system of one qubit and one qutrit (a three-level quantum system) has state space $\mathbb{C}^2 \otimes \mathbb{C}^3 = \mathbb{C}^6$. Tensor products of mixed dimensions have important applications in quantum communication and quantum cryptography. More generally, for any two finite-dimensional Hilbert spaces $\mathcal{H}_A$ and $\mathcal{H}_B$, the state space of the composite system is always their tensor product $\mathcal{H}_A \otimes \mathcal{H}_B$. This construction is the mathematical core of quantum mechanics as a fundamental physical theory, because it allows us to combine independent subsystems into a more complex whole while preserving the individual characteristics of each subsystem.

Summary:

This section introduced the tensor product as the mathematical tool for describing multi-body quantum systems. The dimension of the tensor product of two vector spaces is the product of their individual dimensions; the explicit basis of $\mathbb{C}^2 \otimes \mathbb{C}^2 = \mathbb{C}^4$ is $|00\rangle, |01\rangle, |10\rangle, |11\rangle$. The tensor product of operators is realized via the Kronecker product, and we gave the complete $4 \times 4$ matrix expansions of $Z \otimes X$ and $X \otimes Z$. We derived the $4 \times 4$ matrix representation of the most important two-qubit gate in quantum computing — the CNOT gate — and verified its action on the computational basis. Finally, we distinguished between the concepts of separable and entangled states, introduced the Bell state as the paradigmatic example of entanglement, and briefly discussed the central role of entanglement in quantum information. The tensor product is not merely a mathematical construction but the indispensable path to understanding the exponentially large state space of quantum computing and the non-classical correlations of quantum systems.

Connection to Quantum Computing:

The tensor product is the mathematical foundation of multi-qubit systems in quantum computing. The joint state space of $n$ qubits is $(\mathbb{C}^2)^{\otimes n} = \mathbb{C}^{2^n}$; the dimension grows exponentially with the number of qubits, which is the source of the potential computational power of quantum computing. Describing an $n$-bit system on a classical computer requires $n$ bits, whereas describing $n$ qubits on a quantum computer requires $2^n$ complex amplitudes — this exponential growth allows quantum systems to encode and process exponentially large amounts of information in parallel. The CNOT gate, together with single-qubit gates (such as the Hadamard gate $H$, the phase gate $S$, and the $T$ gate), forms a universal gate set: any quantum computation can be approximated to arbitrary precision by gates from this set. Entangled states such as Bell states are key resources for quantum algorithms (such as Shor’s algorithm and Grover’s algorithm) and quantum communication protocols. Understanding the tensor product and entanglement is the necessary path to mastering quantum computing as it moves from single qubits to multiple qubits, from theory to application. Every frontier area of modern quantum computing — from quantum error correction to quantum simulation, from quantum machine learning to quantum cryptography — is deeply rooted in the mathematical structures of the tensor product and entanglement.

---

1.7 Probability Theory Foundations

If you have ever tossed a coin, you have already encountered the intuition of probability: the chance of heads is $1/2$, and tails is also $1/2$. Quantum computing is equally inseparable from probability, but the probability system it uses differs fundamentally from the classical world. This section begins with familiar classical probability and progressively reveals the distinctive character of quantum probability. Probability theory is not only the foundation of modern statistics but also an indispensable path to understanding the mathematical framework of quantum mechanics. In quantum computing, we will frequently encounter concepts such as “the probability of a measurement outcome” and “the expectation value of a quantum state,” all of which rest on the axiomatic foundation of probability theory.

1.7.1 Probability Spaces

The set of all possible outcomes of a random experiment constitutes the sample space, denoted $\Omega$. For example, when tossing a fair coin, $\Omega = \{\text{heads}, \text{tails}\}$; when rolling a six-sided die, $\Omega = \{1,2,3,4,5,6\}$. Any subset of $\Omega$ is called an event.

A probability measure $P$ assigns to each event a number between $0$ and $1$, satisfying two axioms:

• Non-negativity and boundedness: For any event $A$, $0 \leq P(A) \leq 1$
• Normalization: The probability of the entire sample space is $1$, i.e., $P(\Omega) = 1$
• Additivity: If $A$ and $B$ are mutually exclusive (cannot occur simultaneously), then $P(A \cup B) = P(A) + P(B)$

These three axioms are the cornerstone of all of classical probability theory.

To gain a more intuitive understanding, we can imagine the sample space as a large box containing all possible outcomes. Each outcome is like a small ball in the box, and an event is a set composed of several balls. The role of the probability measure $P$ is to assign a “weight” to each such set — a weight that tells us the relative frequency with which the outcomes in that set appear when the random experiment is repeated. When two events are mutually exclusive, the probability of their union is simply the sum of their individual probabilities, which perfectly matches our everyday intuition: a coin cannot simultaneously land both heads and tails, so the probability of “heads or tails” is simply the sum of the two probabilities.

In quantum computing, the concept of the sample space will be generalized to a Hilbert space, and events will correspond to subspaces or projection operators in that space. This generalization preserves the core idea of the probability measure — assigning numerical values to “possibilities” — while endowing it with a much richer algebraic structure.

1.7.2 Random Variables

To describe random phenomena using numbers, we introduce the random variable $X$, which is a map from the sample space to the real numbers. Random variables fall into two categories:

Discrete random variables: take countably many values (such as the faces of a die). Their distribution is described by a probability mass function (PMF): $p(x_i) = P(X = x_i)$

Continuous random variables: take continuous values (such as the lifetime of an electronic component). Their distribution is described by a probability density function (PDF) $f(x)$, with the probability of the event $X \in [a,b]$ given by $P(a \leq X \leq b) = \int_a^b f(x)\, dx$

The introduction of random variables was a crucial step in making probability theory practical. By converting abstract “events” into concrete “numerical values,” we can quantitatively analyze and compute random phenomena. Discrete random variables are suited to describing countable outcomes, such as the number of times a particular eigenvalue appears in a quantum measurement; continuous random variables are suited to describing continuous variations in physical quantities, such as the position coordinate of a particle in space.

In quantum mechanics, an observable is essentially a special kind of random variable — except that its values are no longer fixed real numbers but are associated with the eigenvalues of measurement outcomes on a quantum state. When we measure a quantum system, the measurement outcome is a random variable whose probability distribution is determined by the expansion coefficients of the quantum state in the eigenbasis of that observable.

1.7.3 Expectation and Variance

The expectation describes the “average value” of a random variable. For a discrete random variable, the explicit definition of the expectation is $\mathbb{E}[X] = \sum_i x_i \, P(X = x_i)$ For a continuous random variable, $\mathbb{E}[X] = \int_{-\infty}^{\infty} x \, f(x)\, dx$

The variance measures the degree to which a random variable deviates from its expectation: $\text{Var}(X) = \mathbb{E}\left[(X - \mathbb{E}[X])^2\right] = \mathbb{E}[X^2] - \bigl(\mathbb{E}[X]\bigr)^2$

The second equality for the variance is a commonly used convenient form for calculations: first compute the expectation of $X^2$, then subtract the square of the expectation.

Expectation and variance are the two most important numerical characteristics for describing a random variable. The expectation tells us the “central location” of the random variable — if we were to repeat the experiment infinitely many times and take the average, that average would converge to the expectation. The variance tells us the “degree of dispersion” of the random variable — the larger the variance, the more the random variable’s values deviate from its center; the smaller the variance, the more concentrated the values are around the expectation.

In quantum mechanics, the concept of expectation corresponds to the quantum expectation value. For a quantum state $|\psi\rangle$ and an observable $A$, the expectation value is $\langle\psi|A|\psi\rangle$. This is precisely the mathematical object we frequently need to compute in quantum computing. Variance in quantum mechanics corresponds to uncertainty — the famous Heisenberg uncertainty principle is essentially an inequality relationship between the variances of two non-commuting observables. When we say “the measurement result of a certain physical quantity is uncertain,” mathematically we are saying that the variance of the random variable corresponding to that physical quantity is non-zero.

1.7.4 Conditional Probability and Bayes’ Theorem

Conditional probability describes the probability of one event occurring given that another event has occurred: $P(A \mid B) = \frac{P(A \cap B)}{P(B)}, \qquad P(B) > 0$

Bayes’ theorem reverses the conditional probability and occupies a central position in statistical inference: $P(A \mid B) = \frac{P(B \mid A) \, P(A)}{P(B)}$

Conditional probability and Bayes’ theorem are among the most philosophically profound concepts in probability theory. Conditional probability answers the question: when we acquire new information (that event $B$ has occurred), how should we update our belief about the probability of other events (event $A$)? Bayes’ theorem provides a mathematical framework for reversing the direction of inference — from the probability of “effect given cause” ($P(B \mid A)$, the likelihood) to the probability of “cause given effect” ($P(A \mid B)$, the posterior). This framework is not only the foundation of modern statistics and machine learning but also has deep connections to quantum measurement theory.

Numerical example: Suppose the prevalence of a certain disease is $1\%$ ($P(D)=0.01$), and the test accuracy is: probability of testing positive given the disease $P(T+ \mid D) = 0.99$, probability of testing positive given no disease $P(T+ \mid \neg D) = 0.05$. Then the probability of actually having the disease given a positive test result is $P(D \mid T+) = \frac{0.99 \times 0.01}{0.99 \times 0.01 + 0.05 \times 0.99} \approx 0.167$

This seemingly counterintuitive result (only about $16.7\%$ actually have the disease despite testing positive) is a testament to the power of conditional probability. Let us unpack this calculation in more detail: the numerator $0.99 \times 0.01 = 0.0099$ is the “true positive” probability — the joint probability of both having the disease and testing positive. The denominator consists of two parts: the first part is the true positive probability $0.0099$, and the second part is the “false positive” probability $0.05 \times 0.99 = 0.0495$, the probability of a healthy person being erroneously flagged as positive. The total denominator is $0.0099 + 0.0495 = 0.0594$, representing all cases that test positive (true or false). Thus, the probability of actually having the disease given a positive test is the proportion of true positives among all positives: $0.0099 / 0.0594 \approx 0.167$. The reason this result is so low is that the disease itself is rare (only $1\%$ prevalence), and the absolute number of false positives far exceeds that of true positives.

In quantum computing, the concept of conditional probability corresponds to quantum measurement update. When we perform a partial measurement on a quantum system and obtain a certain result, the quantum state of the system “collapses,” and the quantum state of the unmeasured part is also updated. Although this update process differs in mathematical form from classical conditional probability, both embody the idea of “revising the state of the system after acquiring new information” at the conceptual level.

1.7.5 Classical Probability vs. Quantum Probability

The most crucial distinction between classical probability and quantum probability is that the quantum world uses probability amplitudes rather than probabilities directly.

In classical probability, if an event can occur in two mutually exclusive ways, the total probability is the sum of the two: $P_{\text{total}} = P_1 + P_2$

In quantum mechanics, each way corresponds to a complex probability amplitude $\psi_1$ and $\psi_2$, and the observed probability is the squared modulus of the probability amplitude: $P_1 = |\psi_1|^2, \qquad P_2 = |\psi_2|^2$

When both ways coexist, the total probability amplitude is $\psi_1 + \psi_2$, and the corresponding probability is $P_{\text{total}} = |\psi_1 + \psi_2|^2 = |\psi_1|^2 + |\psi_2|^2 + \underbrace{\psi_1 \psi_2^* + \psi_1^* \psi_2}_{\text{interference term}}$

Note the appearance of the cross term (interference term)! This means $|\psi_1 + \psi_2|^2 \neq |\psi_1|^2 + |\psi_2|^2$

Using a simpler algebraic analogy: let $\psi_1 = a$, $\psi_2 = b$ be two complex numbers, then $|a + b|^2 = (a + b)(a^* + b^*) = |a|^2 + |b|^2 + a b^* + a^* b$

If $a$ and $b$ are real numbers, the cross term is $2ab$; if $ab < 0$, this term partially cancels the probability, leading to destructive interference; if $ab > 0$, we get constructive interference. It is precisely this interference effect that makes quantum particles behave like waves.

Double-slit analogy: Imagine a particle reaching a certain point on the screen via the left slit with probability amplitude $\psi_L$ and via the right slit with $\psi_R$. Classical thinking would tell you the total probability is $|\psi_L|^2 + |\psi_R|^2$; but quantum mechanics gives $|\psi_L + \psi_R|^2$. When the path-length difference between the two slits to that point causes $\psi_L \approx -\psi_R$, the cross term nearly cancels entirely, and the probability at that point approaches zero — this is the famous dark fringe of double-slit interference.

This distinction is the mathematical root of all the magic of quantum computing. The key to understanding this distinction is recognizing that in quantum mechanics, probability amplitudes are the fundamental physical quantities, and probabilities are merely derivatives of probability amplitudes. Probability amplitudes satisfy the linear superposition principle — two probability amplitudes can be added to obtain a new probability amplitude — but probabilities themselves do not satisfy this principle. This is why quantum systems can simultaneously exist in a “superposition state” of multiple states, whereas classical systems can only be in one state at a time.

At a deeper level, classical probability theory is built on the foundation of set theory — the sample space is a set of outcomes, events are subsets, and probability is a measure on sets. Quantum probability theory, by contrast, is built on the foundation of linear algebra — quantum states are vectors in a Hilbert space, observables are Hermitian operators, and probabilities are given by the inner product of the state vector and the operator. This transition from “sets” to “vector spaces” is the most fundamental mathematical difference between quantum mechanics and classical physics.

Summary:

This section constructed the basic framework of classical probability theory: probability spaces $(\Omega, P)$, random variables and their expectations and variances, conditional probability, and Bayes’ theorem. The core point is that classical probability is a measure on sets of events, and the probabilities of mutually exclusive events simply add. The key distinction of quantum probability is that probabilities are given by the squared modulus of complex probability amplitudes, and superposition produces an interference term $ab^* + a^*b$, so that the total probability does not equal the sum of the individual probabilities. The concepts of expectation and variance correspond in quantum mechanics to quantum expectation values and uncertainty, and are mathematical tools used frequently in the subsequent study of quantum algorithms. Conditional probability and Bayes’ theorem provide classical analogues for understanding quantum measurement updates.

Connection to Quantum Computing:

The state of a qubit in quantum computing is described by probability amplitudes, such as $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$, where the probability of measuring $|0\rangle$ is $|\alpha|^2$. The design of quantum algorithms is essentially the precise manipulation of probability amplitudes, using interference effects to amplify the probability amplitudes of correct answers and suppress those of incorrect answers. For example, Grover’s search algorithm, through constructive amplitude amplification, boosts the probability amplitude of the target state from $1/\sqrt{N}$ to nearly $1$. The calculation of quantum expectation values is an important means of evaluating the performance of quantum algorithms — we often need to compute the expectation value of some observable on the output state of an algorithm to determine whether the algorithm has achieved its intended optimization goal. Understanding the fundamental distinction between classical probability and quantum probability is an essential prerequisite for mastering the design philosophy of quantum algorithms.

---

1.8 Fourier Analysis Primer

If you have ever used music software to view the frequency spectrum of an audio clip, you have already encountered the intuition behind Fourier analysis: any complex sound can be decomposed into a superposition of sine waves of different frequencies. This idea of “decomposition and superposition” is the mathematical engine behind several key speedups in quantum algorithms. Fourier analysis is not only ubiquitous in signal processing, image compression, and communication engineering, but also plays a core role in quantum computing — the Quantum Fourier Transform (QFT) is the cornerstone of algorithms such as Shor’s algorithm and quantum phase estimation.

1.8.1 From Periodic Functions to Fourier Series

The astonishing insight of the Fourier series is that any sufficiently well-behaved periodic function $f(x)$ (with period $T$) can be written as an infinite series of complex exponentials: $f(x) = \sum_{n=-\infty}^{\infty} c_n \, e^{2\pi i n x / T}$

where the coefficients $c_n$ are given by an integral. This is equivalent to saying that the function space has an “orthonormal basis” $\{e^{2\pi i n x / T}\}$, and any periodic function can be expanded in this basis. Physically, this amounts to decomposing a signal into pure tones of different frequencies.

The core idea of the Fourier series is orthogonal decomposition. In three-dimensional space, any vector can be decomposed into the sum of its projections onto three mutually perpendicular coordinate axes. The Fourier series generalizes this idea to infinite-dimensional function spaces: the complex exponential functions $\{e^{2\pi i n x / T}\}$ act like “coordinate axes” in the function space, being mutually “orthogonal” (under a suitable inner product definition), and the Fourier coefficients $c_n$ are the “projected lengths” of the function $f(x)$ along these “coordinate axes.”

From a more intuitive perspective, the Fourier series tells us: a complex periodic waveform, no matter how irregular it may appear, is essentially a superposition of simple sine and cosine waves. The fundamental frequency $n=1$ corresponds to the “basic contour” of the waveform, while higher harmonics $n=2,3,\dots$ are responsible for depicting the “fine texture.” In quantum mechanics, this idea of “decomposition into fundamental modes” corresponds to expanding a quantum state in an energy eigenbasis — each energy eigenstate is like a “pure tone,” and any arbitrary quantum state of the system is a superposition of these “pure tones.”

1.8.2 The Continuous Fourier Transform

For non-periodic functions, we push the period to infinity and obtain the Fourier transform: $F(k) = \int_{-\infty}^{\infty} f(x) \, e^{-2\pi i k x}\, dx$

The inverse transform restores the time-domain (or spatial-domain) representation from the frequency-domain representation: $f(x) = \int_{-\infty}^{\infty} F(k) \, e^{2\pi i k x}\, dk$

This section does not delve into computational techniques; one need only remember the core intuition: the Fourier transform is a coordinate transformation between the “position basis” and the “frequency basis.”

The Fourier transform reveals a profound mathematical symmetry: the time domain and the frequency domain are two equivalent ways of describing the same signal, but with different emphases. In the time domain, we focus on the concrete variation of the signal over time; in the frequency domain, we focus on which frequency components the signal contains and the strength of each component. This is like describing the same person either by physical attributes such as “height, weight, age” or by social attributes such as “personality, hobbies, occupation” — the two descriptive approaches contain equivalent information but are suited to different analytical scenarios.

In quantum mechanics, this “time-frequency duality” corresponds to position-momentum duality. The wave function $\psi(x)$ of a quantum particle is the probability amplitude distribution in position space, and its Fourier transform $\tilde{\psi}(p)$ is the probability amplitude distribution in momentum space. The Heisenberg uncertainty principle $\Delta x \cdot \Delta p \geq \hbar/2$ is a direct mathematical corollary of this duality: the more localized a wave packet is in position space (the smaller $\Delta x$), the more spread out it is in momentum space (the larger $\Delta p$), and vice versa. This principle is equally important in quantum computing — when we try to read out quantum phase information with precision, we must strike a trade-off between measurement accuracy and the number of measurements.

1.8.3 The Discrete Fourier Transform (Focus)

In computation, we deal with a finite number of discrete data points. The Discrete Fourier Transform (DFT) acts on a complex vector $\mathbf{x} = (x_0, x_1, \dots, x_{N-1})$ of length $N$ and outputs another vector $\mathbf{y} = (y_0, y_1, \dots, y_{N-1})$ of length $N$, defined as $y_k = \sum_{j=0}^{N-1} x_j \, \omega_N^{jk}, \qquad k = 0, 1, \dots, N-1$

where $\omega_N = e^{2\pi i / N}$

is the primitive $N$-th root of unity.

The DFT can be written in a compact matrix form. Define the $N \times N$ DFT matrix $F_N$, whose element at row $j$, column $k$ is $(F_N)_{jk} = \omega_N^{jk}, \qquad j, k = 0, 1, \dots, N-1$

Then the DFT is the matrix-vector multiplication: $\mathbf{y} = F_N \mathbf{x}$.

The DFT is the bridge connecting the continuous world to discrete computation. In practical applications, we cannot process continuous functions; we can only sample them to obtain a finite number of discrete data points. The DFT tells us how to achieve a “frequency decomposition” similar to the continuous Fourier transform on discrete data points. The root of unity $\omega_N$ is the core of the DFT — it is uniformly distributed on the unit circle in the complex plane, like the tick marks on a clock face, with each tick corresponding to a “frequency component.”

The DFT also has an important property: it is the foundation of the circular convolution theorem. In the time domain, the circular convolution of two sequences corresponds to their pointwise product in the frequency domain. This property makes the DFT a powerful tool for fast convolution computation, with wide applications in digital filtering, pattern recognition, and other areas. In quantum computing, this property corresponds to the conversion of quantum states between the computational basis and the Fourier basis — the QFT can transform problems that are hard to analyze in the computational basis into ones that become simple and intuitive in the Fourier basis.

Explicit Example: The $2 \times 2$ DFT Matrix

When $N=2$, $\omega_2 = e^{2\pi i / 2} = e^{\pi i} = -1$. The matrix elements are $\omega_2^{jk} = (-1)^{jk}$: $F_2 = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$

Verification: for input $\mathbf{x} = (x_0, x_1)^T$, $y_0 = x_0 \cdot \omega_2^{0} + x_1 \cdot \omega_2^{0} = x_0 + x_1$ $y_1 = x_0 \cdot \omega_2^{0} + x_1 \cdot \omega_2^{1} = x_0 - x_1$

This is precisely the famous Hadamard transform, which is ubiquitous in quantum computing.

This simple $2 \times 2$ example reveals the most direct connection between the DFT and quantum computing. In quantum computing, the single-qubit Hadamard gate corresponds precisely to the normalized $F_2$ matrix: $H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$. The Hadamard gate is one of the most fundamental gates in quantum computing; it converts the computational basis state $|0\rangle$ into the uniform superposition state $\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$, and vice versa. From the perspective of Fourier analysis, the Hadamard gate is the “minimal DFT” on two points, converting information from the “time domain” (computational basis) to the “frequency domain” (superposition basis).

Explicit Example: The $4 \times 4$ DFT Matrix

When $N=4$, $\omega_4 = e^{2\pi i / 4} = e^{\pi i / 2} = i$. The matrix elements are $\omega_4^{jk} = i^{jk}$. Computing element by element (noting that $i^2 = -1$, $i^3 = -i$):

1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{pmatrix}

Observe this matrix: row 1 is all $1$‘s (the DC component); row 2 corresponds to frequency $1$; row 3 to frequency $2$ (the Nyquist frequency); row 4 to frequency $3$, equivalent to frequency $-1$. The elements of each column (except column 1) sum to zero, reflecting orthogonality.

The $4 \times 4$ example reveals the richer structure of the DFT matrix. Note that each row of the matrix corresponds to a different “frequency mode”: row 1 is all equal elements (zero frequency, the DC component); row 2 is $(1, i, -1, -i)$ (sampled complex exponential of one full cycle); row 3 is $(1, -1, 1, -1)$ (sampled cosine of two full cycles, the Nyquist frequency); row 4 is $(1, -i, -1, i)$ (equivalent to sampling at negative frequency $-1$). This regularity endows the DFT matrix with strong symmetries — indeed, the column vectors of the DFT matrix are pairwise orthogonal, though their norms are $\sqrt{N}$ rather than $1$.

1.8.4 Complexity and Quantum Advantage

In classical computation, directly computing the DFT by definition requires $N^2$ complex multiplications and additions, i.e., a time complexity of $O(N^2)$. The Fast Fourier Transform (FFT) exploits the symmetries of $\omega_N$ to reduce the complexity to $O(N \log N)$ — a landmark achievement in digital signal processing.

The core idea of the FFT is divide and conquer. It cleverly decomposes a DFT of length $N$ into a combination of two DFTs of length $N/2$ — one acting on the even-indexed samples, the other on the odd-indexed samples. This decomposition can be applied recursively until the subproblems become trivially simple. Since each decomposition halves the problem size and the number of decomposition layers is $\log_2 N$, the total complexity drops from $O(N^2)$ to $O(N \log N)$. This “divide and conquer” strategy is one of the most powerful ideas in algorithm design, and the FFT is one of its most elegant applications to mathematical structure.

Quantum computing, however, provides an exponentially greater speedup. The Quantum Fourier Transform (QFT) is implemented on $n = \log_2 N$ qubits and requires only $O(n^2) = O((\log N)^2)$ quantum gate operations.

Note a subtle but crucial distinction: the DFT matrix $F_N$ itself is not a unitary matrix — its column vectors, though orthogonal, have norm $\sqrt{N}$ rather than $1$. The normalized QFT matrix $U_{\text{QFT}} = \frac{1}{\sqrt{N}} F_N$

is the unitary matrix, satisfying $U_{\text{QFT}}^{\dagger} U_{\text{QFT}} = I$. This is a direct manifestation of the requirement in quantum mechanics that evolution must be unitary. The QFT, as a unitary transformation, can be naturally implemented on a quantum circuit.

The reason the QFT can achieve exponential speedup is fundamentally quantum parallelism. In classical computation, processing $N$ data points requires operating on those $N$ values sequentially or in parallel; in quantum computation, $n$ qubits can simultaneously represent a superposition of $N = 2^n$ states. The QFT exploits this exponentially large state space, using a clever sequence of quantum gates, to “simultaneously” perform the Fourier transform on all $N$ basis states. This is not truly “parallel computation” — we do not have $N$ independent processors working simultaneously — but rather an exploitation of the mathematical structure of quantum superposition states, so that a quantum circuit containing only $O(n^2)$ gates equivalently performs a transform on an $N$-dimensional vector.

The table below compares the complexities of the three approaches:

Method	Time / Gate Complexity	Note
Direct DFT	$O(N^2)$	Classical
FFT	$O(N \log N)$	Classical optimal
QFT	$O((\log N)^2)$	Quantum, exponential speedup

The QFT is a subroutine of core algorithms such as Shor’s algorithm and quantum phase estimation. Section 3.6 will later unfold in detail the quantum circuit construction and analysis of the QFT.

Summary:

Fourier analysis provides a systematic toolkit for converting functions/signals from the “time domain” to the “frequency domain.” The DFT generalizes this transform to finite discrete data; its matrix form $F_N$ has the primitive $N$-th root of unity $\omega_N = e^{2\pi i / N}$ as its elements. The classical FFT reduces the DFT complexity from $O(N^2)$ to $O(N \log N)$, while the quantum Fourier transform requires only $O((\log N)^2)$ gate operations, achieving an exponential speedup. The key point is that the normalized QFT matrix is unitary and can be directly embedded into a quantum circuit. Understanding the matrix structure of the DFT, the properties of the roots of unity, and the divide-and-conquer philosophy of the FFT is the mathematical foundation for mastering the quantum Fourier transform.

Connection to Quantum Computing:

The QFT is one of the most powerful general-purpose subroutines in the quantum algorithm library. Shor’s algorithm uses the QFT to extract the period from a periodic function, thereby breaking RSA encryption; Quantum Phase Estimation uses the QFT to read out the binary representation of a quantum eigenvalue; the core step of the HHL algorithm (quantum linear system solver) also relies on the QFT to perform frequency-domain operations. Understanding the matrix structure of the DFT and the properties of the roots of unity is an essential prerequisite for mastering these quantum algorithms. In particular, the direct correspondence between the $2 \times 2$ DFT matrix and the Hadamard gate, along with the periodic patterns exhibited by the $4 \times 4$ DFT matrix, are key intuitions for understanding the quantum circuit construction of the QFT. The quantum Fourier transform is not merely a mathematical tool but an exemplary demonstration of the exponential speedup capability of quantum computing — it proves to us that when an algorithm can fully exploit the mathematical structures of quantum superposition and interference, complexity barriers that appear unavoidable in classical computation can be exponentially broken.

---

Appendix

Common Misconceptions & FAQ: Companion Document for the Quantum Computing Primer

This document accompanies Quantum Computing Primer — From First Principles and aims to address the most frequently encountered confusions and misconceptions during the learning process. Each entry is structured as: “Common Misconception -> Correct Understanding -> Why It Matters -> Detailed Explanation,” with references to specific sections of the tutorial where appropriate.

---

Part I: Mathematical Foundations (5 Items)

---

Q1. Squared modulus of a complex number: Are $|z|^2$ and $|z^2|$ the same thing?

Common Misconception: Thinking that $|z|^2 = |z^2|$, because for real numbers $(|x|)^2 = |x^2|$ does hold.

Correct Understanding: For a complex number $z = a + bi$, $|z|^2 = a^2 + b^2$ (always a non-negative real number), while $z^2 = (a^2 - b^2) + 2abi$, and its modulus $|z^2| = \sqrt{(a^2 - b^2)^2 + (2ab)^2} = a^2 + b^2$. The two happen to be numerically equal, but they have entirely different meanings: $|z|^2$ is the square of the modulus, while $|z^2|$ is the modulus after squaring. The reason they are numerically equal is $|z^2| = |z\cdot z| = |z|\cdot|z| = |z|^2$ (moduli multiply under complex multiplication).

Why It Matters: Quantum measurement probability $P = |\langle\phi|\psi\rangle|^2$ uses the square of the modulus of the inner product, not the modulus after squaring the inner product. Distinguishing these two is crucial for subsequently understanding the Born rule.

Detailed Explanation: Complex multiplication corresponds to rotation and scaling (Section 1.1.5). The modulus is the scaling factor, and $|z_1 z_2| = |z_1||z_2|$. Hence $|z^2| = |z||z| = |z|^2$. But note that $|z|^2 = zz^*$ can be computed directly (multiply $z$ by its conjugate), while computing $|z^2|$ requires squaring first, then taking the modulus. In quantum computing, we almost always encounter $|\alpha|^2$ (squared modulus of a probability amplitude), not $|\alpha^2|$. Remember that taking the squared modulus after the inner product is the standard operation of the Born rule (Section 1.4).

---

Q2. Are the inner products $\langle\phi|\psi\rangle$ and $\langle\psi|\phi\rangle$ equal?

Common Misconception: Thinking that the inner product is symmetric, i.e., $\langle\phi|\psi\rangle = \langle\psi|\phi\rangle$ (a habit carried over from the real dot product).

Correct Understanding: The complex inner product satisfies conjugate symmetry: $\langle\phi|\psi\rangle = \langle\psi|\phi\rangle^*$. They are equal only when the result happens to be a real number. For example, Example 1.2 in Section 1.2.3: $\langle\phi|\psi\rangle = 3 + i$, while $\langle\psi|\phi\rangle = 3 - i = (3 + i)^*$.

Why It Matters: The conjugation of the first vector (the bra) in the inner product is the key to guaranteeing $\langle\psi|\psi\rangle \geq 0$ (Section 1.4) and is the mathematical foundation of the normalization condition for quantum states. Getting the order wrong when computing $|\langle\phi|\psi\rangle|^2$ would lead to an incorrect conjugate relationship.

Detailed Explanation: From the definition: $\langle\phi|\psi\rangle = \sum_k \beta_k^* \alpha_k$, while $\langle\psi|\phi\rangle = \sum_k \alpha_k^* \beta_k$. The two are precisely complex conjugates of each other. In quantum mechanics, $|\langle\phi|\psi\rangle|^2$ is interpreted as “the probability of measuring the state $|\psi\rangle$ and finding it in state $|\phi\rangle$,” so the order does not affect the final probability. However, the correct order must be used in intermediate calculations — conjugate the bra’s components first. A common mistake is to confuse the bra-ket order in a projection $P_v = |v\rangle\langle v|$: $\langle v|w\rangle$ is a scalar, whereas $|v\rangle\langle w|$ is an operator; the two are completely different (Section 1.4).

---

Q3. Are matrix products $AB$ and $BA$ the same?

Common Misconception: Thinking that matrix multiplication is commutative, because scalar multiplication is.

Correct Understanding: Matrix multiplication is generally not commutative: $AB \neq BA$. Section 1.3.5 gives the example: $\sigma_x \sigma_z = \begin{pmatrix}0&-1\\1&0\end{pmatrix}$, while $\sigma_z \sigma_x = \begin{pmatrix}0&1\\-1&0\end{pmatrix} = -\sigma_x \sigma_z$. More generally, $[A, B] = AB - BA$ is called the commutator and is one of the most fundamental algebraic structures in quantum mechanics.

Why It Matters: In quantum mechanics, the order of operators corresponds to the order of physical operations. Doing $X$ then $Z$ ($ZX$) versus $Z$ then $X$ ($XZ$) differs by a sign (Section 2.4). The Heisenberg uncertainty principle $[X, P] = i\hbar$ is, at its core, a consequence of non-commutativity. In quantum circuits, the order of gates cannot be arbitrarily swapped.

Detailed Explanation: The $(i,j)$ entry of a matrix product is the dot product of the $i$-th row of $A$ with the $j$-th column of $B$: $(AB)_{ij} = \sum_k A_{ik}B_{kj}$. The commutation relations of the Pauli matrices are central to quantum computing: $[X, Y] = 2iZ$, $[Y, Z] = 2iX$, $[Z, X] = 2iY$ (Section 1.3.5). More broadly, two observables $A$ and $B$ can be simultaneously measured with precision if and only if $[A, B] = 0$. This is the mathematical foundation for understanding the complementarity principle: position and momentum do not commute, and therefore cannot be simultaneously known with precision.

---

Q4. Eigenvectors are just vectors that get “stretched,” right?

Common Misconception: Interpreting the definition $A|v\rangle = \lambda|v\rangle$ of eigenvectors as “the vector is stretched by a factor of $\lambda$” and assuming $\lambda$ must be a positive real number.

Correct Understanding: Eigenvalues can be complex (for general matrices), can be negative, and can even be 0. The eigenvalues of unitary operators are complex numbers of modulus 1, $e^{i\theta}$, corresponding to rotation rather than stretching (Section 1.5). The Pauli $Z$ matrix has eigenvalues $+1$ and $-1$, corresponding to $|0\rangle$ remaining unchanged and $|1\rangle$ flipping sign.

Why It Matters: The eigenvalues of quantum gates (unitary operators) are all of the form $e^{i\theta}$, which guarantees that state normalization is not destroyed (Section 1.3). The phase $\theta$ of the eigenvalues is a core resource for quantum interference. Misunderstanding the “magnitude” of eigenvalues leads to an inability to understand why quantum gates do not alter the total probability amplitude.

Detailed Explanation: The true meaning of the eigenvalue equation $A|v\rangle = \lambda|v\rangle$ is: under the action of $A$, $|v\rangle$ does not change direction (the output of $A$ is parallel to $|v\rangle$). For Hermitian operators, $\lambda$ is real and represents a measurement outcome (Section 1.5, spectral theorem). For unitary operators, $U|v\rangle = e^{i\theta}|v\rangle$ means that $U$ merely adds a global phase factor $e^{i\theta}$ to $|v\rangle$. For example, the $T$ gate (Section 3.2) acting on $|1\rangle$ gives $T|1\rangle = e^{i\pi/4}|1\rangle$; this is not “stretching” but a phase rotation. Beginners often mistakenly think eigenvalues must be positive, and therefore find the $-1$ eigenvalue of the Pauli $Z$ strange — but physically this is precisely the mathematical formulation of a “phase flip.”

---

Q5. The tensor product $|v\rangle\otimes|w\rangle$ is just “putting two vectors side by side,” right?

Common Misconception: Thinking that the state space dimension of $n$ qubits is $n \times 2$ (e.g., 2 qubits = 4 dimensions), or confusing it with the direct sum $\oplus$.

Correct Understanding: The dimension of a tensor product space is the product of the dimensions of the subsystems: $\dim(\mathbb{C}^2)^{\otimes n} = 2^n$. The state space of $n$ qubits is $\mathbb{C}^{2^n}$, not $\mathbb{C}^{2n}$. For example, 2 qubits require 4 complex coefficients $\alpha_{00}, \alpha_{01}, \alpha_{10}, \alpha_{11}$ to describe (Section 1.6).

Why It Matters: The exponential growth of the state space is the fundamental source of the potential advantage of quantum computing. The state space of 50 qubits has $2^{50} \approx 10^{15}$ dimensions (Section 3.1), which classical computers cannot simulate directly. If one mistakenly thinks it is $2n = 100$ dimensions, the mathematical root of quantum advantage is entirely lost.

Detailed Explanation: The tensor product and the direct sum are two different ways of constructing spaces. The direct sum $\mathbb{C}^2 \oplus \mathbb{C}^2$ has dimension $2 + 2 = 4$, with 4 basis vectors, while the tensor product $\mathbb{C}^2 \otimes \mathbb{C}^2$ has dimension $2 \times 2 = 4$; the two happen to coincide numerically in this case but have different meanings. The difference becomes glaring at 3 qubits: the direct sum $\mathbb{C}^2 \oplus \mathbb{C}^2 \oplus \mathbb{C}^2$ has dimension 6, while the tensor product $(\mathbb{C}^2)^{\otimes 3} = \mathbb{C}^8$ has dimension 8. At $n=10$, the direct sum is 20, and the tensor product is 1024. The basis vectors of the tensor product are of the form $|i_1 i_2 \ldots i_n\rangle$ where each $i_k \in \{0,1\}$, giving $2^n$ arrangements (Section 1.6).

---

Part II: Physical Foundations (7 Items)

---

Q6. Is the superposition state $|+\rangle$ just “50% probability of $|0\rangle$ and 50% probability of $|1\rangle$”?

Common Misconception: Equating quantum superposition with a classical probabilistic mixture, thinking that $|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$ is the same state as “with 50% probability in $|0\rangle$ and 50% probability in $|1\rangle$.”

Correct Understanding: The two are fundamentally different. $|+\rangle$ is a pure state (a point on the surface of the Bloch sphere, Section 2.5), possessing a definite quantum phase relationship. “50% $|0\rangle$ + 50% $|1\rangle$” is the mixed state $\rho = \frac{I}{2}$ (the center of the Bloch sphere), which has completely lost coherence. The crucial test: measuring $|+\rangle$ in the $X$ basis deterministically yields $+1$ (because $|+\rangle$ is an eigenstate of $X$), whereas measuring the mixed state $\frac{I}{2}$ in the $X$ basis yields $\pm 1$ with equal probability (Section 2.6).

Why It Matters: Superposition states preserve the relative phase between probability amplitudes, which is the foundation of quantum interference. If $|+\rangle$ were merely a classical mixture, the double-slit experiment would not produce interference fringes (Section 2.1). Virtually all quantum algorithms (such as Grover’s search) rely on the coherent manipulation of probability amplitudes — if superposition were just a classical mixture, these algorithms could not work.

Detailed Explanation: Section 2.6 of the tutorial thoroughly clarifies this issue using density matrices. The density matrix of $|+\rangle$ is $\rho_A = \frac12\begin{pmatrix}1&1\\1&1\end{pmatrix}$, which has off-diagonal elements $1/2$, the hallmark of quantum coherence. The mixed state $\rho_B = \frac12\begin{pmatrix}1&0\\0&1\end{pmatrix}$ has no off-diagonal elements. Measuring $\langle X \rangle$: it is 1 for $\rho_A$ and 0 for $\rho_B$. Although both yield identical statistics when measured in the $Z$ basis (50% each), they are fundamentally different. The Bloch sphere picture (Section 2.5) illustrates this intuitively: pure states lie on the surface, mixed states lie in the interior.

---

Q7. Measurement is just “reading out information,” right?

Common Misconception: Equating quantum measurement with classical measurement — thinking that measurement passively reads out pre-existing properties of the system without affecting the system’s state.

Correct Understanding: Quantum measurement irreversibly changes the state of the system. According to the measurement postulate (Section 2.2, Postulate 4), measurement causes the state to collapse to the corresponding eigenstate. The probability of measurement outcome $a_i$ is given by the Born rule $P(a_i) = |\langle a_i|\psi\rangle|^2$, but the state after measurement becomes $|a_i\rangle$, and the original state $|\psi\rangle$ is destroyed.

Why It Matters: This property profoundly influences the design of quantum algorithms — measurement is typically placed at the end of the algorithm (Section 3.4), because once measurement occurs, the phase information in the quantum state is permanently lost. Quantum error correction faces the same challenge: we cannot directly “check” a quantum state without destroying it. Quantum cryptography (BB84), on the other hand, exploits this property to detect eavesdropping (Section 3.6).

Detailed Explanation: Section 3.5 of the tutorial discusses this property in detail. Take $|+\rangle$ measured in the $Z$ basis: the probability of obtaining 0 is $1/2$, and after measurement the state becomes $|0\rangle$. Even knowing the measurement result, one cannot recover $|+\rangle$ from $|0\rangle$ — the information is irreversibly lost. This is not because our “measurement precision is insufficient” but is a fundamental principle of quantum mechanics. The state after measurement, $\frac{P_i|\psi\rangle}{\sqrt{P(m_i)}}$, is the projection onto the eigenspace, and all the coherence information of the original superposition state is gone.

---

Q8. Does entanglement of two qubits imply superluminal communication?

Common Misconception: Since measuring one qubit in an entangled state “instantly affects” the other (regardless of distance), one can use it to achieve superluminal communication.

Correct Understanding: Superluminal communication is not possible. Although measuring one particle in an entangled state does instantly affect the state of the other particle (quantum mechanics recognizes this as nonlocal correlation), the outcome of a single measurement is completely random, and the sender cannot control the measurement result. To make use of entanglement, both parties must exchange measurement basis and outcome information via a classical channel (at or below the speed of light) (Section 3.6, teleportation). Without a classical channel, entanglement alone cannot transmit any information.

Why It Matters: The Bell state $|\Phi^+\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$ demonstrates the nonlocality of quantum mechanics, but this property does not violate special relativity (Section 2.6). Understanding this point is crucial for correctly appreciating how quantum communication (such as quantum key distribution and quantum teleportation) works. Entanglement + classical communication = quantum information transfer; neither is sufficient alone.

Detailed Explanation: The reduced density matrix in Section 2.6 of the tutorial reveals the reason clearly. For the Bell state, the reduced density matrix of the subsystem is $\rho_A = \frac{I}{2}$, a maximally mixed state — no measurement Alice can perform will change her own reduced density matrix, nor can it convey information to Bob. In the Bell state $|\Phi^+\rangle$, if Alice measures her qubit and gets 0, she knows Bob’s qubit is also 0, but without Alice telling him, Bob still measures his qubit and gets 0 with 50% probability — Bob cannot distinguish “Alice has already measured” from “Alice has not measured yet” (Section 3.3). Classical communication of the measurement outcome is necessary for both parties to establish correlations.

---

Q9. Can both the global phase and the relative phase be ignored?

Common Misconception: The tutorial mentions that “the global phase does not affect physical observations,” leading beginners to think that all phases are unimportant.

Correct Understanding: The global phase (multiplying the entire state by $e^{i\gamma}$) is unobservable, because $P = |e^{i\gamma}\alpha|^2 = |\alpha|^2$ — the squared modulus cancels the global factor. But the relative phase (the phase difference between two components) is crucial; it directly determines measurement probabilities and interference patterns (Section 2.4). For example, $|+\rangle = (|0\rangle + |1\rangle)/\sqrt{2}$ and $|-\rangle = (|0\rangle - |1\rangle)/\sqrt{2}$ differ only by a relative phase of $\pi$, yet when measured in the $X$ basis, the former deterministically yields $+1$ and the latter deterministically yields $-1$.

Why It Matters: The entire power of quantum algorithms comes from the precise manipulation of relative phases. Grover’s algorithm marks the target state through a “phase flip” (Section 3.6), and Shor’s algorithm extracts phase information through the QFT (Section 1.8). If relative phases were unimportant, these algorithms would completely fail.

Detailed Explanation: On the Bloch sphere (Section 2.5), the global phase corresponds to rotating the entire sphere about the $z$-axis without changing the position of a point (equivalent to multiplying all states by the same $e^{i\gamma}$). The relative phase $\phi$ corresponds to the azimuthal angle of the point — changing $\phi$ does move the point’s position on the sphere. Concretely: $|\psi\rangle = \frac{1}{\sqrt{2}}(|0\rangle + e^{i\phi}|1\rangle)$ yields a probability of $+1$ when measured in the $X$ basis of $\cos^2(\phi/2)$; when $\phi = 0$ the probability is 1, and when $\phi = \pi$ it is 0 — the relative phase directly determines the measurement outcome.

---

Q10. Is quantum mechanical probability just due to our “ignorance” of the system’s true state?

Common Misconception: Drawing an analogy between the probabilistic nature of quantum mechanics and classical statistical mechanics, thinking that probability stems from “ignorance” of the system’s microscopic state (a hidden-variable viewpoint).

Correct Understanding: In standard quantum mechanics (the Copenhagen interpretation), the probabilities of measurement outcomes are intrinsic and independent of the observer’s knowledge. Even with complete knowledge of the quantum state $|\psi\rangle$, one cannot predict the outcome of a single measurement — quantum mechanics allows multiple possible outcomes to coexist with definite probabilities. Bell inequality experiments (though not covered in detail in the tutorial) have confirmed that no local hidden-variable theory can reproduce all the predictions of quantum mechanics.

Why It Matters: Understanding the intrinsic nature of quantum probability helps correctly understand the “one-shot” character of quantum algorithms. Quantum computation is not “searching all possibilities in parallel” (see Q14) but a coherent manipulation of probability amplitudes. Quantum randomness is also the cornerstone of the security of quantum cryptography (Section 3.6, BB84): if an eavesdropper cannot predict measurement outcomes, eavesdropping can be detected through statistical tests.

Detailed Explanation: Section 1.7 of the tutorial contrasts classical probability and quantum probability: in classical probability, the probabilities of mutually exclusive events add directly, $P_{\text{total}} = P_1 + P_2$; in quantum probability, probability amplitudes are added first and then the squared modulus is taken, $P_{\text{total}} = |\psi_1 + \psi_2|^2$, producing an interference term. This interference effect cannot be explained as “our ignorance of the system” — interference requires coherent superposition, whereas in a classical mixture there are no coherence relations among the components. The double-slit experiment (Section 2.1), in which a single electron “passes through both slits at once” and interferes with itself, is the most direct evidence for the intrinsic nature of quantum probability.

---

Q11. Is a qubit just a state “between” 0 and 1?

Common Misconception: Interpreting $0 \leq \alpha, \beta \leq 1$ as “between 0 and 1,” as though a qubit is a continuous transitional state between 0 and 1.

Correct Understanding: In the qubit state $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$, $\alpha$ and $\beta$ are complex numbers, not merely real percentages. $|0\rangle$ and $|1\rangle$ are orthogonal directions in a two-dimensional space, and the superposition state $|\psi\rangle$ is a unit vector in the entire space, not a “partially 0, partially 1” analog signal. Use the Bloch sphere (Section 2.5) for understanding: a qubit corresponds to any point on the unit sphere surface, not just the line segment connecting the north pole (0) and the south pole (1).

Why It Matters: If a qubit were merely “partially 0, partially 1,” it would be at best equivalent to a probabilistic bit and would not produce quantum advantage. The complex nature of probability amplitudes, phase interference, and the ability to entangle are the true reasons quantum computing transcends classical computation.

Detailed Explanation: A classical probabilistic bit can be described by a parameter $p \in [0, 1]$ representing “the probability of being 1”; its state space is a line segment. The state space of a qubit is the entire Bloch sphere surface (plus the interior for mixed states), a far higher-dimensional object. The density matrix of a probabilistic bit, $\rho = (1-p)|0\rangle\langle0| + p|1\rangle\langle1|$, has no off-diagonal elements, while the pure-state density matrix of a qubit, $\rho = |\psi\rangle\langle\psi|$, does have off-diagonal elements — the signature of coherence (Section 2.6).

---

Q12. Is the Heisenberg uncertainty principle a problem with measurement instruments?

Common Misconception: Thinking that the uncertainty principle $\Delta x \cdot \Delta p \geq \hbar/2$ arises because measurement instruments “disturb” the system — measuring position jostles the momentum.

Correct Understanding: The uncertainty principle is a fundamental axiom of quantum mechanics, not a matter of measurement precision. It is a direct mathematical corollary of the non-commutativity of operators $[x, p] = i\hbar$ (Section 1.5 of the tutorial). Even with perfect measurement equipment, position and momentum cannot be simultaneously determined with precision — this is a property of the quantum system itself, independent of measurement technology.

Why It Matters: In quantum computing, the complementarity principle (a generalization of the uncertainty principle) means that certain information can only be acquired at the expense of losing other information. For example, in the BB84 protocol (Section 3.6), measuring in the wrong basis irreversibly disturbs the quantum state, which is the foundation of the security of quantum cryptography.

Detailed Explanation: Strictly speaking, for any two non-commuting operators $A$ and $B$, we have $\Delta A \cdot \Delta B \geq \frac{1}{2}|\langle[A, B]\rangle|$, where $\Delta A = \sqrt{\langle A^2\rangle - \langle A\rangle^2}$ is the standard deviation. The tutorial points out in Section 1.7 that variance (the square of the standard deviation) in quantum mechanics corresponds to uncertainty. This inequality is a consequence of operator algebra and is independent of measurement equipment. A more intuitive understanding comes from Fourier analysis (Section 1.8): the narrower a wave packet is in position space, the broader it is in momentum space (the Fourier transform of the position wave function) — this is a mathematical necessity, not a defect of measurement instruments.

---

Part III: Quantum Computing (10 Items)

---

Q13. Do quantum computers achieve speedup by “trying all possible solutions”?

Common Misconception: Thinking that quantum parallelism means “a quantum computer checks all $2^n$ possible inputs simultaneously and then selects the correct answer,” analogous to having $2^n$ classical processors working in parallel.

Correct Understanding: Quantum parallelism is not equivalent to exponential parallel computation. Although $n$ qubits can indeed be in a superposition of all $2^n$ basis states, a measurement can only read out one result (probabilistically). The core challenge of quantum algorithms is: how to use unitary transformations and interference to amplify the probability amplitude of the correct answer to near 1 while canceling the probability amplitudes of incorrect answers — this requires ingenious algorithm design, not simply “running in parallel.”

Why It Matters: This is the most widespread beginner misconception about quantum computing. The $\sqrt{N}$ speedup of Grover’s search (rather than an $N \to 1$ collapse) is the best evidence: if one truly “tried all $N$ items simultaneously,” one query should find the answer, but in reality $O(\sqrt{N})$ queries are needed (Section 3.6).

Detailed Explanation: The Deutsch-Jozsa algorithm in Section 3.6 of the tutorial demonstrates the true nature of quantum parallelism. The algorithm prepares a uniform superposition state $\frac{1}{\sqrt{2^n}}\sum_x|x\rangle$, and one call to the quantum oracle does indeed simultaneously “process” all $x$, but the output state is $\frac{1}{\sqrt{2^n}}\sum_x (-1)^{f(x)}|x\rangle$. Ultimately, Hadamard gates and interference effects extract global properties (constant vs. balanced), rather than reading out all values of $f(x)$. The key point is that quantum parallelism is not “parallel computation” but “parallel manipulation of probability amplitudes” — encoding a function into the phases of probability amplitudes and then using interference to extract global information. A single query cannot read out all results simultaneously; this is a direct constraint of the no-cloning theorem (Section 3.3).

---

Q14. Does the no-cloning theorem mean no quantum information can be copied at all?

Common Misconception: Thinking that the no-cloning theorem forbids any form of copying of quantum information.

Correct Understanding: The specific statement of the no-cloning theorem (Section 3.3) is: there does not exist a single unitary operation $U$ such that for any unknown quantum state $|\psi\rangle$, $U|\psi\rangle|0\rangle = |\psi\rangle|\psi\rangle$. However, known quantum states can be copied (prepared afresh), and we can clone orthogonal quantum states (for example, $|0\rangle$ and $|1\rangle$ can be copied using a CNOT gate). The no-cloning theorem forbids the perfect copying of a general unknown quantum state.

Why It Matters: This subtle distinction directly explains why classical error correction can simply “triple repeat” (000, 111), while quantum error correction requires more complex encoding schemes (such as the Shor code). In classical computation, copying a bit is trivial; in quantum computation, we cannot simply back up an unknown state in triplicate.

Detailed Explanation: The crux of the proof lies in linearity. Suppose a universal cloning machine $U$ exists such that $U|\psi\rangle|0\rangle = |\psi\rangle|\psi\rangle$. If this holds for both $|\psi\rangle$ and $|\phi\rangle$, then for the superposition $|\xi\rangle = (|\psi\rangle + |\phi\rangle)/\sqrt{2}$, linearity gives $U|\xi\rangle|0\rangle = (|\psi\rangle|\psi\rangle + |\phi\rangle|\phi\rangle)/\sqrt{2}$, whereas directly cloning $|\xi\rangle$ would require $(|\psi\rangle + |\phi\rangle)(|\psi\rangle + |\phi\rangle)/2$. These are unequal (unless $\langle\psi|\phi\rangle = 1$). Note that if $|\psi\rangle$ and $|\phi\rangle$ are orthogonal, one could first measure and then prepare — but measurement destroys the original state, so this is not “cloning.”

---

Q15. Is quantum teleportation the “instantaneous transport” of matter?

Common Misconception: Influenced by science fiction, thinking that quantum teleportation (Section 3.6) can instantaneously transport objects from one place to another.

Correct Understanding: Quantum teleportation transports the quantum state (information), not matter itself. Moreover, the process requires a classical communication channel (2 classical bits of information) and does not exceed the speed of light. Teleportation also does not copy the quantum state (no-cloning theorem) — Alice’s original state is destroyed in the measurement process, and the state Bob receives is “reconstructed,” not “copied.”

Why It Matters: Teleportation is a perfect example of “entanglement + classical communication,” demonstrating how quantum information and classical information work together (Section 3.6). It violates neither relativity nor the notion of sci-fi “beaming,” but is the core principle behind quantum communication and quantum repeaters.

Detailed Explanation: Review the teleportation circuit in Section 3.6 of the tutorial. Alice and Bob share a Bell state $|\Phi^+\rangle_{AB}$. Alice performs a CNOT and an $H$ gate on her two qubits ($|\psi\rangle$ + her half of the Bell state), then measures, obtaining a 2-bit classical result $(m, n)$. Alice transmits $(m, n)$ to Bob via a classical channel. Bob then applies $X^m Z^n$ to his qubit, which becomes precisely $|\psi\rangle$. Throughout the process, the quantum state does not “fly” across space — classical information propagates at the speed of light, and entanglement is consumed as a resource. Teleportation cannot be superluminal because Bob must receive the classical information before reconstructing the state.

---

Q16. Does Grover’s algorithm provide exponential speedup for any search problem?

Common Misconception: Thinking that Grover’s algorithm provides the same kind of exponential speedup as Shor’s algorithm (since both arise from quantum effects).

Correct Understanding: Grover’s algorithm provides a quadratic speedup: classical $O(N)$ to quantum $O(\sqrt{N})$, not exponential (Section 3.6). The magnitude of the speedup is limited — in a database of 1 million items, a classical search needs about 500,000 queries, while a quantum search needs about 500. Shor’s algorithm, by contrast, provides an exponential speedup: classical sub-exponential $O(\exp((\log N)^{1/3}))$ to quantum $O((\log N)^3)$.

Why It Matters: Different types of speedup correspond to different application scenarios. Grover’s quadratic speedup, while not changing the computational complexity class of a problem (NP-complete problems under Grover’s algorithm are still exponential time), has practical value for real database searching. Shor’s exponential speedup changes the computational complexity of the problem (factorization goes from hard to easy), threatening the foundations of RSA encryption.

Detailed Explanation: The core of Grover’s algorithm is amplitude amplification (Section 3.6). Each Grover iteration consists of: (1) flipping the phase of the target state (via the oracle); (2) reflecting about the mean (the Grover diffusion operator). Each iteration increases the probability amplitude of the target state by about $2/\sqrt{N}$, so after roughly $\frac{\pi}{4}\sqrt{N}$ iterations, the target state’s probability is close to 1. This $O(\sqrt{N})$ lower bound has been proven optimal — no quantum search algorithm can beat $\Omega(\sqrt{N})$. So Grover’s is a quadratic, not exponential, speedup, and this is not an implementation-level limitation but a fundamental information-theoretic bound.

---

Q17. Can Shor’s algorithm be run directly on existing quantum computers?

Common Misconception: Seeing that Shor’s algorithm has only $O((\log N)^3)$ complexity, thinking that breaking RSA is imminent and that existing quantum computers can run it.

Correct Understanding: The complexity analysis of Shor’s algorithm applies to an ideal, noiseless quantum computer. To factor a 2048-bit RSA key requires roughly several thousand logical qubits, and each logical qubit requires several thousand physical qubits protected by error correction (Section 3.7). This means the number of physical qubits needed reaches into the millions. Currently, the best quantum processors (such as Willow) have only about 105 physical qubits, and gate fidelities are still far from the error-correction threshold.

Why It Matters: This misconception leads to both excessive optimism and excessive pessimism about “when quantum computing will threaten encryption.” The reality is: until error-corrected quantum computers arrive, RSA is safe, but “harvest now, decrypt later” strategies do face real risk.

Detailed Explanation: The “quantum part” of Shor’s algorithm is indeed efficient — the quantum Fourier transform requires only $O(n^2)$ gates, where $n = \log N$ is the number of bits. But to run Shor’s algorithm one needs: (1) enough logical qubits (roughly $2n$); (2) sufficiently low physical error rates to make quantum error correction feasible (the surface code’s error-correction threshold is roughly 1%); (3) enough physical qubits to implement error-correcting codes (roughly 1000 physical qubits per logical qubit). Current quantum processors (Section 3.7) are several orders of magnitude short in both physical qubit count and fidelity.

---

Q18. Does “quantum advantage” mean “quantum computers surpass classical computers on all tasks”?

Common Misconception: Thinking that demonstrations of quantum advantage (such as Sycamore’s 2019 random circuit sampling) mean quantum computers have already “defeated” classical computers.

Correct Understanding: Quantum advantage is problem-specific, not about general computational capability (Section 3.7). Sycamore’s random circuit sampling (RCS) task itself has no practical commercial value — its output is a string of random bits. Moreover, after each quantum advantage demonstration, classical algorithms tend to close the gap within months (e.g., tensor network algorithms reduced the simulation time of Sycamore-class circuits from days to hours). Quantum advantage is an ongoing “arms race,” not a one-time victory.

Why It Matters: Correctly understanding the current state of quantum advantage helps set realistic expectations. Quantum computing may deliver genuine commercial value in areas such as quantum chemistry simulation (e.g., catalyst design for nitrogen fixation), combinatorial optimization, and machine learning, but such “useful” quantum advantage may still be 5-10 years away (Section 3.7).

Detailed Explanation: Section 3.7 of the tutorial discusses this trade-off in detail. Sycamore (53 qubits) claimed 200 seconds for an RCS task that would take a classical computer 10,000 years, but IBM soon pointed out that using better classical algorithms and memory hierarchies could reduce simulation time to 2.5 days. In 2023-2024, new tensor network algorithms reduced it further. Willow (105 qubits) in 2024 reopened the gap (estimated $10^{25}$ years classically, about 5 minutes on Willow), but RCS is still not a “useful” computation. As the tutorial states: “Quantum advantage is not a one-time achievement but an ongoing process.”

---

Q19. Do noisy quantum algorithms like VQE not need error correction?

Common Misconception: Thinking that variational algorithms in the NISQ (Noisy Intermediate-Scale Quantum) era, such as VQE, are completely unaffected by noise because they are “noise-resilient.”

Correct Understanding: Variational quantum-classical hybrid algorithms like VQE do have a certain tolerance to noise — through parameterized quantum circuits and classical optimization, the impact of noise can be partially suppressed. But this does not mean they do not need error correction. As the number of qubits increases, noise effects accumulate, and VQE’s quality degrades severely. VQE merely “works as well as possible under existing noise levels,” not as a “substitute for the noiseless case.”

Why It Matters: This misconception leads to unrealistic expectations about the practicality of NISQ algorithms. Many theoretical analyses assume “sufficiently low noise,” but the noise levels of actual quantum hardware (in particular, two-qubit gate error rates of about 0.1-1%) have a significant impact on the accuracy of algorithms such as VQE. This is the crux of the current debate in quantum computing between the “noisy” and “error-corrected” technical roadmaps (Section 3.7 of the tutorial and the content of Chapter 5).

Detailed Explanation: The basic idea of VQE (content of Chapter 5 of the tutorial) is to treat the expectation value $\langle\psi(\theta)| H |\psi(\theta)\rangle$ of the problem Hamiltonian as a loss function and update the circuit parameters $\theta$ through a classical optimizer. Noise introduces errors at every time step: gate errors cause $|\psi(\theta)\rangle$ to deviate from the target state, and measurement errors bias the expectation value estimate. As the circuit depth increases, these errors accumulate and can lead to “barren plateaus” in variational methods. In Google’s Sycamore experiment, two-qubit gate fidelity was about 99.5% (Section 3.7), which for a depth-20 VQE circuit implies an overall fidelity of roughly $(0.995)^{20} \approx 90\%$ — still acceptable, but for deeper circuits or higher precision requirements, error correction becomes indispensable.

---

Q20. Can the evolution “after” quantum state collapse be described by the Schrodinger equation?

Common Misconception: Thinking that the Schrodinger equation describes all evolution of a quantum system, including the measurement process.

Correct Understanding: The standard framework of quantum mechanics contains two distinct kinds of evolution (Section 2.2 of the tutorial):

1. Unitary evolution (Postulate 2): described by the Schrodinger equation $i\hbar\partial_t|\psi\rangle = H|\psi\rangle$, which is deterministic and reversible.
2. Measurement collapse (Postulate 4): described by the Born rule and the projection postulate, which is probabilistic and irreversible.

The two are fundamentally different processes. Measurement collapse cannot be described by the Schrodinger equation — this is precisely the heart of the “measurement problem.” The Schrodinger equation “fails” at the instant of measurement, as the system state discontinuously jumps from a superposition to an eigenstate.

Why It Matters: This distinction is key to understanding quantum computing. Quantum gate operations (unitary evolution) are deterministic and reversible; quantum measurement is probabilistic and destructive. Quantum algorithms typically place measurement at the end (Section 3.4), and all operations before measurement must be unitary evolution. If one mistakenly thinks measurement can also be described by the Schrodinger equation, one cannot understand why measurement destroys superposition states.

Detailed Explanation: Section 2.2 of the tutorial explicitly lists unitary evolution and measurement collapse as distinct postulates. Postulate 2 (unitary evolution) states: “The evolution of a closed system is described by a unitary operator $U$,” corresponding to the time evolution of the Schrodinger equation. Postulate 4 (measurement) states: “Measurement yields outcome $a_i$ with probability $|\langle a_i|\psi\rangle|^2$, and the system collapses to $|a_i\rangle$.” These two processes cannot be reduced to one another. Although the “quantum operation” formalism in quantum information theory (Kraus operators) can describe both in a unified way, this is mathematical unification only; physically they remain two distinct kinds of processes.

---

Q21. Are density matrices and pure state vectors completely different, mutually incompatible descriptions?

Common Misconception: Thinking that the density matrix is a “separate, independent” description of quantum states, having no direct relationship with the state vector $|\psi\rangle$.

Correct Understanding: The density matrix is a generalization of the state vector. The density matrix of a pure state is simply $\rho = |\psi\rangle\langle\psi|$ — this is the outer product of $|\psi\rangle$ (review the concept of projection operators in Section 1.4), not an independent object. A mixed state $\rho = \sum_i p_i |\psi_i\rangle\langle\psi_i|$ expresses classical uncertainty about which pure state the system is in (Section 2.6). Every description using pure states can be embedded into the density matrix framework, but the converse is not necessarily true.

Why It Matters: The density matrix framework unifies pure states, mixed states, subsystems, and measurement updates. When studying reduced density matrices (Section 2.6), if one does not know that $\rho = |\psi\rangle\langle\psi|$ is the density matrix of a pure state, one may be confused — “Why is a subsystem of an entangled pure state described by a mixed state?” The answer is: taking the partial trace over B of $\rho_{AB} = |\Phi^+\rangle\langle\Phi^+|$ yields $\rho_A = \frac{I}{2}$ — this does not “create” a mixed state, but means “when focusing only on subsystem A, it behaves like a mixed state.”

Detailed Explanation: The core advantage of the density matrix lies in unification. In the pure-state framework, we prepare a quantum state $|\psi\rangle$ and use projection operators $P_i$ to compute probabilities $P(m_i) = \langle\psi|P_i|\psi\rangle$. In the density matrix framework, $\rho = \sum_i p_i|\psi_i\rangle\langle\psi_i|$, the probability is $P(m_j) = \text{Tr}(\rho P_j)$, and the expectation is $\langle M \rangle = \text{Tr}(\rho M)$. The criterion for pure vs. mixed states (Section 2.6): $\text{Tr}(\rho^2) = 1$ for a pure state (e.g., $\rho_A = |+\rangle\langle+|$ has $\text{Tr}(\rho^2)=1$), and $\text{Tr}(\rho^2) < 1$ for a mixed state (e.g., $\frac{I}{2}$ has $\text{Tr}(\rho^2)=1/2$).

---

Q22. Is the QFT just a “quantum version of the FFT” that directly accelerates classical computation?

Common Misconception: Thinking that the Quantum Fourier Transform (QFT) can directly replace the classical FFT and accelerate classical signal-processing tasks.

Correct Understanding: The QFT cannot directly perform a Fourier transform on classical data. The QFT acts on the probability amplitudes of a quantum state, not on classical numerical values. To obtain classical Fourier transform results from the QFT requires quantum state tomography — which needs an exponentially large number of measurements, canceling the QFT’s speed advantage. The true value of the QFT lies in serving as a subroutine embedded in quantum algorithms, providing exponential speedup for the Fourier transform of quantum data (Section 1.8).

Why It Matters: This misconception leads to erroneous claims such as “the QFT can accelerate image processing, audio processing, etc.” The QFT is not an accelerated version of the classical FFT; its inputs and outputs are both quantum states — the reason the QFT is effective in Shor’s algorithm is that we need only measure the output’s frequency information (reading out the period from $|k\rangle$), not all $2^n$ amplitudes.

Detailed Explanation: The QFT transforms $|j\rangle$ into $\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\omega_N^{jk}|k\rangle$ (Section 1.8). This transformation requires only $O(n^2)$ gates, but the output is a superposition state. To extract classical information, one must measure — each measurement yields only one $k$ value, with probability $|y_k|^2$. To recover all $N$ Fourier coefficients requires $O(N)$ measurements. Hence the QFT cannot accelerate the classical computation of Fourier transforms. But in Shor’s algorithm, we only need to know the period $r$ satisfying $\omega_N^{jr} = 1$, which can be done efficiently with one measurement combined with the continued fraction algorithm — without needing to know all Fourier coefficients.

---

Appendix: Cross-Reference of FAQ Items to Tutorial Sections

Item	Topic	Core Reference Section	Difficulty
Q1	$	z	^2$vs.$
Q2	Conjugate symmetry of inner product	1.2.3, 1.4	1 star
Q3	Non-commutativity of matrices	1.3.5, 2.4	1 star
Q4	Eigenvalues and unitary operators	1.5, 3.2	2 stars
Q5	Tensor product dimension	1.6, 3.1	1 star
Q6	Superposition vs. mixture	2.5, 2.6, 3.1	2 stars
Q7	Measurement collapse	2.2 Postulate 4, 3.5	2 stars
Q8	Entanglement and communication	2.6, 3.3, 3.6	3 stars
Q9	Global vs. relative phase	2.4, 2.5	2 stars
Q10	Intrinsic nature of quantum probability	1.7, 2.1	3 stars
Q11	The true face of a qubit	2.5, 3.1	1 star
Q12	The uncertainty principle	1.7, 1.8	2 stars
Q13	The truth about quantum parallelism	3.6	3 stars
Q14	The boundaries of no-cloning	3.3	2 stars
Q15	The principle of teleportation	3.6	2 stars
Q16	Grover’s speedup type	3.6	2 stars
Q17	The reality of Shor’s algorithm	1.8, 3.6, 3.7	3 stars
Q18	The limits of quantum advantage	3.7	2 stars
Q19	NISQ and noise	3.7, Chapter 5	3 stars
Q20	Two types of evolution	2.2	2 stars
Q21	Density matrices and pure states	2.6	2 stars
Q22	Correct application of the QFT	1.8	3 stars

---

Suggested Usage: After reading through the tutorial once, pick entries matching your level of difficulty. 1-star entries are suitable for consolidation after an initial read; 2-star entries for deeper understanding; 3-star entries are appropriate after studying Chapter 3 to test whether you have truly grasped the core ideas. This document encourages readers to return to the corresponding tutorial sections for re-reading when questions arise.

---

Exercises and Solutions

Quantum Computing Primer Companion Exercises | 20 Sections, 60 Problems Difficulty: 1 star Basic · 2 stars Comprehensive · 3 stars Advanced

---

Part I: Mathematical Foundations

---

1.1 Complex Numbers & Euler’s Formula

Exercise 1.1.1 (1 star) Complex Division

Compute $(3+4i)(2-i)/(1+i)$ and express it in the form $a+bi$.

Solution: Numerator = $(3+4i)(2-i)=6-3i+8i-4i^2=10+5i$. Divide by $1+i$:

$$\frac{10+5i}{1+i}=\frac{(10+5i)(1-i)}{(1+i)(1-i)}=\frac{10-10i+5i-5i^2}{2}=\frac{15-5i}{2}=7.5-2.5i$$

Verification: $(7.5-2.5i)(1+i)=7.5+7.5i-2.5i-2.5i^2=10+5i$, which matches.

---

Exercise 1.1.2 (2 stars) The Modulus-Squared Identity

Prove $|z_1+z_2|^2=|z_1|^2+|z_2|^2+2\operatorname{Re}(z_1\overline{z_2})$.

Solution: Let $z_j=a_j+ib_j$. Then $z_1+z_2=(a_1+a_2)+i(b_1+b_2)$.

$$|z_1+z_2|^2=(a_1+a_2)^2+(b_1+b_2)^2 = (a_1^2+b_1^2)+(a_2^2+b_2^2)+2(a_1a_2+b_1b_2)$$

Now $|z_1|^2+|z_2|^2=(a_1^2+b_1^2)+(a_2^2+b_2^2)$, and $\operatorname{Re}(z_1\overline{z_2})=a_1a_2+b_1b_2$. Hence the identity holds.

This is the mathematical root of quantum interference: the cross term $2\operatorname{Re}(z_1\overline{z_2})$ corresponds to the interference term. When the two complex numbers have opposite signs, the cross term is negative, producing destructive interference.

---

Exercise 1.1.3 (2 stars) Addition Formulas via Euler’s Formula

Use Euler’s formula $e^{i\theta}=\cos\theta+i\sin\theta$ to derive the formulas for $\sin(\theta+\phi)$ and $\cos(\theta+\phi)$.

Solution: $e^{i\theta}e^{i\phi}=(\cos\theta+i\sin\theta)(\cos\phi+i\sin\phi)$

Expanding = $(\cos\theta\cos\phi-\sin\theta\sin\phi)+i(\sin\theta\cos\phi+\cos\theta\sin\phi)$.

But $e^{i(\theta+\phi)}=\cos(\theta+\phi)+i\sin(\theta+\phi)$. Comparing real and imaginary parts:

$$\cos(\theta+\phi)=\cos\theta\cos\phi-\sin\theta\sin\phi,\quad \sin(\theta+\phi)=\sin\theta\cos\phi+\cos\theta\sin\phi$$

Complex multiplication equates to multiplying moduli and adding arguments; this is the geometric foundation of quantum phase rotations.

---

1.2 Vector Spaces & Hilbert Spaces

Exercise 1.2.1 (1 star) Linear Independence

Determine whether $|v_1\rangle=(1,0,i)^T,|v_2\rangle=(0,1,0)^T,|v_3\rangle=(i,0,1)^T$ are linearly independent in $\mathbb{C}^3$.

Solution: Set $\alpha_1|v_1\rangle+\alpha_2|v_2\rangle+\alpha_3|v_3\rangle=0$:

$$\begin{cases} \alpha_1+i\alpha_3=0 \\ \alpha_2=0 \\ i\alpha_1+\alpha_3=0 \end{cases}$$

From the first equation $\alpha_1=-i\alpha_3$. Substituting into the third: $i(-i\alpha_3)+\alpha_3=2\alpha_3=0$, so $\alpha_3=0$, and therefore $\alpha_1=\alpha_2=0$. The only solution is the trivial one; the vectors are linearly independent.

---

Exercise 1.2.2 (2 stars) Orthonormality of the Computational Basis

Verify that $|0\rangle=(1,0)^T,|1\rangle=(0,1)^T$ form an orthonormal basis for $\mathbb{C}^2$.

Solution: $\langle0|1\rangle=0$ (orthogonal), $\langle0|0\rangle=\langle1|1\rangle=1$ (normalized). Any $|\psi\rangle=(\alpha,\beta)^T=\alpha|0\rangle+\beta|1\rangle$ can be uniquely expanded, so this is a complete orthonormal basis.

---

Exercise 1.2.3 (2 stars) Dimension of a Function Space

Prove that the set of complex-coefficient polynomials of degree $\leq n$, denoted $P_n(\mathbb{C})$, is a complex vector space. Write down its dimension and a basis.

Solution: Polynomial addition and scalar multiplication are closed; the zero polynomial is the zero element; the additive inverse is $-p(x)$; all axioms are satisfied. A basis is $\{1,x,x^2,\ldots,x^n\}$, yielding $n+1$ linearly independent vectors, so $\dim(P_n)=n+1$.

For example, $f(x)=1+2x+3x^2$ has coordinate vector $(1,2,3,0,\ldots,0)^T$ in this basis.

---

1.3 Linear Operators & Matrix Representation

Exercise 1.3.1 (1 star) Pauli Matrix Products

Compute $XY$ and $YX$, and verify that $XY=iZ$ and $XY\neq YX$.

Solution:

$$X=\begin{pmatrix}0&1\\1&0\end{pmatrix},\; Y=\begin{pmatrix}0&-i\\i&0\end{pmatrix},\; Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}$$ $$XY=\begin{pmatrix}0&1\\1&0\end{pmatrix}\begin{pmatrix}0&-i\\i&0\end{pmatrix}=\begin{pmatrix}i&0\\0&-i\end{pmatrix}=iZ$$ $$YX=\begin{pmatrix}0&-i\\i&0\end{pmatrix}\begin{pmatrix}0&1\\1&0\end{pmatrix}=\begin{pmatrix}-i&0\\0&i\end{pmatrix}=-iZ$$

$XY=-YX$; the Pauli matrices anticommute, illustrating that the order of quantum gates affects the outcome.

---

Exercise 1.3.2 (2 stars) Verifying a Hermitian Matrix

Verify that $A=\begin{pmatrix}1&i\\-i&2\end{pmatrix}$ is Hermitian and find its eigenvalues.

Solution: $A^\dagger=\begin{pmatrix}1&(-i)^*\\(i)^*&2\end{pmatrix}^T=\begin{pmatrix}1&i\\-i&2\end{pmatrix}=A$, so $A$ is Hermitian.

Characteristic equation: $\det\begin{pmatrix}1-\lambda&i\\-i&2-\lambda\end{pmatrix}=(1-\lambda)(2-\lambda)-1=\lambda^2-3\lambda+1=0$

Solving yields $\lambda=\frac{3\pm\sqrt5}{2}$, both real, consistent with the property that Hermitian operators have real eigenvalues.

---

Exercise 1.3.3 (2 stars) Unitary Operators Preserve the Inner Product

Prove that a unitary operator $U$ (satisfying $U^\dagger U=I$) preserves the inner product: $\langle Uv|Uw\rangle=\langle v|w\rangle$.

Solution: $\langle Uv|Uw\rangle=(U|v\rangle)^\dagger(U|w\rangle)=\langle v|U^\dagger U|w\rangle=\langle v|I|w\rangle=\langle v|w\rangle$.

Thus unitary operators preserve the norm and orthogonality, guaranteeing that quantum states remain normalized after evolution.

---

1.4 Inner Products, Norms & Orthogonality

Exercise 1.4.1 (1 star) Inner Product and Norm

Let $|v\rangle=(1+i,2)^T$ and $|w\rangle=(i,1-i)^T$. Compute $\langle v|w\rangle$, $\||v\rangle\|$, and $\||w\rangle\|$.

Solution:

$\langle v|w\rangle=(1-i,2)(i,1-i)^T=(1-i)i+2(1-i)=i+1+2-2i=3-i$

$\||v\rangle\|=\sqrt{(1-i)(1+i)+4}=\sqrt{2+4}=\sqrt6$

$\||w\rangle\|=\sqrt{(-i)i+(1+i)(1-i)}=\sqrt{1+2}=\sqrt3$

---

Exercise 1.4.2 (2 stars) Proof of the Cauchy-Schwarz Inequality

For a complex inner product space $V$, prove $|\langle v|w\rangle|\leq\||v\rangle\|\cdot\||w\rangle\|$.

Solution: If $|w\rangle=0$ the inequality holds trivially. Suppose $|w\rangle\neq0$ and construct $|u\rangle=|v\rangle-\frac{\langle w|v\rangle}{\langle w|w\rangle}|w\rangle$.

$\langle w|u\rangle=\langle w|v\rangle-\frac{\langle w|v\rangle}{\langle w|w\rangle}\langle w|w\rangle=0$, so $|u\rangle\perp|w\rangle$.

By the Pythagorean theorem:

$$\||v\rangle\|^2=\||u\rangle\|^2+\frac{|\langle w|v\rangle|^2}{\||w\rangle\|^2}\geq\frac{|\langle w|v\rangle|^2}{\||w\rangle\|^2}$$

Hence $|\langle v|w\rangle|\leq\||v\rangle\|\cdot\||w\rangle\|$, with equality when $|u\rangle=0$ (the two vectors are linearly dependent).

---

Exercise 1.4.3 (2 stars) Projection Operator Matrix and Properties

For $|\psi\rangle=a|0\rangle+b|1\rangle$ (with $|a|^2+|b|^2=1$), write the matrix of $P=|\psi\rangle\langle\psi|$ and verify $P^2=P$, $P^\dagger=P$.

Solution: $P=\begin{pmatrix}a\\b\end{pmatrix}\begin{pmatrix}a^*&b^*\end{pmatrix}=\begin{pmatrix}|a|^2&ab^*\\a^*b&|b|^2\end{pmatrix}$.

Using $|a|^2+|b|^2=1$ to compute $P^2$:

• $(1,1)$ entry $=|a|^4+|a|^2|b|^2=|a|^2$
• $(1,2)$ entry $=|a|^2ab^*+ab^*|b|^2=ab^*$
• $(2,1)$ entry $=|a|^2a^*b+a^*b|b|^2=a^*b$
• $(2,2)$ entry $=|a|^2|b|^2+|b|^4=|b|^2$

Thus $P^2=P$. $P^\dagger=P$ is obvious.

---

1.5 Eigenvalues & Eigenvectors

Exercise 1.5.1 (1 star) The Eigensystem of Pauli $Y$

Find the eigenvalues and normalized eigenvectors of $Y=\begin{pmatrix}0&-i\\i&0\end{pmatrix}$.

Solution: $\det\begin{pmatrix}-\lambda&-i\\i&-\lambda\end{pmatrix}=\lambda^2-1=0$, eigenvalues $\lambda=\pm1$.

For $\lambda=1$: solve $(-1)v_1-iv_2=0$, giving $v_1=-iv_2$. The normalized eigenvector is $|+i\rangle=\frac1{\sqrt2}(-i,1)^T$.

For $\lambda=-1$: solve $v_1-iv_2=0$, giving $v_1=iv_2$. The normalized eigenvector is $|-i\rangle=\frac1{\sqrt2}(i,1)^T$.

Verification: $\langle+i|-i\rangle=\frac12(i\cdot i+1\cdot1)=\frac12(-1+1)=0$, orthogonal.

---

Exercise 1.5.2 (2 stars) Spectral Decomposition of the $Z$ Matrix

Perform the spectral decomposition of $Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}$.

Solution: Eigenvalue $1$ corresponds to $|0\rangle=(1,0)^T$, eigenvalue $-1$ corresponds to $|1\rangle=(0,1)^T$.

$$Z=(+1)|0\rangle\langle0|+(-1)|1\rangle\langle1| = \begin{pmatrix}1&0\\0&0\end{pmatrix}-\begin{pmatrix}0&0\\0&1\end{pmatrix}=\begin{pmatrix}1&0\\0&-1\end{pmatrix}$$

---

Exercise 1.5.3 (3 stars) Expectation Value for a Three-Level System

$H=\operatorname{diag}(3,2,5)$ in the basis $|0\rangle,|1\rangle,|2\rangle$. Find the eigenvalues and eigenvectors of $H$. If the system is in the state $|\psi\rangle=(|0\rangle+|1\rangle+|2\rangle)/\sqrt3$, compute $\langle H\rangle$.

Solution: Eigenvalues $3,2,5$, with corresponding eigenvectors $|0\rangle,|1\rangle,|2\rangle$.

$\langle H\rangle=\langle\psi|H|\psi\rangle=\frac13(3+2+5)=\frac{10}{3}$.

Or, using the spectral decomposition: $\langle H\rangle=\sum_i\lambda_i|\langle i|\psi\rangle|^2=\frac13(3+2+5)=10/3$.

---

1.6 Tensor Products & Composite Systems

Exercise 1.6.1 (1 star) Computing a Tensor Product

Compute the 4-component vector of $|0\rangle\otimes|+\rangle$ (where $|+\rangle=(|0\rangle+|1\rangle)/\sqrt2$).

Solution: $|0\rangle=(1,0)^T$, $|+\rangle=\frac1{\sqrt2}(1,1)^T$.

$$|0\rangle\otimes|+\rangle=\frac1{\sqrt2}\begin{pmatrix}1\cdot1\\1\cdot1\\0\cdot1\\0\cdot1\end{pmatrix}=\frac1{\sqrt2}\begin{pmatrix}1\\1\\0\\0\end{pmatrix}$$

That is, $\frac1{\sqrt2}(|00\rangle+|01\rangle)$.

---

Exercise 1.6.2 (2 stars) The Bell State Is Not Decomposable

Prove that $|\Phi^+\rangle=(|00\rangle+|11\rangle)/\sqrt2$ cannot be written as $|a\rangle\otimes|b\rangle$.

Solution: Proof by contradiction. Suppose $|a\rangle=\alpha|0\rangle+\beta|1\rangle$, $|b\rangle=\gamma|0\rangle+\delta|1\rangle$. Then

$$|a\rangle\otimes|b\rangle=\alpha\gamma|00\rangle+\alpha\delta|01\rangle+\beta\gamma|10\rangle+\beta\delta|11\rangle$$

Comparing with $(|00\rangle+|11\rangle)/\sqrt2$: $\alpha\gamma=1/\sqrt2,\alpha\delta=0,\beta\gamma=0,\beta\delta=1/\sqrt2$.

If $\alpha=0$ then $\alpha\gamma=0\neq1/\sqrt2$; if $\beta=0$ then $\beta\delta=0\neq1/\sqrt2$; if $\delta=0$ then $\beta\delta=0\neq1/\sqrt2$; if $\gamma=0$ then $\alpha\gamma=0\neq1/\sqrt2$. All cases lead to contradiction. Hence the state is not decomposable; it is entangled.

---

Exercise 1.6.3 (2 stars) CNOT Acting on Superposition States

Compute the result of applying CNOT to $|+0\rangle$ and to $|++\rangle$ (with the first qubit as the control).

Solution:

(a) $|+0\rangle=(|00\rangle+|10\rangle)/\sqrt2$

$$\text{CNOT}|+0\rangle=(\text{CNOT}|00\rangle+\text{CNOT}|10\rangle)/\sqrt2=(|00\rangle+|11\rangle)/\sqrt2=|\Phi^+\rangle$$

A separable state becomes an entangled state through the CNOT.

(b) $|++\rangle=\frac12(|00\rangle+|01\rangle+|10\rangle+|11\rangle)$

$$\text{CNOT}|++\rangle=\frac12(|00\rangle+|01\rangle+|11\rangle+|10\rangle)=|++\rangle$$

$|++\rangle$ is invariant under CNOT — it is an $X$-basis eigenstate of the CNOT gate.

---

1.7 Probability Theory Foundations

Exercise 1.7.1 (1 star) Expectation and Variance of a Die

Compute $\mathbb{E}[X]$ and $\operatorname{Var}(X)$ for the number $X$ showing on a fair six-sided die.

Solution: $\mathbb{E}[X]=\frac16(1+2+3+4+5+6)=3.5$

$\mathbb{E}[X^2]=\frac16(1+4+9+16+25+36)=\frac{91}{6}$

$\operatorname{Var}(X)=\mathbb{E}[X^2]-(\mathbb{E}[X])^2=\frac{91}{6}-\frac{49}{4}=\frac{35}{12}\approx2.917$

---

Exercise 1.7.2 (2 stars) Bayes’ Theorem

A disease has prevalence $2\%$. The test is $95\%$ accurate for patients (positive given disease), and $4\%$ false positive (positive given healthy). Find the probability of actually having the disease given a positive test result.

Solution: $P(D)=0.02$, $P(T^+\mid D)=0.95$, $P(T^+\mid\neg D)=0.04$.

$$P(D\mid T^+)=\frac{0.95\times0.02}{0.95\times0.02+0.04\times0.98}=\frac{0.019}{0.019+0.0392}\approx0.3265$$

Even with a positive test, the probability of having the disease is only about $32.7\%$, because for a rare disease the number of false positives far exceeds true positives.

---

Exercise 1.7.3 (3 stars) Classical vs. Quantum Probability

How is the probability of measuring 0 for $|\psi\rangle=\sqrt{0.3}|0\rangle+\sqrt{0.7}|1\rangle$ in the $Z$ basis similar to or different from a classical bit with $p=0.3$? What if the phase is changed to $e^{i\theta}$?

Solution: $P(0)=|\sqrt{0.3}|^2=0.3$, $P(1)=0.7$, numerically identical to the classical probability.

But the two are fundamentally different:

• Classical: the system is actually in 0 or 1; we merely “do not know” which.
• Quantum: the system is in a coherent superposition: $0.3|0\rangle+0.7|1\rangle$.
• Density matrix comparison: $\rho_{cl}=\begin{pmatrix}0.3&0\\0&0.7\end{pmatrix}$, $\rho_q=\begin{pmatrix}0.3&\sqrt{0.21}\\\sqrt{0.21}&0.7\end{pmatrix}$.
• The off-diagonal elements cause completely different $X$-basis measurement outcomes.

For $|\psi'\rangle=\sqrt{0.3}|0\rangle+e^{i\theta}\sqrt{0.7}|1\rangle$, $Z$-basis measurement probabilities are independent of $\theta$, but $X$-basis measurement probabilities depend on $\theta$. There is no “phase” concept in classical probability.

---

1.8 Fourier Analysis Primer

Exercise 1.8.1 (1 star) The 2-Point DFT Matrix

Write $F_2$ and compute its action on $\mathbf{x}=(1,0)^T$.

Solution: $\omega_2=e^{2\pi i/2}=-1$, $F_2=\begin{pmatrix}1&1\\1&-1\end{pmatrix}$.

$F_2\mathbf{x}=\begin{pmatrix}1&1\\1&-1\end{pmatrix}\begin{pmatrix}1\\0\end{pmatrix}=\begin{pmatrix}1\\1\end{pmatrix}$.

Note that the normalized Hadamard gate $H=F_2/\sqrt2$ is unitary.

---

Exercise 1.8.2 (2 stars) Unitarity of the QFT

Prove that $U_{\text{QFT}}=F_N/\sqrt{N}$ is unitary, where $(F_N)_{jk}=\omega_N^{jk}$ and $\omega_N=e^{2\pi i/N}$.

Solution: $(U^\dagger U)_{jl}=\frac1N\sum_{k=0}^{N-1}\overline{\omega_N^{kj}}\,\omega_N^{kl} =\frac1N\sum_{k=0}^{N-1}\omega_N^{k(l-j)}$.

If $j=l$, the sum is $N$, so $(U^\dagger U)_{jj}=1$. If $j\neq l$, let $r=\omega_N^{l-j}\neq1$. Then $\sum_{k=0}^{N-1}r^k=(1-r^N)/(1-r)$. Since $r^N=(\omega_N^{l-j})^N=1^{l-j}=1$, the sum is 0. Thus $(U^\dagger U)_{jl}=\delta_{jl}$, so $U^\dagger U=I$. Similarly $UU^\dagger=I$.

---

Exercise 1.8.3 (2 stars) 4-Point DFT

Write $F_4$ and compute $\mathbf{y}=F_4\mathbf{x}$ for $\mathbf{x}=(1,0,1,0)^T$.

Solution: $\omega_4=i$, $F_4=\begin{pmatrix}1&1&1&1\\1&i&-1&-i\\1&-1&1&-1\\1&-i&-1&i\end{pmatrix}$.

$$\mathbf{y}=F_4\begin{pmatrix}1\\0\\1\\0\end{pmatrix}= \begin{pmatrix}1\cdot1+1\cdot0+1\cdot1+1\cdot0\\ 1\cdot1+i\cdot0+(-1)\cdot1+(-i)\cdot0\\ 1\cdot1+(-1)\cdot0+1\cdot1+(-1)\cdot0\\ 1\cdot1+(-i)\cdot0+(-1)\cdot1+i\cdot0\end{pmatrix} =\begin{pmatrix}2\\0\\2\\0\end{pmatrix}$$

The DFT of a period-2 sequence has non-zero values only at the DC and Nyquist frequencies.

---

Part II: Physical Foundations of Quantum Mechanics

---

2.1 From Classical to Quantum: Motivation and History

Exercise 2.1.1 (1 star) The Ultraviolet Catastrophe

What is the ultraviolet catastrophe? How did Planck resolve it using energy quantization?

Solution: The classical Rayleigh-Jeans formula $u(\nu,T)\propto\nu^2$ predicts infinite radiated energy at ultraviolet frequencies, in severe disagreement with experiment — the ultraviolet catastrophe.

Planck hypothesized that energy is emitted/absorbed in quanta of $E=h\nu$ and derived:

$$u(\nu,T)=\frac{8\pi h\nu^3}{c^3}\frac1{e^{h\nu/k_BT}-1}$$

At high frequencies the exponential term forces the energy density to zero, avoiding the divergence. This marked the birth of quantum mechanics.

---

Exercise 2.1.2 (2 stars) The Photoelectric Effect

A metal has work function $W=2.0\,\text{eV}$ and is illuminated with light of frequency $\nu=6.0\times10^{14}\,\text{Hz}$. ($h=4.136\times10^{-15}\,\text{eV·s}$.) (a) Find the maximum kinetic energy of photoelectrons. (b) Find the cutoff frequency.

Solution: (a) $E=h\nu=4.136\times10^{-15}\times6.0\times10^{14}=2.482\,\text{eV}$ $E_k=E-W=2.482-2.0=0.482\,\text{eV}$

(b) $h\nu_0=W\implies\nu_0=W/h=2.0/4.136\times10^{-14}=4.84\times10^{14}\,\text{Hz}$

Photoelectrons are emitted only when $\nu>\nu_0$, independent of light intensity — inexplicable by classical wave theory.

---

Exercise 2.1.3 (2 stars) Probability Amplitudes in the Double Slit

Let $\psi_L=\sqrt{0.4}\,e^{i\pi/4}$ and $\psi_R=\sqrt{0.6}\,e^{-i\pi/6}$. Compute the classical probability, the quantum probability, and the interference term.

Solution:

Classical: $P_{\text{classical}}=|\psi_L|^2+|\psi_R|^2=0.4+0.6=1.0$

Quantum: $P_{\text{quantum}}=|\psi_L+\psi_R|^2=|\psi_L|^2+|\psi_R|^2+2\sqrt{0.24}\cos(\pi/4+\pi/6)$

$\cos(5\pi/12)\approx0.2588$, interference term $=2\times\sqrt{0.24}\times0.2588\approx0.2536$

$P_{\text{quantum}}\approx1.2536$ (probability is enhanced at this point; the integral over the entire screen is 1).

The interference term accounts for $25.4\%$ of the probability and is a purely quantum effect.

---

2.2 Basic Postulates of Quantum Mechanics

Exercise 2.2.1 (1 star) Single-Qubit Measurement Probability

$|\psi\rangle=(|0\rangle+i|1\rangle)/\sqrt2$ is measured in the $Z$ basis. Find $P(0)$ and $P(1)$.

Solution: $\langle0|\psi\rangle=1/\sqrt2$, $\langle1|\psi\rangle=i/\sqrt2$.

$P(0)=|1/\sqrt2|^2=1/2$, $P(1)=|i/\sqrt2|^2=1/2$.

This state lies in the $+y$ direction on the equator of the Bloch sphere.

---

Exercise 2.2.2 (2 stars) Unitary Evolution Preserves the Norm

Prove that a normalized state $|\psi\rangle$ remains normalized after evolving under a unitary operator $U$.

Solution: $\langle\psi|U^\dagger U|\psi\rangle=\langle\psi|I|\psi\rangle=\langle\psi|\psi\rangle=1$.

Total probability is conserved under quantum evolution; this is the fundamental reason quantum gates must be unitary matrices.

---

Exercise 2.2.3 (3 stars) Spectral Decomposition of $Z$ and Measurement

$Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}$, and the system is in state $|+\rangle=(|0\rangle+|1\rangle)/\sqrt2$. (a) Verify that $Z$ is Hermitian. (b) Give its spectral decomposition. (c) Find the probability of measuring $+1$ and the state after measurement.

Solution: (a) $Z^\dagger=Z$, Hermitian.

(b) $Z=(+1)|0\rangle\langle0|+(-1)|1\rangle\langle1|$.

(c) $P(+1)=\langle+|(|0\rangle\langle0|)|+\rangle=|\langle0|+\rangle|^2=1/2$.

If $+1$ is measured, the system collapses to $|0\rangle$.

---

2.3 Wave Functions and the Schrodinger Equation

Exercise 2.3.1 (1 star) Normalization in an Infinite Square Well

The ground-state wave function is $\psi(x)=A\sin(\pi x/L)$, $0<x<L$. Find $A$.

Solution: $\int_0^L|A|^2\sin^2(\pi x/L)dx=|A|^2\int_0^L\frac12[1-\cos(2\pi x/L)]dx=|A|^2\cdot\frac L2=1$

$A=\sqrt{2/L}$. The wave function is $\psi(x)=\sqrt{2/L}\sin(\pi x/L)$.

---

Exercise 2.3.2 (2 stars) Time-Independent Schrodinger Equation and Separation of Variables

Prove that if $H|\psi\rangle=E|\psi\rangle$, then $|\psi(t)\rangle=e^{-iEt/\hbar}|\psi\rangle$ satisfies the time-dependent Schrodinger equation.

Solution: $\frac{\partial}{\partial t}|\psi(t)\rangle=-\frac{iE}{\hbar}e^{-iEt/\hbar}|\psi\rangle$

$i\hbar\frac{\partial}{\partial t}|\psi(t)\rangle=E e^{-iEt/\hbar}|\psi\rangle=e^{-iEt/\hbar}H|\psi\rangle=H|\psi(t)\rangle$

The equation holds, provided $H$ does not explicitly depend on time.

---

Exercise 2.3.3 (2 stars) Position Expectation Value

For $\psi_1(x)=\sqrt{2/L}\sin(\pi x/L)$ compute $\langle x\rangle$.

Solution: $\langle x\rangle=\frac2L\int_0^L x\sin^2(\pi x/L)dx$

$=\frac2L\int_0^L x\cdot\frac12[1-\cos(2\pi x/L)]dx=\frac1L\left[\frac{L^2}{2}-0\right]=\frac L2$

$\int_0^L x\cos(2\pi x/L)dx=0$ (integration by parts; the sine terms vanish at the boundaries). In a symmetric potential well, the position expectation value is the center $L/2$.

---

2.4 Two-Level Systems and Spin

Exercise 2.4.1 (1 star) $X$ Eigenstates

Verify that $|\pm\rangle=(|0\rangle\pm|1\rangle)/\sqrt2$ are eigenstates of $X$.

Solution: $X|+\rangle=\begin{pmatrix}0&1\\1&0\end{pmatrix}\frac1{\sqrt2}\begin{pmatrix}1\\1\end{pmatrix}=\frac1{\sqrt2}\begin{pmatrix}1\\1\end{pmatrix}=|+\rangle$, eigenvalue $+1$.

$X|-\rangle=\begin{pmatrix}0&1\\1&0\end{pmatrix}\frac1{\sqrt2}\begin{pmatrix}1\\-1\end{pmatrix}=\frac1{\sqrt2}\begin{pmatrix}-1\\1\end{pmatrix}=-|-\rangle$, eigenvalue $-1$.

$\langle+|-\rangle=0$, orthogonal.

---

Exercise 2.4.2 (2 stars) Pauli Commutation Relations

Verify that $[X,Y]=2iZ$.

Solution: $[X,Y]=XY-YX=iZ-(-iZ)=2iZ$.

Matrix verification: $XY=\begin{pmatrix}i&0\\0&-i\end{pmatrix}$, $YX=\begin{pmatrix}-i&0\\0&i\end{pmatrix}$, their difference is $2iZ$.

Cyclic commutation: $[Y,Z]=2iX$, $[Z,X]=2iY$, manifestations of the spin angular momentum algebra.

---

Exercise 2.4.3 (2 stars) Spin Measurement in the $x$ Direction

$|\psi\rangle=\cos\frac\theta2|0\rangle+e^{i\phi}\sin\frac\theta2|1\rangle$. When measuring spin in the $x$ direction, find $P(S_x=+\hbar/2)$.

Solution: $S_x=\frac\hbar2X$. The $X$ eigenstate is $|+\rangle=(|0\rangle+|1\rangle)/\sqrt2$.

$$\langle+|\psi\rangle=\frac1{\sqrt2}(\cos\frac\theta2+e^{i\phi}\sin\frac\theta2)$$ $$P(+\hbar/2)=|\langle+|\psi\rangle|^2=\frac12\left(1+\sin\theta\cos\phi\right)$$

When $\theta=\pi/2,\phi=0$ ($|+\rangle$), $P=1$; when $\theta=\pi/2,\phi=\pi$ ($|-\rangle$), $P=0$.

---

2.5 The Bloch Sphere

Exercise 2.5.1 (1 star) Bloch Sphere Coordinates

Find the Bloch sphere coordinates of $|0\rangle,|1\rangle,|+\rangle,|-i\rangle$.

Solution: Parameterizing as $|\psi\rangle=\cos\frac\theta2|0\rangle+e^{i\phi}\sin\frac\theta2|1\rangle$, the coordinates are $(x,y,z)=(\sin\theta\cos\phi,\sin\theta\sin\phi,\cos\theta)$.

State	$\theta$	$\phi$	$(x,y,z)$
$	0\rangle$	$0$	arbitrary
$	1\rangle$	$\pi$	arbitrary
$	+\rangle$	$\pi/2$	$0$
$	-i\rangle$	$\pi/2$	$-\pi/2$

---

Exercise 2.5.2 (2 stars) The Bloch Vector of a Pure State Has Length 1

For any pure state, prove that $\langle X\rangle^2+\langle Y\rangle^2+\langle Z\rangle^2=1$.

Solution: For $|\psi\rangle=\cos\frac\theta2|0\rangle+e^{i\phi}\sin\frac\theta2|1\rangle$:

$\langle Z\rangle=\cos^2\frac\theta2-\sin^2\frac\theta2=\cos\theta$ $\langle X\rangle=\sin\theta\cos\phi$ $\langle Y\rangle=\sin\theta\sin\phi$

$\langle X\rangle^2+\langle Y\rangle^2+\langle Z\rangle^2=\sin^2\theta(\cos^2\phi+\sin^2\phi)+\cos^2\theta=1$

Pure states correspond to points on the sphere surface; mixed states to points in the interior.

---

Exercise 2.5.3 (2 stars) The $R_z(\pi)$ Rotation

Compute the action of $R_z(\pi)=e^{-i\pi Z/2}$ on $|+\rangle$ and $|0\rangle$.

Solution: $e^{-i\alpha Z/2}=\cos\frac\alpha2 I-i\sin\frac\alpha2 Z$

For $\alpha=\pi$: $R_z(\pi)=-iZ$.

$R_z(\pi)|0\rangle=-iZ|0\rangle=-i|0\rangle$ (a global phase; physically unchanged).

$R_z(\pi)|+\rangle=-iZ|+\rangle=-i\frac1{\sqrt2}(|0\rangle-|1\rangle)=-i|-\rangle$.

$|+\rangle$ rotates $180^\circ$ about the $z$-axis to reach $|-\rangle$. $|0\rangle$, lying on the $z$-axis, is unchanged by the rotation.

---

2.6 Measurement Theory and Density Matrices

Exercise 2.6.1 (1 star) The Maximally Mixed State

For $\rho=I/2$, compute $\operatorname{Tr}(\rho)$, $\operatorname{Tr}(\rho^2)$, and determine whether it is a pure or mixed state.

Solution: $\operatorname{Tr}(\rho)=1/2+1/2=1$. $\rho^2=I/4$, $\operatorname{Tr}(\rho^2)=1/4+1/4=1/2<1$, so it is a mixed state.

$Z$-basis measurement: $P(0)=P(1)=1/2$. The maximally mixed state is uniformly distributed in any basis and corresponds to the center of the Bloch sphere.

---

Exercise 2.6.2 (2 stars) Reduced Density Matrix of a Bell State

For $|\Phi^+\rangle=(|00\rangle+|11\rangle)/\sqrt2$, compute $\rho_A=\operatorname{Tr}_B(|\Phi^+\rangle\langle\Phi^+|)$.

Solution: $\rho_{AB}=\frac12(|00\rangle\langle00|+|00\rangle\langle11|+|11\rangle\langle00|+|11\rangle\langle11|)$

${}_B\langle0|\rho_{AB}|0\rangle_B=\frac12|0\rangle\langle0|$, ${}_B\langle1|\rho_{AB}|1\rangle_B=\frac12|1\rangle\langle1|$

$\rho_A=\frac12|0\rangle\langle0|+\frac12|1\rangle\langle1|=I/2$, the maximally mixed state!

The whole is a pure state, but the subsystem is completely mixed — the essence of entanglement is that the information of the subsystem is entirely lost in correlations.

---

Exercise 2.6.3 (3 stars) Density Matrix of a Probabilistic Mixture

A system has probability $1/2$ to be in $|+\rangle$ and $1/2$ to be in $|0\rangle$. Compute $\rho$, $\operatorname{Tr}(\rho^2)$, and determine whether it is pure or mixed.

Solution: $\rho=\frac12|+\rangle\langle+|+\frac12|0\rangle\langle0|$

$|+\rangle\langle+|=\frac12\begin{pmatrix}1&1\\1&1\end{pmatrix}$, $|0\rangle\langle0|=\begin{pmatrix}1&0\\0&0\end{pmatrix}$

$\rho=\frac12\begin{pmatrix}3/2&1/2\\1/2&1/2\end{pmatrix}=\begin{pmatrix}3/4&1/4\\1/4&1/4\end{pmatrix}$

$\rho^2=\begin{pmatrix}5/8&1/4\\1/4&1/8\end{pmatrix}$, $\operatorname{Tr}(\rho^2)=5/8+1/8=3/4<1$, so it is a mixed state.

For a general parameter $p$: $\rho(p)=p|+\rangle\langle+|+(1-p)|0\rangle\langle0|$, $\operatorname{Tr}(\rho^2)=1-p+p^2$. When $p=0$ or $1$ it is pure; when $p=1/2$ the mixedness is maximal ($3/4$).

---

Part III: Fundamentals of Quantum Computing

---

3.1 Qubits

Exercise 3.1.1 (1 star) Normalizing a Quantum State

Normalize $|\psi\rangle=3|0\rangle+4|1\rangle$.

Solution: $\||\psi\rangle\|=\sqrt{3^2+4^2}=5$. The normalized state is:

$|\hat\psi\rangle=\frac35|0\rangle+\frac45|1\rangle$. $P(0)=(3/5)^2=0.36$, $P(1)=0.64$.

---

Exercise 3.1.2 (2 stars) Bloch Sphere Parameterization

Express $|\psi\rangle=\frac{1+i}2|0\rangle+\frac{1-i}2|1\rangle$ in terms of $(\theta,\phi)$.

Solution: $|\alpha|^2=|\beta|^2=1/2$, $\cos\frac\theta2=1/\sqrt2\implies\theta=\pi/2$.

$\alpha=\frac1{\sqrt2}e^{i\pi/4}$, $\beta=\frac1{\sqrt2}e^{-i\pi/4}$, relative phase $\phi=-\pi/2$.

$(\theta,\phi)=(\pi/2,-\pi/2)$, which is $|-i\rangle$. The original state differs from $|-i\rangle$ by a global phase of $e^{i\pi/4}$.

---

Exercise 3.1.3 (3 stars) Dimension of an $n$-Qubit State Space

(a) Prove that the state space of $n$ qubits has dimension $2^n$. (b) Neglecting the global phase, how many real parameters describe an $n$-qubit pure state? (c) For $n=50$, how many complex parameters are needed?

Solution: (a) $\mathcal{H}=(\mathbb{C}^2)^{\otimes n}$, $\dim=2^n$.

(b) $2^n$ complex amplitudes; normalization removes 1 constraint; global phase removes 1. Real parameters $=2^{n+1}-2$.

(c) $2^{50}\approx1.13\times10^{15}$ complex parameters, about 18 PB (double precision). This exceeds classical computer memory, revealing the root of quantum advantage.

---

3.2 Single-Qubit Gates

Exercise 3.2.1 (1 star) Basic Action of the $H$ Gate

Compute $H|0\rangle$, $H|1\rangle$, $H|+\rangle$, and verify $H^2=I$.

Solution: $H=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}$

$H|0\rangle=|+\rangle$, $H|1\rangle=|-\rangle$, $H|+\rangle=|0\rangle$

$H^2=\frac12\begin{pmatrix}1&1\\1&-1\end{pmatrix}\begin{pmatrix}1&1\\1&-1\end{pmatrix}=I$, self-inverse.

---

Exercise 3.2.2 (2 stars) Conjugation Relations of $H$

Prove $HXH=Z$ and $HZH=X$.

Solution: $HX=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}\begin{pmatrix}0&1\\1&0\end{pmatrix}=\frac1{\sqrt2}\begin{pmatrix}1&1\\-1&1\end{pmatrix}$

$(HX)H=\frac12\begin{pmatrix}1&1\\-1&1\end{pmatrix}\begin{pmatrix}1&1\\1&-1\end{pmatrix}=\frac12\begin{pmatrix}2&0\\0&-2\end{pmatrix}=Z$

$HZH$ similarly gives $X$. The $H$ gate transforms between the $X$ and $Z$ bases.

---

Exercise 3.2.3 (2 stars) Relations Among Phase Gates

Prove $S=T^2$, $Z=S^2=T^4$.

Solution: $T=\begin{pmatrix}1&0\\0&e^{i\pi/4}\end{pmatrix}$, $S=\begin{pmatrix}1&0\\0&i\end{pmatrix}$, $Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}$.

$T^2=\begin{pmatrix}1&0\\0&e^{i\pi/2}\end{pmatrix}=S$, $S^2=\begin{pmatrix}1&0\\0&i^2\end{pmatrix}=Z$, $T^4=(T^2)^2=S^2=Z$.

$T,S,Z$ are rotations about the $z$-axis by $\pi/4,\pi/2,\pi$, respectively.

---

3.3 Multi-Qubit Gates and Entanglement

Exercise 3.3.1 (1 star) CNOT on Superposition States

Compute the action of CNOT on $|1+\rangle$ and $|+-\rangle$ (with the first qubit as control).

Solution: $|1+\rangle=(|10\rangle+|11\rangle)/\sqrt2$

$\text{CNOT}|1+\rangle=(|11\rangle+|10\rangle)/\sqrt2=|1+\rangle$, unchanged.

$|+-\rangle=\frac12(|00\rangle-|01\rangle+|10\rangle-|11\rangle)$

$\text{CNOT}|+-\rangle=\frac12(|00\rangle-|01\rangle+|11\rangle-|10\rangle)=|+-\rangle$, also unchanged.

$|1+\rangle$ and $|+-\rangle$ are both $X$-basis eigenstates of the CNOT gate.

---

Exercise 3.3.2 (2 stars) Entanglement of $|\Psi^-\rangle$

Prove that $|\Psi^-\rangle=(|01\rangle-|10\rangle)/\sqrt2$ is an entangled state.

Solution: Assume $|\Psi^-\rangle=|a\rangle\otimes|b\rangle$, with $|a\rangle=\alpha|0\rangle+\beta|1\rangle$, $|b\rangle=\gamma|0\rangle+\delta|1\rangle$.

Expanding gives $\alpha\gamma=0$, $\alpha\delta=1/\sqrt2$, $\beta\gamma=-1/\sqrt2$, $\beta\delta=0$.

$\alpha=0\implies\alpha\delta=0$, contradiction; $\beta=0\implies\beta\gamma=0$, contradiction; $\gamma=0\implies\beta\gamma=0$, contradiction; $\delta=0\implies\beta\delta=0$, contradiction.

Not decomposable; it is an entangled state. $|\Psi^-\rangle$ is the unique antisymmetric Bell state.

---

Exercise 3.3.3 (3 stars) Proof of the No-Cloning Theorem

Prove that there does not exist a unitary operator $U$ such that $U|\psi\rangle|0\rangle=|\psi\rangle|\psi\rangle$ for all $|\psi\rangle$.

Solution: Take two non-orthogonal, non-identical states $|\psi\rangle,|\phi\rangle$ ($0<|\langle\psi|\phi\rangle|<1$).

Suppose such a $U$ exists. Then $U|\psi\rangle|0\rangle=|\psi\rangle|\psi\rangle$, $U|\phi\rangle|0\rangle=|\phi\rangle|\phi\rangle$.

Inner product of left sides: $\langle\psi|\langle0|U^\dagger U|\phi\rangle|0\rangle=\langle\psi|\phi\rangle$ Inner product of right sides: $\langle\psi|\langle\psi|\cdot|\phi\rangle|\phi\rangle=(\langle\psi|\phi\rangle)^2$

Hence $\langle\psi|\phi\rangle=(\langle\psi|\phi\rangle)^2$, which implies $\langle\psi|\phi\rangle=0$ or $1$, contradicting the premise.

A universal cloning machine cannot exist. Quantum information cannot be copied; this is the foundation of the security of quantum cryptography.

---

3.4 Quantum Circuits

Exercise 3.4.1 (1 star) Bell State Preparation Circuit

Analyze what state is prepared by the following circuit:

|1⟩ —H—•—
|0⟩ ———⊕—

Solution: Initial state: $|10\rangle$.

After $H$: $(|0\rangle-|1\rangle)|0\rangle/\sqrt2=(|00\rangle-|10\rangle)/\sqrt2$

After CNOT: $(|00\rangle-|11\rangle)/\sqrt2=|\Phi^-\rangle$

The circuit prepares $|\Phi^-\rangle$.

---

Exercise 3.4.2 (2 stars) GHZ State Circuit Tracking

Write the state after each step of the circuit that prepares the GHZ state $(|000\rangle+|111\rangle)/\sqrt2$.

Solution: Circuit:

|0⟩ —H—•——————
|0⟩ ———⊕—•———
|0⟩ —————⊕———

1. Initial: $|000\rangle$
2. After $H$: $(|000\rangle+|100\rangle)/\sqrt2$
3. After CNOT$_{12}$: $(|000\rangle+|110\rangle)/\sqrt2$
4. After CNOT$_{23}$: $(|000\rangle+|111\rangle)/\sqrt2=|\text{GHZ}\rangle$

Three-qubit complete entanglement: measuring one qubit determines the other two.

---

Exercise 3.4.3 (2 stars) Designing a $|\Phi^-\rangle$ Circuit

Design a circuit to prepare $|\Phi^-\rangle=(|00\rangle-|11\rangle)/\sqrt2$.

Solution: Two methods.

Method 1 (standard circuit + $Z$ gate):

|0⟩ —H—•——Z—
|0⟩ ———⊕———

After $H$: $(|00\rangle+|10\rangle)/\sqrt2$; after CNOT: $(|00\rangle+|11\rangle)/\sqrt2$; after $Z$: $(|00\rangle-|11\rangle)/\sqrt2$.

Method 2 (change the initial state, see 3.4.1):

|1⟩ —H—•—
|0⟩ ———⊕—

Directly yields $|\Phi^-\rangle$, more concise.

---

3.5 Quantum Measurement and Readout

Exercise 3.5.1 (1 star) Measurement Probability and Expectation Value

$|\psi\rangle=0.6|0\rangle+0.8|1\rangle$. Find $P(0),P(1),\langle Z\rangle$.

Solution: $P(0)=|0.6|^2=0.36$, $P(1)=|0.8|^2=0.64$.

$\langle Z\rangle=|0.6|^2-|0.8|^2=0.36-0.64=-0.28$ (near the Bloch sphere’s south pole).

---

Exercise 3.5.2 (2 stars) Expectation Values in Three Directions

Compute $\langle X\rangle,\langle Y\rangle,\langle Z\rangle$ for $|+\rangle$ and verify the sum of squares equals 1.

Solution: $|+\rangle$ is an $X$ eigenstate (eigenvalue $+1$), so $\langle X\rangle=1$.

$\langle Z\rangle=\langle+|Z|+\rangle=\frac12(1-1)=0$ $\langle Y\rangle=\langle+|Y|+\rangle=\frac12(-i+i)=0$

$\langle X\rangle^2+\langle Y\rangle^2+\langle Z\rangle^2=1$, Bloch coordinates $(1,0,0)$, a pure state.

---

Exercise 3.5.3 (3 stars) Measurement in the $X$ Basis

For $|\psi\rangle=\alpha|0\rangle+\beta|1\rangle$ measured in the $X$ basis, find $P_+$ and $P_-$.

Solution: $\langle+|\psi\rangle=(\alpha+\beta)/\sqrt2$, $\langle-|\psi\rangle=(\alpha-\beta)/\sqrt2$.

$P_+=\frac{|\alpha+\beta|^2}{2}=\frac{|\alpha|^2+|\beta|^2+2\operatorname{Re}(\alpha^*\beta)}{2}=\frac12+\operatorname{Re}(\alpha^*\beta)$

$P_-=\frac12-\operatorname{Re}(\alpha^*\beta)$

When $|\psi\rangle=|+\rangle$, $P_+=1$; when $|\psi\rangle=|0\rangle$, $P_+=P_-=1/2$.

The $Z$-basis state is completely random in the $X$ basis, reflecting complementarity.

---

3.6 Introduction to Quantum Algorithms

Exercise 3.6.1 (1 star) BB84 Basis Comparison

Alice sends $|+\rangle$. What are Bob’s measurement outcomes if he uses the $X$ basis or the $Z$ basis?

Solution: $X$-basis measurement: $|+\rangle$ is an $X$ eigenstate, so $+$ (bit 0) is obtained with probability 1.

$Z$-basis measurement: $P(0)=|\langle0|+\rangle|^2=1/2$, $P(1)=1/2$, completely random.

When the bases match ($X/X$), the probability is $1/2$ and the result is deterministic. When they differ, the result is random and discarded.

---

Exercise 3.6.2 (2 stars) Teleportation Tracking

Alice wants to transmit $|1\rangle$. They share $|\Phi^+\rangle_{AB}=(|00\rangle+|11\rangle)/\sqrt2$. Find Bob’s state after Alice’s measurement.

Solution: Three-qubit initial state: $|\Psi_0\rangle=|1\rangle_A|\Phi^+\rangle_{AB}=(|100\rangle+|111\rangle)/\sqrt2$.

CNOT$_{12}$ (Alice on her two qubits): $|\Psi_1\rangle=(|110\rangle+|101\rangle)/\sqrt2$.

$H_1$: $|\Psi_2\rangle=\frac12(|010\rangle-|110\rangle+|001\rangle-|101\rangle)$.

The four measurement outcomes and Bob’s corrections:

Alice gets	Bob’s state	Correction gate	Final state
$(0,0)$	$	1\rangle$	$I$
$(0,1)$	$	0\rangle$	$X$
$(1,0)$	$	1\rangle$	$Z$
$(1,1)$	$	0\rangle$	$ZX$

Regardless of the case, Bob ends up with $|1\rangle$. Teleportation succeeds.

---

Exercise 3.6.3 (3 stars) A Single Grover Iteration ($N=4$)

$N=4$, target state $|\omega\rangle=|11\rangle$. Prove that a single iteration yields the target state with probability 1.

Solution: Initial: $|s\rangle=H^{\otimes2}|00\rangle=\frac12(|00\rangle+|01\rangle+|10\rangle+|11\rangle)$.

$U_\omega|x\rangle=(-1)^{f(x)}|x\rangle$, where $f(x)=1$ only for $x=11$.

$U_\omega|s\rangle=\frac12(|00\rangle+|01\rangle+|10\rangle-|11\rangle)$.

Average amplitude: $\bar a=\frac14(\frac12+\frac12+\frac12-\frac12)=\frac14$.

$U_s=2|s\rangle\langle s|-I$: $a_i\to2\bar a-a_i$.

• $|00\rangle$: $2\cdot\frac14-\frac12=0$
• $|01\rangle$: $0$
• $|10\rangle$: $0$
• $|11\rangle$: $2\cdot\frac14-(-\frac12)=1$

We obtain $|11\rangle$; measurement yields the target state with probability 1. For $N=4$, a single Grover iteration is perfectly successful.

---

File Information: 60 problems covering 20 sections · Part I 24 problems · Part II 18 problems · Part III 18 problems Difficulty Distribution: 1 star: 20 problems · 2 stars: 30 problems · 3 stars: 10 problems

---

Part 1: Mathematical Foundations - Feynman Workbook

Learn by doing, teach to learn

This workbook follows the Feynman learning method: the best test of understanding is whether you can teach it to someone else in simple language. Each section has 4 problems covering four abilities: computation, proof, teaching, and insight.

Difficulty markings: 1 star Computation / 2 stars Proof / Teaching / Insight

---

1.1 Complex Numbers & Euler’s Formula

(1 star) Power Computation in Polar Form

Compute $(1+i)^6$. Hint: First express $1+i$ in polar form, then use De Moivre’s theorem.

(2 stars) Proof of De Moivre’s Theorem

Use Euler’s formula $e^{i\theta} = \cos\theta + i\sin\theta$ to prove De Moivre’s theorem:

$$(\cos\theta + i\sin\theta)^n = \cos(n\theta) + i\sin(n\theta), \quad n \in \mathbb{Z}$$

and explain whether it still holds when $n$ is a negative integer.

(Teaching) Feynman: Explain the “Necessity” of Complex Numbers to a High Schooler

Imagine you are sitting across from a high school student who has studied trigonometry but has never encountered complex numbers. He asks: “Why does quantum mechanics have to use complex numbers? Wouldn’t real numbers be more ‘natural’? Can’t that phase $e^{i\theta}$ you talk about be replaced by the pair of real numbers $(\cos\theta, \sin\theta)$?”

Answer him in at most 3 sentences. If you find it helpful, you may sketch a simple diagram to illustrate.

(Insight) What If $i^2 = 1$?

Suppose we defined a “new number” $j$ satisfying $j^2 = 1$ but $j \neq \pm 1$ (the split-complex numbers). What would “multiplication” of $z = a + bj$ look like? Would the definition $|z|^2 = z z^*$ still be meaningful?

Going further: if quantum mechanics used $j$ instead of $i$, would the superposition of probability amplitudes still produce interference? Try to speculate.

---

1.2 Vector Spaces & Hilbert Spaces

(1 star) Verifying the Legitimacy of a Basis

Determine whether the following two vectors form a basis for $\mathbb{C}^2$:

$$|v_1\rangle = \begin{pmatrix}1 \\ i\end{pmatrix},\quad |v_2\rangle = \begin{pmatrix}i \\ 1\end{pmatrix}$$

If we take only one of them, can it generate all of $\mathbb{C}^2$? Why?

(2 stars) Maximal Orthonormal Set

In $\mathbb{C}^n$, prove: given any set of orthonormal vectors $\{|e_1\rangle, |e_2\rangle, \ldots, |e_m\rangle\}$, if $m < n$, then there must exist $|v\rangle \neq 0$ that is orthogonal to all $|e_i\rangle$.

(In other words: $\mathbb{C}^n$ cannot contain more than $n$ non-zero mutually orthogonal vectors.)

(Teaching) Feynman: Explain Basis and Dimension with a “Bookshelf” Analogy

Your friend has never studied linear algebra but understands the real-world concept of “dimension” (length, width, height).

Using a bookshelf, the arrangement of books, or coordinate positioning as an analogy, help them understand:

1. What a “basis” of a vector space is.
2. What “dimension” is.
3. Why the same vector has different coordinates in different bases.

(Insight) Function Spaces Are Also Vector Spaces

Consider the set $L^2(\mathbb{R})$ of all square-integrable functions from $\mathbb{R}$ to $\mathbb{C}$. It is also an (infinite-dimensional) vector space.

1. Can you guess what operations “vector addition” and “scalar multiplication” correspond to in this space?
2. What is a “basis” in this space?
3. What does infinite dimensionality mean? What essential differences does it have from the finite-dimensional $\mathbb{C}^n$?

---

1.3 Linear Operators & Matrix Representation

(1 star) Computing a Commutator

Compute the commutator $[X, Y] = XY - YX$ of the Pauli matrices and express the result as a multiple of $Z$.

Given:

$$X = \begin{pmatrix}0&1\\1&0\end{pmatrix},\quad Y = \begin{pmatrix}0&-i\\i&0\end{pmatrix},\quad Z = \begin{pmatrix}1&0\\0&-1\end{pmatrix}$$

(2 stars) Eigenvalues of a Hermitian Operator Are Real

Let $A$ be a Hermitian operator, i.e., $A^\dagger = A$. Prove that all eigenvalues of $A$ are real.

Hint: Let $A|\lambda\rangle = \lambda|\lambda\rangle$, compute $\langle\lambda|A|\lambda\rangle$, and use Hermiticity.

(Teaching) Feynman: Unitary Operators Are Like “Revolving Doors”

In at most 4 sentences and with an everyday-life analogy, explain to a beginner why quantum gates must be unitary operators.

Your explanation should include:

• Unitary operators preserve the “length” of a vector.
• Why length matters (the sum of probabilities must be 1).
• An example of what a non-unitary operation would do.

(Insight) The Correspondence Between Operators and Matrices Is a “Choice”

The tutorial says: given a basis, each linear operator corresponds to a unique matrix. But if we change the basis, the matrix representing the same operator changes.

1. Can you describe this change using a similarity transformation ($A' = P^{-1}AP$)?
2. Which properties of an operator (eigenvalues, trace, determinant) are invariant under a change of basis?
3. Why does quantum mechanics focus more on the operator itself than on its concrete matrix representation?

---

1.4 Inner Products, Norms & Orthogonality

(1 star) Gram-Schmidt Orthogonalization

Perform the Gram-Schmidt orthogonalization process on the following two vectors:

$$|v_1\rangle = \begin{pmatrix}1 \\ 1 \\ 0\end{pmatrix},\quad |v_2\rangle = \begin{pmatrix}1 \\ 0 \\ 1\end{pmatrix}$$

Starting from $|v_1\rangle$, obtain an orthonormal basis.

(2 stars) The Parallelogram Law

In a complex inner product space, prove the parallelogram law:

$$\| |v\rangle + |w\rangle \|^2 + \| |v\rangle - |w\rangle \|^2 = 2\left(\| |v\rangle \|^2 + \| |w\rangle \|^2\right)$$

and explain its geometric meaning. (Hint: expand both sides using the inner product.)

(Teaching) Feynman: Explain “Projection” to a 5-Year-Old

Suppose you have a flashlight and a wall. You need to explain to a 5-year-old what it means “to project one vector onto another.”

Use everyday language; no formulas needed. Then add one sentence describing the role “projection” plays in quantum measurement.

(Insight) Cauchy-Schwarz and the Uncertainty Principle

In quantum mechanics, the Heisenberg uncertainty principle can be written as:

$$\Delta A \, \Delta B \geq \frac{1}{2} \left| \langle [A, B] \rangle \right|$$

where $\Delta A$ is the standard deviation of operator $A$ and $[A, B]$ is the commutator.

1. How is this inequality mathematically similar to the Cauchy-Schwarz inequality $|\langle v | w \rangle| \leq \|v\| \|w\|$?
2. Can you see why “uncertainty” is essentially a geometric property (an inner angle in an inner product space) rather than a complex physical hypothesis?

---

1.5 Eigenvalues & Eigenvectors

(1 star) The Eigensystem of the Hadamard Matrix

Find the eigenvalues and normalized eigenvectors of the following matrix:

$$H = \frac{1}{\sqrt{2}}\begin{pmatrix}1 & 1 \\ 1 & -1\end{pmatrix}$$

(This is one of the most important gates in quantum computing — the Hadamard gate.)

(2 stars) Commuting Operators Share Eigenvectors

Let $A$ and $B$ be two Hermitian operators with $[A, B] = 0$ (they commute). Prove: there exists a basis that simultaneously diagonalizes both $A$ and $B$.

Hint: first decompose the space into the eigenspaces of $A$, then prove that $B$ leaves each eigenspace invariant.

(Teaching) Feynman: Spectral Decomposition Is Like “A Prism Splitting Light”

Use a physical analogy to explain the spectral decomposition theorem to a fellow student:

“Any Hermitian operator can be decomposed as $A = \sum_i \lambda_i |\lambda_i\rangle\langle\lambda_i|$.”

We suggest using the analogy of white light passing through a prism and being decomposed into monochromatic light. Then explain why this decomposition is so important for quantum measurement.

(Insight) Why Measurement Can Only Yield Eigenvalues

Quantum mechanics has a fundamental postulate: when measuring a physical quantity $A$, the result can only be one of the eigenvalues of $A$.

1. If $A$ were not Hermitian (its eigenvalues could be complex), what would measurement outcomes imply?
2. If the system is in a superposition state $|\psi\rangle = \alpha|\lambda_1\rangle + \beta|\lambda_2\rangle$, what is the probability of measuring $\lambda_1$?
3. What does the state of the system become after measurement? This is called “wave function collapse” — can you describe this process in the language of projection operators?

---

1.6 Tensor Products & Composite Systems

(1 star) Two-Qubit Tensor Product

Given:

$$|a\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle), \quad |b\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$$

Compute the expansion of $|a\rangle \otimes |b\rangle$ in the computational basis $\{|00\rangle, |01\rangle, |10\rangle, |11\rangle\}$.

(2 stars) Existence of the Schmidt Decomposition

For a bipartite pure state $|\psi\rangle \in \mathcal{H}_A \otimes \mathcal{H}_B$, prove that there exist orthonormal sets $\{|u_i\rangle\}$ in $\mathcal{H}_A$ and $\{|v_i\rangle\}$ in $\mathcal{H}_B$ such that:

$$|\psi\rangle = \sum_{i} \sigma_i |u_i\rangle \otimes |v_i\rangle$$

where $\sigma_i \geq 0$ and $\sum_i \sigma_i^2 = 1$.

(Hint: take the partial trace of $|\psi\rangle\langle\psi|$ over $\mathcal{H}_A$ and perform a spectral decomposition of the resulting density matrix.)

(Teaching) Feynman: Explain Entanglement Using “Two Coins”

In at most 4 sentences, explain to a friend with no physics background: what is a tensor product? What is entanglement?

You may use two coins in different scenarios (tossed, glued together, correlated) as an analogy. Be careful to distinguish “classical correlation” from “quantum entanglement.”

(Insight) What If the World Were Made of Product States?

Suppose some physical law stipulated that all multi-particle states must be decomposable product states (i.e., $|\psi\rangle = |a\rangle \otimes |b\rangle$, with no other forms allowed).

1. Would quantum computing still have an advantage? Why?
2. Would Bell’s inequality still be violated?
3. Would quantum communication (such as quantum key distribution) still exist?

---

1.7 Probability Theory Foundations

(1 star) Joint Distribution of Biased Coins

There are two biased coins: Coin A has probability of heads $p_A = 0.6$, Coin B has $p_B = 0.3$, and the two are independent.

1. Find the joint probability distribution of the outcomes of tossing both coins (4 possible combinations).
2. If, after someone tosses both coins, you learn that at least one came up heads, what is the conditional probability that both are heads?

(2 stars) Derivation of the Law of Total Probability

Let $\{B_i\}$ be a partition of the sample space $\Omega$ (mutually exclusive and $\cup_i B_i = \Omega$). Prove the law of total probability:

$$P(A) = \sum_i P(A \mid B_i) P(B_i)$$

and from it derive Bayes’ formula.

(Teaching) Feynman: The “Essential Difference” Between Classical and Quantum Probability

You engage in a short debate with a fellow student:

He says: “Isn’t quantum probability just the complex-number version of classical probability? You just replace $|a|^2$ with $|a+bi|^2$, right?”

In at most 3 sentences, point out where his understanding goes wrong. Key points: interference, phase, non-commutativity.

(Insight) Where Does Interference Come From?

In classical probability, for mutually exclusive events $A$ and $B$, $P(A \cup B) = P(A) + P(B)$.

In quantum probability, for two possible evolution paths, the probability amplitudes are added first and then the squared modulus is taken:

$$P = |\psi_1 + \psi_2|^2 = |\psi_1|^2 + |\psi_2|^2 + 2\,\text{Re}(\psi_1^*\psi_2)$$

1. This extra “cross term” $2\,\text{Re}(\psi_1^*\psi_2)$ is the source of the interference term. Under what conditions does it vanish?
2. If $\psi_1$ and $\psi_2$ are orthogonal ($\langle\psi_1|\psi_2\rangle = 0$), will there be interference?
3. Can this explain why measurement destroys interference — because measurement makes the paths “distinguishable”?

---

1.8 Fourier Analysis Primer

(1 star) Frequency Identification with the 4-Point DFT

Compute the action of $F_4$ on $\mathbf{x} = (1, 0, -1, 0)^T$. What are the frequency components of this sequence?

(Reference: the matrix elements of $F_4$ are $(F_4)_{jk} = \omega_4^{jk}$, where $\omega_4 = e^{2\pi i/4} = i$.)

(2 stars) The Convolution Theorem of the DFT

Let $\mathbf{x}, \mathbf{y} \in \mathbb{C}^N$ and define the circular convolution:

$$(\mathbf{x} * \mathbf{y})_k = \sum_{j=0}^{N-1} x_j \, y_{(k-j) \bmod N}$$

Prove that the discrete Fourier transform turns a circular convolution into an element-wise product:

$$F_N(\mathbf{x} * \mathbf{y}) = (F_N\mathbf{x}) \odot (F_N\mathbf{y})$$

where $\odot$ denotes element-wise multiplication.

(Teaching) Feynman: Explain the “Exponential Speedup” of the QFT to a Beginner

Suppose you are sitting next to a colleague who understands the classical FFT (Fast Fourier Transform) but has never encountered quantum computing. He says:

“FFT is already $O(N \log N)$, and you’re telling me QFT is $O(\log^2 N)$ — how is that possible? If $N$ is the number of data points, how can $\log N$ bits possibly hold $N$ data points?”

In at most 4 sentences, help him understand that the $N$ in QFT and the $N$ in FFT refer to “size” in different senses.

(Insight) The DFT Is a Change of Basis

The discrete Fourier transform is essentially a transformation of a vector in $\mathbb{C}^N$ from the “time-domain basis” $\{|t_k\rangle\}$ (the standard basis) to the “frequency-domain basis” $\{|f_j\rangle\}$.

1. Can you write explicit expressions for these two bases?
2. Why is the Fourier transform a “unitary transformation”? What are the practical benefits of unitarity?
3. In quantum computing, switching between the computational basis and the $X$ basis is essentially performing a “miniature Fourier transform.” Can you see the relationship between the $H$ gate (Hadamard gate) and $F_2$?

---

Reference Answers

1.1 Complex Numbers & Euler’s Formula

(1 star) Power Computation in Polar Form

$1+i = \sqrt{2}\, e^{i\pi/4}$, so $(1+i)^6 = (\sqrt{2})^6 e^{i\cdot 6\pi/4} = 8 e^{i 3\pi/2} = 8(\cos 3\pi/2 + i\sin 3\pi/2) = -8i$.

Algebraic verification: $(1+i)^2 = 1 + 2i + i^2 = 2i$, $(1+i)^4 = (2i)^2 = -4$, $(1+i)^6 = (1+i)^4 (1+i)^2 = (-4)(2i) = -8i$, consistent.

(2 stars) Proof of De Moivre’s Theorem

$(\cos\theta + i\sin\theta)^n = (e^{i\theta})^n = e^{i n\theta} = \cos(n\theta) + i\sin(n\theta)$.

When $n$ is a negative integer, let $n = -m$. Then $(\cos\theta + i\sin\theta)^{-m} = 1/(\cos\theta + i\sin\theta)^m = 1/e^{i m\theta} = e^{-i m\theta} = \cos(m\theta) - i\sin(m\theta) = \cos((-m)\theta) + i\sin((-m)\theta)$, which also holds.

(Teaching) Reference Answer Highlights: The key is “simultaneous operation” rather than “separate storage.” If you use two real numbers $(\cos\theta, \sin\theta)$, multiplication requires manually applying trigonometric identities; complex numbers encode rotation as a single multiplication $e^{i\theta_1} \cdot e^{i\theta_2} = e^{i(\theta_1+\theta_2)}$. In quantum mechanics, the superposition and interference of multiple phases naturally correspond to the addition and multiplication structure of complex numbers — representing them as pairs of real numbers loses this algebraic consistency. More succinctly: complex numbers are not “two real numbers” but “one number with internal structure,” whose multiplication structure exactly encodes rotation, and quantum mechanics is fundamentally a dynamics of rotations.

(Insight) Reference Answer Highlights: If $j^2 = 1$, then the multiplication of $z = a + bj$ is $(a_1+b_1j)(a_2+b_2j) = (a_1a_2+b_1b_2) + (a_1b_2+a_2b_1)j$. If we define $z^* = a - bj$, then $zz^* = a^2 - b^2$ (which can be positive or negative) and is not a well-defined modulus. In quantum mechanics, probability amplitudes must satisfy normalization; the “modulus” of a split-complex number can be negative or zero for non-trivial solutions, causing the probability interpretation to fail. The interference term would also change from $\cos$-type to $\cosh$-type, and probabilities could exceed 1. Hence the choice $i^2 = -1$ is necessary for the probability interpretation of quantum mechanics.

---

1.2 Vector Spaces & Hilbert Spaces

(1 star) Verifying the Legitimacy of a Basis

$|v_1\rangle$ and $|v_2\rangle$ are linearly independent: setting $\alpha|v_1\rangle + \beta|v_2\rangle = 0$ gives $\alpha + i\beta = 0$ and $i\alpha + \beta = 0$, solving to $\alpha = \beta = 0$. Two linearly independent vectors in $\mathbb{C}^2$ (dimension 2) form a basis.

Taking only one vector (e.g., $|v_1\rangle$) can only generate vectors of the form $c(1, i)^T$, and cannot generate $(1, 0)^T$ or $(0, 1)^T$, so it cannot span all of $\mathbb{C}^2$.

(2 stars) Maximal Orthonormal Set

Construct the projection operator $P = \sum_{i=1}^m |e_i\rangle\langle e_i|$. Since $m < n$, the rank of $P$ is $m$, so $I-P \neq 0$. Take $|v\rangle$ to be any non-zero column vector of $I-P$. Then for each $i$, $\langle e_i | v \rangle = \langle e_i| (I-P)|v\rangle = \langle e_i | v\rangle - \sum_j \langle e_i|e_j\rangle\langle e_j|v\rangle = \langle e_i|v\rangle - \langle e_i|v\rangle = 0$. Hence $|v\rangle$ is orthogonal to all $|e_i\rangle$.

(Teaching) Reference Answer Highlights: Use bookshelf dividers as an analogy for “basis vectors”; the position of each book is uniquely determined by its coordinates along the dividers (uniqueness of basis representation). The dimension is the number of dividers needed for the bookshelf. The same position (the same vector) described using a horizontal bookshelf versus a vertical one will have different numerical coordinates — this is a change of basis changing the coordinates.

(Insight) Reference Answer Highlights: Vector addition corresponds to function addition $(f+g)(x) = f(x)+g(x)$, and scalar multiplication corresponds to $(cf)(x) = c\cdot f(x)$. A “basis” corresponds to a set of basis functions (such as the Fourier basis $\{e^{i n x}\}$ or the polynomial basis $\{x^n\}$), and each function can be expanded in terms of these basis functions. Infinite dimensionality means infinitely many basis functions are needed to represent an arbitrary function exactly, which is fundamentally different from the finite-dimensional $\mathbb{C}^n$: in finite dimensions any vector can be represented exactly by a finite basis, whereas in infinite dimensions issues of convergence and analysis arise.

---

1.3 Linear Operators & Matrix Representation

(1 star) Computing a Commutator

$$XY = \begin{pmatrix}0&1\\1&0\end{pmatrix}\begin{pmatrix}0&-i\\i&0\end{pmatrix} = \begin{pmatrix}i&0\\0&-i\end{pmatrix} = iZ$$ $$YX = \begin{pmatrix}0&-i\\i&0\end{pmatrix}\begin{pmatrix}0&1\\1&0\end{pmatrix} = \begin{pmatrix}-i&0\\0&i\end{pmatrix} = -iZ$$

Hence $[X, Y] = XY - YX = iZ - (-iZ) = 2iZ$.

(2 stars) Eigenvalues of a Hermitian Operator Are Real

Let $A|\lambda\rangle = \lambda|\lambda\rangle$. Compute $\langle\lambda|A|\lambda\rangle$:

$\langle\lambda|A|\lambda\rangle = \langle\lambda| (\lambda|\lambda\rangle) = \lambda\langle\lambda|\lambda\rangle = \lambda \| |\lambda\rangle\|^2$

On the other hand, using Hermiticity $A^\dagger = A$:

$\langle\lambda|A|\lambda\rangle = (\langle\lambda|A|\lambda\rangle)^\dagger = (A|\lambda\rangle)^\dagger |\lambda\rangle = (\lambda^*\langle\lambda|)|\lambda\rangle = \lambda^* \||\lambda\rangle\|^2$

Therefore $\lambda = \lambda^*$, so $\lambda$ is real.

(Teaching) Reference Answer Highlights: A unitary operator is like a perfect revolving door — you push the door, it rotates a full circle and returns to its original position, and you emerge from the other side with your height and weight (length) unchanged. Similarly, after a quantum state evolves through a unitary gate, the sum of probabilities remains 1. If the door were not unitary (for instance, you came out half as tall), the sum of probabilities would no longer be 1, which is physically impossible. Concretely, a non-unitary operation could be “gain” (probability > 1) or “loss” (probability < 1), neither consistent with the requirement of unitary evolution in quantum mechanics.

(Insight) Reference Answer Highlights: Under a change of basis, the operator transforms as $A' = P^{-1}AP$. Invariants include: eigenvalues (spectrum), trace ($\text{tr}(A)$), determinant, rank, and characteristic polynomial. Quantum mechanics focuses more on the operator itself than on its matrix representation because physical observation outcomes (eigenvalues, probabilities) are invariant under changes of basis — they are intrinsic physical properties that do not depend on the observer’s mathematical description.

---

1.4 Inner Products, Norms & Orthogonality

(1 star) Gram-Schmidt Orthogonalization

Let $|u_1\rangle = |v_1\rangle / \| |v_1\rangle\| = (1,1,0)^T / \sqrt{2}$.

Compute the projection component: $\langle u_1 | v_2\rangle = \frac{1}{\sqrt{2}}(1,1,0)(1,0,1)^T = \frac{1}{\sqrt{2}}$.

$|w_2\rangle = |v_2\rangle - \langle u_1 | v_2\rangle |u_1\rangle = (1,0,1)^T - \frac{1}{2}(1,1,0)^T = (\frac12, -\frac12, 1)^T$.

Normalize: $\| |w_2\rangle\| = \sqrt{1/4 + 1/4 + 1} = \sqrt{3/2}$.

$|u_2\rangle = \frac{1}{\sqrt{6}}(1, -1, 2)^T$.

Orthonormal basis: $|u_1\rangle = \frac{1}{\sqrt{2}}(1,1,0)^T$, $|u_2\rangle = \frac{1}{\sqrt{6}}(1,-1,2)^T$.

(2 stars) The Parallelogram Law

$$\begin{aligned} \| |v\rangle + |w\rangle\|^2 &= \langle v+w | v+w\rangle = \langle v|v\rangle + \langle v|w\rangle + \langle w|v\rangle + \langle w|w\rangle \\ \| |v\rangle - |w\rangle\|^2 &= \langle v-w | v-w\rangle = \langle v|v\rangle - \langle v|w\rangle - \langle w|v\rangle + \langle w|w\rangle \end{aligned}$$

Adding the two equations, the cross terms cancel, yielding $2\langle v|v\rangle + 2\langle w|w\rangle = 2(\| |v\rangle\|^2 + \| |w\rangle\|^2)$.

Geometric meaning: the sum of the squares of the diagonals of a parallelogram equals the sum of the squares of its four sides — this characterizes inner product spaces and does not necessarily hold in general normed spaces.

(Teaching) Reference Answer Highlights: The flashlight beam shining on a wall creates a spot of light — this is “the projection of the vector in the direction of the flashlight.” If the wall direction is $|w\rangle$ and the flashlight direction is $|v\rangle$, the projection is the “shadow” of $|v\rangle$ falling on $|w\rangle$. Regarding quantum measurement: the projection operator $P = |\psi\rangle\langle\psi|$ describes the “collapse” of the quantum state onto a particular direction during measurement.

(Insight) Reference Answer Highlights: The left-hand side of the Cauchy-Schwarz inequality $|\langle v | w \rangle| \leq \|v\|\|w\|$ can be rewritten as $|\langle \Delta A \,\psi | \Delta B \,\psi\rangle|$, exactly matching the structure of the uncertainty principle. The commonality is: the modulus of the inner product of two vectors (or two deviations) is bounded by the product of their lengths. This reveals that “uncertainty” is essentially the triangle inequality in vector geometry, not some mysterious quantum mysticism — it arises from the geometric structure of the inner product space itself.

---

1.5 Eigenvalues & Eigenvectors

(1 star) The Eigensystem of the Hadamard Matrix

Characteristic equation: $\det\begin{pmatrix}1/\sqrt{2}-\lambda & 1/\sqrt{2} \\ 1/\sqrt{2} & -1/\sqrt{2}-\lambda\end{pmatrix} = 0$

That is, $(-1/\sqrt{2}-\lambda)(1/\sqrt{2}-\lambda) - 1/2 = 0$, $-\frac12 + \lambda^2 - \frac12 = 0$, $\lambda^2 = 1$, $\lambda = \pm 1$.

For $\lambda = +1$, solving gives $|h_+\rangle = \frac{1}{\sqrt{4-2\sqrt{2}}}(1, \sqrt{2}-1)^T$. For $\lambda = -1$, by orthogonality, $|h_-\rangle \propto (\sqrt{2}-1, -1)^T$, which can be normalized.

(Note: a more common way to express this is $H|+\rangle = |0\rangle$, $H|0\rangle = |+\rangle$, but that is an understanding in the $X$ basis.)

(2 stars) Commuting Operators Share Eigenvectors

Let $A|a_i\rangle = a_i|a_i\rangle$ and decompose the space into the eigenspaces of $A$: $V_a = \{|v\rangle : A|v\rangle = a|v\rangle\}$. Since $[A,B]=0$, for any $|v\rangle \in V_a$, $A(B|v\rangle) = B(A|v\rangle) = a(B|v\rangle)$, so $B|v\rangle \in V_a$. Restricted to $V_a$, $B$ is a Hermitian operator and can be diagonalized within $V_a$. Diagonalizing within each eigenspace yields a simultaneous diagonalization.

(Teaching) Reference Answer Highlights: White light (an arbitrary quantum state) passes through a prism (the spectral decomposition of a Hermitian operator) and is decomposed into light of different colors (eigenvectors), each color corresponding to a specific wavelength (eigenvalue). The spectral decomposition formula $A = \sum_i \lambda_i |\lambda_i\rangle\langle\lambda_i|$ tells us: the action of operator $A$ is “first measure the components along each eigen-direction, then weight by the eigenvalues and sum.” Its importance for quantum measurement is: measurement is “decomposing you into a combination of eigenvectors, then telling me which eigenvalue you land on.”

(Insight) Reference Answer Highlights: If $A$ is not Hermitian, its eigenvalues can be complex and cannot serve as “observable physical quantities” — measurement outcomes must be real numbers. Measurement probability: $P(\lambda_1) = |\alpha|^2$. After measurement, the state collapses to $|\lambda_1\rangle$, which can be described using a projection operator: $|\psi\rangle \to \frac{P_{\lambda_1}|\psi\rangle}{\|P_{\lambda_1}|\psi\rangle\|}$, where $P_{\lambda_1} = |\lambda_1\rangle\langle\lambda_1|$.

---

1.6 Tensor Products & Composite Systems

(1 star) Two-Qubit Tensor Product

$|a\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$, $|b\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$.

$$\begin{aligned} |a\rangle \otimes |b\rangle &= \frac12(|0\rangle + |1\rangle) \otimes (|0\rangle - |1\rangle) \\ &= \frac12(|00\rangle - |01\rangle + |10\rangle - |11\rangle) \end{aligned}$$

In vector form: $\frac12(1, -1, 1, -1)^T$.

(2 stars) Existence of the Schmidt Decomposition

Consider the partial trace of $|\psi\rangle\langle\psi|$ over $\mathcal{H}_A$: $\rho_A = \text{tr}_B(|\psi\rangle\langle\psi|)$. $\rho_A$ is a positive semidefinite operator with trace 1. Its spectral decomposition is $\rho_A = \sum_i \sigma_i^2 |u_i\rangle\langle u_i|$, where $\sigma_i^2 > 0$ are eigenvalues and $|u_i\rangle$ are the corresponding eigenvectors. Define $|v_i\rangle = \frac{1}{\sigma_i} (\langle u_i| \otimes I_B) |\psi\rangle$. One can verify that $\{|v_i\rangle\}$ is orthonormal and $|\psi\rangle = \sum_i \sigma_i |u_i\rangle \otimes |v_i\rangle$. Also, $\sum_i \sigma_i^2 = \text{tr}(\rho_A) = 1$.

(Teaching) Reference Answer Highlights: Two independent coins — whether A comes up heads or tails does not affect B (a product state). Two coins glued together — you only know “either both heads or both tails” but not which (classical correlation). Two “quantum entangled coins” — they are not merely correlated; before you measure A and find heads, it is in a superposition of heads and tails, and simultaneously B is also in the corresponding superposition. The instant you measure A, B’s state is simultaneously determined, regardless of the distance between them. The tensor product $\otimes$ is mathematically the operation of “combining two systems.” An entangled state is one that cannot be written in the form $|a\rangle\otimes|b\rangle$.

(Insight) Reference Answer Highlights: If all states were product states, quantum computing would be equivalent to classical probabilistic computation (each qubit evolves independently), with no exponential state space and no parallelism from entanglement. Bell’s inequality would not be violated (since there is no entanglement to produce stronger correlations). Quantum communication protocols (such as BB84, which does not directly require entanglement but whose security and entanglement distillation protocols rely entirely on entanglement) would be severely limited or impossible.

---

1.7 Probability Theory Foundations

(1 star) Joint Distribution of Biased Coins

1. Four outcomes:

   • (H, H): $0.6 \times 0.3 = 0.18$
   • (H, T): $0.6 \times 0.7 = 0.42$
   • (T, H): $0.4 \times 0.3 = 0.12$
   • (T, T): $0.4 \times 0.7 = 0.28$

2. At least one heads: $P = 0.18 + 0.42 + 0.12 = 0.72$. Both heads: 0.18. Conditional probability: $0.18 / 0.72 = 0.25$.

(2 stars) Derivation of the Law of Total Probability

For any event $A$, $A = A \cap \Omega = A \cap (\cup_i B_i) = \cup_i (A \cap B_i)$. Since the $B_i$ are mutually exclusive, the $A \cap B_i$ are also mutually exclusive. By the additivity of probability:

$P(A) = \sum_i P(A \cap B_i) = \sum_i P(A \mid B_i) P(B_i)$.

Bayes’ formula: $P(B_j \mid A) = \frac{P(A \cap B_j)}{P(A)} = \frac{P(A \mid B_j) P(B_j)}{\sum_i P(A \mid B_i) P(B_i)}$.

(Teaching) Reference Answer Highlights: It is not as simple as “replacing real numbers with complex numbers.” In classical probability, probabilities add directly: $P = p_1 + p_2$. In quantum probability, probability amplitudes (complex numbers) are added first and then the modulus is taken: $P = |\psi_1 + \psi_2|^2 = |\psi_1|^2 + |\psi_2|^2 + 2\text{Re}(\psi_1^*\psi_2)$. The extra cross term $2\text{Re}(\psi_1^*\psi_2)$ depends on the relative phase — a concept that has no analogue in classical probability. Phase can lead to “destructive interference” (where the probability actually decreases), which is impossible in classical probability.

(Insight) Reference Answer Highlights: The cross term vanishes when $\psi_1$ and $\psi_2$ are orthogonal (i.e., $\langle\psi_1|\psi_2\rangle = 0$) — which corresponds to the two paths being “physically distinguishable.” When the paths are indistinguishable (as in the double-slit experiment when we do not observe which slit), $\psi_1$ and $\psi_2$ are not orthogonal and the interference term appears. This is precisely the core of how measurement causes decoherence: measurement makes the paths distinguishable and thereby eliminates the interference term.

---

1.8 Fourier Analysis Primer

(1 star) Frequency Identification with the 4-Point DFT

$\omega_4 = i$, and $F_4$ is the same matrix as in Exercise 1.8.3 of the workbook.

$\mathbf{y} = F_4(1,0,-1,0)^T$:

$y_0 = 1\cdot1 + 1\cdot0 + 1\cdot(-1) + 1\cdot0 = 0$ $y_1 = 1\cdot1 + i\cdot0 + i^2\cdot(-1) + i^3\cdot0 = 1 - 1 = 0$ $y_2 = 1\cdot1 + (-1)\cdot0 + 1\cdot(-1) + (-1)\cdot0 = 0$ $y_3 = 1\cdot1 + (-i)\cdot0 + (-1)\cdot(-1) + i\cdot0 = 1 + 1 = 2$

So $\mathbf{y} = (0, 0, 0, 2)^T$. The sequence $(1,0,-1,0)$ is a pure sine wave of period 4; the frequency $f = 3/4$ (or $-1/4$) corresponds to $y_3$ being non-zero.

(2 stars) The Convolution Theorem of the DFT

$(F_N(\mathbf{x}*\mathbf{y}))_k = \sum_{n=0}^{N-1} \omega_N^{kn} \sum_{j=0}^{N-1} x_j y_{(n-j)\bmod N}$

Swap the order of summation: $= \sum_{j=0}^{N-1} \omega_N^{kj} x_j \sum_{n=0}^{N-1} \omega_N^{k(n-j)} y_{(n-j)\bmod N}$

Let $m = n-j$ (mod $N$). The second sum becomes $\sum_{m=0}^{N-1} \omega_N^{km} y_m = (F_N\mathbf{y})_k$.

Hence $(F_N(\mathbf{x}*\mathbf{y}))_k = (F_N\mathbf{x})_k \cdot (F_N\mathbf{y})_k$, the element-wise product.

(Teaching) Reference Answer Highlights: The $N$ in FFT is the number of data points, while the $N$ in QFT is the dimension of the quantum state space (there are $2^n$ amplitudes). The input to the QFT is not $N$ classical data points but the $2^n$ probability amplitudes encoded by $n$ qubits. The QFT circuit needs only $O(n^2) = O(\log^2 N)$ gates to simultaneously transform all $2^n$ amplitudes — quantum parallelism makes this “exponential leap” possible. The key insight: the QFT is not “computing a classical DFT faster” but using quantum parallelism to directly manipulate a high-dimensional state.

(Insight) Reference Answer Highlights: The time-domain basis $\{|t_k\rangle\}$ is the standard basis $\{|0\rangle, |1\rangle, \ldots, |N-1\rangle\}$, and the $j$-th frequency-domain basis vector $\{|f_j\rangle\}$ is $\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} \omega_N^{-jk} |t_k\rangle$. The Fourier transform matrix $U_{\text{QFT}} = F_N/\sqrt{N}$ satisfies $U^\dagger U = I$, so it is a unitary transformation. Unitarity guarantees energy conservation (Parseval’s theorem). $H = F_2/\sqrt{2}$: the Hadamard gate is precisely the $N=2$ quantum Fourier transform. More generally, $H^{\otimes n}$ performs a “local Fourier transform” on $n$ qubits simultaneously, while the full QFT also includes controlled phase gates — the difference is that $H^{\otimes n}$ can only produce equal-weight superpositions, whereas the QFT can encode frequency information.

---

Open Questions

The following questions have no standard answers. They are designed to stimulate cross-disciplinary thinking, literature reading, and creative reasoning.

1. Complex Numbers in Circuits vs. in Quantum Mechanics

   Complex numbers are used in circuit analysis to simplify AC circuit calculations (the impedance method), but they are a “convenience” rather than a “necessity” — you could also slog through with differential equations. In quantum mechanics, complex numbers appear to be “necessary” — the Schrodinger equation explicitly contains $i$, and probability amplitudes must be complex. What is the essential difference in the demand for complex numbers between these two contexts? Is there an experiment that can prove complex numbers are “real” in quantum mechanics rather than merely convenient?

2. Can Quantum Probability Be Fully Described Using Real Vector Spaces?

   Some researchers have attempted to reconstruct quantum mechanics using real Hilbert spaces (with all coefficients real). Consult the literature (or reason on your own): how does a real-vector-space quantum mechanics differ from the standard complex quantum mechanics? Is there an experiment that can distinguish between them? (Hint: consider the algebraic closure property of complex numbers and the differences in entanglement structure.)

3. “Matrix Mechanics” vs. “Wave Mechanics” — Two Equivalent Mathematical Systems

   Heisenberg created matrix mechanics (describing quantum mechanics with infinite-dimensional matrices), and Schrodinger created wave mechanics (using partial differential equations). Schrodinger later proved the two are equivalent. From the perspectives of linear operators (matrices) and function spaces (Hilbert spaces), can you explain to a second-year physics major, in no more than 500 words, why the two are “two sides of the same coin”?

4. The “Curse of Dimensionality” of the Tensor Product — The Limit of Classical Simulation

   The state space of an $n$-qubit system has dimension $2^n$. An $n=50$ quantum computer needs $2^{50} \approx 10^{15}$ complex numbers to describe its state, far exceeding the memory of classical computers. But physically, are we really “storing” that much information? Or are these amplitudes merely mathematical constructs? Consult discussions on the “quantum state complexity hypothesis” and present your own understanding.

5. The Fourier Transform Is Everywhere

   The Fourier transform appears in signal processing, quantum mechanics (position-momentum representation transformation), optics (Fraunhofer diffraction is essentially a Fourier transform), and even number theory (the $\zeta$ function and Fourier analysis). Detecting quantum nonlocality via the CHSH inequality also employs ideas from Fourier analysis. Choose a field you are familiar with (engineering, physics, mathematics, data science, music), compare it with the quantum Fourier transform, and write a short essay of about 300 words describing their connections and differences.