Chapter 3: Introduction to Quantum Computing

Chapter 3: Foundations of Quantum Computing

In the previous two chapters, we established all the mathematical and physical tools necessary to understand quantum computing. From complex numbers, Hilbert spaces, and linear algebra to the five postulates of quantum mechanics, spin- $1/2$ , the Bloch sphere, and measurement theory — all of this preparation points toward a single goal: Quantum Computing. This chapter will piece these fragments together into a complete picture, starting from the most basic qubit and progressively building toward the core ideas of quantum algorithms. Each section will repeatedly reference the content of the previous two chapters, allowing the reader to see how those abstract concepts come to life in quantum computing.

3.1 Qubits

Definition of a Qubit

A Quantum Bit (Qubit) is the fundamental unit of information in quantum computing, analogous to the bit in classical computing. However, unlike a classical bit, which can only be 0 or 1, a qubit can exist in a Superposition of 0 and 1.

The quantum state of a single qubit can be expressed as:

$\lvert\psi\rangle = \alpha\lvert0\rangle + \beta\lvert1\rangle$

where $\alpha, \beta \in \mathbb{C}$ are complex Probability Amplitudes, satisfying the normalization condition:

$\lvert\alpha\rvert^2 + \lvert\beta\rvert^2 = 1$

Here $\lvert0\rangle$ and $\lvert1\rangle$ constitute the Computational Basis, corresponding to an orthonormal basis of the two-dimensional Hilbert space $\mathbb{C}^2$ . Recall the bra-ket notation we learned in Section 1.2: $\lvert0\rangle = \begin{pmatrix}1\\0\end{pmatrix}$ , $\lvert1\rangle = \begin{pmatrix}0\\1\end{pmatrix}$ . These two basis vectors correspond to the spin-up and spin-down states of a spin- $1/2$ particle, the simplest non-trivial quantum system in quantum mechanics.

Remember spin- $1/2$ from Section 2.4? The qubit is precisely the abstraction of spin- $1/2$ . In the Stern-Gerlach experiment, the electron’s spin state lives in a two-dimensional complex vector space, with spin-up $\lvert\uparrow\rangle$ corresponding to $\lvert0\rangle$ and spin-down $\lvert\downarrow\rangle$ corresponding to $\lvert1\rangle$ . The qubit borrows this mathematical structure but is no longer tied to a specific physical realization — it can be spin, energy levels, photon polarization, or any quantum system with two orthogonal states. The power of this abstraction lies in the fact that, regardless of the underlying physical implementation, the mathematical description of a qubit is unified.

Bloch Sphere Representation

Every qubit can be represented as a point on the Bloch sphere. Recalling Section 2.5, using the irrelevance of the global phase, we can parameterize any single-qubit state as:

$\lvert\psi\rangle = \cos\frac{\theta}{2}\lvert0\rangle + e^{i\phi}\sin\frac{\theta}{2}\lvert1\rangle$

where $\theta \in [0, \pi]$ , $\phi \in [0, 2\pi)$ . This parameterization comes directly from the Bloch sphere coordinates in Section 2.5:

$\vec{n} = (\sin\theta\cos\phi, \sin\theta\sin\phi, \cos\theta)$

Every point on the sphere corresponds to a Pure State. In particular:

North pole ( $\theta = 0$ ): $\lvert0\rangle$
South pole ( $\theta = \pi$ ): $\lvert1\rangle$
Equator ( $\theta = \pi/2$ ): equal-probability superposition states, such as $\lvert+\rangle = (\lvert0\rangle + \lvert1\rangle)/\sqrt{2}$ ( $\phi = 0$ ) and $\lvert-\rangle = (\lvert0\rangle - \lvert1\rangle)/\sqrt{2}$ ( $\phi = \pi$ )

Points on the sphere are pure states; points inside the sphere are Mixed States. This distinction is crucial and will be used repeatedly throughout the text. The Bloch sphere is a powerful tool for visualizing single-qubit states: state evolution corresponds to trajectories on the sphere, gate operations correspond to rotations, and measurement corresponds to projection.

Classical Bits vs. Qubits

A classical bit is deterministically either 0 or 1. A qubit, by contrast, achieves superposition through probability amplitudes. But it must be emphasized: a superposition state is not a probabilistic mixture.

Consider a classical probabilistic mixture: with probability $p$ it is 0, and with probability $1-p$ it is 1. The corresponding density matrix is:

$\rho_{\text{classical}} = p\lvert0\rangle\langle0\rvert + (1-p)\lvert1\rangle\langle1\rvert = \begin{pmatrix}p&0\\0&1-p\end{pmatrix}$

This is completely different from the density matrix $\rho = \lvert\psi\rangle\langle\psi\rvert$ of the quantum superposition state $\lvert\psi\rangle = \alpha\lvert0\rangle + \beta\lvert1\rangle$ . A classical mixture corresponds to a point inside the Bloch sphere (on the $z$ -axis), while a quantum pure state corresponds to a point on the surface of the sphere. In Section 2.5, we already saw that the Bloch vector of a mixed state has length less than 1, having lost coherence. This distinction is the fundamental source of quantum computing’s advantage: superposition states preserve the relative phase between probability amplitudes, whereas classical mixtures completely lose phase information.

Physical Implementations of Qubits

Qubits are not purely mathematical constructs — they correspond to real physical systems. The main physical implementations include:

Spin- $1/2$ Particles: The spin-up/spin-down of electrons or atomic nuclei (Section 2.4). This is the most intuitive physical picture of a qubit. NMR quantum computing exploits the quantum states of nuclear spins for computation, typically requiring operation in cryogenic, strong-magnetic-field environments.
Ion Traps: Two internal energy levels of trapped ions (typically two sub-levels of the hyperfine ground state) encode $\lvert0\rangle$ and $\lvert1\rangle$ . Lasers precisely control transitions between energy levels. Ion-trap qubits have relatively long coherence times but slower gate operation speeds.
Superconducting Qubits: Anharmonic circuits built using Josephson Junctions. Charge qubits, flux qubits, and Transmons are the main types. They currently dominate many quantum computing platforms because they can leverage existing semiconductor fabrication processes and offer fast gate speeds.
Photon Polarization: Horizontal/vertical polarization (or circular polarization) of photons serves as $\lvert0\rangle$ and $\lvert1\rangle$ . Photons are stable at room temperature and well-suited for quantum communication, but two-photon interactions are difficult, making two-qubit gates challenging.
Topological Qubits: Exploit topologically protected states such as Majorana zero modes. In theory, they possess extremely strong noise immunity, but they remain at an early research stage.

The reader need not delve into the details of each implementation, but should know this: qubits are real physical systems, governed by the five postulates of quantum mechanics. Regardless of the chosen physical implementation, the mathematical structure of the qubit is unified — this is precisely the elegance of quantum computing theory.

Multiple Qubits

When we consider multiple qubits, the tensor product from Section 1.6 becomes the central tool. The state space of two qubits is the tensor product of their individual spaces:

$\mathbb{C}^2 \otimes \mathbb{C}^2 = \mathbb{C}^4$

In general, the dimension of the state space of $n$ qubits is:

$\dim(\mathbb{C}^2)^{\otimes n} = 2^n$

This means that $n$ qubits require $2^n$ complex probability amplitudes to describe their state. This is the fundamental source of quantum computing’s exponential advantage. For example, 50 qubits require $2^{50} \approx 10^{15}$ complex numbers to describe, which already exceeds the memory capacity of many classical computers. 300 qubits would require $2^{300} \approx 10^{90}$ complex numbers — a figure larger than the number of atoms in the observable universe — hinting at the profound fact that quantum systems are classically intractable to simulate.

For two qubits, the computational basis consists of four orthonormal states:

$\lvert00\rangle = \lvert0\rangle \otimes \lvert0\rangle, \quad \lvert01\rangle = \lvert0\rangle \otimes \lvert1\rangle$ $\lvert10\rangle = \lvert1\rangle \otimes \lvert0\rangle, \quad \lvert11\rangle = \lvert1\rangle \otimes \lvert1\rangle$

A general two-qubit state is:

$\lvert\psi\rangle = \alpha_{00}\lvert00\rangle + \alpha_{01}\lvert01\rangle + \alpha_{10}\lvert10\rangle + \alpha_{11}\lvert11\rangle$

satisfying $\sum_{i,j} |\alpha_{ij}|^2 = 1$ .

If a state can be written as $\lvert\psi\rangle = \lvert\psi_1\rangle \otimes \lvert\psi_2\rangle$ , it is called a Separable State; otherwise, it is called an Entangled State, which is the central topic of Section 3.3. The existence of entangled states is key to quantum computing surpassing classical computing: it means that the information of the system cannot be decomposed into the sum of the information of its subsystems.

Summary: A qubit is the unit of information in quantum computing, described by a unit vector in a two-dimensional Hilbert space, corresponding to a point on the Bloch sphere. Its essential distinction from a classical bit lies in superposition and phase coherence — superposition is not a probabilistic mixture but a quantum coherent superposition that preserves phase information. Multiple qubits are combined via the tensor product, with the state-space dimension growing exponentially, providing an exponentially large workspace for quantum parallelism.

Connection to Quantum Computing: The qubit is the starting point of all quantum algorithms. The $2^n$ -dimensional state space of $n$ qubits provides an exponentially large “workspace,” and superposition states allow simultaneous processing of multiple computational paths. The leap from spin- $1/2$ to the abstract qubit marks our transition from natural quantum-mechanical phenomena to artificial quantum information processing. Understanding the mathematical structure and physical implementations of qubits is the first step into the world of quantum algorithms.

3.2 Single-Qubit Gates

Quantum Gates = Unitary Operators

In classical computing, gates (such as AND, OR, NOT) perform deterministic transformations on bits. In quantum computing, a Quantum Gate corresponds to a Unitary Operator $U$ , satisfying:

$U^\dagger U = UU^\dagger = I$

Recall the discussion of unitary matrices in Section 1.3: unitary transformations preserve the norm of vectors. Thus, if $\lvert\psi\rangle$ satisfies the normalization condition, then $U\lvert\psi\rangle$ also does:

$\langle\psi\rvert U^\dagger U\lvert\psi\rangle = \langle\psi\rvert\psi\rangle = 1$

This means quantum gates preserve probability conservation — the unitary matrices of Section 1.3 are precisely the mathematical embodiment of quantum gates. The reversibility (unitarity) of quantum gates is one of the fundamental differences between quantum and classical computing: classical gates like AND and OR are irreversible (multiple inputs map to the same output), whereas quantum gates must be reversible.

Since any unitary transformation can be decomposed into a sequence of $2\times 2$ unitary matrices, single-qubit gates form the fundamental building blocks of all quantum gates. The matrix operations and properties learned in Section 1.3 are now direct tools for manipulating quantum states.

Pauli Gates

In Section 1.3, we already thoroughly introduced the Pauli matrices. Now they reappear as quantum gates, becoming the most basic quantum operations:

$X$ Gate (Quantum NOT):

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

$X\lvert0\rangle = \lvert1\rangle, \quad X\lvert1\rangle = \lvert0\rangle$

The $X$ gate flips the computational basis, analogous to the classical NOT gate. On the Bloch sphere, $X$ corresponds to a rotation of $\pi$ ( $180°$ ) about the $x$ -axis. It moves the north pole to the south pole, the south pole to the north pole, while points on the equator stay on the equator but flip their $\phi$ coordinate.

$Z$ Gate (Phase Flip):

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

$Z\lvert0\rangle = \lvert0\rangle, \quad Z\lvert1\rangle = -\lvert1\rangle$

The $Z$ gate leaves $\lvert0\rangle$ unchanged but adds a $\pi$ phase to $\lvert1\rangle$ . On the Bloch sphere, $Z$ corresponds to a rotation of $\pi$ about the $z$ -axis. It transforms $\lvert+\rangle$ on the equator into $\lvert-\rangle$ , and $\lvert-\rangle$ into $\lvert+\rangle$ .

$Y$ Gate:

$Y = \begin{pmatrix}0&-i\\i&0\end{pmatrix} = iXZ$

$Y\lvert0\rangle = i\lvert1\rangle, \quad Y\lvert1\rangle = -i\lvert0\rangle$

$Y$ is the combination of $X$ and $Z$ (up to a global phase $i$ ). On the Bloch sphere, $Y$ corresponds to a rotation of $\pi$ about the $y$ -axis. The three Pauli gates each correspond to a $\pi$ rotation about one of the three coordinate axes, forming the basis of Bloch sphere rotations.

The following table summarizes the action of the Pauli gates on key states:

Gate	$\lvert0\rangle$	$\lvert1\rangle$	$\lvert+\rangle$
$X$	$\lvert1\rangle$	$\lvert0\rangle$	$\lvert+\rangle$
$Z$	$\lvert0\rangle$	$-\lvert1\rangle$	$\lvert-\rangle$
$Y$	$i\lvert1\rangle$	$-i\lvert0\rangle$	$-i\lvert-\rangle$

Note that $X\lvert+\rangle = \lvert+\rangle$ and $Z\lvert+\rangle = \lvert-\rangle$ — the $X$ gate is diagonal in the $\lvert\pm\rangle$ basis (eigenvalues $\pm 1$ ), while the $Z$ gate is diagonal in the $\lvert0/1\rangle$ basis. This reveals how different gates act in different bases and hints at the importance of basis transformations in quantum computing.

Hadamard Gate

The Hadamard Gate $H$ is one of the most important single-qubit gates in quantum computing:

$H = \frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&-1\end{pmatrix}$

Its action is to transform the computational basis into the superposition basis:

$H\lvert0\rangle = \frac{1}{\sqrt{2}}(\lvert0\rangle + \lvert1\rangle) = \lvert+\rangle$ $H\lvert1\rangle = \frac{1}{\sqrt{2}}(\lvert0\rangle - \lvert1\rangle) = \lvert-\rangle$

And vice versa:

$H\lvert+\rangle = \lvert0\rangle, \quad H\lvert-\rangle = \lvert1\rangle$

The $H$ gate transforms the computational basis into the $X$ basis, which is crucial for measurement and algorithms. For example, measuring $\lvert+\rangle$ in the $Z$ basis yields 0 or 1 with equal probability; but if we first apply an $H$ gate and then measure, we deterministically obtain 0. This ability to change bases is at the heart of many quantum algorithms.

Important properties of the Hadamard gate:

Self-inverse: $H^2 = I$ , meaning two $H$ gates are equivalent to the identity operation
Conjugation relations: $HXH = Z$ , $HZH = X$

The first property means $H$ is its own inverse. The second property shows that the $H$ gate can “swap” the roles of $X$ and $Z$ — frequently used in quantum error correction and algorithm design. For example, if you want to measure a state in the $X$ basis, you can first apply an $H$ gate (rotating the $X$ basis to the $Z$ basis), and then measure in the $Z$ basis.

On the Bloch sphere, $H$ corresponds to a rotation of $\pi$ about the axis $(\hat{x} + \hat{z})/\sqrt{2}$ . It maps the $z$ -axis to the $x$ -axis and the $x$ -axis to the $z$ -axis, intuitively demonstrating the symmetry between the computational basis and the $X$ basis.

Phase Gates

$S$ Gate (Phase Gate):

$S = \begin{pmatrix}1&0\\0&i\end{pmatrix}$

$S\lvert0\rangle = \lvert0\rangle, \quad S\lvert1\rangle = i\lvert1\rangle$

The $S$ gate adds a $\pi/2$ phase to $\lvert1\rangle$ . Note that $S^2 = Z$ . On the Bloch sphere, the $S$ gate corresponds to a rotation of $\pi/2$ about the $z$ -axis, rotating states on the equator by a quarter turn along the $z$ direction.

$T$ Gate ( $\pi/8$ Gate):

$T = \begin{pmatrix}1&0\\0&e^{i\pi/4}\end{pmatrix}$

$T\lvert0\rangle = \lvert0\rangle, \quad T\lvert1\rangle = e^{i\pi/4}\lvert1\rangle$

The $T$ gate adds a $\pi/4$ phase, and $T^2 = S$ , $T^4 = Z$ . The $T$ gate corresponds to a rotation of $\pi/4$ about the $z$ -axis and is one of the key gates for implementing arbitrary single-qubit rotations. Together with the $H$ gate and the CNOT gate, the $T$ gate forms a universal gate set for quantum computing.

Universal Gate Sets

A set of quantum gates is called Universal if any unitary transformation can be approximated to arbitrary precision by a sequence of gates from that set. The Solovay-Kitaev Theorem guarantees the efficiency of this approximation: a circuit of size $O(\log^c(1/\epsilon))$ can approximate any $n$ -qubit unitary transformation to precision $\epsilon$ .

Important facts:

$\{H, S, T, \text{CNOT}\}$ is a universal single-qubit + two-qubit gate set
$\{H, T, \text{CNOT}\}$ is also universal (since $S = T^2$ )

This means that using only the $H$ , $T$ , and CNOT gates (Section 3.3), we can implement any quantum algorithm. The existence of a universal gate set is the theoretical foundation for the programmability of quantum computers: there is no need to design specialized hardware for each algorithm — one simply combines a small number of elementary gates.

Rotations on the Bloch Sphere

Recall Section 2.5: any single-qubit unitary transformation can be written as

$U = e^{i\alpha} R_{\hat{n}}(\theta) = e^{i\alpha} e^{-i\frac{\theta}{2}\vec{\sigma}\cdot\hat{n}}$

where $\vec{\sigma} = (X, Y, Z)$ is the Pauli vector, $\hat{n}$ is the unit rotation axis, and $\theta$ is the rotation angle. This decomposition is a direct consequence of the spectral theorem from Section 1.5.

Specifically:

$X = -iR_x(\pi)$ , rotation of $\pi$ about the $x$ -axis
$Y = -iR_y(\pi)$ , rotation of $\pi$ about the $y$ -axis
$Z = -iR_z(\pi)$ , rotation of $\pi$ about the $z$ -axis
$H = -iR_{(\hat{x}+\hat{z})/\sqrt{2}}(\pi)$
$S = e^{i\pi/4}R_z(\pi/2)$

This geometric perspective intuitively shows how each gate moves states on the Bloch sphere. For example, any single-qubit state can be prepared from $\lvert0\rangle$ using appropriate $R_z$ and $R_y$ rotations — this is the basic method of quantum state preparation.

Summary: Single-qubit gates are $2\times 2$ unitary matrices that preserve the normalization of states. Pauli gates implement bit flips and phase flips, corresponding to $\pi$ rotations on the Bloch sphere. The Hadamard gate transforms between the computational basis and the $X$ basis and is a key tool for creating superposition states. The phase gates $S$ and $T$ provide continuous phase control. The existence of a universal gate set means that a small number of elementary gates can implement any quantum computation.

Connection to Quantum Computing: Single-qubit gates are the basic building blocks of quantum circuits. The Hadamard gate is indispensable for creating superposition states (the prerequisite for quantum parallelism). The existence of a universal gate set means we only need a small number of elementary gates to implement any quantum computation, which is the foundation for the programmability of quantum computers. Understanding the geometric action of each gate on the Bloch sphere is key to intuitively grasping quantum state evolution.

3.3 Multi-Qubit Gates & Entanglement

Tensor Product Review

Before discussing multi-qubit gates, let us review the tensor product from Section 1.6. If $A$ acts on the first qubit and $B$ acts on the second qubit, the joint operation is their tensor product $A \otimes B$ , acting on the composite state $\lvert a\rangle \otimes \lvert b\rangle$ :

$(A \otimes B)(\lvert a\rangle \otimes \lvert b\rangle) = A\lvert a\rangle \otimes B\lvert b\rangle$

For $2\times 2$ matrices $A = \begin{pmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{pmatrix}$ and $B$ , we have:

$A \otimes B = \begin{pmatrix}a_{11}B & a_{12}B\\a_{21}B & a_{22}B\end{pmatrix}$

This is a $4\times 4$ matrix. Key properties: $(A \otimes B)(C \otimes D) = AC \otimes BD$ , $(A \otimes B)^\dagger = A^\dagger \otimes B^\dagger$ . These properties guarantee the unitarity of tensor products: if $A$ and $B$ are both unitary, then $A \otimes B$ is also unitary.

CNOT Gate

The Controlled-NOT (CNOT) gate is the most important two-qubit gate and the key to generating entanglement. Without the CNOT gate, multi-qubit systems could not achieve genuine quantum advantage.

The matrix representation of the CNOT gate is:

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

In the computational basis $\{\lvert00\rangle, \lvert01\rangle, \lvert10\rangle, \lvert11\rangle\}$ , this matrix means:

When the control qubit is $\lvert0\rangle$ , the target qubit is unchanged
When the control qubit is $\lvert1\rangle$ , the target qubit is flipped ( $X$ gate applied)

Formally:

$\text{CNOT}\lvert c\rangle\lvert t\rangle = \lvert c\rangle\lvert t \oplus c\rangle$

where $\oplus$ is addition modulo 2 (classical XOR). The CNOT gate is analogous to the classical XOR gate, but acting on quantum superposition states produces entirely different effects.

Let us verify a few key actions:

$\text{CNOT}\lvert00\rangle = \lvert00\rangle$ $\text{CNOT}\lvert01\rangle = \lvert01\rangle$ $\text{CNOT}\lvert10\rangle = \lvert11\rangle$ $\text{CNOT}\lvert11\rangle = \lvert10\rangle$

Note that CNOT transforms the separable state $\lvert1\rangle(\lvert0\rangle + \lvert1\rangle)/\sqrt{2}$ into an entangled state — this is the content of the next subsection. This simple example already demonstrates how quantum gates can convert separable states into entangled states.

Bell States: Maximally Entangled States

Bell States are the four maximally entangled states of two qubits, forming an orthonormal basis of the two-qubit Hilbert space. They are the most fundamental entanglement resource in quantum information.

$\lvert\Phi^+\rangle = \frac{1}{\sqrt{2}}(\lvert00\rangle + \lvert11\rangle)$ $\lvert\Phi^-\rangle = \frac{1}{\sqrt{2}}(\lvert00\rangle - \lvert11\rangle)$ $\lvert\Psi^+\rangle = \frac{1}{\sqrt{2}}(\lvert01\rangle + \lvert10\rangle)$ $\lvert\Psi^-\rangle = \frac{1}{\sqrt{2}}(\lvert01\rangle - \lvert10\rangle)$

These states cannot be written as the tensor product of two single-qubit states. For example, suppose $\lvert\Phi^+\rangle = (a\lvert0\rangle + b\lvert1\rangle) \otimes (c\lvert0\rangle + d\lvert1\rangle)$ . Expanding and comparing coefficients yields $ad = bc = 1/\sqrt{2}$ but $bd = ac = 0$ , a contradiction. This contradiction proves the non-classical nature of entangled states.

The Bell state preparation circuit is one of the most fundamental quantum circuits:

|0⟩ —H—•—    →    |Φ⁺⟩
|0⟩ ———⊕——

Derivation:

Initial state: $\lvert00\rangle$
Apply $H$ to the first qubit: $H\lvert0\rangle \otimes \lvert0\rangle = \frac{1}{\sqrt{2}}(\lvert0\rangle + \lvert1\rangle) \otimes \lvert0\rangle = \frac{1}{\sqrt{2}}(\lvert00\rangle + \lvert10\rangle)$
Apply CNOT: $\frac{1}{\sqrt{2}}(\text{CNOT}\lvert00\rangle + \text{CNOT}\lvert10\rangle) = \frac{1}{\sqrt{2}}(\lvert00\rangle + \lvert11\rangle) = \lvert\Phi^+\rangle$

Similarly, changing the input of the first qubit or adding a $Z$ gate can prepare the other three Bell states. Although simple, the Bell state preparation circuit reveals the core capability of quantum circuits: creating complex entangled states through simple gate combinations.

Measuring Entanglement

How do we quantify entanglement? One conceptual approach uses the Reduced Density Matrix, which we studied in Section 2.6.

For the Bell state $\lvert\Phi^+\rangle$ , taking the partial trace (tracing out the second system):

$\rho_A = \text{Tr}_B(\lvert\Phi^+\rangle\langle\Phi^+\rvert) = \frac{1}{2}(\lvert0\rangle\langle0\rvert + \lvert1\rangle\langle1\rvert) = \frac{I}{2}$

This is the completely mixed state, corresponding to the center of the Bloch sphere! This means that if we look only at the first qubit, we are completely ignorant of its state — no measurement can give us any information about this single qubit. Entanglement = “the subsystem’s information is incomplete.”

Compare with the separable state $\lvert00\rangle$ : $\rho_A = \lvert0\rangle\langle0\rvert$ , a pure state, completely determined. The subsystem of an entangled state is in a state of maximum uncertainty, while the entire system is in a completely determined pure state — this is one of the most counterintuitive features of quantum mechanics.

No-Cloning Theorem

The No-Cloning Theorem is a fundamental limitation of quantum information and the basis for the security of quantum cryptography.

Theorem: There exists no unitary operator $U$ such that for all states $\lvert\psi\rangle$ :

$U(\lvert\psi\rangle \otimes \lvert0\rangle) = \lvert\psi\rangle \otimes \lvert\psi\rangle$

Proof: Suppose such a $U$ exists. Take two distinct states $\lvert\psi\rangle$ and $\lvert\phi\rangle$ :

$U(\lvert\psi\rangle \otimes \lvert0\rangle) = \lvert\psi\rangle \otimes \lvert\psi\rangle$ $U(\lvert\phi\rangle \otimes \lvert0\rangle) = \lvert\phi\rangle \otimes \lvert\phi\rangle$

Consider the superposition state $\lvert\xi\rangle = (\lvert\psi\rangle + \lvert\phi\rangle)/\sqrt{2}$ . By linearity:

$U(\lvert\xi\rangle \otimes \lvert0\rangle) = \frac{1}{\sqrt{2}}U(\lvert\psi\rangle \otimes \lvert0\rangle) + \frac{1}{\sqrt{2}}U(\lvert\phi\rangle \otimes \lvert0\rangle) = \frac{1}{\sqrt{2}}(\lvert\psi\rangle\otimes\lvert\psi\rangle + \lvert\phi\rangle\otimes\lvert\phi\rangle)$

But if $U$ can clone $\lvert\xi\rangle$ , we should have:

$U(\lvert\xi\rangle \otimes \lvert0\rangle) = \lvert\xi\rangle \otimes \lvert\xi\rangle = \frac{1}{2}(\lvert\psi\rangle + \lvert\phi\rangle) \otimes (\lvert\psi\rangle + \lvert\phi\rangle)$

The two are not equal (unless $\langle\psi\rvert\phi\rangle = 1$ , i.e., the two states are identical), a contradiction! Therefore, a perfect universal cloning machine does not exist.

Significance: Classical information can be perfectly copied, but quantum information cannot. This means an eavesdropper cannot obtain information by “copying” quantum communications without being detected — this is the core security guarantee of quantum cryptography. The no-cloning theorem is both a constraint on quantum computing (we cannot casually copy intermediate results as in classical computing) and the security foundation for quantum communication.

Summary: The CNOT gate is the most important two-qubit gate, capable of transforming separable states into entangled states. Bell states are maximally entangled states, requiring only $H$ plus CNOT to prepare. A reduced density matrix that is completely mixed is the hallmark of entanglement — subsystem information is completely lost, yet the overall system information is intact. The no-cloning theorem forbids the perfect copying of unknown quantum states, laying the security foundation for quantum cryptography.

Connection to Quantum Computing: Entanglement is the key resource that enables quantum computing to surpass classical computing. Without entanglement, quantum computing could be efficiently simulated by a classical computer. The CNOT gate, together with single-qubit gates, constitutes universal quantum computation. The no-cloning theorem both constrains quantum information processing (intermediate results cannot be copied) and protects quantum communication security — this dual-edged nature is a central theme of quantum information science.

3.4 Quantum Circuits

Circuit Conventions

A Quantum Circuit is a graphical language for describing quantum computational processes. It is analogous to classical circuit diagrams but follows the special rules of quantum mechanics. Its basic conventions are as follows:

Horizontal lines: Represent qubits, with time flowing from left to right
Boxes / boxes with letters: Single-qubit gates (e.g., $H$ , $X$ , $Z$ , $S$ , $T$ )
Solid dots $\bullet$ : Control qubit of a CNOT gate
Circles with $\oplus$ : Target qubit of a CNOT gate
Meter symbol: Measurement operation
Double lines: Classical bits after measurement

Legend:
|ψ⟩ ——      Qubit wire (initial state |ψ⟩)
——H——      Single-qubit gate (H gate)
——•——     CNOT control qubit
——⊕——     CNOT target qubit
——[M]—►   Measurement, output classical bit
═══        Classical bit wire (double line)

The reading order of quantum circuits is important: gates act sequentially from left to right. Mathematically, if a circuit has gates $U_1, U_2, \ldots, U_n$ from left to right, the total evolution operator is $U_n \cdots U_2 U_1$ (note the reverse order, since the rightmost gate acts last).

Example Circuit 1: Bell State Preparation

|0⟩ —H—•—    →    |Φ⁺⟩
|0⟩ ———⊕——

Step-by-step evolution:

Initial state: $\lvert\psi_0\rangle = \lvert00\rangle$
$H$ gate on first qubit: $\lvert\psi_1\rangle = (H \otimes I)\lvert00\rangle = \lvert+\rangle\lvert0\rangle = \frac{1}{\sqrt{2}}(\lvert00\rangle + \lvert10\rangle)$
CNOT gate: $\lvert\psi_2\rangle = \text{CNOT}\lvert\psi_1\rangle = \frac{1}{\sqrt{2}}(\lvert00\rangle + \lvert11\rangle) = \lvert\Phi^+\rangle$

Note the time ordering of the circuit: gates act sequentially from left to right. Mathematically, the rightmost gate acts first on the state (if we write the circuit as a matrix product, we multiply in reverse order).

Example Circuit 2: Quantum Teleportation

The circuit for quantum teleportation is explained in detail in Section 3.6; here we only present the circuit structure:

|ψ⟩ ————•—H—[M]—►─────┐
        |              │
|Φ⁺⟩₁——⊕————[M]—►────┼──► Classical communication → Bob's correction
        │              │
|Φ⁺⟩₂————————————XⁿZᵐ─┘

Here $\lvert\psi\rangle$ is the unknown state Alice wishes to transmit, and $\lvert\Phi^+\rangle$ is the Bell state shared between Alice and Bob. Alice measures her two qubits, sends the 2-bit classical result to Bob, and Bob applies the correction gates $X$ and $Z$ based on the result. This circuit showcases one of the most astonishing phenomena in quantum computing: transmitting a quantum state using entanglement and classical communication.

Example Circuit 3: GHZ State Preparation

The GHZ State (Greenberger-Horne-Zeilinger State) is a generalization of maximally entangled states to multiple qubits:

$\lvert\text{GHZ}\rangle = \frac{1}{\sqrt{2}}(\lvert000\rangle + \lvert111\rangle)$

Preparation circuit:

|0⟩ —H—•——————    →    |GHZ⟩
|0⟩ ———⊕—•————
|0⟩ —————⊕————

Evolution:

Initial state: $\lvert000\rangle$
$H$ gate on first qubit: $\frac{1}{\sqrt{2}}(\lvert000\rangle + \lvert100\rangle)$
CNOT(1→2): $\frac{1}{\sqrt{2}}(\lvert000\rangle + \lvert110\rangle)$
CNOT(2→3): $\frac{1}{\sqrt{2}}(\lvert000\rangle + \lvert111\rangle) = \lvert\text{GHZ}\rangle$

The three qubits are entangled: measuring any one qubit instantly determines the states of the other two. The GHZ state is a natural generalization of the Bell state to three-qubit systems, demonstrating the complexity of multipartite entanglement.

Circuit Depth and Width

The complexity of a quantum circuit is characterized by two quantities:

Circuit Width $n$ : the number of qubits
Circuit Depth $d$ : the longest path of gate operations (the number of gate layers from left to right)

For example, the GHZ preparation circuit has width 3 and depth 3 (three layers of gates: $H$ , CNOT, CNOT). The Size of a circuit is the total number of gates. A circuit with $n$ qubits and depth $d$ typically has size $O(nd)$ .

Circuit depth directly affects the runtime of algorithms: on a quantum computer, gates in the same layer can be executed in parallel, so depth (rather than total gate count) determines the time complexity. Reducing circuit depth is an important goal of quantum algorithm optimization.

Measurement Symbols

Measurement is represented by the meter symbol:

——[M]—►

After measurement, the qubit collapses to a classical result (0 or 1), and the quantum wire becomes a classical double line:

——[M]—►═══

Classical information can be used for Conditional Operations — for example, in teleportation, Bob decides whether to apply $X$ and $Z$ gates based on the classical bits received from Alice. Conditional operations are the foundation of quantum-classical hybrid computation.

Summary: A quantum circuit is a graphical representation of a quantum algorithm, with time flowing from left to right. Basic elements include quantum wires, single-qubit gates, CNOT gates, and measurements. Circuit complexity is characterized by width (number of qubits) and depth (number of gate layers). Bell states, teleportation, and GHZ states are classic examples that demonstrate the capabilities of circuits.

Connection to Quantum Computing: Quantum circuits are the standard language for describing quantum algorithms. Any quantum computation can be represented as a quantum circuit, and circuit depth directly affects the runtime of algorithms. Understanding circuit diagrams is a foundational skill for reading quantum algorithm papers and implementing quantum programs. From simple Bell state preparation to complex quantum algorithms, circuit diagrams provide an intuitive way to describe algorithms.

3.5 Quantum Measurement & Readout

Review of Computational Basis Measurement

The mathematical framework of quantum measurement was established in Section 2.6 and Postulate 4 of Section 2.2. For a single-qubit state $\lvert\psi\rangle = \alpha\lvert0\rangle + \beta\lvert1\rangle$ , measuring in the computational basis ( $Z$ basis):

Probability of obtaining result 0: $p(0) = \lvert\alpha\rvert^2 = \langle\psi\rvert\lvert0\rangle\langle0\rvert\lvert\psi\rangle$
Probability of obtaining result 1: $p(1) = \lvert\beta\rvert^2 = \langle\psi\rvert\lvert1\rangle\langle1\rvert\lvert\psi\rangle$

After measurement, the state Collapses to the corresponding eigenstate:

$\lvert\psi\rangle \xrightarrow{\text{measured 0}} \lvert0\rangle, \quad \lvert\psi\rangle \xrightarrow{\text{measured 1}} \lvert1\rangle$

This is a direct application of Postulate 4 (Projection Postulate) from Section 2.2. The probabilistic nature of measurement is not due to our ignorance (as in classical probability) but is an intrinsic randomness of quantum mechanics — even if we know the quantum state perfectly, we cannot predict the outcome of a single measurement.

Measurement in the $X$ Basis

The computational basis is not the only measurement basis. The $X$ basis consists of $\lvert+\rangle$ and $\lvert-\rangle$ , the eigenstates of the $X$ operator:

$X\lvert+\rangle = +1\cdot\lvert+\rangle, \quad X\lvert-\rangle = -1\cdot\lvert-\rangle$

To measure a state in the $X$ basis, there are two equivalent methods:

Method 1: First apply an $H$ gate, then measure in the $Z$ basis (since $H\lvert+\rangle = \lvert0\rangle$ , $H\lvert-\rangle = \lvert1\rangle$ )

Method 2: Directly project onto $\lvert+\rangle\langle+\rvert$ and $\lvert-\rangle\langle-\rvert$

Take the example of measuring $\lvert+\rangle$ in the $Z$ basis:

$p(0) = |\langle0\rvert+\rangle|^2 = \left|\frac{1}{\sqrt{2}}\right|^2 = \frac{1}{2}$ $p(1) = |\langle1\rvert+\rangle|^2 = \left|\frac{1}{\sqrt{2}}\right|^2 = \frac{1}{2}$

Although $\lvert+\rangle$ is deterministic in the $X$ basis (always measuring $+1$ ), it is completely random in the $Z$ basis — once again illustrating that measurement depends on the chosen basis. Different measurement bases reveal different aspects of a quantum state, a manifestation of the complementarity principle of quantum mechanics in quantum computing.

Expectation Values

The Expectation Value in quantum mechanics corresponds to the statistical average over many measurements.

For the $Z$ operator:

$\langle Z \rangle = \langle\psi\rvert Z\lvert\psi\rangle = (\alpha^*\langle0\rvert + \beta^*\langle1\rvert)(\alpha\lvert0\rangle - \beta\lvert1\rangle) = |\alpha|^2 - |\beta|^2$

Geometrically, $\langle Z \rangle$ is precisely the $z$ -coordinate of the state on the Bloch sphere. For example:

$\lvert0\rangle$ : $\langle Z \rangle = 1$ (north pole)
$\lvert1\rangle$ : $\langle Z \rangle = -1$ (south pole)
$\lvert+\rangle$ : $\langle Z \rangle = 0$ (equator)

Similarly, the $X$ expectation value is:

$\langle X \rangle = \langle\psi\rvert X\lvert\psi\rangle = \alpha^*\beta + \alpha\beta^* = 2\text{Re}(\alpha^*\beta)$

This is the $x$ -coordinate on the Bloch sphere. For $\lvert+\rangle$ , $\langle X \rangle = 1$ ; for $\lvert-\rangle$ , $\langle X \rangle = -1$ .

Statistical Interpretation and Measurement Precision

A single quantum measurement result is random. To estimate an expectation value, one needs to prepare many identical copies and statistically analyze the measurement results.

Suppose we perform $N$ $Z$ -basis measurements, obtaining $N_0$ zeros and $N_1$ ones. Then the estimate of $\langle Z \rangle$ is:

$\hat{Z} = \frac{N_0 - N_1}{N} \approx \langle Z \rangle$

By the law of large numbers, the estimation error decreases as $N$ increases, with precision $1/\sqrt{N}$ (the standard quantum limit). This is the basis of sample complexity in quantum computing. For example, to estimate $\langle Z \rangle$ to a precision of $0.01$ , approximately $N \approx 10000$ measurements are needed.

Example of posterior probability updating after measurement: Suppose we have an unknown state and our prior belief is that it is $\lvert0\rangle$ or $\lvert+\rangle$ , each with 50% probability. If we measure 0 in the $Z$ basis:

If the state is $\lvert0\rangle$ , the probability of measuring 0 is 1
If the state is $\lvert+\rangle$ , the probability of measuring 0 is $1/2$

By Bayes’ formula, the posterior probability that the state is $\lvert0\rangle$ given that we measured 0 is:

$p(\lvert0\rangle | \text{measured 0}) = \frac{1 \times 0.5}{1 \times 0.5 + 0.5 \times 0.5} = \frac{2}{3}$

Physical Meaning of Measurement and Collapse

Measurement is not merely a means of obtaining information; it also irreversibly changes the quantum state. This property endows quantum computing with a unique “one-shot” character:

Once measured, the superposition state collapses to a basis state, and the original information (relative phases between probability amplitudes) is lost
Hence, quantum computations typically place measurements at the end (unless intermediate measurements are used for specific algorithms)
This is also why quantum error correction is difficult: we cannot casually “check” a quantum state without destroying it

The density matrix framework of Section 2.6 can describe measurement in a unified way: after the measurement operator $M_m$ acts, the unnormalized state is $M_m\rho M_m^\dagger$ , with probability $\text{Tr}(M_m^\dagger M_m \rho)$ . This framework is more general than the pure-state description and can handle mixed states and more general measurements (POVMs).

Summary: Quantum measurement in the computational basis yields 0 and 1 with probabilities $|\alpha|^2$ and $|\beta|^2$ . Different measurement bases yield different statistical results, embodying the complementarity of quantum mechanics. Expectation values correspond to Bloch sphere coordinates and require statistical estimation through many measurements. Measurement leads to irreversible collapse, a key constraint of quantum computing.

Connection to Quantum Computing: Measurement is the only way for quantum algorithms to extract classical results. Since individual measurements are random, many quantum algorithms (such as the Variational Quantum Eigensolver, VQE) require extensive sampling to estimate expectation values. The choice of measurement basis directly affects algorithm design (such as basis comparison in BB84). Understanding the statistical properties of measurement is the foundation for analyzing the complexity and practical feasibility of quantum algorithms.

3.6 Quantum Algorithm Primer

The first five sections of this chapter have built the complete toolbox for understanding quantum computing. Now, we bring these tools together in concrete quantum algorithms, showing how they work in concert to solve real problems. The emphasis of this section is conceptual understanding, not technical details — our goal is for the reader to see how those seemingly abstract mathematical and physical concepts produce astonishing practical effects at the algorithmic level.

Quantum Teleportation

Problem: Alice has an unknown quantum state $\lvert\psi\rangle = \alpha\lvert0\rangle + \beta\lvert1\rangle$ , and she wants to “transmit” this state to Bob, who is far away. By the No-Cloning Theorem (Section 3.3), she cannot copy this state. But she can achieve transmission through shared entanglement and classical communication — this is quantum teleportation.

Resources: Alice and Bob share in advance a Bell pair $\lvert\Phi^+\rangle_{AB} = (\lvert00\rangle + \lvert11\rangle)/\sqrt{2}$ . Alice holds the first qubit, Bob holds the second.

Circuit:

|ψ⟩ ————•—H—[M]—►─────┐
        |              │
|Φ⁺⟩₁——⊕————[M]—►────┼──► Classical channel (2 bits) → Bob
        │              │
|Φ⁺⟩₂————————————XⁿZᵐ─┘

Steps (Alice’s operations on the left, Bob’s on the right):

Alice applies CNOT to her two qubits: control is $\lvert\psi\rangle$ , target is her half of the Bell pair.

Three-qubit initial state: $\lvert\psi\rangle_A \otimes \lvert\Phi^+\rangle_{AB} = (\alpha\lvert0\rangle + \beta\lvert1\rangle) \otimes \frac{1}{\sqrt{2}}(\lvert00\rangle + \lvert11\rangle)$
Alice applies an $H$ gate to the first qubit: producing superposition in preparation for measurement.
Alice measures her two qubits, obtaining a two-bit classical result $(m, n)$ , where $m, n \in \{0, 1\}$ .
Alice tells Bob $(m, n)$ via a classical channel. This is key: only classical information is transmitted, not quantum states.
Bob applies correction gates to his qubit based on $(m, n)$ :
- If $m=1$ , apply the $X$ gate
- If $n=1$ , apply the $Z$ gate
That is, Bob applies $X^m Z^n$ .

Result: Bob’s qubit becomes precisely $\lvert\psi\rangle$ .

Key Insight: Entanglement + Classical Communication = Quantum Information Transmission. Alice’s measurement causes her unknown state to “disappear” (collapse), while the classical communication tells Bob how to reconstruct the original state from the entangled qubit in his possession. Without shared entanglement, classical communication alone cannot transmit a quantum state; without classical communication, entanglement alone cannot transmit either (otherwise it would violate relativistic causality). Teleportation demonstrates one of the most profound features of quantum mechanics: entanglement enables information transmission that surpasses what classical communication alone can achieve.

BB84 Quantum Key Distribution

Problem: How can Alice and Bob establish a shared secret key over an insecure channel?

The BB84 Protocol, proposed by Bennett and Brassard in 1984, is the cornerstone of quantum cryptography.

Protocol flow:

Alice randomly selects a basis and a bit: For each qubit, Alice randomly chooses the $Z$ basis or the $X$ basis, and randomly prepares $\lvert0\rangle$ , $\lvert1\rangle$ , $\lvert+\rangle$ , or $\lvert-\rangle$ . She sends the qubits to Bob.
Bob randomly selects a basis for measurement: For each arriving qubit, Bob randomly chooses the $Z$ basis or the $X$ basis to measure and records the result.
Basis comparison (classical communication): Alice and Bob announce which bases they used over a public channel (but do not reveal the measurement results).
Retain bits with matching bases: Only the measurement results where both used the same basis are retained as the raw key.
Error detection: Both parties publicly compare a subset of bits to check for an abnormally high error rate that would indicate eavesdropping.

Basis comparison example:

Bit #	Alice’s Basis	Alice’s State	Bob’s Basis	Bob’s Measurement	Same Basis?	Keep?
1	$Z$	$\lvert0\rangle$	$Z$	0	Yes	0
2	$Z$	$\lvert1\rangle$	$X$	+ or -	No	Discard
3	$X$	$\lvert+\rangle$	$X$	+	Yes	+
4	$X$	$\lvert-\rangle$	$Z$	0 or 1	No	Discard
5	$Z$	$\lvert1\rangle$	$Z$	1	Yes	1

Security principle:

If an eavesdropper Eve intercepts the qubits and measures them, since she does not know which basis Alice used, there is a 50% probability she chooses the wrong basis. Measuring in the wrong basis disturbs the quantum state (measurement collapse from Section 3.5), introducing an error rate of about 25%. Alice and Bob can detect eavesdropping by checking the error rate.

The No-Cloning Theorem (Section 3.3) guarantees that Eve cannot copy the qubits to avoid disturbance — she must measure immediately, inevitably leaving a trace. This is the quantum-mechanical guarantee of BB84’s security.

Deutsch-Jozsa Algorithm

Problem: Given a function $f: \{0,1\}^n \to \{0,1\}$ , determine whether it is a constant function (the same output for all inputs) or a balanced function (exactly half the inputs output 0 and half output 1).

Classical complexity: Worst case requires $2^{n-1}+1$ queries (must check more than half the inputs to be certain).

Quantum complexity: Only 1 query required!

Core idea: Quantum parallelism. By applying Hadamard gates to superpose all inputs, a single query simultaneously evaluates all $2^n$ inputs. Then, interference is used to extract the global property (constant vs. balanced).

Specifically, the algorithm prepares the input register as an equal-amplitude superposition of all $2^n$ computational basis states:

$\lvert\psi\rangle = \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}\lvert x\rangle$

Then a quantum oracle (a unitary transformation implementing the function $f$ ) is applied, followed by interference-based measurement to extract the information. Although the type of function the Deutsch-Jozsa algorithm decides is rather specialized and lacks practical application value, it is a classic pedagogical example that demonstrates the principle of quantum parallelism.

Grover’s Search Algorithm

Problem: Search for a target item among $N = 2^n$ unsorted database entries.

Classical complexity: On average requires $N/2$ queries, worst case $N$ queries.

Quantum complexity: $O(\sqrt{N})$ queries.

Core idea: Amplitude Amplification. Grover’s algorithm iteratively “marks” the target item (flipping its phase) and “diffuses” (rotating all states toward the target state), gradually amplifying the probability amplitude of the target state.

For $N$ items, after approximately $\frac{\pi}{4}\sqrt{N}$ iterations, measurement yields the target item with high probability. This provides a quadratic speedup for large database searches.

Algorithm	Classical Complexity	Quantum Complexity	Speedup
Search $N$ items	$O(N)$	$O(\sqrt{N})$	Quadratic

Although the speedup is only quadratic (rather than exponential), Grover’s algorithm applies to any unstructured search problem and has been proven to be the optimal quantum search algorithm — no faster quantum search algorithm exists.

Shor’s Algorithm

Problem: Factor a large integer $N$ .

Significance: The security of modern RSA encryption rests on the assumption that factoring large integers is hard on classical computers. Shor’s algorithm can efficiently factor large integers on a quantum computer, thereby threatening RSA encryption.

Core idea: Reduce factoring to a period-finding problem, then accelerate period-finding using the Quantum Fourier Transform (QFT).

Recall the DFT from Section 1.8. The quantum Fourier transform is the quantum implementation of the DFT, capable of completing in $O((\log N)^2)$ time an operation that classically requires $O(N\log N)$ . This exponential speedup comes from quantum parallelism: QFT processes all frequency components simultaneously.

Complexity comparison:

Algorithm	Classical Complexity	Quantum Complexity	Speedup
Factor $N$	$O(\exp((\log N)^{1/3}))$ (best classical)	$O((\log N)^3)$	Exponential

Shor’s algorithm’s exponential speedup makes it the most attention-grabbing algorithm in quantum computing and one of the primary drivers of quantum computing research. It demonstrates the astonishing power of quantum computers on specific mathematical problems, while also reminding us that quantum computing is not just scientific curiosity — it bears on the foundations of information security.

Summary: Quantum teleportation uses entanglement and classical communication to transmit a quantum state, demonstrating the non-classical capability of entanglement; BB84 achieves secure key distribution through basis comparison and the no-cloning theorem, serving as the cornerstone of quantum cryptography; Deutsch-Jozsa showcases quantum parallelism — one operation evaluates all inputs; Grover provides a quadratic speedup for search, proven to be optimal; Shor’s algorithm achieves an exponential speedup for factoring via QFT, threatening RSA encryption.

Connection to Quantum Computing: These five algorithms showcase the core sources of quantum computing’s advantage: superposition states enable parallel computation, entanglement provides non-classical correlations, and quantum interference extracts global information. From key distribution to database search, from factoring to quantum communication, these algorithms lay the practical foundations of quantum information science. We have now accumulated enough mathematical and physical tools to understand them — this is precisely the value of all the content in the first two chapters. Quantum computing is not mysterious magic, but the systematic application of the principles of quantum mechanics.

3.7 Quantum Advantage Demonstrations

What is quantum advantage: Quantum advantage (formerly called “quantum supremacy”) refers to the ability of a quantum computer to surpass the most advanced classical computers on a specific task. Note that this is not a surpassing of general-purpose computing power (universal quantum computers have not yet been realized), but rather a computational speedup on carefully designed specific problems. Demonstrations of quantum advantage are not necessarily practical (the output of random circuit sampling, for instance, has no commercial value); their significance lies in experimentally verifying that a quantum system’s computational power has broken through the limits of classical simulation.

Google Sycamore 2019:

53-qubit superconducting processor, using the Random Circuit Sampling (RCS) task
Task: sample the probability distribution of output bitstrings from a random quantum circuit
Classical simulation estimate: the most powerful classical supercomputer at the time (Summit) would need approximately 10,000 years
Sycamore runtime: approximately 200 seconds to complete 1 million samples
Controversy and discussion: IBM proposed that classical simulation could be completed in 2.5 days (using better algorithms and Summit’s storage hierarchy). Regardless of the exact numbers, Sycamore marked the first time quantum computing clearly surpassed classical computing on a well-defined task
Key engineering details: of the 53 qubits, only 53 were actually usable (one was faulty), with two-qubit gate fidelity of approximately 99.5%
Linear cross-entropy benchmarking (XEB) fidelity of approximately 0.2% — verified correct operation of the quantum circuit

China’s Jiuzhang / Zuchongzhi:

Jiuzhang 2020 (USTC, Pan Jianwei / Lu Chaoyang team): photonic quantum Gaussian Boson Sampling, 76 photon modes, classical simulation estimated to require 600 million years, Jiuzhang completed in 200 seconds
Zuchongzhi 2021 (USTC, Zhu Xiaobo team): 66-qubit superconducting processor, RCS task 2–3 orders of magnitude faster than Sycamore
Jiuzhang 2.0 2021: 113 photon modes, classical simulation time for Gaussian Boson Sampling estimated at $10^{24}$ years, Jiuzhang completed in approximately 2 hours
Key turning point in 2023: these two experiments demonstrated that both China and the US have simultaneously achieved quantum advantage on both superconducting and photonic routes

The classical simulation counterattack:

2023–2024: new tensor network algorithms (based on boundary MPS) reduced the classical simulation time of Sycamore-class circuits from days to hours — on GPU clusters
October 2024: Google’s 67-qubit upgraded Sycamore RCS experiment reopened the gap with classical simulation
The dynamics of this “arms race” indicate that quantum advantage is not a one-time achievement but an ongoing process — quantum hardware advances, but classical simulation algorithms also advance

Willow 2024 RCS Demonstration:

The Willow processor demonstrated stronger quantum advantage on the RCS task: classical simulation estimated to require $10^{25}$ years, Willow completed in approximately 5 minutes
Compared to 2019, Willow’s advantage comes from: more qubits (105), higher fidelity (99.85% two-qubit gates), and lower crosstalk
More importantly: Willow’s RCS was run in “error-correction mode” — although RCS itself does not require error correction, the parallel error-correction circuits proved that the processor can maintain quantum advantage while performing error correction

Limitations and Controversies of Quantum Advantage:

Non-practicality: the outputs of RCS and Gaussian Boson Sampling have no practical application value — they are “benchmarks of computational power,” not “useful computation”
The progressive nature of classical simulation: after each quantum advantage demonstration, the classical community typically finds more efficient simulation algorithms within a few months — hence quantum advantage is not a one-time “victory”
From advantage to utility: genuinely commercially valuable quantum advantage needs to be realized in the following domains: quantum chemistry simulation (fertilizer production, battery design), combinatorial optimization (logistics, finance), machine learning (drug discovery)
The verification problem: when quantum computers become large enough, their outputs cannot be fully verified by classical computers — a trust problem arises

Summary: Quantum advantage demonstrations (Sycamore 2019, Jiuzhang 2020, Willow 2024) have shown, on carefully designed sampling tasks, that quantum computing can surpass classical simulation. These demonstrations are necessary steps in validating quantum hardware capabilities, but there remains a gap between them and practical quantum speedup. RCS and Gaussian Boson Sampling are “computational power benchmarks,” not “useful computation.” Genuine quantum advantage needs to be realized in application domains such as quantum chemistry, optimization, or machine learning.

Connection to Quantum Computing: Quantum advantage demonstrations are the “proof of capability” for the field of quantum computing — they answer the fundamental question “can quantum computers really surpass classical computers?” Each demonstration drives bidirectional progress in hardware engineering (more qubits, higher fidelity, lower noise) and classical simulation algorithms (tensor networks, approximation algorithms). Understanding the current state of quantum advantage (what it has done and what it has not done) is essential for assessing the overall development trajectory of quantum computing and technological pathway choices.

Chapter 3 Summary

This chapter crystallizes the mathematics (linear algebra, probability theory, Fourier transforms) and physics (quantum mechanical postulates, spin, Bloch sphere, measurement theory) of the first two chapters into the core framework of quantum computing:

3.1 Qubit = abstraction of spin- $1/2$ , living on the Bloch sphere
3.2 Single-qubit gates = unitary matrices = Bloch sphere rotations; the $H$ gate creates superpositions
3.3 CNOT + entanglement = the “soul” of quantum computing; the no-cloning theorem safeguards security
3.4 Quantum circuits = a graphical language for algorithms
3.5 Measurement = the only path to extract classical results, but at an irreversible cost
3.6 Algorithms = the integrated application of all the above tools

Quantum computing is not mysterious magic, but the systematic application of the principles of quantum mechanics. When you understand qubits, gates, entanglement, and measurement, you have already grasped all the foundational concepts needed to understand this field. What follows is building more complex circuits, more subtle algorithms, and deeper physical implementations on top of this framework — but the core ideas are already here.

Appendix

Part 3: Foundations of Quantum Computing — Feynman Technique Exercises

Companion Tutorial: Quantum Computing Primer — From First Principles, Part 3 (3.1–3.6)

Method: Feynman Technique — teaching is the best way to learn. Each section has 4 problems, covering computation, derivation, explanation, and insight.

Difficulty: ⭐ (Basic) → ⭐⭐ (Advanced) → 🗣️ (Feynman Explanation) → 💭 (Deep Insight)

3.1 Qubits
3.2 Single-Qubit Gates
3.3 Multi-Qubit Gates & Entanglement
3.4 Quantum Circuits
3.5 Quantum Measurement & Readout
3.6 Quantum Algorithm Primer
Answers
Open Questions

3.1 Qubits

Exercise 3.1.1 ⭐ Three-State Normalization

Normalize the following state and compute the probabilities of each measurement outcome:

$\lvert\psi\rangle = 2\lvert0\rangle + i\lvert1\rangle - (1+i)\lvert0\rangle$

Hint: First simplify the expression, then normalize.

Exercise 3.1.2 ⭐⭐ From Amplitudes to Bloch Coordinates

Given $\lvert\psi\rangle = \frac{1}{\sqrt{3}}\lvert0\rangle + \frac{1+i}{\sqrt{6}}\lvert1\rangle$ , find its Bloch sphere coordinates $(\theta,\phi)$ and the corresponding 3D vector $\vec{n} = (n_x, n_y, n_z)$ .

Exercise 3.1.3 🗣️ Feynman: Explain Qubits to Your Grandmother

Your grandmother asks: “You say a qubit can be both 0 and 1 at the same time — so is it half-dead and half-alive, like Schrödinger’s cat?”

In no more than 8 sentences (without using any formulas), explain to your grandmother:

The essential difference between quantum “superposition” and “a glass half full of water”
Why measurement “destroys” a superposition state
Compare it with a “chord” in classical music (multiple notes sounding simultaneously) vs. quantum superposition

Exercise 3.1.4 💭 Insight: The Curse of Dimensionality

The state space of $n$ qubits has dimension $2^n$ . For an $n=100$ quantum processor, describing its state requires $2^{100} \approx 10^{30}$ complex parameters.

(a) What does this number imply? How does it relate to the simulation capabilities of classical computers? (b) However — can we really “use” this $2^n$ -dimensional space? Measurement only yields $n$ classical bits, so to what extent is this vast state space “accessible”? (c) Is this “dimensional explosion” the sole source of quantum advantage? If not, what other key factors are there?

3.2 Single-Qubit Gates

Exercise 3.2.1 ⭐ $H$ - $T$ Sequence Calculation

Compute the final state after applying the following gate sequence to $\lvert0\rangle$ :

$T \cdot H \cdot T \cdot H \lvert0\rangle$

Express the result as $(\theta, \phi)$ coordinates on the Bloch sphere. Hint: $T = \begin{pmatrix}1&0\\0&e^{i\pi/4}\end{pmatrix}$ .

Exercise 3.2.2 ⭐⭐ Decomposition of an Arbitrary Rotation

Prove that any single-qubit unitary operator $U$ can be decomposed as

$U = e^{i\alpha} R_z(\beta) R_y(\gamma) R_z(\delta)$

where $R_y(\theta) = e^{-i\theta Y/2}$ and $R_z(\theta) = e^{-i\theta Z/2}$ .

Hint: Recall the parameterization $U = e^{i\alpha} R_{\hat{n}}(\theta)$ on the Bloch sphere, and exploit the commutation relations of the $Y$ and $Z$ generators.

Exercise 3.2.3 🗣️ Feynman: Explain Quantum Gates to a Programmer

You are an experienced backend engineer. Your colleague, upon seeing quantum gates, says: “Isn’t this just matrix multiplication? I could write some numpy to compute this stuff.”

In no more than 6 sentences, explain from the perspective of physical information: why quantum gates are not merely matrix multiplication. What are the two essential differences between a “gate” operating on a quantum state and an “instruction” running on a classical CPU?

Exercise 3.2.4 💭 Insight: The Special Status of the $T$ Gate

In the gate set $\{H, T, \text{CNOT}\}$ , the $T$ gate is the only one that is not a “Clifford gate.” Clifford gates ( $H$ , $S$ , CNOT) map Pauli matrices to Pauli matrices, but the $T$ gate cannot.

(a) Why must a universal gate set for quantum computing include a non-Clifford gate? (b) What does this mean for implementing fault-tolerant quantum computing? Why is the cost of the $T$ gate in surface-code “magic state distillation” far higher than other gates? (c) If the $T$ gate is so expensive, why don’t we just switch to a different universal gate set?

3.3 Multi-Qubit Gates & Entanglement

Exercise 3.3.1 ⭐ Gate Operations on an Entangled State

Given the state $\lvert\Phi^+\rangle = (\lvert00\rangle + \lvert11\rangle)/\sqrt{2}$ , apply the following operations in sequence:

Apply an $H$ gate to the first qubit
CNOT (control = first qubit, target = second qubit)
Apply a $Z$ gate to the first qubit

Find the final state.

Exercise 3.3.2 ⭐⭐ Product Gates Cannot Create Entanglement

Suppose we have a two-qubit gate $U$ that can be written as a tensor product:

$U = A \otimes B$

where $A$ and $B$ are single-qubit unitary operators. Prove: if the input state is separable, the output of $U(A \otimes B)$ must also be separable. What does this imply?

Exercise 3.3.3 🗣️ Feynman: Explain Entanglement to a Sci-Fi Fan

Your friend says: “I get quantum entanglement — it’s when two particles, no matter how far apart, instantly affect each other. Einstein called it ‘spooky action at a distance,’ right?”

In no more than 7 sentences (without using any formulas), correct this misconception. You need to explain:

What entanglement means mathematically (not “telepathy,” but “correlation”)
Why entanglement cannot be used for faster-than-light communication (“measurement collapse” is local)
What entanglement is actually useful for (give one concrete example)

Exercise 3.3.4 💭 Insight: Entanglement as a “Resource”

Entanglement is often called a “resource” of quantum computing, just as energy is a resource in thermodynamics.

(a) Why is entanglement non-classical? Can quantum computing without entanglement be efficiently simulated by a classical computer? (b) If entanglement is a resource, what does it “consume”? What cost does preparing a Bell pair incur? (c) “Entanglement distillation” and “entanglement swapping” tell us that entanglement can be purified and routed. What does this mean? Can entanglement be “transmitted” like electricity?

3.4 Quantum Circuits

Exercise 3.4.1 ⭐ Circuit Tracking

Write out the quantum state after each step of the following circuit (trace from the far left):

|0⟩ —H—•——H—•—
|0⟩ ———⊕——H—⊕—
|0⟩ ————————⊕—

Circuit width = 3, depth = 5. What is the final state?

Exercise 3.4.2 ⭐⭐ Proving CNOT Gate Equivalence

Prove that the following two circuits are equivalent (i.e., they give the same output for any input state):

Circuit A:

—•—     —X—
  |   =   |
—⊕—     —•—

Circuit B:

—⊕—     —•—
  |   =   |
—•—     —⊕—

That is, after swapping the control and target qubits of a CNOT and applying $H$ gates on both sides, we obtain the same CNOT. In other words:

$(H \otimes H) \cdot \text{CNOT}_{1\to2} \cdot (H \otimes H) = \text{CNOT}_{2\to1}$

Exercise 3.4.3 🗣️ Feynman: Explain “Reversibility” to a Hardware Engineer

Your colleague is a hardware engineer. After seeing a quantum circuit, she is puzzled: “In classical circuits, a NAND gate only needs 4 transistors. Quantum gates look so complicated. Why must quantum gates be reversible? Isn’t that wasteful?”

In no more than 6 sentences, explain:

Starting from the postulates of quantum mechanics, why it must be unitary (reversible)
What would happen if a classical irreversible gate (such as AND) were used on a quantum computer
What is the cost of using classical reversible gates (such as Toffoli)

Exercise 3.4.4 💭 Insight: Circuit Depth vs. Quantum Advantage

The depth of a quantum circuit determines the actual runtime of an algorithm. The typical constraints of current NISQ (Noisy Intermediate-Scale Quantum) devices are:

Qubit count: 50–1000
Circuit depth: < 100 (beyond this, noise drowns out the useful signal)

(a) What can a circuit with 100 qubits and depth 50 achieve? What can it not achieve? (b) Why is the depth constraint more fatal than the qubit-count constraint? Give examples. (c) The Quantum Volume metric simultaneously considers qubit count and depth. What does this tell us?

3.5 Quantum Measurement & Readout

Exercise 3.5.1 ⭐ Expectation Value Calculation

For the state $\lvert\psi\rangle = \frac{1}{\sqrt{2}}(\lvert0\rangle - e^{i\pi/3}\lvert1\rangle)$ , compute its expectation values $\langle X\rangle, \langle Y\rangle, \langle Z\rangle$ in the three directions, and verify that $\langle X\rangle^2 + \langle Y\rangle^2 + \langle Z\rangle^2 = 1$ .

Exercise 3.5.2 ⭐⭐ The “Counterintuitive” Nature of Measurement

Consider a two-qubit state $\lvert\Psi^-\rangle = (\lvert01\rangle - \lvert10\rangle)/\sqrt{2}$ .

(a) Prove that any measurement on a single qubit yields completely random results ( $P(0) = P(1) = 1/2$ ). (b) But if you measure both qubits, the results are always opposite (one 0, one 1). (c) Use an analogy to explain this “globally determined, locally random” phenomenon.

Exercise 3.5.3 🗣️ Feynman: Explain Quantum Probability to a Statistician

Your friend (a statistics professor) says: “Isn’t your measurement probability just classical conditional probability? A particle has a 60% chance of being 0 and a 40% chance of being 1 — how is that different from me flipping an unfair coin?”

In no more than 8 sentences, explain the fundamental difference between the two. Include:

The interference effect of “probability amplitudes” (the role of phase)
Post-measurement collapse vs. conditional updating in classical probability
An example: the different measurement results of $\lvert+\rangle$ in the $X$ basis and the $Z$ basis — why a classical coin cannot do this

Exercise 3.5.4 💭 Insight: The Cost of Quantum Tomography

To determine the state of an unknown qubit, we need to measure many copies in different bases — this is quantum state tomography.

(a) For a single-qubit pure state, what is the theoretical minimum number of measurements needed to determine it? Why? (b) For an unknown pure state of $n$ qubits, how does the number of required measurements scale with $n$ ? What fundamental limitation does this represent? (c) In classical estimation, the precision of $N$ samples is $O(1/\sqrt{N})$ (the standard quantum limit). Is there a way to surpass this limit (such as quantum-enhanced sensing)? What does this imply?

3.6 Quantum Algorithm Primer

Exercise 3.6.1 ⭐ BB84 Eavesdropping Probability Analysis

In the BB84 protocol, suppose the eavesdropper Eve adopts the following strategy: for each intercepted qubit, she measures with probability $p$ and forwards it directly (without measuring) with probability $1-p$ .

(a) If Alice and Bob choose bases randomly ( $Z$ or $X$ , each 50%), what error rate does Eve’s measurement introduce? (b) If Alice and Bob require the error rate not to exceed 5% to consider the channel secure, what is the maximum $p$ Eve can use without being detected?

Exercise 3.6.2 ⭐⭐ Geometric Interpretation of Grover Iteration

In Grover search, the angle between the initial state $\lvert s\rangle$ and the target state $\lvert \omega\rangle$ is expressed as $\sin\theta = 1/\sqrt{N}$ .

(a) Prove that one Grover iteration rotates $\lvert s\rangle$ toward $\lvert \omega\rangle$ by an angle of $2\theta$ . (b) Prove that the optimal number of iterations is approximately $\frac{\pi}{4}\sqrt{N}$ . (c) For a database of $N=10^6$ , what are the classical and quantum query counts?

Exercise 3.6.3 🗣️ Feynman: Explain to a CEO “What a Quantum Computer Does”

Your CEO, after reading the news, excitedly says: “I get it! A quantum computer is a supercomputer that ‘tries all possibilities at once’! Encryption, passwords, search — everything is doomed! We need to invest right now!”

In no more than 10 sentences, calmly explain why this understanding is problematic. Include:

Why the “try everything at once” analogy is wrong (the intermediate measurement / collapse problem)
Quantum computers are not fast on all problems — give an example of one where they are not
The current state (as of 2026) of quantum computers (how many qubits, how much noise, what they can and cannot do)

Exercise 3.6.4 💭 Insight: Post-Quantum Cryptography

Shor’s algorithm threatens RSA and ECC, but Grover’s algorithm only provides a quadratic speedup for symmetric encryption (such as AES), reducing the effective strength of a 128-bit key to 64 bits.

(a) If a quantum computer with 10,000 logical qubits becomes available in 2040, will AES-256 still be secure? (b) The standardization of post-quantum cryptography (PQC) is underway. What kind of hard problems are the candidate schemes selected by NIST (such as Kyber, Dilithium) based on? Why are these problems considered resistant to quantum attacks? (c) Between now and 2040, do you think a quantum computer is more likely to first achieve quantum advantage (demonstrating useful computation) or to first break RSA? Why?

Answers

3.1 Qubits

3.1.1 Three-State Normalization

Simplify: $2\lvert0\rangle + i\lvert1\rangle - (1+i)\lvert0\rangle = (2 - 1 - i)\lvert0\rangle + i\lvert1\rangle = (1 - i)\lvert0\rangle + i\lvert1\rangle$

Norm: $\|(1-i)\|^2 + \|i\|^2 = (1^2 + 1^2) + 1 = 3$

Normalized state: $\lvert\hat\psi\rangle = \frac{1-i}{\sqrt{3}}\lvert0\rangle + \frac{i}{\sqrt{3}}\lvert1\rangle$

Probabilities: $P(0) = |(1-i)/\sqrt{3}|^2 = 2/3$ , $P(1) = |i/\sqrt{3}|^2 = 1/3$

3.1.2 From Amplitudes to Bloch Coordinates

Amplitudes: $\alpha = 1/\sqrt{3}$ , $\beta = (1+i)/\sqrt{6}$

$|\alpha|^2 = 1/3$ , $|\beta|^2 = (1^2 + 1^2)/6 = 2/6 = 1/3$ (good, correctly normalized)

$\cos\frac{\theta}{2} = \sqrt{1/3}$ , $\theta = 2\arccos(1/\sqrt{3}) \approx 1.9106$ rad

Phase of $\beta$ : $\arg(1+i) = \pi/4$

$\alpha$ is a positive real number (phase 0), so $\phi = \pi/4$

Bloch vector: $\vec{n} = (\sin\theta\cos\phi,\ \sin\theta\sin\phi,\ \cos\theta)$

$\sin\frac{\theta}{2} = \sqrt{2/3}$ , $\sin\theta = 2\sin\frac{\theta}{2}\cos\frac{\theta}{2} = 2\sqrt{2/9} = 2\sqrt{2}/3$

$\cos\theta = \cos^2\frac{\theta}{2} - \sin^2\frac{\theta}{2} = 1/3 - 2/3 = -1/3$

$\vec{n} = (2\sqrt{2}/3 \cdot \sqrt{2}/2,\ 2\sqrt{2}/3 \cdot \sqrt{2}/2,\ -1/3) = (2/3,\ 2/3,\ -1/3)$

Check: $|\vec{n}| = \sqrt{4/9 + 4/9 + 1/9} = 1$ . Pure state.

3.1.3 🗣️ Key Points for Answer

Key points (not all need to be used; choose those suited to the audience):

Analogy 1 (Chord vs. single note): A chord consists of multiple notes sounding simultaneously, but this is not “uncertainty about which note to play” — it is an intentional superposition that contains more information than a single note. A qubit is like a chord played by a thousand musicians simultaneously, not a “half-full glass of water” compromise.
Analogy 2 (Coin vs. arrow): A classical bit is like a static coin (either heads or tails). A qubit is like a spinning coin — it is in a dynamic superposition that includes phase information (which direction is it spinning? how fast?). Measurement is like slapping your hand down on the spinning coin — you only get “heads” or “tails,” but you lose the information about the direction of spin.
Why measurement destroys: Because measurement requires the quantum state to interact with our macroscopic measurement apparatus. This interaction is too “violent” — it is equivalent to demanding “are you 0 or 1?” — the quantum state is forced to choose an answer, and the original superposition information is lost. It’s like asking a person deep in thought “are you hungry or not?” — this simple binary question interrupts their deep contemplation.

3.1.4 💭 Insight Answer

(a) $2^{100}$ complex parameters, if stored as double-precision floating-point numbers, would require approximately $2^{100} \times 16$ bytes $\approx 1.6 \times 10^{31}$ bytes. This far exceeds the total storage capacity of all devices on Earth. Hence, a classical computer cannot simulate the arbitrary state of 100 qubits — this is the fundamental logic behind “quantum supremacy” experiments.

(b) Key constraint: we can only extract $n$ classical bits of information through measurement. So the extraction efficiency of useful information from this $2^n$ -dimensional space is limited. This leads to the central problem of quantum computing: how to ingeniously design algorithms so that interference effects “amplify” the probability amplitude of the correct answer while “suppressing” the wrong answers? In other words, quantum computers cannot arbitrarily access the vast state space — they need carefully orchestrated interference patterns to extract global information.

(c) Dimensional explosion is not the sole source. Entanglement and interference are equally important. Without entanglement (using only separable states), classical computers can simulate efficiently. Without interference, superposition states cannot produce signal enhancement. So quantum advantage = superposition (dimensionality) + entanglement (correlation) + interference (signal extraction) — all three are indispensable.

3.2 Single-Qubit Gates

3.2.1 $H$ - $T$ Sequence Calculation

$H\lvert0\rangle = \frac{1}{\sqrt{2}}(\lvert0\rangle + \lvert1\rangle)$

$T\cdot H\lvert0\rangle = \frac{1}{\sqrt{2}}(\lvert0\rangle + e^{i\pi/4}\lvert1\rangle)$

$H\cdot T\cdot H\lvert0\rangle$ : $H\lvert0\rangle = \lvert+\rangle$ , $H\lvert e^{i\pi/4}\rangle$ requires computation

Simpler method: use matrix multiplication.

$H = \frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&-1\end{pmatrix},\quad T = \begin{pmatrix}1&0\\0&e^{i\pi/4}\end{pmatrix}$

$TH = \frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\e^{i\pi/4}&-e^{i\pi/4}\end{pmatrix}$

$HTH = \frac12\begin{pmatrix}1&1\\1&-1\end{pmatrix}\begin{pmatrix}1&1\\e^{i\pi/4}&-e^{i\pi/4}\end{pmatrix} = \frac12\begin{pmatrix}1+e^{i\pi/4} & 1-e^{i\pi/4}\\ 1-e^{i\pi/4} & 1+e^{i\pi/4}\end{pmatrix}$

So: $HTH\lvert0\rangle = \frac12\begin{pmatrix}1+e^{i\pi/4}\\ 1-e^{i\pi/4}\end{pmatrix}$

Note $1+e^{i\pi/4} = \sqrt{2+\sqrt{2}}\cdot e^{i\pi/8}$ , $1-e^{i\pi/4} = \sqrt{2-\sqrt{2}}\cdot e^{i3\pi/8}$

Final $T$ : $T(HTH\lvert0\rangle) = \frac12\begin{pmatrix}1+e^{i\pi/4}\\ e^{i\pi/4}(1-e^{i\pi/4})\end{pmatrix}$

Simplify: $e^{i\pi/4}(1-e^{i\pi/4}) = e^{i\pi/4} - e^{i\pi/2} = e^{i\pi/4} - i$

The final state $(\theta, \phi)$ can be obtained by computing $|\alpha|^2$ and the phase difference.

3.2.2 Proof of Arbitrary Rotation Decomposition

Any $U \in SU(2)$ can be written as $U = e^{i\alpha}R_{\hat{n}}(\theta) = e^{i\alpha}e^{-i\frac{\theta}{2}\vec{\sigma}\cdot\hat{n}}$

Express $\hat{n}$ in spherical coordinates: $\hat{n} = (\sin\Theta\cos\Phi,\ \sin\Theta\sin\Phi,\ \cos\Theta)$

From the identity: $e^{-i\frac{\theta}{2}\vec{\sigma}\cdot\hat{n}} = \cos\frac{\theta}{2}I - i\sin\frac{\theta}{2}(\hat{n}\cdot\vec{\sigma})$

Construct $R_z(\beta)R_y(\gamma)R_z(\delta)$ :

$R_z(\beta) = \begin{pmatrix}e^{-i\beta/2}&0\\0&e^{i\beta/2}\end{pmatrix}$ $R_y(\gamma) = \begin{pmatrix}\cos(\gamma/2)&-\sin(\gamma/2)\\\sin(\gamma/2)&\cos(\gamma/2)\end{pmatrix}$

The product yields:

$R_z(\beta)R_y(\gamma)R_z(\delta) = \begin{pmatrix}e^{-i(\beta+\delta)/2}\cos(\gamma/2) & -e^{-i(\beta-\delta)/2}\sin(\gamma/2)\\ e^{i(\beta-\delta)/2}\sin(\gamma/2) & e^{i(\beta+\delta)/2}\cos(\gamma/2)\end{pmatrix}$

This is a general $SU(2)$ matrix (diagonal entries are complex conjugates, off-diagonal entries form another conjugate pair). It is precisely the form of any single-qubit unitary transformation, up to a global phase. Geometric meaning: first use $R_z(\delta)$ to rotate the state to the correct longitude, use $R_y(\gamma)$ to adjust the latitude, then use $R_z(\beta)$ to adjust the final phase. This is the “Euler angle” decomposition of quantum state preparation.

3.2.3 🗣️ Key Points for Answer

Quantum gates are physical processes, not just computations: When you apply a gate to a quantum state, you are actually manipulating a physical system — bombarding a superconducting circuit with microwave pulses, or irradiating ions with lasers — this physical process obeys the Schrödinger equation, not a simple array operation. Your numpy code simulates this physical process, but is not the physical process itself.
Irreversibility of measurement: Every instruction on a classical CPU is deterministic — you can freely copy and inspect intermediate values. But in quantum gate operations, the intermediate state collapses as soon as it is measured. You cannot “take a peek” midway through the computation without destroying it. This means debugging quantum programs is fundamentally different from debugging classical programs.
Parallelism has a cost: You can operate in parallel on quantum superpositions, but reading out the result causes collapse. The real problem is: you are not “trying all possibilities at once,” but rather using carefully designed interference to amplify the probability amplitude of the correct answer and attenuate the wrong ones. This is more like orchestrating water-wave interference than spawning multiple CPU threads.

3.2.4 💭 Insight Answer

(a) The Clifford gate set ( $H, S, CNOT$ ) can be efficiently simulated by a classical computer via the Gottesman-Knill theorem — purely Clifford circuits have no quantum advantage. A non-Clifford gate (such as $T$ ) must be inserted to break through this limitation. Hence universal quantum computing = Clifford + non-Clifford. The $T$ gate provides a phase-rotation precision that Clifford gates cannot replicate.

(b) In fault-tolerant quantum computing, Clifford gates can be implemented with very low resource cost via stabilizer codes (such as the surface code). But the $T$ gate cannot be directly implemented fault-tolerantly — it requires magic state distillation, a high-overhead process (potentially over 100 physical $T$ gates to synthesize one high-fidelity logical $T$ gate). The $T$ gate is “expensive” not because of physical difficulty, but because it lies outside the stabilizer formalism. Hence, when estimating quantum computing resources, one often only looks at “how many $T$ gates are needed.”

(c) Switching gate sets won’t help much. Any universal gate set must contain a non-Clifford gate, and any non-Clifford gate faces similarly high costs in the surface code. This is an intrinsic limitation of fault-tolerant universal quantum computing, not something that can be circumvented by switching gate sets.

3.3 Multi-Qubit Gates & Entanglement

3.3.1 Gate Operations on an Entangled State

Initial: $\lvert\Phi^+\rangle = \frac{1}{\sqrt{2}}(\lvert00\rangle + \lvert11\rangle)$

$H$ gate on first qubit: $\lvert\psi_1\rangle = \frac{1}{\sqrt{2}}(H\lvert0\rangle \otimes \lvert0\rangle + H\lvert1\rangle \otimes \lvert1\rangle)$ $= \frac{1}{2}[(\lvert0\rangle+\lvert1\rangle)\lvert0\rangle + (\lvert0\rangle-\lvert1\rangle)\lvert1\rangle]$ $= \frac{1}{2}(\lvert00\rangle + \lvert10\rangle + \lvert01\rangle - \lvert11\rangle)$
CNOT (control=1, target=2): Flip second qubit when first is $|1\rangle$ : $\lvert\psi_2\rangle = \frac{1}{2}(\lvert00\rangle + \lvert11\rangle + \lvert01\rangle - \lvert10\rangle)$
$Z$ gate on first qubit: $Z\lvert\psi_2\rangle = \frac{1}{2}(\lvert00\rangle - \lvert11\rangle + \lvert01\rangle + \lvert10\rangle)$

Final state: $\frac{1}{2}(\lvert00\rangle + \lvert01\rangle + \lvert10\rangle - \lvert11\rangle)$

This is not a Bell state (amplitudes are not uniformly $1/\sqrt{2}$ ). It equals $\frac{1}{\sqrt{2}}(\lvert0+\rangle - \lvert1-\rangle)$ .

3.3.2 Product Gates Preserve Separability Proof

Separable input state: $\lvert\psi_{in}\rangle = \lvert\phi_1\rangle \otimes \lvert\phi_2\rangle$

Apply $U = A \otimes B$ :

$\lvert\psi_{out}\rangle = (A \otimes B)(\lvert\phi_1\rangle \otimes \lvert\phi_2\rangle) = (A\lvert\phi_1\rangle) \otimes (B\lvert\phi_2\rangle)$

This is clearly also separable (a tensor product of two single-qubit states).

Significance: Using only gates in tensor-product form cannot create entanglement. To create entanglement, one must use a non-tensor-product gate like CNOT. This is precisely why CNOT is so important — it is the simplest gate capable of generating entanglement. Without CNOT or an equivalent two-qubit gate, quantum computation would have no genuine “quantumness.”

3.3.3 🗣️ Key Points for Answer

Entanglement is about correlation, not signaling: Entanglement does not mean there is an “information channel” between the two particles. It means there is a statistical correlation between the measurement results of the two particles — when you measure the first as 0, the second is necessarily 1 (for $\lvert\Psi^-\rangle$ ). But this correlation can only be seen after the fact, by comparing data, and cannot be used to transmit information in real time.
Why it cannot be used for faster-than-light communication: Suppose Alice and Bob share an entangled pair. Alice measures her particle first and gets 0 or 1 (each with 50% probability). Bob’s particle now “knows” Alice’s result — but Bob himself cannot know, because his measurement result is also random. Alice’s measurement has not sent any signal to Bob; Bob cannot distinguish whether his particle has already been measured. This guarantees that relativistic causality is not violated.
The real use of entanglement: Entanglement can be used for quantum teleportation — transmitting a quantum state (not faster than light; classical communication is also needed). It can also be used for quantum key distribution — if someone eavesdrops on the channel, the entanglement is destroyed, and this can be detected.

An analogy: Entanglement is like two people each holding one glove from a pair in a box. When one person opens their box and finds a left-hand glove, they “know” the other person must have the right-hand glove — but individually, before opening the box, neither knows what they have. This is not faster-than-light communication; it is merely correlation.

3.3.4 💭 Insight Answer

(a) Yes! Quantum states without entanglement (i.e., separable states) can be efficiently simulated by classical computers. Specifically, describing an $n$ -qubit separable state as a tensor product of $n$ single-qubit states requires only $O(n)$ parameters, not $2^n$ . So entanglement is the true source of “quantumness” — without entanglement there is no quantum advantage.

(b) Entanglement “consumes” separability. Preparing a Bell pair requires an $H$ gate and a CNOT gate, and CNOT requires a physical interaction between two qubits (such as capacitive coupling on a superconducting chip). This comes at a cost: the fidelity of two-qubit gates is typically lower than that of single-qubit gates, and entanglement decays with decoherence (entanglement “death”). Maintaining high-quality entanglement is a core engineering challenge of current quantum computing.

(c) Entanglement can be “transferred” between different systems (entanglement swapping). Two particles that have never interacted can become entangled through an intermediary particle — this lays the foundation for quantum networks and quantum repeaters. Imagine a “quantum internet”: through entanglement swapping and entanglement distillation, we can establish high-quality entanglement links across long distances. This differs from electricity transmission (electricity transmits energy, whereas entanglement transmits correlation), but in a topological sense, entanglement is indeed a resource that can be routed and purified.

3.4 Quantum Circuits

3.4.1 Circuit Tracking

Circuit:

|0⟩ —H—•——H—•—
|0⟩ ———⊕——H—⊕—
|0⟩ ————————⊕—

Step-by-step tracking:

Initial: $\lvert000\rangle$
$H$ on first qubit: $\frac{1}{\sqrt{2}}(\lvert000\rangle + \lvert100\rangle)$
CNOT $_{1\to2}$ : $\frac{1}{\sqrt{2}}(\lvert000\rangle + \lvert110\rangle)$
$H$ on second qubit: $\frac{1}{\sqrt{2}}(\lvert000\rangle + \frac{1}{\sqrt{2}}(\lvert100\rangle - \lvert110\rangle))$ ? Note $H(\lvert110\rangle) = \lvert1\rangle \otimes \frac{1}{\sqrt{2}}(\lvert0\rangle + \lvert1\rangle) \otimes \lvert0\rangle = \frac{1}{\sqrt{2}}(\lvert100\rangle + \lvert110\rangle)$

Correction: $H$ only acts on the second qubit: $\frac{1}{\sqrt{2}}(\lvert000\rangle + \lvert110\rangle) \xrightarrow{H_2} \frac{1}{\sqrt{2}}[\lvert0\rangle \otimes H\lvert0\rangle \otimes \lvert0\rangle + \lvert1\rangle \otimes H\lvert1\rangle \otimes \lvert0\rangle]$ $= \frac{1}{2}[(\lvert000\rangle + \lvert010\rangle) + (\lvert100\rangle - \lvert110\rangle)]$ $= \frac{1}{2}(\lvert000\rangle + \lvert010\rangle + \lvert100\rangle - \lvert110\rangle)$

CNOT $_{1\to2}$ : flip the second qubit when the first is $|1\rangle$ : $\frac{1}{2}(\lvert000\rangle + \lvert010\rangle + \lvert110\rangle - \lvert100\rangle)$
CNOT $_{2\to3}$ : flip the third qubit when the second is $|1\rangle$ :

$\lvert000\rangle \to \lvert000\rangle$
$\lvert010\rangle \to \lvert011\rangle$
$\lvert110\rangle \to \lvert111\rangle$
$\lvert100\rangle \to \lvert100\rangle$

Final state: $\frac{1}{2}(\lvert000\rangle + \lvert011\rangle + \lvert111\rangle - \lvert100\rangle)$

This is a four-component entangled state, not a GHZ state.

3.4.2 Proof of CNOT Gate Equivalence

We need to prove: $(H \otimes H) \cdot \text{CNOT}_{1\to2} \cdot (H \otimes H) = \text{CNOT}_{2\to1}$

Work through the left-hand side on the computational basis:

First apply $H$ to both qubits: $\lvert00\rangle \to \frac{1}{2}(\lvert00\rangle + \lvert01\rangle + \lvert10\rangle + \lvert11\rangle)$

After CNOT $_{1\to2}$ : $\frac{1}{2}(\lvert00\rangle + \lvert01\rangle + \lvert11\rangle + \lvert10\rangle)$ = no change! Because the input is symmetric.

Wait, we need to work through each basis vector more carefully.

For $\lvert00\rangle$ : $(H\otimes H)\lvert00\rangle = \frac{1}{2}(\lvert00\rangle + \lvert01\rangle + \lvert10\rangle + \lvert11\rangle)$ After $\text{CNOT}_{1\to2}$ : $\frac{1}{2}(\lvert00\rangle + \lvert01\rangle + \lvert11\rangle + \lvert10\rangle)$ = $\frac{1}{2}(\lvert00\rangle + \lvert01\rangle + \lvert10\rangle + \lvert11\rangle)$ = $\lvert++\rangle$ Then $(H\otimes H)\lvert++\rangle = \lvert00\rangle$ .

For $\lvert01\rangle$ : $(H\otimes H)\lvert01\rangle = \frac{1}{2}(\lvert00\rangle - \lvert01\rangle + \lvert10\rangle - \lvert11\rangle)$ After $\text{CNOT}_{1\to2}$ : $\frac{1}{2}(\lvert00\rangle - \lvert01\rangle + \lvert11\rangle - \lvert10\rangle)$ = $\frac{1}{2}(\lvert00\rangle - \lvert01\rangle - \lvert10\rangle + \lvert11\rangle)$ After $(H\otimes H)$ : $\frac{1}{2}[(H\otimes H)(\lvert00\rangle - \lvert01\rangle - \lvert10\rangle + \lvert11\rangle)]$ $(H\otimes H)\lvert00\rangle = \lvert++\rangle = \frac{1}{2}(\lvert00\rangle + \lvert01\rangle + \lvert10\rangle + \lvert11\rangle)$ $(H\otimes H)\lvert01\rangle = \lvert+-\rangle = \frac{1}{2}(\lvert00\rangle - \lvert01\rangle + \lvert10\rangle - \lvert11\rangle)$ $(H\otimes H)\lvert10\rangle = \lvert-+\rangle = \frac{1}{2}(\lvert00\rangle + \lvert01\rangle - \lvert10\rangle - \lvert11\rangle)$ $(H\otimes H)\lvert11\rangle = \lvert--\rangle = \frac{1}{2}(\lvert00\rangle - \lvert01\rangle - \lvert10\rangle + \lvert11\rangle)$

So in the above expression: $\frac{1}{2}[\lvert++\rangle - \lvert+-\rangle - \lvert-+\rangle + \lvert--\rangle]$ $= \frac{1}{2}[\lvert++\rangle - \lvert+-\rangle - \lvert-+\rangle + \lvert--\rangle]$

Compute the representation of $\lvert01\rangle$ in this basis… A simpler method is to verify directly with matrices.

Direct matrix verification: $\text{CNOT}_{1\to2} = \begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{pmatrix}$

$(H\otimes H) = \frac12\begin{pmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{pmatrix}$

Computing $(H\otimes H)\cdot\text{CNOT}_{1\to2}\cdot(H\otimes H)$ yields:

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

QED. Geometric meaning: The $H$ gate swaps the $Z$ basis and the $X$ basis. In the $X$ basis, the control-target relationship of CNOT is reversed.

3.4.3 🗣️ Key Points for Answer

Unitarity comes from the postulates: Quantum mechanics requires that time-evolution operators be unitary (preserving inner products), which is a direct requirement of Postulate 3. If an irreversible gate were used, the system would lose information and violate probability conservation — this is not allowed in quantum mechanics.
The disaster of irreversible gates: If we tried to use an AND gate (irreversible, input 00/01/10/11 → output 0/0/0/1, losing 2 bits of information), in quantum mechanics this means information is “leaked” into the environment, i.e., decoherence. Decoherence destroys quantum superposition, reducing quantum computation to classical computation.
The cost of reversibility: Classical reversible gates (such as Toffoli) require more physical resources — a Toffoli gate in quantum implementation requires about 8 elementary gates (CNOT + single-qubit gates). By comparison, a classical NAND only needs 4 transistors. The “reversibility” of quantum computing is a double-edged sword: it protects quantum coherence, but at a greater gate-implementation cost.

3.4.4 💭 Insight Answer

(a) 100 qubits, depth 50 — this roughly describes the capability of today’s most advanced quantum processors. What can be done: simple problems with certain variational quantum algorithms (VQE), small-scale quantum chemistry simulations (such as the H2 molecule), random circuit sampling (validating quantum advantage). What cannot be done: Shor’s algorithm factoring large numbers (requires depth $10^9+$ ), Grover search on large databases.

(b) The depth constraint is more fatal because: you can exploit more parallelism by increasing the qubit count, but the depth limit means you cannot execute complex algorithms. For example, the circuit depth required by Shor’s algorithm grows polynomially with input length (roughly $O((\log N)^3)$ ); for a 2048-bit RSA key, the depth is approximately $10^9$ — far beyond the ~100 depth capability of current devices. Increasing the qubit count does not solve the depth problem.

(c) Quantum volume $V_Q = \min[n, d]^2$ , where $n$ is the qubit count and $d$ is the maximum depth. It reflects the comprehensive capability of a quantum processor: a device with 1000 qubits but depth only 5 ( $V_Q = 25$ ) is not necessarily more useful than one with 50 qubits and depth 50 ( $V_Q = 2500$ ). This metric tells us: qubit count is not everything; quality and depth are equally important.

3.5 Quantum Measurement & Readout

3.5.1 Expectation Value Calculation

$\lvert\psi\rangle = \frac{1}{\sqrt{2}}(\lvert0\rangle - e^{i\pi/3}\lvert1\rangle)$ , where $\alpha = 1/\sqrt{2}$ , $\beta = -e^{i\pi/3}/\sqrt{2}$

$\langle Z\rangle = |\alpha|^2 - |\beta|^2 = \frac12 - \frac12 = 0$

$\langle X\rangle = \alpha^*\beta + \alpha\beta^* = \frac{1}{\sqrt{2}}\cdot\frac{-e^{i\pi/3}}{\sqrt{2}} + \frac{1}{\sqrt{2}}\cdot\frac{-e^{-i\pi/3}}{\sqrt{2}} = -\frac12(e^{i\pi/3} + e^{-i\pi/3}) = -\cos(\pi/3) = -\frac12$

$\langle Y\rangle = i(\alpha\beta^* - \alpha^*\beta) = i\left[\frac{1}{\sqrt{2}}\cdot\frac{-e^{-i\pi/3}}{\sqrt{2}} - \frac{1}{\sqrt{2}}\cdot\frac{-e^{i\pi/3}}{\sqrt{2}}\right] = \frac{i}{2}(-e^{-i\pi/3} + e^{i\pi/3}) = \frac{i}{2}\cdot 2i\sin(\pi/3) = -\sin(\pi/3) = -\frac{\sqrt{3}}{2}$

Verification: $\langle X\rangle^2 + \langle Y\rangle^2 + \langle Z\rangle^2 = \frac14 + \frac34 + 0 = 1$ . It is a pure state.

3.5.2 Proof of the “Counterintuitive” Nature of Measurement

(a) $\lvert\Psi^-\rangle = \frac{1}{\sqrt{2}}(\lvert01\rangle - \lvert10\rangle)$

Measure the first qubit in the computational basis:

$P_1(0) = \text{Tr}[(\lvert0\rangle\langle0\rvert \otimes I) \lvert\Psi^-\rangle\langle\Psi^-\rvert]$

$\langle\Psi^-\rvert(\lvert0\rangle\langle0\rvert \otimes I)\lvert\Psi^-\rangle = \frac12(\langle01\rvert - \langle10\rvert)(\lvert0\rangle\langle0\rvert \otimes I)(\lvert01\rangle - \lvert10\rangle)$

$= \frac12\langle01\rvert(\lvert0\rangle\langle0\rvert \otimes I)\lvert01\rangle + \frac12\langle10\rvert(\lvert0\rangle\langle0\rvert \otimes I)\lvert10\rangle$ (cross terms vanish)

$= \frac12\langle1\rvert I\lvert1\rangle\langle0\rvert0\rangle\langle0\rvert0\rangle + \frac12\langle0\rvert I\lvert0\rangle\langle1\rvert0\rangle\langle0\rvert1\rangle$

$= \frac12 \cdot 1 \cdot 1 \cdot 1 + \frac12 \cdot 1 \cdot 0 = \frac12$

Similarly $P_1(1) = 1/2$ . By symmetry, the same holds for the second qubit.

(b) Measuring both qubits simultaneously: $P(00) = P(11) = 0$ , $P(01) = P(10) = 1/2$ . So the two qubits always yield opposite results.

(c) Analogy: Imagine two magic balls. When looked at individually, each is red/blue completely randomly. But if you look at both at the same time, their colors are always different. This is not because there is “communication” between the balls, but because they were made to be “paired” — one is always red, the other always blue, but we don’t know which is which. Quantum entanglement is stronger than this analogy (involving choice of basis, phase, etc.), but the core feature of “globally determined, locally random” is similar.

3.5.3 🗣️ Key Points for Answer

Probability amplitudes have phase; classical probabilities do not: Classical probability has only magnitude (0.6 vs. 0.4), but quantum probability amplitudes are complex numbers containing phase information. Phase produces interference effects: $\lvert+\rangle = (\lvert0\rangle + \lvert1\rangle)/\sqrt{2}$ and $\lvert-\rangle = (\lvert0\rangle - \lvert1\rangle)/\sqrt{2}$ have exactly the same measurement probabilities ( $P(0)=P(1)=0.5$ ), but in the $X$ basis they produce completely different results. A classical coin cannot do this — you won’t find two different coins that give the same probability of heads but behave completely differently under a different kind of “measurement.”
Collapse is not conditional updating: Classical conditional probability is information updating — if you flip an unfair coin but don’t look at the result, the conditional probability only reflects a change in your knowledge; the coin itself hasn’t changed. But post-measurement collapse in quantum mechanics is a physical change — the quantum state really is altered, not just your ignorance of it. Measure $\lvert+\rangle$ in the $Z$ basis; after getting 0, the state becomes $\lvert0\rangle$ , and measuring again in the $Z$ basis gives 0 (deterministically). But classical probability updating after tossing and getting heads also gives heads on the next toss — superficially similar. The difference is: if you switch to the $X$ basis after measurement, $\lvert0\rangle$ ‘s $X$ measurement result is random ( $P(+)=P(-)=0.5$ ), whereas a classical unfair coin behaves the same in any “basis.”
Example: For $\lvert+\rangle$ measured in the $Z$ basis, $P(0)=P(1)=0.5$ ; measured in the $X$ basis, $P(+)=1$ . The same state in different “measurement directions” gives completely different statistics. No classical probability distribution can achieve this. This proves that quantum probability is not classical probability.

3.5.4 💭 Insight Answer

(a) Theoretically, a single-qubit pure state requires $\infty$ measurements to determine (since each individual measurement yields a random result; only with enough statistics can we estimate precisely). But in practice, from an information-theoretic perspective, a single-qubit pure state has 2 real parameters ( $\theta, \phi$ ); theoretically, a minimum of 2 bits of information can encode it — but extracting these 2 bits requires many measurements (because each measurement produces only 1 bit, and there is statistical noise).

(b) An $n$ -qubit pure state has $2^{n+1} - 2$ real parameters. The sample complexity of standard quantum state tomography is $O(2^n)$ , growing exponentially with $n$ . This is the fundamental reason quantum state tomography does not scale — even if we have prepared these states, the cost of measuring them to confirm is too high. This motivates research on “quantum verification” — confirming quantum state properties without full tomography.

(c) The standard quantum limit $1/\sqrt{N}$ can be surpassed by using entangled initial states (such as GHZ states), reaching the Heisenberg limit $1/N$ — this is quantum-enhanced sensing. For example, using an interferometer with $N$ entangled particles, the phase estimation precision can reach $1/N$ , improving on the classical limit $1/\sqrt{N}$ by a factor of $\sqrt{N}$ . This is a core advantage of quantum metrology and a direct manifestation of the “interference” capability of quantum computing.

3.6 Quantum Algorithm Primer

3.6.1 BB84 Eavesdropping Probability Analysis

(a) When Eve intercepts and measures, she has a 50% chance of choosing the wrong basis. Choosing the wrong basis gives a wrong result with 50% probability, so each measurement introduces a $0.5 \times 0.5 = 25\%$ error rate. But if Eve measures with probability $p$ and forwards with probability $1-p$ , the overall error rate = $p \times 25\%$ .

Concise derivation:

Eve measures with probability: $p$
Eve chooses wrong basis with probability: $1/2$
When Eve chooses the wrong basis, measurement error probability: $1/2$
Error rate per bit = $p \cdot \frac12 \cdot \frac12 = \frac{p}{4}$

(b) Set $p/4 < 0.05$ , giving $p < 0.2$ . That is, if Eve intercepts more than 20% of the qubits, she will be detected.

3.6.2 Geometric Interpretation of Grover Iteration

(a) Define the initial state $\lvert s\rangle = \frac{1}{\sqrt{N}}\sum_x \lvert x\rangle$ . Decompose it into the target component and the orthogonal component:

$\lvert s\rangle = \sin\theta\lvert \omega\rangle + \cos\theta\lvert \omega^\perp\rangle$

where $\sin\theta = 1/\sqrt{N}$ .

Grover iteration $G = U_s U_\omega$ , where:

$U_\omega = I - 2\lvert\omega\rangle\langle\omega\rvert$ (marking, reflection about $\lvert \omega^\perp\rangle,\lvert\omega\rangle$ )
$U_s = 2\lvert s\rangle\langle s\rvert - I$ (diffusion, reflection about $\lvert s\rangle$ )

The composition of two reflections = a rotation of $2\theta$ . Each iteration rotates $\lvert s\rangle$ toward $\lvert\omega\rangle$ by $2\theta$ .

(b) The total rotation angle needed is $\pi/2$ (from initial $\theta$ to $\pi/2$ , i.e., pointing toward $\lvert\omega\rangle$ ).

Number of iterations $k$ : $k \cdot 2\theta + \theta = \pi/2$ , giving $k = \frac{\pi}{4\theta} - \frac12$

Since $\sin\theta \approx \theta = 1/\sqrt{N}$ (for large $N$ ), $k \approx \frac{\pi}{4}\sqrt{N} - \frac12 \approx \frac{\pi}{4}\sqrt{N}$

(c) $N = 10^6$ , classical worst case $N = 10^6$ queries, average $5\times 10^5$ queries. Quantum: $k \approx \frac{\pi}{4}\sqrt{10^6} = \frac{\pi}{4} \cdot 1000 \approx 785$ queries. Speedup factor: approximately $10^6/785 \approx 1274$ x.

3.6.3 🗣️ Key Points for Answer

“Trying everything at once” is impossible: If a quantum computer truly “tried all possibilities at once,” measurement would yield a superposition of all possible results — but measurement gives only one result. So the biggest problem with the “try everything at once” analogy is: you can only extract one result.
Interference is key: The secret of quantum algorithms lies not in parallelism, but in interference. Take Grover’s search as an example: we are not listing all possibilities and then picking the right one — we use amplitude amplification to make the probability amplitude of the correct item larger and wrong items smaller. This is more like tidal waves converging energy to a point, rather than reading from multiple folders simultaneously.
Quantum computers are not fast on all problems: Classical computers may always be faster than quantum computers on general tasks (sorting, database management, office software). Quantum computers only have an advantage on specific problems: factoring (Shor), search (Grover), simulating quantum systems. It will not replace your laptop.
The real state in 2026: Today’s most advanced quantum processors have 1000+ physical qubits (e.g., IBM Condor), but logical qubits (effective qubits after error correction) remain in the single digits. Noise levels limit circuit depth to approximately 50–100 layers. We can demonstrate “quantum supremacy” with random circuit sampling (Google 2019, 53 qubits), and we can run small-scale variational algorithms, but there is still no recognized, commercially valuable “quantum advantage” demonstration. Breaking RSA-2048 requires several million logical qubits; at the current rate of progress, it is estimated to take another 10–20 years.

3.6.4 💭 Insight Answer

(a) AES-256’s effective key strength against Grover’s search is reduced to 128 bits — still secure in the classical-computing sense ( $2^{128}$ operations far exceed any feasible attack). However, if faster quantum algorithms emerge in the future (not limited to Grover), the situation could change. The current academic consensus is that AES-256 is post-quantum secure, but AES-128 may be at risk.

(b) The PQC standards selected by NIST are primarily based on:

Lattice-based cryptography: Kyber (KEM), Dilithium (signatures). Security is based on the Learning With Errors (LWE) problem — a variant of the closest vector problem on lattices — for which no known efficient quantum algorithm exists.
Hash-based signatures: SPHINCS+, based on the irreversibility of hash functions, for which Grover only provides a quadratic speedup.

The root of these problems’ resistance to quantum attacks lies in their lack of reliance on structured algebraic structures (such as the cyclic groups of RSA), instead depending on “noise” and “randomness,” making the quantum Fourier transform ineffective in the way it is against RSA.

(c) There is no definitive answer to this question, but three mainstream views exist:

Quantum advantage first (optimistic view): Within 5–10 years, quantum simulation (materials science, chemistry) will demonstrate commercially valuable advantages, such as more efficient catalyst or battery material design.
RSA broken first (pessimistic / cryptographic perspective): Although more qubits are needed, cryptography is an attacker’s problem — the attacker only needs to succeed once, while the defender needs to be safe forever. Therefore, even if a quantum RSA break only appears in 2040, we should migrate to PQC now.
Simultaneous but in different domains: Quantum advantage will be achieved earlier in simulation (2028–2032), while RSA breaking requires a longer timeline (2035–2045). The two realization paths are completely different — simulation requires fewer logical qubits but higher precision, while RSA breaking requires many logical qubits with less stringent precision requirements.

I most agree with the third view: quantum computing’s advantage will first manifest in scientific computing domains; the cryptographic threat is a longer-term but more severe challenge.

Open Questions

These questions have no standard answers and are suitable for classroom discussion, debate, or deep reflection. Each question touches on the intersection of technology, society, or philosophy.

1. Where is the “killer application” of quantum advantage?

Shor’s algorithm threatens cryptography, Grover’s search accelerates searching, VQE simulates quantum chemistry. But which one is the “killer application” of quantum computers? Or, does quantum computing even need a “killer application” like classical computing had (spreadsheets, web browsing) to prove its value? Could quantum advantage be dispersed across many narrow domains, with no single killer application?

2. Will quantum computing exacerbate or alleviate digital inequality?

The construction cost of quantum computers is estimated to be in the billions of dollars; initially, only a few organizations (Google, IBM, governments) may have access. Considering the business model of cloud quantum services, will this aggravate the monopoly of large tech companies over computing resources, or will cloud services allow more people to benefit? What would the “digital divide” look like in the era of quantum computing?

3. If PQC is deployed ahead of time, does Shor’s algorithm still have engineering significance?

If the entire world completes the PQC migration by 2030 (NIST has already issued standards), breaking RSA with a quantum computer loses its practical significance — no important encrypted data would still be using RSA. Then what is the primary motivation for developing large-scale fault-tolerant quantum computers? Pure scientific research? Simulating quantum systems? Or do we still need to be vigilant against unknown cryptographic breakthroughs?

4. Is quantum randomness truly random?

Quantum measurement outcomes are probabilistic — does this mean that quantum computers are “true random number generators”? Classical computers can only generate pseudo-random numbers (dependent on algorithms and seeds), whereas quantum computers can generate random numbers based on measurement outcomes. Is this philosophically “more random”? What does this mean for industries such as cryptography, Monte Carlo simulation, and lotteries?

5. Is the concept of “quantum supremacy” reasonable?

In 2019, Google announced “quantum supremacy” (using the 53-qubit Sycamore processor to complete, in 200 seconds, a computational task that would take a classical supercomputer 10,000 years). But subsequently, IBM disputed this conclusion, pointing out that classical algorithms could simulate this specific circuit more efficiently. This controversy leads to a deeper question: is the term “quantum supremacy” meaningful? Should we replace it with more constructive metrics (such as advantage on useful computational tasks)? What would constitute a convincing “quantum advantage” demonstration?

File Info: 6 sections × 4 problems = 24 core problems + 5 open questions

Difficulty Distribution: ⭐ 6 problems · ⭐⭐ 6 problems · 🗣️ 6 problems · 💭 6 problems

Total Lines: approximately 850 lines

Quantum Computing Primer — Code Verification Supplement

Companion Tutorial: Quantum Computing Primer — From First Principles

Purpose: This document provides Python + NumPy + Qiskit code blocks for verifying key mathematical derivations in the tutorial and demonstrating quantum computing concepts. All code can be copied and pasted to run directly.

Runtime Environment Requirements:

Python ≥ 3.9

pip install numpy qiskit qiskit-aer

For printing colored matrices, optionally install pip install rich (not required)

Installation and Imports

## ============================================================
## Environment Setup: Install Dependencies
## ============================================================
## Run in terminal:
##   pip install numpy qiskit qiskit-aer
#
## If Qiskit version is 1.x, please use AerSimulator:
##   from qiskit_aer import AerSimulator
## ============================================================

import numpy as np

## ---------- Qiskit 1.x Compatible Imports ----------
try:
    from qiskit import QuantumCircuit, transpile
    from qiskit_aer import AerSimulator
    from qiskit.visualization import plot_histogram
    HAS_QISKIT = True
except ImportError:
    HAS_QISKIT = False
    print("⚠️  Qiskit not installed. Only the NumPy portion is executable.")
    print("   Install command: pip install qiskit qiskit-aer")

Part 1: Mathematical Foundation Verification

Corresponding to Tutorial Sections 1.1 – 1.8

1.1 Complex Number Operations and Euler’s Formula

Corresponding Tutorial: 1.1.2 Arithmetic Operations and Conjugation, 1.1.4 Derivation of Euler’s Formula

Verification Goal: Complex number arithmetic, conjugation, modulus computation, and numerical verification of Euler’s formula

## ============================================================
## Example 1: Basic Complex Number Operations — Verifying Tutorial Section 1.1.2
## ============================================================

## Using Python's built-in complex type
z1 = 1 + 2j   # Corresponds to the numerator of Tutorial Example 1.1
z2 = 3 - 1j   # Corresponds to the denominator of Tutorial Example 1.1

## --- Addition and Subtraction ---
print("=== Complex Addition and Subtraction ===")
print(f"z1 = {z1}")
print(f"z2 = {z2}")
print(f"z1 + z2 = {z1 + z2}")   # Expected: (4+1j)
print(f"z1 - z2 = {(1+2j) - (3-1j)}")  # Expected: (-2+3j)

## --- Multiplication (Tutorial Formula) ---
## (a+bi)(c+di) = (ac-bd) + (ad+bc)i
print("\n=== Complex Multiplication ===")
print(f"z1 * z2 = {z1 * z2}")   # Expected: (5+5j)
## Verification: (1+2j)(3-1j) = 3 -1j + 6j -2j² = 3+5j+2 = 5+5j ✓

## --- Conjugation ---
print("\n=== Complex Conjugation (Tutorial 1.1.2) ===")
print(f"Conjugate of z1 conj(z1) = {z1.conjugate()}")   # Expected: (1-2j)
print(f"Conjugate of z2 conj(z2) = {z2.conjugate()}")   # Expected: (3+1j)

## --- Division (Verification of Example 1.1) ---
print("\n=== Complex Division (Tutorial Example 1.1) ===")
result = (1 + 2j) / (3 - 1j)
print(f"(1+2j)/(3-1j) = {result}")
print(f"Expected value: 0.1 + 0.7j")
print(f"Verification: result × denominator = {result * (3-1j)} (should be 1+2j)")

## --- Modulus Computation ---
print("\n=== Modulus (Tutorial 1.1.3) ===")
z3 = 1 + 1j
print(f"|{z3}| = {abs(z3):.4f}")   # Expected: sqrt(2) ≈ 1.4142
print(f"Verification: sqrt(1²+1²) = {np.sqrt(1**2 + 1**2):.4f}")

## ============================================================
## Example 2: Numerical Verification of Euler's Formula — Verifying Tutorial Section 1.1.4
## ============================================================

print("=== Euler's Formula e^(iθ) = cosθ + i sinθ — Numerical Verification ===")

thetas = [0, np.pi/4, np.pi/2, np.pi, 3*np.pi/2, 2*np.pi]
labels = ["0", "π/4", "π/2", "π", "3π/2", "2π"]

for theta, label in zip(thetas, labels):
    euler = np.exp(1j * theta)          # e^(iθ)
    trig  = np.cos(theta) + 1j * np.sin(theta)  # cosθ + i sinθ
    diff  = abs(euler - trig)
    print(f"θ={label:6s}: e^(iθ)={euler:8.4f}, cos+isin={trig:8.4f}, diff={diff:.2e}")
    assert diff < 1e-15, "Euler's formula numerical verification failed!"

print("\n✅ Euler's formula verification passed: all differences at ~10^-16 scale (floating-point precision)")

## ---------- Special Verification: Euler's Identity e^(iπ) + 1 = 0 ----------
print("\n=== Euler's Identity e^(iπ) + 1 = 0 ===")
val = np.exp(1j * np.pi) + 1
print(f"e^(iπ) + 1 = {val}")
print(f"Real part={val.real:.2e}, Imag part={val.imag:.2e}")
assert abs(val) < 1e-15, "Euler's identity verification failed!"
print("✅ Euler's identity verification passed!")

## ============================================================
## Example 3: Geometric Meaning of Complex Multiplication — Verifying Tutorial Section 1.1.5
## ============================================================
## Core tutorial conclusion: Complex multiplication = moduli multiply + arguments add

print("=== Geometric Meaning of Complex Multiplication ===")

z = 1 + 1j   # modulus = √2, argument = π/4
w = np.sqrt(2) * np.exp(1j * np.pi/4)  # modulus = √2, argument = π/4

product = z * w
r_product = abs(product)
theta_product = np.angle(product)

print(f"z = {z}, |z|={abs(z):.4f}, arg(z)={np.angle(z):.4f}")
print(f"w = √2·e^(iπ/4), |w|={abs(w):.4f}, arg(w)={np.angle(w):.4f}")
print(f"z·w = {product}")
print(f"|z·w| = {r_product:.4f} (expected: 2.0)")
print(f"arg(z·w) = {theta_product:.4f} (expected: π/2 ≈ {np.pi/2:.4f})")
print(f"Verification: moduli multiply √2·√2=2, arguments add π/4+π/4=π/2")

## Verify the tutorial example: multiplying by i is equivalent to a 90° rotation
print("\n=== Multiplying by i = 90° Rotation ===")
v = 2 + 0j
print(f"v = {v}")
print(f"v × i = {v * 1j}")     # Expected: 2i (90° counterclockwise rotation)
print(f"v × i² = {v * 1j * 1j}")  # Expected: -2 (180° rotation)
print(f"v × i⁴ = {v * (1j**4)}")   # Expected: 2 (360° rotation, back to original)

1.2 Vector Spaces and Bra-Ket Notation

Corresponding Tutorial: 1.2.3 Bra-Ket Notation, 1.2.5 C² Qubit Space

Verification Goal: Implement Dirac notation in matrix form using NumPy, inner product computation

## ============================================================
## Example 4: NumPy Implementation of Bra-Ket Notation — Verifying Tutorial Section 1.2.3
## ============================================================

print("=== Matrix Representation of Bra-Ket Notation ===")

## Define |0⟩ and |1⟩ (Tutorial 1.2.5)
ket0 = np.array([[1], [0]])  # |0⟩
ket1 = np.array([[0], [1]])  # |1⟩

## bra = conjugate transpose of ket
bra0 = ket0.conj().T          # ⟨0|
bra1 = ket1.conj().T          # ⟨1|

print("|0⟩ =")
print(ket0)
print("\n⟨0| =")
print(bra0)

## Verify orthonormality
print("\n=== Orthonormality Verification ===")
print(f"⟨0|0⟩ = {bra0 @ ket0}")   # Expected: 1
print(f"⟨1|1⟩ = {bra1 @ ket1}")   # Expected: 1
print(f"⟨0|1⟩ = {bra0 @ ket1}")   # Expected: 0
print(f"⟨1|0⟩ = {bra1 @ ket0}")   # Expected: 0

## ---------- Verify Tutorial Example 1.2 ----------
print("\n=== Verification of Tutorial Example 1.2 ===")
psi = np.array([[1], [1j]])       # |ψ⟩ = (1, i)^T
phi = np.array([[2], [1+1j]])     # |φ⟩ = (2, 1+i)^T

bra_psi = psi.conj().T            # ⟨ψ|
bra_phi = phi.conj().T            # ⟨φ|

## Compute inner products
ip_phi_psi = bra_phi @ psi        # ⟨φ|ψ⟩
ip_psi_phi = bra_psi @ phi        # ⟨ψ|φ⟩

print(f"|ψ⟩ = \n{psi}")
print(f"|φ⟩ = \n{phi}")
print(f"⟨φ|ψ⟩ = {ip_phi_psi[0,0]}")          # Expected: 3+i
print(f"⟨ψ|φ⟩ = {ip_psi_phi[0,0]}")          # Expected: 3-i
print(f"⟨ψ|φ⟩ = ⟨φ|ψ⟩*? {ip_psi_phi[0,0] == ip_phi_psi[0,0].conjugate()}")

## ---------- Verify Normalization of |+⟩ (Tutorial Example 1.3) ----------
print("\n=== Tutorial Example 1.3: |+⟩ Normalization Verification ===")
ket_plus = (ket0 + ket1) / np.sqrt(2)   # |+⟩
bra_plus = ket_plus.conj().T
norm_plus = (bra_plus @ ket_plus)[0, 0]
print(f"|+⟩ = 1/√2 (|0⟩ + |1⟩)")
print(f"⟨+|+⟩ = {norm_plus:.4f}")   # Expected: 1
assert abs(norm_plus - 1) < 1e-15, "Normalization verification failed"
print("✅ Normalization verification passed!")

1.3 Linear Operators and Pauli Matrices

Corresponding Tutorial: 1.3.4 Pauli Matrices, 1.3.5 Matrix Operations, Anti-commutation Relations

Verification Goal: Unitarity, Hermiticity, anti-commutation relations, and algebraic properties of Pauli matrices

## ============================================================
## Example 5: Pauli Matrices and Property Verification — Verifying Tutorial Sections 1.3.4 & 1.3.5
## ============================================================

print("=== Definition of Pauli Matrices ===")
I = np.array([[1, 0], [0, 1]], dtype=complex)
X = np.array([[0, 1], [1, 0]], dtype=complex)
Y = np.array([[0, -1j], [1j, 0]], dtype=complex)
Z = np.array([[1, 0], [0, -1]], dtype=complex)

paulis = {"I": I, "X": X, "Y": Y, "Z": Z}
for name, mat in paulis.items():
    print(f"\n{name} =")
    print(mat)

## ---------- Verify Unitarity: U†U = I ----------
print("\n=== Unitarity Verification (U†U = I) ===")
for name, mat in paulis.items():
    u_dag_u = mat.conj().T @ mat
    is_unitary = np.allclose(u_dag_u, I)
    print(f"{name}†·{name} = I? {is_unitary}")
    if not is_unitary:
        print(f"Difference:\n{u_dag_u - I}")

## ---------- Verify Hermiticity: H† = H ----------
print("\n=== Hermiticity Verification (H† = H) ===")
for name, mat in paulis.items():
    is_hermitian = np.allclose(mat.conj().T, mat)
    print(f"{name}† = {name}? {is_hermitian}")

## ---------- Verify Squaring Identity: X² = Y² = Z² = I ----------
print("\n=== Squaring Identity Verification (Pauli² = I) ===")
for name, mat in paulis.items():
    sq = mat @ mat
    is_id = np.allclose(sq, I)
    print(f"{name}² = I? {is_id}")

## ---------- Verify Anti-commutation Relation: XY = -YX ----------
print("\n=== Anti-commutation Relation Verification (Tutorial 1.3.5) ===")
xy = X @ Y
yx = Y @ X
print(f"XY = \n{xy}")
print(f"YX = \n{yx}")
print(f"XY = -YX? {np.allclose(xy, -yx)}")

## ---------- Verify Commutation Relations: XY = iZ ----------
print(f"\n=== Pauli Algebra Relations (Tutorial 1.3.5) ===")
print(f"XY = iZ? {np.allclose(X @ Y, 1j * Z)}")
print(f"YZ = iX? {np.allclose(Y @ Z, 1j * X)}")
print(f"ZX = iY? {np.allclose(Z @ X, 1j * Y)}")

## ---------- Verify XY ≠ YX (Non-commutativity) ----------
print(f"\n=== Non-commutativity of Matrix Multiplication ===")
print(f"XY == YX? {np.allclose(xy, yx)}")  # Expected: False

1.4 Inner Products, Norms, and Projection Operators

Corresponding Tutorial: 1.4 Inner Products and Projection Operators

Verification Goal: Properties of inner products, Cauchy-Schwarz inequality, construction of projection operators

## ============================================================
## Example 6: Inner Products, Norms, and Projection Operators — Verifying Tutorial Section 1.4
## ============================================================

print("=== Norm Computation (Tutorial 1.4 Norm and Distance) ===")
v = np.array([[1], [1j]])   # |v⟩ = (1, i)^T
norm_v = np.sqrt((v.conj().T @ v)[0, 0])
print(f"|v⟩ = \n{v}")
print(f"||v⟩|| = sqrt(⟨v|v⟩) = {norm_v:.4f}")   # Expected: √2 ≈ 1.4142

## Normalization
v_norm = v / norm_v
print(f"\nAfter normalization: ⟨v̂|v̂⟩ = {(v_norm.conj().T @ v_norm)[0,0]:.4f}")  # Expected: 1

## ---------- Cauchy-Schwarz Inequality Verification ----------
print("\n=== Cauchy-Schwarz Inequality |⟨v|w⟩| ≤ ||v||·||w|| ===")
psi = np.array([[1], [0]], dtype=complex)     # |0⟩
phi = np.array([[1], [1]], dtype=complex) / np.sqrt(2)  # |+⟩
ip = (psi.conj().T @ phi)[0, 0]
norm_psi = np.sqrt((psi.conj().T @ psi)[0, 0])
norm_phi = np.sqrt((phi.conj().T @ phi)[0, 0])
lhs = abs(ip)
rhs = norm_psi * norm_phi
print(f"|⟨ψ|φ⟩| = {lhs:.4f}")
print(f"||ψ||·||φ|| = {rhs:.4f}")
print(f"Inequality holds? {lhs <= rhs + 1e-15}")

## ---------- Projection Operator Construction ----------
print("\n=== Projection Operator P₀ = |0⟩⟨0| (Tutorial 1.4) ===")
ket0 = np.array([[1], [0]], dtype=complex)
bra0 = ket0.conj().T
P0 = ket0 @ bra0
print("P0 =")
print(P0)
print(f"P0² = P0? {np.allclose(P0 @ P0, P0)}")   # Idempotence verification

## Completeness relation
ket1 = np.array([[0], [1]], dtype=complex)
bra1 = ket1.conj().T
P1 = ket1 @ bra1
print(f"\nP0 + P1 = I? {np.allclose(P0 + P1, np.eye(2))}")   # Completeness verification

## Projection for computing probability
psi_plus = (ket0 + ket1) / np.sqrt(2)  # |+⟩
p0 = (psi_plus.conj().T @ P0 @ psi_plus)[0, 0]
p1 = (psi_plus.conj().T @ P1 @ psi_plus)[0, 0]
print(f"\nMeasuring |+⟩: P(0) = {p0:.2f}, P(1) = {p1:.2f}")
print(f"Sum of probabilities = {p0 + p1:.2f}")  # Expected: 1.0

1.5 Eigenvalues and the Spectral Theorem

Corresponding Tutorial: 1.5 Eigenvalues and Eigenvectors, Spectral Decomposition of Pauli Matrices

Verification Goal: NumPy eigenvalue decomposition, numerical verification of the spectral theorem

## ============================================================
## Example 7: Eigenvalues and Spectral Decomposition — Verifying Tutorial Section 1.5
## ============================================================

print("=== Eigenvalues of Pauli Z Matrix (Tutorial 1.5 Explicit Computation) ===")
Z = np.array([[1, 0], [0, -1]], dtype=complex)
eigvals_Z, eigvecs_Z = np.linalg.eigh(Z)  # eigh optimized for symmetric/Hermitian matrices
print(f"Z matrix:")
print(Z)
print(f"Eigenvalues: {eigvals_Z}")   # Expected: [-1, 1]
print(f"Eigenvectors (columns):\n{eigvecs_Z}")
print(f"Verification trace = sum of eigenvalues: tr(Z)={np.trace(Z):.0f}, sum(λ)={sum(eigvals_Z):.0f}")
print(f"Verification det = product of eigenvalues: det(Z)={np.linalg.det(Z):.0f}, prod(λ)={np.prod(eigvals_Z):.0f}")

## ---------- Spectral Decomposition Verification of Pauli X Matrix ----------
print("\n=== Spectral Decomposition of Pauli X Matrix (Tutorial 1.5) ===")
X = np.array([[0, 1], [1, 0]], dtype=complex)
eigvals_X, eigvecs_X = np.linalg.eigh(X)

## Spectral decomposition: X = Σ λᵢ |vᵢ⟩⟨vᵢ|
X_reconstructed = np.zeros((2, 2), dtype=complex)
for i in range(2):
    vec = eigvecs_X[:, [i]]
    proj = vec @ vec.conj().T
    X_reconstructed += eigvals_X[i] * proj

print(f"Original X matrix:\n{X}")
print(f"Spectral decomposition reconstruction of X:\n{X_reconstructed}")
print(f"Verification consistent? {np.allclose(X, X_reconstructed)}")

## ---------- Non-Pauli Example from the Tutorial ----------
print("\n=== Eigenvalues of H = [[3,1],[1,3]] from the Tutorial ===")
H = np.array([[3, 1], [1, 3]], dtype=complex)
eigvals_H, eigvecs_H = np.linalg.eigh(H)
print(f"H matrix:\n{H}")
print(f"Eigenvalues: {eigvals_H}")   # Expected: [2, 4]
print(f"Eigenvectors:\n{eigvecs_H}")

## ---------- Unitary Operator Eigenvalue Verification ----------
print("\n=== Verification that Unitary Operator Eigenvalues have Modulus 1 (end of Tutorial 1.5) ===")
## Phase gate P(θ) = diag(1, e^(iθ))
theta = np.pi/3
P = np.array([[1, 0], [0, np.exp(1j * theta)]], dtype=complex)
eigvals_P = np.linalg.eigvals(P)
print(f"P(π/3) = diag(1, e^(iπ/3))")
print(f"Eigenvalues: {eigvals_P}")
print(f"Eigenvalue moduli: {[abs(v) for v in eigvals_P]}")  # Expected: [1, 1]

1.6 Tensor Products and the CNOT Gate

Corresponding Tutorial: 1.6 Tensor Products and Multi-body Systems, CNOT Gate Matrix

Verification Goal: Kronecker product, two-qubit basis, CNOT gate matrix construction

## ============================================================
## Example 8: Tensor Products and Kronecker Products — Verifying Tutorial Section 1.6
## ============================================================

print("=== Two-Qubit Basis Vectors (Tutorial 1.6) ===")
ket0 = np.array([[1], [0]], dtype=complex)
ket1 = np.array([[0], [1]], dtype=complex)

## Tensor product construction |ij⟩ = |i⟩ ⊗ |j⟩
ket00 = np.kron(ket0, ket0)
ket01 = np.kron(ket0, ket1)
ket10 = np.kron(ket1, ket0)
ket11 = np.kron(ket1, ket1)

print(f"|00⟩ = \n{ket00}")
print(f"|01⟩ = \n{ket01}")
print(f"|10⟩ = \n{ket10}")
print(f"|11⟩ = \n{ket11}")

## ---------- Verify Z⊗X from the Tutorial ----------
print("\n=== Z ⊗ X Computation (Tutorial 1.6) ===")
Z = np.array([[1, 0], [0, -1]], dtype=complex)
X = np.array([[0, 1], [1, 0]], dtype=complex)
Z_kron_X = np.kron(Z, X)
print("Z ⊗ X =")
print(Z_kron_X)
print(f"Shape: {Z_kron_X.shape} (expected: 4×4)")

## Verify action on |0⟩⊗|+⟩
ket_plus = (ket0 + ket1) / np.sqrt(2)
state_in = np.kron(ket0, ket_plus)
state_out = Z_kron_X @ state_in
print(f"\n(Z⊗X) · |0+⟩ = \n{state_out}")
print(f"Verification: same as |0+⟩? {np.allclose(state_out, state_in)}")
print("(Because Z|0⟩=|0⟩, X|+⟩=|+⟩, so |0+⟩ is an eigenvector with eigenvalue +1)")

## ---------- CNOT Gate Matrix Construction (Tutorial Formula) ----------
print("\n=== CNOT Gate Matrix Construction (Tutorial 1.6) ===")
P0 = np.array([[1, 0], [0, 0]], dtype=complex)  # |0⟩⟨0|
P1 = np.array([[0, 0], [0, 1]], dtype=complex)  # |1⟩⟨1|
I2 = np.eye(2, dtype=complex)
CNOT_from_formula = np.kron(P0, I2) + np.kron(P1, X)
print("CNOT = P₀⊗I + P₁⊗X =")
print(CNOT_from_formula)

## Verify CNOT action on the computational basis
print("\n=== CNOT Acting on the Computational Basis ===")
for i, label in enumerate(["|00⟩", "|01⟩", "|10⟩", "|11⟩"]):
    basis_states = [ket00, ket01, ket10, ket11]
    result = CNOT_from_formula @ basis_states[i]
    print(f"CNOT·{label} = \n{result}")

## ---------- Bell State: Prove Non-decomposability ----------
print("\n=== Bell State Entanglement Verification (Tutorial 1.6) ===")
bell = (ket00 + ket11) / np.sqrt(2)
print(f"|Φ⁺⟩ = (|00⟩ + |11⟩)/√2 = \n{bell}")
## Attempt factorization check
## If |Φ⁺⟩ = (a|0⟩+b|1⟩) ⊗ (c|0⟩+d|1⟩) = ac|00⟩ + ad|01⟩ + bc|10⟩ + bd|11⟩
## then ad = 0 and bc = 0, but simultaneously ac = bd = 1/√2, contradiction
print("Cannot be written as |a⟩⊗|b⟩ (ad=0 contradicts ac=1/√2)")
print("✅ Confirmed |Φ⁺⟩ is an entangled state")

1.7 Probability Amplitudes and Interference

Corresponding Tutorial: 1.7.5 Classical Probability vs. Quantum Probability

Verification Goal: Interference terms arising from superposition of probability amplitudes

## ============================================================
## Example 9: Quantum Interference — Verifying Tutorial Section 1.7.5
## ============================================================

print("=== Quantum Interference: |ψ₁+ψ₂|² ≠ |ψ₁|² + |ψ₂|² ===")

## Define two complex probability amplitudes
psi1 = 0.6 + 0.0j
psi2 = 0.0 + 0.8j

## Classical probability: direct addition
P_classical = abs(psi1)**2 + abs(psi2)**2

## Quantum probability: add first, then square modulus
psi_total = psi1 + psi2
P_quantum = abs(psi_total)**2

print(f"ψ₁ = {psi1}")
print(f"ψ₂ = {psi2}")
print(f"Classical probability P_classical = |ψ₁|² + |ψ₂|² = {P_classical:.4f}")
print(f"Quantum probability P_quantum = |ψ₁+ψ₂|² = {P_quantum:.4f}")
print(f"Interference term = P_quantum - P_classical = {P_quantum - P_classical:.4f}")
print(f"P_classical ≠ P_quantum? {abs(P_classical - P_quantum) > 1e-10}")

## ---------- Demonstrate Constructive and Destructive Interference ----------
print("\n=== Constructive Interference vs. Destructive Interference ===")

## Constructive interference: same phase
a = 0.5 + 0.0j
b = 0.5 + 0.0j
constructive = abs(a + b)**2
separate = abs(a)**2 + abs(b)**2
print(f"Same phase: ψ₁={a}, ψ₂={b}")
print(f"  |ψ₁|²+|ψ₂|² = {separate:.4f}, |ψ₁+ψ₂|² = {constructive:.4f} (enhanced)")

## Destructive interference: opposite phase
c = 0.5 + 0.0j
d = -0.5 + 0.0j
destructive = abs(c + d)**2
print(f"Opposite phase: ψ₁={c}, ψ₂={d}")
print(f"  |ψ₁|²+|ψ₂|² = {abs(c)**2+abs(d)**2:.4f}, |ψ₁+ψ₂|² = {destructive:.4f} (cancelled)")

1.8 Discrete Fourier Transform

Corresponding Tutorial: 1.8 Fourier Analysis, DFT Matrix

Verification Goal: 2×2 and 4×4 DFT matrices, relationship with the Hadamard gate

## ============================================================
## Example 10: DFT Matrix — Verifying Tutorial Section 1.8.3
## ============================================================

print("=== 2×2 DFT Matrix (Tutorial 1.8) ===")
## N=2, ω₂ = e^(2πi/2) = -1
N2 = 2
omega2 = np.exp(2j * np.pi / N2)
F2 = np.array([[omega2**(j*k) for k in range(N2)] for j in range(N2)])
print(f"F₂ = \n{F2}")
print(f"Verification: F₂ = [[1,1],[1,-1]]? {np.allclose(F2, [[1,1],[1,-1]])}")

## After normalization, it is the Hadamard gate
H = F2 / np.sqrt(2)
print(f"\nF₂/√2 = Hadamard gate H = \n{H}")

## ---------- 4×4 DFT Matrix ----------
print("\n=== 4×4 DFT Matrix (Tutorial 1.8.3) ===")
N4 = 4
omega4 = np.exp(2j * np.pi / N4)
F4 = np.array([[omega4**(j*k) for k in range(N4)] for j in range(N4)])
print(f"F₄ =")
print(np.array2string(F4, precision=2, suppress_small=True))
print(f"\nExpected value (from tutorial):")
print("[[1,  1,    1,    1  ]")
print(" [1,  i,   -1,   -i ]")
print(" [1, -1,   1,   -1 ]")
print(" [1, -i,  -1,    i ]]")

## Verify orthogonality of column vectors
print(f"\nF₄ columns orthogonal? ", end="")
for i in range(N4):
    for j in range(i+1, N4):
        dot = F4[:, i].conj().T @ F4[:, j]
        if abs(dot) > 1e-10:
            print(f"Column {i} not orthogonal to column {j} (inner product={dot:.4f})")
            break
    else:
        continue
    break
else:
    print("Yes (all columns pairwise orthogonal)")

## Verify normalization to unitary
print(f"(F₄/2)†(F₄/2) = I? {np.allclose((F4/2).conj().T @ (F4/2), np.eye(N4))}")

Part 2: Physical Foundation Verification

Corresponding to Tutorial Sections 2.1 – 2.6

2.2 Quantum Postulates: State Initialization and Unitary Evolution

Corresponding Tutorial: 2.2 The Five Postulates

Verification Goal: State preparation (Postulate 1), unitary evolution (Postulate 2), measurement probabilities (Postulate 4)

## ============================================================
## Example 11: Quantum State Preparation and Unitary Evolution — Verifying Tutorial Section 2.2
## ============================================================

print("=== Postulate 1: State Space ===")
## Initial state |0⟩
psi0 = np.array([[1], [0]], dtype=complex)
print(f"Initial state |0⟩ = \n{psi0}")
print(f"⟨0|0⟩ = {(psi0.conj().T @ psi0)[0,0]:.0f}")  # Normalization

print("\n=== Postulate 2: Unitary Evolution ===")
## Hadamard gate
H = np.array([[1, 1], [1, -1]], dtype=complex) / np.sqrt(2)
psi1 = H @ psi0  # H|0⟩ = |+⟩
print(f"H|0⟩ = |+⟩ = \n{psi1}")
print(f"⟨ψ₁|ψ₁⟩ = {(psi1.conj().T @ psi1)[0,0]:.4f}")  # Preserves normalization

print("\n=== Postulate 4: Born Rule ===")
## Probability of measuring |+⟩ in the Z basis
ket0 = np.array([[1], [0]], dtype=complex)
ket1 = np.array([[0], [1]], dtype=complex)
P0 = abs((ket0.conj().T @ psi1)[0,0])**2
P1 = abs((ket1.conj().T @ psi1)[0,0])**2
print(f"Measuring Z basis on the |+⟩ state:")
print(f"  P(0) = |⟨0|+⟩|² = {P0:.4f}")   # Expected: 0.5
print(f"  P(1) = |⟨1|+⟩|² = {P1:.4f}")   # Expected: 0.5
print(f"  P(0) + P(1) = {P0+P1:.4f}")     # Expected: 1.0

print("\n=== Postulate 3: Observables (Expectation Values) ===")
Z = np.array([[1, 0], [0, -1]], dtype=complex)
exp_Z = (psi1.conj().T @ Z @ psi1)[0, 0]
print(f"⟨+|Z|+⟩ = {exp_Z:.4f} (expected: 0)")

2.3 Infinite Square Well Wavefunctions

Corresponding Tutorial: 2.3 Wavefunctions and the Schrödinger Equation, Infinite Square Well

Verification Goal: Normalization, orthogonality, and visualization of wavefunctions

## ============================================================
## Example 12: Infinite Square Well Wavefunctions — Verifying Tutorial Section 2.3
## ============================================================

import numpy as np

## Well parameters
L = 1.0      # Well width
N = 1000     # Number of sample points
x = np.linspace(0, L, N)
dx = L / N

## Wavefunction: ψₙ(x) = √(2/L) · sin(nπx/L)
def psi_n(n, x, L):
    return np.sqrt(2/L) * np.sin(n * np.pi * x / L)

print("=== Infinite Square Well Wavefunction Verification ===")
for n in [1, 2, 3]:
    psi = psi_n(n, x, L)
    # Numerical integration to verify normalization ∫|ψ|²dx = 1
    norm = np.sum(np.abs(psi)**2) * dx
    print(f"n={n}: ∫|ψₙ|² dx = {norm:.6f} (expected 1.0)")
    assert abs(norm - 1) < 0.01

## Verify orthogonality ∫ψₘ*·ψₙ dx = 0 (m ≠ n)
print("\n=== Orthogonality Verification ===")
for m, n in [(1, 2), (1, 3), (2, 3)]:
    psi_m = psi_n(m, x, L)
    psi_n_val = psi_n(n, x, L)
    overlap = np.sum(psi_m.conj() * psi_n_val) * dx
    print(f"∫ψₘ*·ψₙ dx (m={m}, n={n}) = {overlap:.6f} (expected 0)")

## Plot wavefunctions (requires matplotlib)
try:
    import matplotlib.pyplot as plt
    plt.figure(figsize=(8, 5))
    for n in [1, 2, 3, 4]:
        psi = psi_n(n, x, L)
        plt.plot(x, psi, label=f"n={n}")
    plt.xlabel("x")
    plt.ylabel("ψₙ(x)")
    plt.title("Infinite Square Well Wavefunctions ψₙ(x) = √(2/L)·sin(nπx/L)")
    plt.legend()
    plt.grid(alpha=0.3)
    plt.savefig("infinite_well_wavefunctions.png", dpi=150)
    print("\n📊 Wavefunction plot saved as infinite_well_wavefunctions.png")
except ImportError:
    print("\n(matplotlib not installed, skipping plot)")

2.4 Spin and Pauli Matrix Measurements

Corresponding Tutorial: 2.4 Two-Level Systems and Spin

Verification Goal: Expectation values of spin operators, eigenvalues ±1

## ============================================================
## Example 13: Spin Measurements and Expectation Values — Verifying Tutorial Section 2.4
## ============================================================

print("=== Expectation Values of Spin-1/2 Operators ===")

## Pauli matrices
sigma_x = np.array([[0, 1], [1, 0]], dtype=complex)
sigma_y = np.array([[0, -1j], [1j, 0]], dtype=complex)
sigma_z = np.array([[1, 0], [0, -1]], dtype=complex)

## Spin operators Sᵢ = (ℏ/2)·σᵢ, setting ℏ=1 here
hbar = 1
Sx = hbar/2 * sigma_x
Sy = hbar/2 * sigma_y
Sz = hbar/2 * sigma_z

## Several quantum states
ket0 = np.array([[1], [0]], dtype=complex)
ket1 = np.array([[0], [1]], dtype=complex)
ket_plus = (ket0 + ket1) / np.sqrt(2)
ket_minus = (ket0 - ket1) / np.sqrt(2)
ket_plus_i = (ket0 + 1j * ket1) / np.sqrt(2)

states = {
    "|0⟩": ket0,
    "|1⟩": ket1,
    "|+⟩": ket_plus,
    "|-⟩": ket_minus,
    "|+i⟩": ket_plus_i,
}

ops = {"Sx": Sx, "Sy": Sy, "Sz": Sz}

print(f"{'State':8s} {'⟨Sx⟩':10s} {'⟨Sy⟩':10s} {'⟨Sz⟩':10s}")
print("-" * 40)
for name, state in states.items():
    exps = []
    for op_name, op in ops.items():
        exp = (state.conj().T @ op @ state)[0, 0].real
        exps.append(f"{exp:8.3f}")
    print(f"{name:8s} {exps[0]:10s} {exps[1]:10s} {exps[2]:10s}")

## Verify Stern-Gerlach: spin in any direction only takes values ±ℏ/2
print("\n=== Stern-Gerlach: Eigenvalue Verification ===")
for name, op in [("Sx", Sx), ("Sy", Sy), ("Sz", Sz)]:
    eigvals = np.linalg.eigvalsh(op)  # eigh returns sorted real eigenvalues
    print(f"{name} eigenvalues: {eigvals} (should be ±{hbar/2})")

2.5 Bloch Sphere Coordinates

Corresponding Tutorial: 2.5 Bloch Sphere

Verification Goal: Parameterization (θ, φ) → (x,y,z) coordinates, Bloch vector

## ============================================================
## Example 14: Bloch Sphere Coordinates — Verifying Tutorial Section 2.5
## ============================================================

print("=== Bloch Sphere Coordinate Computation (Tutorial 2.5) ===")

## Arbitrary pure state parameterization: |ψ⟩ = cos(θ/2)|0⟩ + e^(iφ)sin(θ/2)|1⟩
## Bloch vector: (x,y,z) = (sinθ cosφ, sinθ sinφ, cosθ)

def bloch_coords(theta, phi):
    """Compute Bloch sphere coordinates from (θ, φ)"""
    x = np.sin(theta) * np.cos(phi)
    y = np.sin(theta) * np.sin(phi)
    z = np.cos(theta)
    # Verify on the unit sphere
    r = np.sqrt(x**2 + y**2 + z**2)
    return x, y, z, r

def state_vector(theta, phi):
    """Construct quantum state vector from (θ, φ)"""
    return np.array([[np.cos(theta/2)],
                     [np.exp(1j * phi) * np.sin(theta/2)]], dtype=complex)

## ---------- Verify Tutorial Table: Positions of Standard States on the Sphere ----------
test_cases = [
    ("|0⟩",    0,       0),
    ("|1⟩",    np.pi,   0),
    ("|+⟩",    np.pi/2, 0),
    ("|-⟩",    np.pi/2, np.pi),
    ("|+i⟩",   np.pi/2, np.pi/2),
    ("|-i⟩",   np.pi/2, 3*np.pi/2),
]

print(f"{'State':8s} {'θ':8s} {'φ':8s} {'x':8s} {'y':8s} {'z':8s} {'On Sphere?':10s}")
print("-" * 60)
for name, theta, phi in test_cases:
    x, y, z, r = bloch_coords(theta, phi)
    print(f"{name:8s} {theta:8.2f} {phi:8.2f} {x:+8.3f} {y:+8.3f} {z:+8.3f} {r==1}")

## ---------- Verify Bloch Vector = (⟨X⟩, ⟨Y⟩, ⟨Z⟩) ----------
print("\n=== Bloch Vector = (⟨X⟩, ⟨Y⟩, ⟨Z⟩) Verification (Tutorial 2.5) ===")
X = np.array([[0, 1], [1, 0]], dtype=complex)
Y = np.array([[0, -1j], [1j, 0]], dtype=complex)
Z = np.array([[1, 0], [0, -1]], dtype=complex)

theta, phi = np.pi/3, np.pi/4  # Choose an arbitrary state
psi = state_vector(theta, phi)

x_exp = (psi.conj().T @ X @ psi)[0, 0].real
y_exp = (psi.conj().T @ Y @ psi)[0, 0].real
z_exp = (psi.conj().T @ Z @ psi)[0, 0].real
x_geo, y_geo, z_geo, _ = bloch_coords(theta, phi)

print(f"State: θ={theta:.4f}, φ={phi:.4f}")
print(f"Bloch vector (geometric):  ({x_geo:.4f}, {y_geo:.4f}, {z_geo:.4f})")
print(f"Bloch vector (expectation): ({x_exp:.4f}, {y_exp:.4f}, {z_exp:.4f})")
print(f"Consistent? {np.allclose([x_geo, y_geo, z_geo], [x_exp, y_exp, z_exp])}")

2.6 Density Matrices and Purity

Corresponding Tutorial: 2.6 Measurement Theory and Density Matrices

Verification Goal: Pure vs. mixed state density matrices, purity, reduced density matrices

## ============================================================
## Example 15: Density Matrices and Purity — Verifying Tutorial Section 2.6
## ============================================================

print("=== Pure State Density Matrix ===")
## Pure state |+⟩
ket_plus = np.array([[1], [1]], dtype=complex) / np.sqrt(2)
rho_pure = ket_plus @ ket_plus.conj().T
print(f"ρ_pure = |+⟩⟨+| = \n{rho_pure}")
print(f"Tr(ρ) = {np.trace(rho_pure):.4f}")      # Expected: 1
print(f"Tr(ρ²) = {np.trace(rho_pure @ rho_pure):.4f}")  # Pure state: 1

print("\n=== Mixed State Density Matrix ===")
## 50% |0⟩ + 50% |1⟩ (classical mixture)
ket0 = np.array([[1], [0]], dtype=complex)
ket1 = np.array([[0], [1]], dtype=complex)
rho_mixed = 0.5 * (ket0 @ ket0.conj().T) + 0.5 * (ket1 @ ket1.conj().T)
print(f"ρ_mixed = 0.5|0⟩⟨0| + 0.5|1⟩⟨1| = \n{rho_mixed}")
print(f"Tr(ρ) = {np.trace(rho_mixed):.4f}")      # Expected: 1
print(f"Tr(ρ²) = {np.trace(rho_mixed @ rho_mixed):.4f}")  # Mixed state: < 1

## ---------- Key Test: ⟨X⟩ ----------
print("\n=== Key Test: ⟨X⟩ (Tutorial 2.6) ===")
X = np.array([[0, 1], [1, 0]], dtype=complex)
exp_X_pure = np.trace(rho_pure @ X)
exp_X_mixed = np.trace(rho_mixed @ X)
print(f"Pure state ⟨X⟩ = Tr(ρ_pure·X) = {exp_X_pure:.4f}")   # Expected: 1
print(f"Mixed state ⟨X⟩ = Tr(ρ_mixed·X) = {exp_X_mixed:.4f}")  # Expected: 0

## The two states are statistically identical under Z measurement, but completely different under X measurement!
Z = np.array([[1, 0], [0, -1]], dtype=complex)
print(f"\nTwo states measured in the Z basis:")
print(f"  Pure state P(0) = {rho_pure[0,0]:.2f}, P(1) = {rho_pure[1,1]:.2f}")
print(f"  Mixed state P(0) = {rho_mixed[0,0]:.2f}, P(1) = {rho_mixed[1,1]:.2f}")

## ---------- Reduced Density Matrix: Bell State ----------
print("\n=== Reduced Density Matrix of the Bell State (Tutorial 2.6) ===")
ket00 = np.kron(ket0, ket0)
ket11 = np.kron(ket1, ket1)
bell = (ket00 + ket11) / np.sqrt(2)   # |Φ⁺⟩
rho_bell = bell @ bell.conj().T       # Overall density matrix (pure state)

print(f"Overall Tr(ρ²) = {np.trace(rho_bell @ rho_bell):.4f} (pure state = 1)")

## Partial trace over the second qubit
## ρ_A = Tr_B(ρ_AB) = Σ_j ⟨j_B|ρ_AB|j_B⟩
rho_A = np.zeros((2, 2), dtype=complex)
basis_B = [ket0, ket1]
for j, b in enumerate(basis_B):
    # ⟨j|ρ_AB|j⟩ (on the B part)
    # rho_bell is a 4×4 matrix; we need to contract over the B subspace
    proj = np.kron(np.eye(2), b @ b.conj().T)
    rho_A += proj @ rho_bell @ proj.conj().T

## Cleaner approach: direct numerical trace
rho_A_simple = np.zeros((2, 2), dtype=complex)
for j, b in enumerate(basis_B):
    # Construct ⟨j| acting on the B part
    inner = np.kron(np.eye(2), b.conj().T) @ rho_bell @ np.kron(np.eye(2), b)
    rho_A_simple += inner

print(f"\nReduced density matrix ρ_A = Tr_B(|Φ⁺⟩⟨Φ⁺|) = \n{rho_A_simple}")
print(f"Tr(ρ_A²) of ρ_A = {np.trace(rho_A_simple @ rho_A_simple):.4f} (mixed state < 1)")
print("✅ The subsystem of an entangled pure state is a mixed state!")

Part 3: Quantum Computing Examples

Corresponding to Tutorial Sections 3.1 – 3.6

The following examples require Qiskit. If not installed, run pip install qiskit qiskit-aer

3.1–3.2 Single-Qubit Gate Simulation (Qiskit)

Corresponding Tutorial: 3.1 Qubits, 3.2 Single-Qubit Gates

Verification Goal: Qiskit simulation of X, Z, H, S, T gates acting on |0⟩

## ============================================================
## Example 16: Single-Qubit Gate Simulation — Verifying Tutorial Section 3.2
## ============================================================

if HAS_QISKIT:
    from qiskit import QuantumCircuit, transpile
    from qiskit_aer import AerSimulator
    import numpy as np

    print("=== Single-Qubit Gate Simulation ===")

    # Helper function: run circuit and get statevector
    def run_and_get_statevec(qc):
        """Compile and simulate the circuit, returning the statevector"""
        simulator = AerSimulator()
        qc.save_statevector()
        compiled = transpile(qc, simulator)
        result = simulator.run(compiled).result()
        return result.get_statevector()

    # Test various gates acting on |0⟩
    for gate_name, gate_cmd in [("I (Identity)", 'id'), ("X (NOT)", 'x'),
                                 ("Z (Phase Flip)", 'z'), ("H (Hadamard)", 'h'),
                                 ("S (Phase π/2)", 's'), ("T (π/8 Gate)", 't')]:
        qc = QuantumCircuit(1)
        eval(f"qc.{gate_cmd}(0)")  # Apply gate on qubit 0
        sv = run_and_get_statevec(qc)
        print(f"  {gate_name:14s}: {sv}")

    # Verify self-inverse property: H² = I
    print("\n=== Self-Inverse Verification ===")
    qc = QuantumCircuit(1)
    qc.h(0)
    qc.h(0)  # Two H gates
    sv = run_and_get_statevec(qc)
    print(f"H·H|0⟩ = {sv} (should be |0⟩ = [1+0j, 0+0j])")
    assert np.allclose(sv, [1, 0]), "H² verification failed!"
    print("✅ H² = I verification passed!")

    # Verify HXH = Z
    print("\n=== HXH = Z Verification ===")
    qc = QuantumCircuit(1)
    qc.h(0)
    qc.x(0)
    qc.h(0)
    sv = run_and_get_statevec(qc)
    # HXH|0⟩ = Z|0⟩ = |0⟩
    print(f"HXH|0⟩ = {sv}")

    qc2 = QuantumCircuit(1)
    qc2.z(0)
    sv2 = run_and_get_statevec(qc2)
    print(f"Z|0⟩   = {sv2}")
    print(f"Consistent? {np.allclose(sv, sv2)}")
else:
    print("⚠️  Qiskit required. Using pure NumPy approximation:")
    H = np.array([[1, 1], [1, -1]], dtype=complex) / np.sqrt(2)
    X = np.array([[0, 1], [1, 0]], dtype=complex)
    Z = np.array([[1, 0], [0, -1]], dtype=complex)
    ket0 = np.array([[1], [0]], dtype=complex)
    print(f"H·H|0⟩ = {H @ H @ ket0}")
    print(f"HXH|0⟩ = {H @ X @ H @ ket0}")
    print(f"Z|0⟩   = {Z @ ket0}")

3.3 Bell State Preparation and Entanglement Verification (Qiskit)

Corresponding Tutorial: 3.3 Multi-Qubit Gates & Entanglement

Verification Goal: Bell state preparation circuit, CNOT gate, entanglement verification

## ============================================================
## Example 17: Bell State Preparation and Entanglement Verification — Verifying Tutorial Section 3.3
## ============================================================

if HAS_QISKIT:
    from qiskit import QuantumCircuit, transpile
    from qiskit_aer import AerSimulator

    print("=== Bell State |Φ⁺⟩ Preparation (Tutorial 3.3) ===")
    qc = QuantumCircuit(2)
    qc.h(0)       # H gate
    qc.cx(0, 1)   # CNOT gate
    qc.save_statevector()

    simulator = AerSimulator()
    compiled = transpile(qc, simulator)
    result = simulator.run(compiled).result()
    sv = result.get_statevector()

    print(f"Prepared state: {sv}")
    print(f"|Φ⁺⟩ = (|00⟩ + |11⟩)/√2 amplitudes: {sv[0]:.4f}, {sv[-1]:.4f}")
    print(f"Other components: {sv[1]:.4f}, {sv[2]:.4f} (should be 0)")

    # Verify entanglement: subsystem is completely random in Z basis
    print("\n=== Entanglement Verification: Measurement Statistics ===")
    qc2 = QuantumCircuit(2, 2)
    qc2.h(0)
    qc2.cx(0, 1)
    qc2.measure(0, 0)
    qc2.measure(1, 1)

    compiled2 = transpile(qc2, simulator)
    result2 = simulator.run(compiled2, shots=4096).result()
    counts = result2.get_counts()
    print(f"Measurement result statistics (4096 shots):")
    for outcome, count in sorted(counts.items()):
        print(f"  |{outcome}⟩: {count:5d} shots ({100*count/4096:.1f}%)")

    # Verify: only |00⟩ and |11⟩
    assert '01' not in counts or counts['01'] < 10, "Entanglement preparation failed!"
    assert '10' not in counts or counts['10'] < 10, "Entanglement preparation failed!"
    print("✅ Entanglement verification passed: only |00⟩ and |11⟩ observed")

    # ---------- Demonstrate the 4 Bell States ----------
    print("\n=== Four Bell States (Tutorial 3.3) ===")
    bell_circuits = {
        "|Φ⁺⟩": lambda qc: (qc.h(0), qc.cx(0, 1)),
        "|Φ⁻⟩": lambda qc: (qc.h(0), qc.z(0), qc.cx(0, 1)),
        "|Ψ⁺⟩": lambda qc: (qc.h(0), qc.x(1), qc.cx(0, 1)),
        "|Ψ⁻⟩": lambda qc: (qc.x(0), qc.h(0), qc.cx(0, 1)),
    }
    for name, circuit_fn in bell_circuits.items():
        qc = QuantumCircuit(2)
        circuit_fn(qc)
        qc.save_statevector()
        compiled = transpile(qc, simulator)
        sv = simulator.run(compiled).result().get_statevector()
        print(f"  {name}: {sv}")

else:
    print("⚠️  Qiskit required to run this example.")

3.4 GHZ State Preparation Circuit (Qiskit)

Corresponding Tutorial: 3.4 Quantum Circuits, GHZ State Preparation

Verification Goal: Multi-qubit entanglement, circuit depth concept

## ============================================================
## Example 18: GHZ State Preparation Circuit — Verifying Tutorial Section 3.4
## ============================================================

if HAS_QISKIT:
    from qiskit import QuantumCircuit, transpile
    from qiskit_aer import AerSimulator

    print("=== GHZ State Preparation (Tutorial 3.4) ===")
    n = 4  # 4 qubits
    qc = QuantumCircuit(n)
    qc.h(0)
    for i in range(n-1):
        qc.cx(i, i+1)  # Cascaded CNOTs
    qc.save_statevector()

    simulator = AerSimulator()
    compiled = transpile(qc, simulator)
    result = simulator.run(compiled).result()
    sv = result.get_statevector()

    print(f"GHZ state amplitudes (only |0000⟩ and |1111⟩ non-zero):")
    for i, amp in enumerate(sv):
        if abs(amp) > 1e-10:
            state_label = format(i, f'0{n}b')
            print(f"  |{state_label}⟩: {amp:.4f}")

    # Measurement verification
    print(f"\n=== GHZ Measurement (4096 shots) ===")
    qc2 = QuantumCircuit(n, n)
    qc2.h(0)
    for i in range(n-1):
        qc2.cx(i, i+1)
    qc2.measure_all()

    compiled2 = transpile(qc2, simulator)
    result2 = simulator.run(compiled2, shots=4096).result()
    counts = result2.get_counts()
    for outcome, count in sorted(counts.items()):
        if count > 10:
            print(f"  |{outcome}⟩: {count:5d} shots ({100*count/4096:.1f}%)")

else:
    print("⚠️  Qiskit required to run this example.")

3.5 Quantum Measurement and Expectation Values

Corresponding Tutorial: 3.5 Quantum Measurement & Readout

Verification Goal: Measurement in different bases, expectation value estimation

## ============================================================
## Example 19: Measurement in Different Bases — Verifying Tutorial Section 3.5
## ============================================================

if HAS_QISKIT:
    from qiskit import QuantumCircuit, transpile
    from qiskit_aer import AerSimulator

    print("=== Measuring |+⟩ in the Z Basis and X Basis ===")
    simulator = AerSimulator()

    # Z basis measurement (direct measurement)
    qc_z = QuantumCircuit(1, 1)
    qc_z.h(0)
    qc_z.measure(0, 0)
    compiled_z = transpile(qc_z, simulator)
    result_z = simulator.run(compiled_z, shots=4096).result()
    counts_z = result_z.get_counts()
    print(f"Z basis measurement: {counts_z}")

    # X basis measurement (H first, then measure in Z)
    qc_x = QuantumCircuit(1, 1)
    qc_x.h(0)
    qc_x.h(0)  # Second H rotates X basis to Z basis
    qc_x.measure(0, 0)
    compiled_x = transpile(qc_x, simulator)
    result_x = simulator.run(compiled_x, shots=4096).result()
    counts_x = result_x.get_counts()
    print(f"X basis measurement: {counts_x}")

    # Note: |+⟩ measured in the X basis is deterministic (always +1)

    print("\n=== Expectation Value Estimation (Tutorial 3.5) ===")
    # Prepare |+⟩ and measure Z, estimate ⟨Z⟩
    counts = result_z.get_counts()
    N = 4096
    n0 = counts.get('0', 0)
    n1 = counts.get('1', 0)
    exp_Z_est = (n0 - n1) / N
    exp_Z_exact = 0.0  # ⟨+|Z|+⟩ = 0
    print(f"⟨Z⟩ estimate: {exp_Z_est:.4f} (exact value: {exp_Z_exact})")
    print(f"Estimation error: {abs(exp_Z_est - exp_Z_exact):.4f} (∼ 1/√N ≈ {1/np.sqrt(N):.4f})")

else:
    print("⚠️  Qiskit required to run this example.")

3.6 Quantum Teleportation Simulation (Qiskit)

Corresponding Tutorial: 3.6 Quantum Algorithm Primer — Quantum Teleportation

Verification Goal: Complete teleportation circuit, entanglement + classical communication to transmit a quantum state

## ============================================================
## Example 20: Quantum Teleportation — Verifying Tutorial Section 3.6
## ============================================================

if HAS_QISKIT:
    from qiskit import QuantumCircuit, transpile
    from qiskit_aer import AerSimulator

    print("=== Quantum Teleportation Simulation ===")

    # ---- Step 1: Alice prepares the unknown state to transmit ----
    # Here we use a known state for verification: |ψ⟩ = cos(θ/2)|0⟩ + e^(iφ)sin(θ/2)|1⟩
    # Choose θ = π/3, φ = π/4 (arbitrary state)
    theta, phi = np.pi/3, np.pi/4

    qc = QuantumCircuit(3, 3)  # q0=Alice's state, q1=Alice's Bell pair, q2=Bob's Bell pair

    # Alice prepares the state |ψ⟩ to transmit
    qc.ry(theta, 0)      # Rotate about y-axis by θ
    qc.rz(phi, 0)        # Rotate about z-axis by φ

    # ---- Step 2: Shared entangled pair |Φ⁺⟩ ----
    qc.h(1)
    qc.cx(1, 2)          # Create Bell state between q1 and q2

    # ---- Step 3: Alice's operations ----
    qc.barrier()
    qc.cx(0, 1)          # CNOT: q0(control), q1(target)
    qc.h(0)              # Hadamard gate

    # ---- Step 4: Alice measures and sends classical bits ----
    qc.measure(0, 0)
    qc.measure(1, 1)

    # ---- Step 5: Bob corrects based on classical result ----
    qc.barrier()
    qc.cx(1, 2)          # If q1=1 → X gate
    qc.cz(0, 2)          # If q0=1 → Z gate

    # ---- Verification: is Bob's state equal to the original? ----
    # By contrast: apply the inverse operation to Bob's state; if teleportation succeeded, we should get |0⟩
    qc.ry(-theta, 2)
    qc.rz(-phi, 2)
    qc.measure(2, 2)     # If result is 0, teleportation succeeded

    simulator = AerSimulator()
    compiled = transpile(qc, simulator)
    result = simulator.run(compiled, shots=4096).result()
    counts = result.get_counts()

    # Tally success / failure
    success = sum(count for outcome, count in counts.items() if outcome[-1] == '0')
    fail = 4096 - success
    print(f"Teleportation {'succeeded' if success > 4000 else 'failed'}:")
    print(f"  ✅ q2 returned to |0⟩: {success} shots ({100*success/4096:.1f}%)")
    print(f"  ❌ did not return to |0⟩: {fail} shots ({100*fail/4096:.1f}%)")
    print(f"  Tolerance threshold: 95% (noise and non-ideal gates reduce fidelity)")
    if success / 4096 > 0.95:
        print("\n✅ Quantum teleportation simulation verification passed!")
    else:
        print("\n⚠️  Teleportation fidelity insufficient; please check the circuit.")

else:
    print("⚠️  Qiskit required to run this example.")

3.6 Grover’s Search Algorithm Simulation (Qiskit)

Corresponding Tutorial: 3.6 Grover’s Search Algorithm

Verification Goal: Amplitude amplification, quadratic speedup concept

## ============================================================
## Example 21: Grover's Search Algorithm — Verifying Tutorial Section 3.6
## ============================================================

if HAS_QISKIT:
    from qiskit import QuantumCircuit, transpile
    from qiskit_aer import AerSimulator

    print("=== Grover's Search Algorithm (2 qubits, searching for |11⟩) ===")

    # ---- Setup ----
    n = 2            # 2 qubits
    target = "11"    # Target state
    oracle = QuantumCircuit(n)

    # ---- Oracle: Mark |11⟩ ----
    # Flip the phase of |11⟩: apply CZ gate
    oracle.cz(0, 1)

    # ---- Diffusion Operator (Amplitude Amplification) ----
    def diffusion(n):
        qc = QuantumCircuit(n)
        qc.h(range(n))
        qc.x(range(n))
        qc.h(n-1)
        qc.mcx(list(range(n-1)), n-1)  # Multi-controlled Z
        qc.h(n-1)
        qc.x(range(n))
        qc.h(range(n))
        return qc

    # ---- Complete Grover Circuit ----
    qc = QuantumCircuit(n, n)

    # 1. Prepare uniform superposition
    qc.h(range(n))

    # 2. One Grover iteration (for 2 qubits, one is sufficient)
    qc.append(oracle, range(n))
    qc.append(diffusion(n), range(n))

    # 3. Measure
    qc.measure(range(n), range(n))

    # ---- Simulate ----
    simulator = AerSimulator()
    compiled = transpile(qc, simulator)
    result = simulator.run(compiled, shots=4096).result()
    counts = result.get_counts()

    print(f"Measurement results:")
    for outcome, count in sorted(counts.items()):
        print(f"  |{outcome}⟩: {count:5d} shots ({100*count/4096:.1f}%)")

    target_count = counts.get(target, 0)
    print(f"\nTarget state |{target}⟩ probability: {100*target_count/4096:.1f}%")
    print(f"Classical search random probability: 25% (1 target among 2 qubits)")
    print(f"Grover search probability: {100*target_count/4096:.1f}%")
    if target_count / 4096 > 0.80:
        print("✅ Grover amplitude amplification verification passed!")
    else:
        print("⚠️  Probability low; consider increasing the number of iterations.")

else:
    print("⚠️  Qiskit required to run this example.")

3.6 Quantum Fourier Transform (Qiskit)

Corresponding Tutorial: 1.8 Fourier Analysis + 3.6 QFT

Verification Goal: Relationship between QFT and the DFT matrix

## ============================================================
## Example 22: Quantum Fourier Transform — Verifying Sections 1.8 and 3.6
## ============================================================

if HAS_QISKIT:
    from qiskit import QuantumCircuit, transpile
    from qiskit_aer import AerSimulator
    import numpy as np

    print("=== Quantum Fourier Transform QFT (3 qubits) ===")

    def qft_rotations(qc, n):
        """QFT subcircuit: controlled rotations"""
        for qubit in range(n):
            qc.h(qubit)
            for other in range(qubit+1, n):
                angle = np.pi / (2**(other - qubit))
                qc.cp(angle, other, qubit)
        # Swap qubits to correct ordering
        for i in range(n // 2):
            qc.swap(i, n-1-i)
        return qc

    # ---- Compute the action of QFT on |001⟩ ----
    n = 3
    qc = QuantumCircuit(n)
    qc.x(0)  # Prepare |001⟩ (least significant bit)
    qft_rotations(qc, n)
    qc.save_statevector()

    simulator = AerSimulator()
    compiled = transpile(qc, simulator)
    result = simulator.run(compiled).result()
    sv = result.get_statevector()

    print(f"Statevector of QFT|001⟩:")
    for i, amp in enumerate(sv):
        if abs(amp) > 1e-10:
            state_label = format(i, f'0{n}b')
            print(f"  |{state_label}⟩: {amp:.4f}")

    # ---- NumPy Verification: Direct DFT ----
    N = 2**n
    omega = np.exp(2j * np.pi / N)
    # QFT matrix: (F_N)ⱼₖ = ω^(j·k) / √N
    QFT_matrix = np.array([[omega**(j*k) for k in range(N)]
                            for j in range(N)], dtype=complex) / np.sqrt(N)

    input_vec = np.zeros(N, dtype=complex)
    input_vec[1] = 1  # |001⟩ (index 1)
    expected = QFT_matrix @ input_vec

    print(f"\nNumPy DFT Verification:")
    for i, amp in enumerate(expected):
        if abs(amp) > 1e-10:
            state_label = format(i, f'0{n}b')
            print(f"  |{state_label}⟩: {amp:.4f}")

    # Compare Qiskit and NumPy results
    qiskit_result = np.array([sv[i] for i in range(N)])
    match = np.allclose(qiskit_result, expected, atol=1e-10)
    print(f"\nQiskit QFT consistent with NumPy DFT? {match}")
    if match:
        print("✅ QFT verification passed!")
else:
    print("⚠️  Qiskit required to run this example.")

Appendix: Comprehensive Exercises

The following comprehensive exercises combine multiple concepts to verify key derived conclusions from the tutorial.

Comprehensive 1: Demonstration of the No-Cloning Theorem

Corresponding Tutorial: 3.3 No-Cloning Theorem

Verification Approach: Attempt to construct a “cloning” circuit and observe that it cannot work for arbitrary states

## ============================================================
## Comprehensive Exercise 1: No-Cloning Theorem — Verifying Tutorial Section 3.3
## ============================================================

print("=== No-Cloning Theorem Demonstration ===")
print("Suppose there exists a 'quantum cloning machine' that works for both |0⟩ and |1⟩...")

## Attempt to construct a unitary operator U such that:
## U|00⟩ = |00⟩ (clone |0⟩)
## U|10⟩ = |11⟩ (clone |1⟩)
## What happens to U acting on the superposition (|0⟩+|1⟩)/√2?

ket0 = np.array([[1], [0]], dtype=complex)
ket1 = np.array([[0], [1]], dtype=complex)
ket00 = np.kron(ket0, ket0)
ket10 = np.kron(ket1, ket0)

## Define the matrix form of this "cloning machine"
## Requirements: U|00⟩ = |00⟩, U|10⟩ = |11⟩
## In the basis {|00⟩,|01⟩,|10⟩,|11⟩}
U = np.zeros((4, 4), dtype=complex)
U[:, 0] = ket00.flatten()     # U|00⟩ = |00⟩
U[:, 2] = np.kron(ket1, ket1).flatten()  # U|10⟩ = |11⟩
## Fill in the mappings for |01⟩ and |11⟩ to preserve unitarity
U[:, 1] = np.kron(ket0, ket1).flatten()  # U|01⟩ = |01⟩
U[:, 3] = np.kron(ket1, ket0).flatten()  # U|11⟩ = |10⟩

## Verify unitarity
is_unitary = np.allclose(U.conj().T @ U, np.eye(4))
print(f"U is unitary? {is_unitary}")

## Observe action on superposition state
psi = (ket0 + ket1) / np.sqrt(2)  # |+⟩
input_state = np.kron(psi, ket0)   # |+⟩⊗|0⟩
output_state = U @ input_state

print(f"\nInput: |+⟩⊗|0⟩ = \n{input_state}")
print(f"Output: U(|+⟩⊗|0⟩) = \n{output_state}")

## True cloning should yield: |+⟩⊗|+⟩
true_clone = np.kron(psi, psi)
print(f"True clone: |+⟩⊗|+⟩ = \n{true_clone}")
print(f"\nAre they equal? {np.allclose(output_state, true_clone)}")
print("❌ Not equal! A universal cloning machine does not exist — the no-cloning theorem holds!")

Comprehensive 2: Qubit vs. Classical Bit — Measurement Comparison

Corresponding Tutorial: 3.1 Classical vs. Qubit

Verification Goal: Quantum superposition states lie on the equator of the Bloch sphere; classical mixtures lie on the Z-axis

## ============================================================
## Comprehensive Exercise 2: Qubit vs. Classical Bit — Verifying Section 3.1
## ============================================================

print("=== Qubit vs. Classical Bit ===")

## Prepare three states that are statistically identical under Z measurement
## but completely different under X measurement

## State 1: |+⟩ (quantum superposition state)
ket_plus = np.array([[1], [1]], dtype=complex) / np.sqrt(2)

## State 2: Classical mixture 50%|0⟩+50%|1⟩
rho_classical = np.array([[0.5, 0], [0, 0.5]], dtype=complex)

## State 3: Another superposition state |+i⟩
ket_plus_i = np.array([[1], [1j]], dtype=complex) / np.sqrt(2)
rho_plus_i = ket_plus_i @ ket_plus_i.conj().T

X = np.array([[0, 1], [1, 0]], dtype=complex)
Z = np.array([[1, 0], [0, -1]], dtype=complex)

print(f"{'State':20s} {'P(Z=0)':10s} {'P(Z=1)':10s} {'⟨X⟩':10s} {'⟨Z⟩':10s}")
print("-" * 60)

## |+⟩
p0_plus = abs(ket_plus[0])**2
p1_plus = abs(ket_plus[1])**2
expX_plus = (ket_plus.conj().T @ X @ ket_plus)[0,0].real
expZ_plus = (ket_plus.conj().T @ Z @ ket_plus)[0,0].real
print(f"{'|+⟩ (quantum superpos.)':20s} {p0_plus:10.2f} {p1_plus:10.2f} {expX_plus:10.2f} {expZ_plus:10.2f}")

## Classical mixture
p0_class = rho_classical[0,0].real
p1_class = rho_classical[1,1].real
expX_class = np.trace(rho_classical @ X).real
expZ_class = np.trace(rho_classical @ Z).real
print(f"{'Classical mix (50/50)':20s} {p0_class:10.2f} {p1_class:10.2f} {expX_class:10.2f} {expZ_class:10.2f}")

## |+i⟩
p0_plus_i = abs(ket_plus_i[0])**2
p1_plus_i = abs(ket_plus_i[1])**2
expX_plus_i = np.trace(rho_plus_i @ X).real
expZ_plus_i = np.trace(rho_plus_i @ Z).real
print(f"{'|+i⟩ (quantum superpos.)':20s} {p0_plus_i:10.2f} {p1_plus_i:10.2f} {expX_plus_i:10.2f} {expZ_plus_i:10.2f}")

print("\n✅ Conclusion: Z measurement cannot distinguish the three states, but X measurement can!")
print("   This is the essential difference between qubits and classical bits: phase information.")

Summary Reference Table

Example #	Content	Corresponding Tutorial	Technology
1	Complex arithmetic and division	1.1.2	Python `complex`
2	Euler’s formula e^(iθ) = cosθ + i sinθ	1.1.4	`numpy.exp`
3	Rotation and scaling of complex numbers	1.1.5	`numpy.angle`
4	Bra-ket notation and inner products	1.2.3	`numpy` matrix operations
5	Pauli matrix property verification	1.3.4–1.3.5	`numpy.linalg`
6	Projection operators and probability	1.4	outer product `ket @ bra`
7	Eigenvalues / spectral decomposition	1.5	`numpy.linalg.eigh`
8	Tensor products and CNOT construction	1.6	`numpy.kron`
9	Quantum interference	1.7.5	complex modulus squared
10	DFT matrix	1.8.3	roots of unity `exp(2πi/N)`
11	Quantum postulate verification	2.2	matrix simulation
12	Infinite square well wavefunctions	2.3	numerical integration
13	Spin expectation values	2.4	Pauli matrices
14	Bloch sphere coordinates	2.5	parameterization verification
15	Density matrices and purity	2.6	`Tr(ρ)`, `Tr(ρ²)`
16	Single-qubit gates	3.2	Qiskit
17	Bell state preparation	3.3	Qiskit
18	GHZ state preparation	3.4	Qiskit
19	Multi-basis measurement and expectation values	3.5	Qiskit
20	Quantum teleportation	3.6	Qiskit
21	Grover’s search	3.6	Qiskit
22	Quantum Fourier Transform	1.8+3.6	Qiskit+NumPy
C1	No-cloning theorem	3.3	NumPy unitary matrices
C2	Classical vs. quantum bit	3.1	density matrix comparison

File Info

Companion Tutorial: Quantum Computing Primer — From First Principles

Total code examples: 24 (22 main examples + 2 comprehensive exercises)

Last updated: 2026-05-28

Chapter 3: Introduction to Quantum Computing

Chapter 3: Foundations of Quantum Computing

3.1 Qubits

Definition of a Qubit

Bloch Sphere Representation

Classical Bits vs. Qubits

Physical Implementations of Qubits

Multiple Qubits

3.2 Single-Qubit Gates

Quantum Gates = Unitary Operators

Pauli Gates

Hadamard Gate

Phase Gates

Universal Gate Sets

Rotations on the Bloch Sphere

3.3 Multi-Qubit Gates & Entanglement

Tensor Product Review

CNOT Gate

Bell States: Maximally Entangled States

Measuring Entanglement

No-Cloning Theorem

3.4 Quantum Circuits

Circuit Conventions

Example Circuit 1: Bell State Preparation

Example Circuit 2: Quantum Teleportation

Example Circuit 3: GHZ State Preparation

Circuit Depth and Width

Measurement Symbols

3.5 Quantum Measurement & Readout

Review of Computational Basis Measurement

Measurement in the XXX Basis

Expectation Values

Statistical Interpretation and Measurement Precision

Physical Meaning of Measurement and Collapse

3.6 Quantum Algorithm Primer

Quantum Teleportation

BB84 Quantum Key Distribution

Deutsch-Jozsa Algorithm

Grover’s Search Algorithm

Shor’s Algorithm

3.7 Quantum Advantage Demonstrations

Chapter 3 Summary

Appendix

Part 3: Foundations of Quantum Computing — Feynman Technique Exercises

Table of Contents

3.1 Qubits

Exercise 3.1.1 ⭐ Three-State Normalization

Exercise 3.1.2 ⭐⭐ From Amplitudes to Bloch Coordinates

Exercise 3.1.3 🗣️ Feynman: Explain Qubits to Your Grandmother

Exercise 3.1.4 💭 Insight: The Curse of Dimensionality

3.2 Single-Qubit Gates

Exercise 3.2.1 ⭐ HHH-TTT Sequence Calculation

Exercise 3.2.2 ⭐⭐ Decomposition of an Arbitrary Rotation

Exercise 3.2.3 🗣️ Feynman: Explain Quantum Gates to a Programmer

Exercise 3.2.4 💭 Insight: The Special Status of the TTT Gate

3.3 Multi-Qubit Gates & Entanglement

Exercise 3.3.1 ⭐ Gate Operations on an Entangled State

Exercise 3.3.2 ⭐⭐ Product Gates Cannot Create Entanglement

Exercise 3.3.3 🗣️ Feynman: Explain Entanglement to a Sci-Fi Fan

Exercise 3.3.4 💭 Insight: Entanglement as a “Resource”

3.4 Quantum Circuits

Exercise 3.4.1 ⭐ Circuit Tracking

Exercise 3.4.2 ⭐⭐ Proving CNOT Gate Equivalence

Exercise 3.4.3 🗣️ Feynman: Explain “Reversibility” to a Hardware Engineer

Exercise 3.4.4 💭 Insight: Circuit Depth vs. Quantum Advantage

3.5 Quantum Measurement & Readout

Exercise 3.5.1 ⭐ Expectation Value Calculation

Exercise 3.5.2 ⭐⭐ The “Counterintuitive” Nature of Measurement

Exercise 3.5.3 🗣️ Feynman: Explain Quantum Probability to a Statistician

Exercise 3.5.4 💭 Insight: The Cost of Quantum Tomography

3.6 Quantum Algorithm Primer

Exercise 3.6.1 ⭐ BB84 Eavesdropping Probability Analysis

Exercise 3.6.2 ⭐⭐ Geometric Interpretation of Grover Iteration

Exercise 3.6.3 🗣️ Feynman: Explain to a CEO “What a Quantum Computer Does”

Exercise 3.6.4 💭 Insight: Post-Quantum Cryptography

Answers

3.1 Qubits

3.1.1 Three-State Normalization

3.1.2 From Amplitudes to Bloch Coordinates

3.1.3 🗣️ Key Points for Answer

Measurement in the $X$ Basis

Exercise 3.2.1 ⭐ $H$ - $T$ Sequence Calculation

Exercise 3.2.4 💭 Insight: The Special Status of the $T$ Gate

3.2.1 $H$ - $T$ Sequence Calculation