Chapter 5: Advanced Topics

Chapter 5: Advanced Topics in Quantum Computing

The first four chapters have built a complete foundation for understanding quantum computing: from linear algebra and complex numbers (Chapter 1), quantum mechanics principles (Chapter 2), qubits and quantum gates (Chapter 3), to the mathematical form of the quantum Fourier transform and the core ideas of Shor’s algorithm (Chapter 4). However, some key technical details and frontier topics remain unexplored. This chapter fills those gaps, deepening the reader’s understanding of quantum computing across five dimensions: we will show how to convert the abstract quantum Fourier transform into a concrete quantum circuit; we will learn quantum phase estimation—an exponentially accelerated technique for reading the eigenvalues of a quantum system; we will confront the greatest enemy of real quantum computers—noise and decoherence; we will explore the most important algorithmic paradigm of the NISQ (Noisy Intermediate-Scale Quantum) era—variational quantum algorithms; and finally, we will introduce §5.5 Hamiltonian simulation—one of the most promising applications of quantum computing in quantum chemistry and materials science. These five topics respectively correspond to circuit implementation of quantum algorithms, core applications, physical limitations, near-term practice, and core application prospects, together forming a complete bridge from theory to experiment.

5.1 Quantum Fourier Transform Circuit Construction

From DFT to QFT: Review and Motivation

Recall the discrete Fourier transform (DFT) studied in §1.8. For $N = 2^n$ complex numbers $x_0, x_1, \ldots, x_{N-1}$ , the DFT transforms them into a new set of complex numbers $y_0, y_1, \ldots, y_{N-1}$ :

$y_k = \frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}x_j\omega_N^{jk}, \quad \omega_N = e^{2\pi i/N}$

In quantum computing, the Quantum Fourier Transform (QFT) is the quantum implementation of the DFT. It does not transform an array of classical data; rather, it transforms the amplitudes of a quantum state. Given an $n$ -qubit state:

$\lvert\psi\rangle = \sum_{j=0}^{N-1}x_j\lvert j\rangle$

The QFT transforms it into:

$U_{\text{QFT}}\lvert\psi\rangle = \sum_{k=0}^{N-1}y_k\lvert k\rangle$

where $y_k$ are precisely the DFT coefficients above. Expressed in terms of basis states, the action of the QFT is:

$U_{\text{QFT}}\lvert j\rangle = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\omega_N^{jk}\lvert k\rangle$

This is one of the most important transforms in quantum computing. From a matrix perspective, $U_{\text{QFT}}$ is a $2^n \times 2^n$ unitary matrix whose $(j,k)$ entry is $\omega_N^{jk}/\sqrt{N}$ —the quantum version of the DFT matrix from §1.8. But the key point is: classical computers require $O(N\log N) = O(2^n n)$ operations to compute the DFT, while a quantum computer needs only $O(n^2)$ quantum gates to implement the QFT—an exponential speedup.

Binary Fraction Representation: Factoring the QFT

To convert the QFT into a circuit, we need to factor the above sum into a tensor product of single-qubit states. This is the central technique of QFT circuit construction.

First, we introduce the binary fraction representation: for a binary decimal $0.j_1 j_2 \ldots j_m$ , its value is:

$0.j_1 j_2 \ldots j_m = \frac{j_1}{2} + \frac{j_2}{4} + \cdots + \frac{j_m}{2^m}$

For example, $0.1 = 1/2$ , $0.01 = 1/4$ , $0.11 = 3/4$ .

Now, represent the integer $j$ as an $n$ -bit binary number $j = j_1 j_2 \ldots j_n$ , i.e., $j = j_1 2^{n-1} + j_2 2^{n-2} + \cdots + j_n 2^0$ . The QFT acting on the basis state $\lvert j\rangle = \lvert j_1 j_2 \ldots j_n\rangle$ yields, after a series of algebraic manipulations (expanding the exponential and separating variables), the remarkable factorized form:

$U_{\text{QFT}}\lvert j_1 j_2 \ldots j_n\rangle = \frac{1}{2^{n/2}}\left(\lvert0\rangle + e^{2\pi i \cdot 0.j_n}\lvert1\rangle\right) \otimes \left(\lvert0\rangle + e^{2\pi i \cdot 0.j_{n-1}j_n}\lvert1\rangle\right) \otimes \cdots \otimes \left(\lvert0\rangle + e^{2\pi i \cdot 0.j_1 j_2 \ldots j_n}\lvert1\rangle\right)$

Let us verify this formula for correctness. Taking $n=1$ as an example: $j = j_1$ , $N = 2$ , then:

$U_{\text{QFT}}\lvert j_1\rangle = \frac{1}{\sqrt{2}}\left(\lvert0\rangle + e^{2\pi i \cdot 0.j_1}\lvert1\rangle\right)$

When $j_1 = 0$ , $e^{2\pi i \cdot 0} = 1$ , yielding $\frac{1}{\sqrt{2}}(\lvert0\rangle + \lvert1\rangle)$ ; when $j_1 = 1$ , $e^{2\pi i \cdot 1/2} = e^{\pi i} = -1$ , yielding $\frac{1}{\sqrt{2}}(\lvert0\rangle - \lvert1\rangle)$ . This is precisely the action of the Hadamard gate $H$ ! So the single-qubit QFT is simply the $H$ gate.

The importance of this factorization is that the output state has been written as the tensor product of $n$ single-qubit states. This means we can use $n$ parallel single-qubit operations to prepare each factor of the output state—this is the key to constructing an efficient quantum circuit.

Controlled Phase Rotation Gates $CR_k$

Consider the $l$ -th factor in the factorization:

$\lvert0\rangle + e^{2\pi i \cdot 0.j_{n-l+1} \ldots j_n}\lvert1\rangle$

The phase $e^{2\pi i \cdot 0.j_{n-l+1} \ldots j_n}$ can be expanded as:

$e^{2\pi i \cdot 0.j_{n-l+1}} \cdot e^{2\pi i \cdot 0.0j_{n-l+2}} \cdot \cdots \cdot e^{2\pi i \cdot 0.0\ldots 0j_n}$

Each exponential term corresponds to a controlled phase rotation. For this, we define the Controlled-Phase Rotation gate $CR_k$ :

$CR_k = \begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&e^{2\pi i/2^k}\end{pmatrix}$

It acts on two qubits: when the control qubit is $\lvert1\rangle$ , it adds a phase $e^{2\pi i/2^k}$ to the $\lvert1\rangle$ component of the target qubit; when the control qubit is $\lvert0\rangle$ , the target qubit is unchanged. Note that $CR_1$ is just the controlled- $Z$ gate (CZ), since $e^{2\pi i/2} = e^{\pi i} = -1$ .

The matrix of $CR_k$ is diagonal in the computational basis $\{\lvert00\rangle, \lvert01\rangle, \lvert10\rangle, \lvert11\rangle\}$ , which makes it relatively easy to implement experimentally (many physical platforms natively support diagonal two-qubit gates).

Cascade Circuit Construction of the QFT

Now we can construct the complete QFT circuit. The QFT circuit operates sequentially from the first qubit to the $n$ -th qubit:

Qubit 1: Apply $H$ , then sequentially apply $CR_2, CR_3, \ldots, CR_n$ , with control qubits being qubits 2, 3, $\ldots$ , $n$ , respectively.

$H$ produces $\lvert0\rangle + e^{2\pi i \cdot 0.j_1}\lvert1\rangle$
$CR_2$ (control = qubit 2) adds phase $e^{2\pi i \cdot 0.0j_2} = e^{2\pi i j_2/4}$ , transforming the phase to $e^{2\pi i \cdot 0.j_1 j_2}$
$CR_3$ (control = qubit 3) adds phase $e^{2\pi i j_3/8}$ , transforming the phase to $e^{2\pi i \cdot 0.j_1 j_2 j_3}$
and so on…

Qubit 2: Apply $H$ , then sequentially apply $CR_2, CR_3, \ldots, CR_{n-1}$ , with control qubits being qubits 3, 4, $\ldots$ , $n$ , respectively.

…

Qubit $n$ : Apply $H$ only.

The 3-qubit QFT circuit is as follows:

j₁: |j₁⟩ —H—•—————•———     → output bit 3
              |     |
j₂: |j₂⟩ ————R₂—H—•———     → output bit 2
                    |
j₃: |j₃⟩ ————R₃—R₂—H—     → output bit 1

where $R_k$ denotes the $CR_k$ gate, with the control qubit above and the target qubit below. In the diagram, $R_2$ controls from qubit 2 to qubit 1, $R_3$ controls from qubit 3 to qubit 1, and so on.

More generally, an $n$ -qubit QFT circuit requires:

$n$ $H$ gates
$\sum_{k=1}^{n-1}k = n(n-1)/2$ controlled-phase gates

The total gate count is $O(n^2)$ . Since $H$ gates on different qubits can be executed in parallel (they do not interfere with each other), while controlled-phase gates involve different qubit pairs, the circuit depth is also $O(n)$ (if all two-qubit gates can be executed in parallel), or $O(n^2)$ under the most conservative estimate.

Bit-Reversal Problem and SWAP Gate Correction

Carefully examine the factorized output:

$\text{1st factor} \otimes \text{2nd factor} \otimes \cdots \otimes \text{$n$-th factor}$

where the $l$ -th factor corresponds to $e^{2\pi i \cdot 0.j_{n-l+1}\ldots j_n}$ , meaning it depends only on the input bits $j_{n-l+1}, \ldots, j_n$ . This implies:

The 1st output factor (most significant) depends only on the least significant input bit $j_n$
The $n$ -th output factor (least significant) depends on all input bits $j_1, \ldots, j_n$

Thus, the bit order of the QFT circuit output is reversed. If we want the output arranged in the normal order $k_1 k_2 \ldots k_n$ , we need to append $\lfloor n/2 \rfloor$ SWAP gates at the end of the circuit to reverse the bit order.

The SWAP gate exchanges the states of two qubits; its matrix is:

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

A SWAP can be implemented using 3 CNOT gates: CNOT(1→2), CNOT(2→1), CNOT(1→2). Therefore, the complete QFT circuit (including bit-order correction) requires $O(n^2)$ elementary gates.

Complete Numerical Example for 3-Qubit QFT

Let us verify the correctness of the QFT circuit with a concrete 3-qubit example. Take the input state $\lvert\psi\rangle = \lvert011\rangle$ (i.e., $j = 3$ ).

Step 1: Initial state $\lvert\psi_0\rangle = \lvert0\rangle_1 \otimes \lvert1\rangle_2 \otimes \lvert1\rangle_3$

Step 2: Apply $H$ to qubit 1 $\lvert\psi_1\rangle = \frac{1}{\sqrt{2}}(\lvert0\rangle_1 + \lvert1\rangle_1) \otimes \lvert1\rangle_2 \otimes \lvert1\rangle_3$

Step 3: $CR_2$ (control = qubit 2, target = qubit 1)

Control qubit 2 is $\lvert1\rangle$ , so the $\lvert1\rangle$ component of target qubit 1 acquires phase $e^{2\pi i/4} = e^{\pi i/2} = i$ :

$\lvert\psi_2\rangle = \frac{1}{\sqrt{2}}(\lvert0\rangle_1 + i\lvert1\rangle_1) \otimes \lvert1\rangle_2 \otimes \lvert1\rangle_3$

Step 4: $CR_3$ (control = qubit 3, target = qubit 1)

Control qubit 3 is $\lvert1\rangle$ , so the $\lvert1\rangle$ component of target qubit 1 acquires an additional phase $e^{2\pi i/8} = e^{\pi i/4} = \frac{1+i}{\sqrt{2}}$ :

$i \cdot e^{\pi i/4} = e^{\pi i/2} \cdot e^{\pi i/4} = e^{3\pi i/4} = -\frac{1}{\sqrt{2}} + \frac{i}{\sqrt{2}}$

So:

$\lvert\psi_3\rangle = \frac{1}{\sqrt{2}}(\lvert0\rangle_1 + e^{3\pi i/4}\lvert1\rangle_1) \otimes \lvert1\rangle_2 \otimes \lvert1\rangle_3$

This corresponds to $\lvert0\rangle + e^{2\pi i \cdot 0.011}\lvert1\rangle = \lvert0\rangle + e^{2\pi i \cdot 3/8}\lvert1\rangle$ .

Step 5: Apply $H$ to qubit 2

Qubit 2 is currently $\lvert1\rangle$ , and $H\lvert1\rangle = \frac{1}{\sqrt{2}}(\lvert0\rangle - \lvert1\rangle)$ :

$\lvert\psi_4\rangle = \frac{1}{\sqrt{2}}(\lvert0\rangle_1 + e^{3\pi i/4}\lvert1\rangle_1) \otimes \frac{1}{\sqrt{2}}(\lvert0\rangle_2 - \lvert1\rangle_2) \otimes \lvert1\rangle_3$

Step 6: $CR_2$ (control = qubit 3, target = qubit 2)

Control qubit 3 is $\lvert1\rangle$ , and the $\lvert1\rangle$ component of qubit 2 acquires phase $i$ :

$\lvert\psi_5\rangle = \frac{1}{\sqrt{2}}(\lvert0\rangle_1 + e^{3\pi i/4}\lvert1\rangle_1) \otimes \frac{1}{\sqrt{2}}(\lvert0\rangle_2 + i(-1)\lvert1\rangle_2) \otimes \lvert1\rangle_3$

$= \frac{1}{\sqrt{2}}(\lvert0\rangle_1 + e^{3\pi i/4}\lvert1\rangle_1) \otimes \frac{1}{\sqrt{2}}(\lvert0\rangle_2 + e^{3\pi i/2}\lvert1\rangle_2) \otimes \lvert1\rangle_3$

This corresponds to $\lvert0\rangle + e^{2\pi i \cdot 0.11}\lvert1\rangle$ .

Step 7: Apply $H$ to qubit 3

$\lvert\psi_6\rangle = \frac{1}{\sqrt{2}}(\lvert0\rangle_1 + e^{3\pi i/4}\lvert1\rangle_1) \otimes \frac{1}{\sqrt{2}}(\lvert0\rangle_2 + e^{3\pi i/2}\lvert1\rangle_2) \otimes \frac{1}{\sqrt{2}}(\lvert0\rangle_3 - \lvert1\rangle_3)$

This corresponds to $\lvert0\rangle + e^{2\pi i \cdot 0.1}\lvert1\rangle$ .

Step 8: SWAP correction for bit order (qubit 1 ↔ qubit 3)

The final output (ignoring the normalization factor $1/2^{3/2}$ ) is a superposition of 8 basis states, with amplitudes given by $e^{2\pi i \cdot 3k/8}/\sqrt{8}$ , where $k = 0, 1, \ldots, 7$ . This is precisely the result of applying the DFT to the basis state $\lvert3\rangle$ .

Approximate QFT and Depth Optimization

On real quantum computers, very small phase rotations (such as $CR_n$ for large $n$ , where $e^{2\pi i/2^n} \approx 1$ ) are difficult to implement accurately. A practical optimization is the Approximate QFT: discard all $CR_k$ gates with $k > k_{\max}$ , where $k_{\max} = O(\log n)$ . The error of this approximation can be controlled to be arbitrarily small, while the circuit depth reduces to $O(n \log n)$ , and in some architectures can even be optimized to $O(n)$ .

Summary: The quantum Fourier transform achieves efficient circuit construction by factorizing the output state into a tensor product of single-qubit states. The QFT circuit consists of $n$ $H$ gates and $n(n-1)/2$ controlled-phase rotation gates, with total complexity of $O(n^2)$ gates. The binary fraction representation reveals that each output bit depends only on a subset of input bits, which is the key to the cascaded circuit structure. The reversed output bit order must be corrected with SWAP gates. The 3-qubit numerical example verifies the correctness of the circuit.

Connection to Quantum Computing: The QFT is the core subroutine of Shor’s algorithm and quantum phase estimation. The transition from the abstract DFT matrix to the concrete cascaded circuit of $H$ gates and controlled-phase gates is a critical step from the mathematical description of quantum algorithms to their physical implementation. Understanding the circuit construction of the QFT is the foundation for understanding how these exponentially accelerated algorithms run on real quantum hardware. The $O(n^2)$ circuit complexity means the QFT can be implemented on moderate-scale quantum computers, making it one of the most practical transforms in near-term quantum computing.

5.2 Quantum Phase Estimation

Problem Statement: Reading the Eigenvalues of a Quantum System

Quantum Phase Estimation (QPE) is one of the most powerful subroutines in quantum computing. It solves the following problem:

Given: a unitary operator $U$ and one of its eigenvectors $\lvert u\rangle$ , satisfying $U\lvert u\rangle = e^{2\pi i \theta}\lvert u\rangle$ . Goal: estimate the numerical value of the phase $\theta \in [0, 1)$ .

This problem may seem abstract, but it captures the essence of many core quantum algorithms. For example, in Shor’s algorithm, $U$ is the unitary operator implementing modular exponentiation, $\lvert u\rangle$ is the corresponding period state, and the precise value of $\theta$ directly provides the key information needed for factorization.

On a classical computer, there is no direct method to estimate the eigenphase of a unitary operator—we typically need to compute all matrix elements of $U$ and diagonalize, with complexity $O(N^3)$ (where $N = 2^n$ ). Quantum phase estimation, by leveraging quantum parallelism and the QFT, can directly “read” the phase with a complexity of only $O(n^2)$ gates—an exponential speedup.

Algorithm Circuit Structure: Ancilla Register + Controlled Unitary Operations + Inverse QFT

The QPE circuit consists of three parts, using two quantum registers:

First register (ancilla/counting register): $t$ qubits, initialized to $\lvert0\rangle^{\otimes t}$
Second register (target register): holds the eigenvector $\lvert u\rangle$ (assumed to have been prepared)

The circuit structure is as follows:

|0⟩ —H—•——————•——————•———H†—S†—...—     → measure → binary estimate of θ
|0⟩ —H—|  U¹   |  U²   |   —H†—...—
|0⟩ —H—|       |       |     ...
  ⋮    |       |       |
|0⟩ —H—•———————•———————•———————...—
       |       |       |
|u⟩ ——U¹——U²——U⁴——...——U^(2^{t-1})—     → |u⟩ (unchanged)

Step 1: Create a superposition

Apply $H$ gates to all $t$ ancilla qubits:

$\frac{1}{\sqrt{2^t}}\sum_{x=0}^{2^t-1}\lvert x\rangle \otimes \lvert u\rangle$

Step 2: Controlled unitary operations encode the phase

Sequentially apply controlled $U^{2^k}$ operations, with the control qubit being the $k$ -th qubit of the ancilla register and the target being $\lvert u\rangle$ . The controlled $U^{2^k}$ acts as: when the control qubit is $\lvert1\rangle$ , apply $U^{2^k}$ to the target; when the control qubit is $\lvert0\rangle$ , the target is unchanged.

Mathematically, for the ancilla qubits in state $\lvert x\rangle = \lvert x_{t-1} x_{t-2} \ldots x_0\rangle$ (where $x_k \in \{0,1\}$ ), the controlled operations transform the target state as:

$U^{x_0} \cdot U^{2x_1} \cdot U^{4x_2} \cdots U^{2^{t-1}x_{t-1}}\lvert u\rangle = U^x\lvert u\rangle = e^{2\pi i \theta x}\lvert u\rangle$

Thus, the state of the entire ancilla-target system becomes:

$\frac{1}{\sqrt{2^t}}\sum_{x=0}^{2^t-1}e^{2\pi i \theta x}\lvert x\rangle \otimes \lvert u\rangle$

This is the critical step: the phase $\theta$ has been encoded into the amplitudes of the ancilla register! Note the form of this state—it closely resembles the output state of the QFT.

Step 3: Inverse QFT reads the phase

Apply the Inverse Quantum Fourier Transform (Inverse QFT, QFT $^\dagger$ ) to the ancilla register part of the above state. QFT $^\dagger$ is the Hermitian conjugate of the QFT; it transforms a frequency-domain representation back to the time domain.

If $\theta$ can be exactly represented as a $t$ -bit binary number, i.e., $\theta = 0.\theta_1 \theta_2 \ldots \theta_t$ , then the inverse QFT transforms the ancilla register precisely into $\lvert\theta_1 \theta_2 \ldots \theta_t\rangle$ . Measuring the ancilla register, we directly read out the binary representation of $\theta$ !

More precisely, if $\theta = j/2^t$ (i.e., a $t$ -bit binary fraction), then:

$\text{QFT}^\dagger\left(\frac{1}{\sqrt{2^t}}\sum_{x=0}^{2^t-1}e^{2\pi i j x/2^t}\lvert x\rangle\right) = \lvert j\rangle$

This is a direct consequence of the defining property (orthogonality) of the QFT.

Precision Analysis and Success Probability

When $\theta$ is not a $t$ -bit binary fraction (i.e., cannot be represented exactly), QPE yields the best $t$ -bit approximation of $\theta$ . Let $\delta$ be the distance between the true value of $\theta$ and the nearest $t$ -bit binary fraction $b/2^t$ ( $|\delta| \leq 1/2^{t+1}$ ).

The probability that the measurement outcome falls near $b$ satisfies:

$p(|\text{measurement outcome} - b| < 2^{t-m}) \geq 1 - \frac{1}{2(2^{m-t}-1)}$

In particular, to obtain an estimate with $n$ bits of precision (i.e., error less than $1/2^n$ ), one needs $t = n + O(1)$ ancilla qubits. More precisely, to obtain $n$ bits of precision with probability at least $1-\epsilon$ , one needs:

$t = n + \left\lceil\log_2\left(2 + \frac{1}{2\epsilon}\right)\right\rceil$

For example, to obtain $n$ bits of precision with 99% success probability, roughly $t = n + 8$ ancilla qubits are needed.

Relationship to Shor’s Algorithm

The core of Shor’s algorithm is order finding: given an integer $a$ coprime to $N$ , find the smallest positive integer $r$ such that $a^r \equiv 1 \pmod{N}$ . This problem can be formulated as phase estimation:

Define a unitary operator $U$ : $U\lvert x\rangle = \lvert ax \mod N\rangle$ (acting on $\lceil\log_2 N\rceil$ qubits). The eigenstates of this $U$ are:

$\lvert u_s\rangle = \frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}e^{-2\pi i s k/r}\lvert a^k \mod N\rangle$

with corresponding eigenvalues $e^{2\pi i s/r}$ , where $s = 0, 1, \ldots, r-1$ .

By using QPE to estimate $s/r$ , and then using the continued fraction expansion to extract $r$ from the approximation of $s/r$ , we obtain the mechanism by which QFT/QPE plays its central role in Shor’s algorithm. QPE transforms an abstract number-theoretic problem into a physical measurement of a quantum system’s eigenphase—a profound intersection of mathematics and physics.

Implementation Challenges: Controlled $U^{2^k}$ Operations

The theoretical framework of QPE is elegant and concise, but its experimental implementation faces major challenges:

Preparing the eigenstate $\lvert u\rangle$ : we usually do not know the explicit form of $\lvert u\rangle$ . In practice, we prepare $\lvert1\rangle$ (or another simple state), which can be expressed as a superposition of all eigenstates: $\lvert1\rangle = \sum_s \lvert u_s\rangle/\sqrt{r}$ . QPE simultaneously estimates multiple eigenphases, and the measurement outcome gives some value of $s/r$ with a certain probability—this is sufficient for order finding.
Implementing controlled $U^{2^k}$ : this is the greatest experimental challenge. For the modular exponentiation in Shor’s algorithm, $U^{2^k}\lvert x\rangle = \lvert a^{2^k}x \mod N\rangle$ , one needs to implement $O((\log N)^3)$ elementary gates. While theoretically feasible, the gate fidelity and coherence time of current quantum hardware limit the scale of executable $U^{2^k}$ .
Qubit count: Shor’s algorithm for factoring an $L$ -bit integer requires roughly $2L$ qubits for the ancilla register, plus $O(L)$ qubits for the target register. For 2048-bit RSA ( $L = 2048$ ), roughly 4000–5000 qubits are needed—far beyond the current state-of-the-art quantum computers (~1000 qubits).

Summary: Quantum phase estimation achieves exponentially accelerated estimation of the eigenphase of a unitary operator by creating a superposition in the ancilla register, applying controlled $U^{2^k}$ operations to encode the phase into the amplitudes, and then using the inverse QFT to convert the phase information into a measurable binary representation. $t$ ancilla qubits provide roughly $t - O(1)$ bits of precision. The order finding in Shor’s algorithm is a direct application of QPE. The implementation of controlled $U^{2^k}$ is the main bottleneck in current experiments.

Connection to Quantum Computing: QPE is a general-purpose tool for “reading” the intrinsic information of a quantum system. It is used not only in Shor’s algorithm, but widely in quantum chemistry (computing molecular energy levels), quantum simulation (reading system evolution frequencies), and quantum machine learning. Understanding the circuit structure and precision analysis of QPE is key to understanding how quantum computers extract useful classical information from abstract quantum states. QPE exemplifies the typical paradigm of quantum algorithm design: encoding problems using superposition and extracting answers using quantum interference.

5.3 Noise Models and Decoherence

Open Quantum Systems: Why Noise Is Unavoidable

In the preceding chapters, we discussed only closed quantum systems—ideal systems that are completely isolated from the external environment and governed solely by precisely controlled unitary evolution. In reality, no quantum system is completely isolated. Open quantum systems are continuously coupled to their environment, leading to the degradation and loss of quantum information.

Why is this coupling unavoidable? Because qubits are real physical systems (electron spins, superconducting circuits, ion energy levels, etc.), they necessarily interact with surrounding environmental degrees of freedom such as electromagnetic fields, lattice vibrations (phonons), and thermal radiation. These environmental degrees of freedom constitute an enormous “heat bath,” whose Hilbert space dimension is typically exponentially larger than that of the qubit. Entanglement between the qubit and the environment causes the pure state of the qubit to evolve into the mixed states we studied in §2.6—this is the physical origin of decoherence.

Understanding noise is not optional supplementary knowledge; it is the basis for evaluating the practical feasibility of any quantum computing scheme. All current quantum computers operate in the “NISQ” (Noisy Intermediate-Scale Quantum) era, where noise is the primary factor limiting computational scale and depth.

Operator-Sum Representation (Kraus Representation)

For open quantum systems, evolution is no longer a unitary map from pure state to pure state, but a completely positive trace-preserving map (CPTP map) from density matrix to density matrix. Such maps can be characterized by the operator-sum representation, also known as the Kraus representation:

$\rho \to \mathcal{E}(\rho) = \sum_k E_k \rho E_k^\dagger$

where $\{E_k\}$ are called Kraus operators, satisfying the completeness relation:

$\sum_k E_k^\dagger E_k = I$

This condition ensures that the map is trace-preserving: $\text{Tr}(\mathcal{E}(\rho)) = \text{Tr}(\rho) = 1$ .

The physical meaning of the Kraus representation is: the action of the environment on the quantum system can be viewed as a statistical mixture of a series of “quantum operations.” Each $E_k$ corresponds to one possible “response” of the environment, and the overall evolution is the probability-weighted average of these responses. This is entirely analogous to channel models for classical noise—except that here the “channel” acts on density matrices rather than classical probability distributions.

If there is only one Kraus operator $E_0 = U$ (a unitary matrix), it reduces to the unitary evolution of a closed system: $\mathcal{E}(\rho) = U\rho U^\dagger$ . Thus, the Kraus representation is a natural generalization of unitary evolution, uniformly describing everything from pure unitary evolution to complete depolarization.

Depolarizing Channel

The depolarizing channel is one of the simplest noise models, describing a process in which the quantum state is completely randomized with probability $p$ :

$\mathcal{E}(\rho) = (1-p)\rho + \frac{p}{3}(X\rho X + Y\rho Y + Z\rho Z)$

The corresponding Kraus operators are:

$E_0 = \sqrt{1-p}\, I, \quad E_1 = \sqrt{\frac{p}{3}}\, X, \quad E_2 = \sqrt{\frac{p}{3}}\, Y, \quad E_3 = \sqrt{\frac{p}{3}}\, Z$

Completeness check: $E_0^\dagger E_0 + E_1^\dagger E_1 + E_2^\dagger E_2 + E_3^\dagger E_3 = (1-p)I + \frac{p}{3}(I + I + I) = I$ ✓

Physical meaning: with probability $1-p$ , the quantum state is unaffected; with probability $p/3$ each, an $X$ , $Y$ , or $Z$ error is applied (bit flip, phase flip, or both). When $p = 1$ , any input state becomes the completely mixed state $I/2$ —information is completely lost.

On the Bloch sphere, the depolarizing channel uniformly shrinks all points toward the center:

$\vec{r} \to (1-p)\vec{r}$

i.e., the length of the Bloch vector is reduced by a factor of $1-p$ , but the direction is unchanged. When $p = 1$ , the entire sphere collapses to the center $\vec{r} = \vec{0}$ .

Bit-Flip Channel

The bit-flip channel flips the qubit ( $\lvert0\rangle \leftrightarrow \lvert1\rangle$ ) with probability $p$ , corresponding to a classical “bit error”:

$\mathcal{E}(\rho) = (1-p)\rho + p X\rho X$

Kraus operators: $E_0 = \sqrt{1-p}\, I$ , $E_1 = \sqrt{p}\, X$ .

On the Bloch sphere, the effect of the bit-flip channel is:

$(x, y, z) \to (x, (1-2p)y, (1-2p)z)$

Let me recompute. Setting $\rho = \frac{1}{2}(I + xX + yY + zZ)$ , we have:

$\mathcal{E}(\rho) = (1-p)\rho + p X\rho X = \frac{1}{2}\left(I + xX + (1-2p)yY + (1-2p)zZ\right)$

So the Bloch coordinates transform as:

$x \to x, \quad y \to (1-2p)y, \quad z \to (1-2p)z$

i.e., the $x$ coordinate is unchanged, while the $y$ and $z$ coordinates are scaled by a factor of $1-2p$ . When $p = 1/2$ , the $y$ and $z$ components vanish completely, and the state becomes $\rho = \frac{1}{2}(I + xX)$ —if initially $x = 0$ , it becomes the completely mixed state. The bit-flip channel preserves information on the $x$ axis but compresses the state in the $y$ - $z$ plane.

Phase-Flip Channel (Dephasing Channel)

The phase-flip channel, also called the dephasing channel, applies a $Z$ gate (flipping the phase of $\lvert1\rangle$ ) with probability $p$ :

$\mathcal{E}(\rho) = (1-p)\rho + p Z\rho Z$

Kraus operators: $E_0 = \sqrt{1-p}\, I$ , $E_1 = \sqrt{p}\, Z$ .

Effect on the Bloch sphere:

$\mathcal{E}(\rho) = \frac{1}{2}\left(I + (1-2p)xX + (1-2p)yY + zZ\right)$

i.e.:

$x \to (1-2p)x, \quad y \to (1-2p)y, \quad z \to z$

This is the core mechanism of decoherence! The phase-flip channel compresses the state in the $x$ - $y$ plane (attenuating the coherence terms) but preserves the $z$ coordinate (the occupation probabilities of the energy eigenstates). When $p = 1/2$ , the $x$ and $y$ components vanish, and the state becomes a classical probability mixture $\rho = \frac{1+z}{2}\lvert0\rangle\langle0\rvert + \frac{1-z}{2}\lvert1\rangle\langle1\rvert$ —quantum coherence is completely lost, leaving only classical probabilistic information.

The importance of the dephasing channel is that it is the dominant noise mechanism in most physical systems. Due to energy conservation constraints, processes in which the system exchanges energy with the environment (causing changes in $z$ ) are typically much slower than pure phase information loss ( $x$ , $y$ decay). Hence, $T_2$ (phase coherence time) is typically shorter than $T_1$ (energy relaxation time)—this is the most common limiting factor in experimental quantum computing.

Amplitude Damping Channel

The amplitude damping channel describes the process of energy dissipating from the quantum system into the environment, such as spontaneous emission decay of an excited state to the ground state:

$\mathcal{E}(\rho) = E_0 \rho E_0^\dagger + E_1 \rho E_1^\dagger$

where:

$E_0 = \begin{pmatrix}1&0\\0&\sqrt{1-\gamma}\end{pmatrix}, \quad E_1 = \begin{pmatrix}0&\sqrt{\gamma}\\0&0\end{pmatrix}$

The parameter $\gamma \in [0, 1]$ is the probability of energy dissipation. $E_1$ transforms $\lvert1\rangle$ (the excited state) into $\lvert0\rangle$ (the ground state), corresponding to energy $\hbar\omega$ released into the environment. $E_0$ reduces the amplitude of $\lvert1\rangle$ while leaving $\lvert0\rangle$ unchanged.

Completeness check:

$E_0^\dagger E_0 + E_1^\dagger E_1 = \begin{pmatrix}1&0\\0&1-\gamma\end{pmatrix} + \begin{pmatrix}0&0\\0&\gamma\end{pmatrix} = I$

On the Bloch sphere, amplitude damping attracts the state toward the north pole ( $\lvert0\rangle$ , the ground state):

$\rho = \frac{1}{2}\begin{pmatrix}1+z&x-iy\\x+iy&1-z\end{pmatrix} \to \frac{1}{2}\begin{pmatrix}1+z+\gamma(1-z)&\sqrt{1-\gamma}(x-iy)\\\sqrt{1-\gamma}(x+iy)&(1-\gamma)(1-z)\end{pmatrix}$

The coordinate transformation is:

$x \to \sqrt{1-\gamma}\, x, \quad y \to \sqrt{1-\gamma}\, y, \quad z \to z + \gamma(1-z) = 1 - (1-\gamma)(1-z)$

As $\gamma \to 1$ , any state approaches $\lvert0\rangle$ . When $\gamma \ll 1$ , the system undergoes exponential decay $e^{-t/T_1}$ , where $T_1$ is the energy relaxation time.

Quantum Error Mitigation

Quantum error correction (§4.4) actively corrects errors through redundant encoding, but requires a large number of physical qubits and physical error rates far below the threshold. In the NISQ era (Noisy Intermediate-Scale Quantum), hardware has not yet reached the error-correction threshold, giving rise to an alternative technical route—Quantum Error Mitigation (QEM). Unlike QEC, QEM does not correct errors, but removes the influence of noise in classical post-processing, estimating noise-free expectation values in an unbiased manner. The core observation of QEM is: while we cannot eliminate noise on quantum hardware, we can cleverly vary the noise and measure its influence, then “subtract” the noise contribution on a classical computer.

Zero-Noise Extrapolation (ZNE):

Core idea: measure the expectation value of the same observable at different noise levels, then extrapolate to the zero-noise limit
How to control the noise level: systematically amplify noise through pulse stretching (lengthening gate operation times on superconducting platforms) or gate folding (inserting decompositions of identity gates to increase circuit depth)
Fitting model: $\langle O \rangle(\lambda) = \langle O \rangle_0 + a_1\lambda + a_2\lambda^2 + \cdots$ , where $\lambda$ is the noise amplification factor
Richardson extrapolation or exponential fitting
Experimental validation: ZNE techniques can reduce energy estimation errors in VQE by a factor of 5–10 (IBM, Rigetti 2020–2022)

Probabilistic Error Cancellation (PEC):

Core idea: represent noisy quantum gates as combinations of ideal gates and noise channels, then invert the noise through Monte Carlo sampling
Implementation: decompose each noisy gate into a linear combination of ideal gates, sample in a “quasi-probability” manner, and multiply by a sign factor $\gamma$ to correct expectation values
Cost: sampling variance grows with $\gamma^2$ , and $\gamma$ grows exponentially with circuit depth—hence PEC is only applicable to shallow circuits
Applicability: compared to ZNE, PEC provides more accurate correction at low depth but at higher cost

Virtual Distillation:

A more recent method (2021–2022), which “distills” a noise-free state by preparing $M$ copies and measuring the expectation value of the swap operator
Does not require additional ancilla qubits, but requires a $\text{SWAP}$ gate network
Applicable to medium-depth circuits; a method that sits between QEC and QEM

Measurement Error Mitigation:

The simplest form of QEM: by preparing known basis states (such as $\lvert0\rangle^{\otimes n}$ and $\lvert1\rangle^{\otimes n}$ ) and measuring them, construct a measurement error response matrix $A$ , then correct all subsequent measurements via $P_{\text{corrected}} = A^{-1} P_{\text{raw}}$
Complexity: $O(2^n)$ for full matrix correction, or use tensor product decomposition approximations

QEC vs QEM comparison:

Dimension	Quantum Error Correction (QEC)	Quantum Error Mitigation (QEM)
Goal	Actively correct errors	Post-process to remove noise bias
Quantum overhead	Large number of ancilla qubits ( $d^2:1$ )	Additional circuit executions (2–10x depth)
Classical overhead	Real-time decoder	Monte Carlo / extrapolation fitting
Error scaling	Exponential (below threshold)	Polynomial (extrapolation order)
Applicable era	Fault-tolerant era (2030+)	NISQ era (present)
Demonstrated	Below threshold (Willow $10^{-5}$ )	2–10x precision improvement (IBM/Google)

$T_1$ and $T_2$ Times

In experimental quantum computing, noise is characterized by two characteristic times:

$T_1$ (Energy Relaxation Time, Longitudinal Relaxation Time): describes the rate at which energy leaks from the excited state to the ground state. If the system is in $\lvert1\rangle$ at $t = 0$ , the evolution of the $z$ coordinate satisfies:

$z(t) = 2e^{-t/T_1} - 1$

i.e., the excited-state occupation probability decays as $e^{-t/T_1}$ . A larger $T_1$ means the qubit can retain energy longer.

$T_2$ (Decoherence Time, Transverse Relaxation Time): describes the rate at which a quantum superposition state (a state in the $x$ - $y$ plane) loses coherence. The decay of the $x$ and $y$ coordinates satisfies:

$x(t) = x(0)\, e^{-t/T_2}, \quad y(t) = y(0)\, e^{-t/T_2}$

The relationship between $T_2$ and $T_1$ is:

$\frac{1}{T_2} = \frac{1}{2T_1} + \frac{1}{T_\phi}$

where $T_\phi$ is the pure dephasing time, describing the rate of pure phase noise (phase randomization that conserves energy). Typically $T_\phi \ll T_1$ , hence $T_2 \ll T_1$ —phase coherence is lost much more rapidly than energy relaxation.

Current state-of-the-art superconducting qubits: $T_1 \sim 100\text{--}500\,\mu\text{s}$ , $T_2 \sim 50\text{--}200\,\mu\text{s}$ . This means quantum computations must be completed within a time far shorter than $\sim 100\,\mu\text{s}$ , or noise will overwhelm the quantum signal. Since a typical single-qubit gate time is about $\sim 10\text{--}50\,\text{ns}$ , current systems can execute roughly $10^3\text{--}10^4$ gate operations—this defines the computational boundary of the NISQ era.

Implications of Noise for Quantum Error Correction

The analysis of the above noise models reveals a key fact: single-qubit errors can be viewed as a statistical mixture of $I$ , $X$ , $Y$ , and $Z$ . This suggests a strategy for combating noise: if we can detect and correct $X$ , $Y$ , and $Z$ errors, we can protect quantum information.

However, the challenge of quantum error correction is far greater than that of classical error correction, for three reasons:

Continuous errors: quantum errors are continuous (arbitrary rotations on the Bloch sphere), whereas classical errors are discrete (bit flips). Although the Kraus representation decomposes continuous evolution into a mixture of discrete operations, the error-correction circuits themselves are also affected by noise.
No-cloning theorem: we cannot copy quantum information to protect it, so we must employ more sophisticated encoding strategies (such as encoding one logical qubit into multiple physical qubits).
Measurement destroys coherence: to detect errors, we need to measure certain observables, but measurement causes collapse. Quantum error-correcting codes (such as Steane code, Shor code, surface code) circumvent this limitation by measuring stabilizers rather than the qubits themselves—stabilizer measurements reveal error information without destroying the encoded quantum state.

The surface code is currently the most promising quantum error correction scheme. It uses physical qubits on a two-dimensional lattice to encode one logical qubit, detecting $X$ and $Z$ errors through local stabilizer measurements. The threshold theorem of the surface code states: if the single-qubit error rate is below about $1\%$ , the logical error rate can be arbitrarily reduced—this is the theoretical foundation of fault-tolerant quantum computing.

Summary: Open quantum systems coupling to the environment leads to information loss, uniformly described by the Kraus operator-sum representation. The depolarizing channel completely randomizes the quantum state with probability $p$ ; the bit-flip channel preserves the $x$ coordinate but compresses $y$ and $z$ ; the phase-flip (dephasing) channel is the core mechanism of decoherence, attenuating $x$ and $y$ but preserving $z$ ; amplitude damping describes energy dissipation, attracting the state toward the ground state. The $T_1$ and $T_2$ times characterize the noise strength, and current hardware limits NISQ-era circuit depths to roughly $10^3\text{--}10^4$ gates. Quantum error correction combats noise through multi-qubit encoding and stabilizer measurements, with the surface code being the most promising fault-tolerant scheme; in the NISQ era, quantum error mitigation (ZNE, PEC, virtual distillation) estimates noise-free expectation values in an unbiased manner through classical post-processing, providing an alternative noise-management strategy for current hardware that complements QEC for the fault-tolerant era.

Connection to Quantum Computing: Noise is the greatest obstacle to the transition of quantum computing from theory to practice. Understanding noise models not only helps us evaluate the practical feasibility of quantum algorithms, but also guides the design of quantum error-correcting codes. The variational quantum algorithms of the NISQ era (§5.4) are held in high hope precisely because of their noise robustness compared to algorithms requiring deep circuits (such as Shor’s algorithm). From the dephasing channel to the $T_2$ time, from the Kraus representation to the surface code, noise theory bridges abstract quantum algorithms and real physical hardware.

5.4 Variational Quantum Algorithms

Quantum-Classical Hybrid Architecture

The quantum algorithms we have studied so far (Shor, Grover, QPE) all assume an ideal fault-tolerant quantum computer—millions of qubits, extremely low error rates, and sufficiently long coherence times. But current and near-term foreseeable quantum hardware is far from meeting this standard. Devices in the NISQ (Noisy Intermediate-Scale Quantum) era have $\sim 50\text{--}1000$ qubits, limited coherence times, and significant gate error rates. Under these constraints, new algorithmic paradigms are needed.

Variational Quantum Algorithms (VQA) arose in response. Their core idea: use the quantum computer as a “parameterized state preparer,” and hand the difficult optimization problem to a classical computer.

The hybrid architecture workflow is:

A classical optimizer chooses a set of parameters $\vec{\theta}$
The quantum computer uses a parameterized circuit $U(\vec{\theta})$ to prepare a trial state $\lvert\psi(\vec{\theta})\rangle$
The quantum computer measures some observable of that state, obtaining an estimate of the energy (or other cost function) $E(\vec{\theta})$
The classical computer updates the parameters $\vec{\theta} \to \vec{\theta}'$ based on $E(\vec{\theta})$
Repeat steps 2–4 until convergence

This loop exploits the quantum computer’s advantage in state preparation and measurement (operations in an exponentially large Hilbert space), while avoiding the noise accumulation of deep quantum circuits—the parameterized circuits are typically very shallow ( $O(1)$ or $O(\log n)$ depth). The classical optimizer handles parameter updates, using mature classical optimization algorithms (gradient descent, Adam, L-BFGS, etc.).

Variational Principle: The Energy Upper Bound

The theoretical foundation of variational quantum algorithms is the variational principle: for any quantum state $\lvert\psi\rangle$ , the expectation value of the Hamiltonian $H$ satisfies:

$\langle\psi|H|\psi\rangle \geq E_0$

where $E_0$ is the ground-state energy (lowest eigenvalue) of $H$ . Equality holds if and only if $\lvert\psi\rangle$ is the ground state.

This means: if we can prepare a trial state $\lvert\psi(\vec{\theta})\rangle$ close to the ground state, its energy expectation value provides an upper bound on the ground-state energy. By minimizing $\langle H \rangle_{\vec{\theta}}$ , we simultaneously obtain an estimate of the ground-state energy and an approximation to the ground state itself.

This principle is especially important in quantum chemistry: the electronic structure of molecules is described by the Schrödinger equation $H\lvert\psi\rangle = E\lvert\psi\rangle$ , but exact solution is impossible on classical computers for multi-electron systems (beyond roughly 20 electrons). Variational quantum algorithms offer a possible path for computing molecular ground-state energies on NISQ devices.

VQE: Variational Quantum Eigensolver

The Variational Quantum Eigensolver (VQE) is the most famous algorithm in the VQA family, specifically designed for finding the ground-state energy and ground-state wavefunction of a quantum system.

Algorithm flow:

1. Parameterized Quantum Circuit (Ansatz):

Choose a parameterized circuit $U(\vec{\theta})$ that transforms the initial state $\lvert0\rangle^{\otimes n}$ into a trial state:

$\lvert\psi(\vec{\theta})\rangle = U(\vec{\theta})\lvert0\rangle^{\otimes n}$

Common ansätze include:

Hardware-Efficient Ansatz (HEA): uses simple gate layers matching the native gate set of the target quantum hardware (e.g., single-qubit rotations + entangling gates). Shallow depth, but may struggle to represent complex ground states.
UCCSD (Unitary Coupled Cluster with Single and Double excitations): built from quantum-chemistry-inspired excitation operators; physically well-motivated, but circuit depth is larger.

2. Energy Measurement:

Decompose the Hamiltonian $H$ into a linear combination of Pauli operators (via the Jordan-Wigner transformation or Bravyi-Kitaev transformation):

$H = \sum_k c_k P_k, \quad P_k \in \{I, X, Y, Z\}^{\otimes n}$

The energy expectation value is:

$\langle H \rangle_{\vec{\theta}} = \sum_k c_k \langle\psi(\vec{\theta})|P_k|\psi(\vec{\theta})\rangle$

Each $\langle P_k \rangle$ can be measured in the computational basis after an appropriate basis rotation. For example, to measure $\langle X \rangle$ , first apply $H$ gates to all relevant qubits, then measure $Z$ .

3. Classical Optimization:

Use a classical optimizer to minimize $\langle H \rangle_{\vec{\theta}}$ . Commonly used optimizers include:

Gradient descent: requires estimating the gradient $\partial \langle H \rangle / \partial \theta_i$
SPSA (Simultaneous Perturbation Stochastic Approximation): estimates all gradient components using only 2 function evaluations, suitable for noisy environments
L-BFGS: a quasi-Newton method, converges quickly but is sensitive to noise

Quantum method for gradient estimation:

The parameter shift rule allows exact gradient computation:

$\frac{\partial \langle H \rangle}{\partial \theta_i} = \frac{1}{2}\left(\langle H \rangle_{\theta_i + \pi/2} - \langle H \rangle_{\theta_i - \pi/2}\right)$

This requires only evaluating the energy at $\theta_i \pm \pi/2$ , with no need for numerical differentiation.

Application: Quantum Chemistry

The most important application of VQE is computing the ground-state energy of molecules. For example, computing the ground-state energy of the hydrogen molecule $H_2$ requires 4 qubits (4 spin orbitals), and VQE can be implemented on current NISQ devices. For larger molecules (such as $N_2$ , $H_2O$ ), more qubits and deeper circuits are needed, but this remains one of the most promising near-term quantum advantage application scenarios.

QAOA: Quantum Approximate Optimization Algorithm

The Quantum Approximate Optimization Algorithm (QAOA), proposed by Farhi, Goldstone, and Gutmann in 2014, is specifically designed for solving combinatorial optimization problems.

Problem setting:

A combinatorial optimization problem can be formulated as: minimize a cost function $C(z)$ defined on $n$ -bit binary strings, where $z \in \{0,1\}^n$ . For example, the MaxCut problem: given a graph $G = (V, E)$ , partition the vertices into two sets to maximize the number of edges between the two sets.

Map the cost function to a problem Hamiltonian $C$ :

$C = \sum_{z} C(z) \lvert z\rangle\langle z\rvert$

The ground state $\lvert z_{\text{opt}}\rangle$ corresponds to the optimal solution. But directly finding the ground state is hard (NP-hard).

QAOA circuit structure:

QAOA uses $p$ layers of alternating unitary evolution:

$\lvert\psi(\vec{\gamma}, \vec{\beta})\rangle = e^{-i\beta_p B}e^{-i\gamma_p C} \cdots e^{-i\beta_1 B}e^{-i\gamma_1 C} \lvert+\rangle^{\otimes n}$

where:

Mixer Hamiltonian: $B = \sum_{j=1}^{n} X_j$ , i.e., the sum of $X$ gates on all qubits. Its role is to drive the system in a “random walk” through solution space.
Problem Hamiltonian: $C = \sum_{\langle j,k\rangle \in E} \frac{1}{2}(I - Z_j Z_k)$ (for the MaxCut example)
Initial state: $\lvert+\rangle^{\otimes n}$ , the equal superposition of all qubits

The parameters $\vec{\gamma} = (\gamma_1, \ldots, \gamma_p)$ and $\vec{\beta} = (\beta_1, \ldots, \beta_p)$ are adjusted by a classical optimizer to minimize the expectation value $\langle C \rangle$ .

QAOA circuit example for $p=1$ (3-qubit MaxCut):

|0⟩ —H—Rz(γ₁)—•——————Rx(β₁)—
               | (ZZ)
|0⟩ —H—Rz(γ₁)—⊕—•—————Rx(β₁)—
                  | (ZZ)
|0⟩ —H—Rz(γ₁)———⊕——Rx(β₁)—

where $Rz(\gamma)$ comes from the diagonal evolution of $e^{-i\gamma C}$ , and the $ZZ$ gate (a variant of the controlled- $Z$ gate) implements $e^{-i\gamma Z_j Z_k/2}$ .

Applications:

QAOA has been applied to MaxCut, graph coloring, the traveling salesman problem (TSP), portfolio optimization, and other problems. Although whether QAOA’s approximation ratio can surpass classical algorithms for general problems remains an open question, for certain specific problem instances, QAOA has demonstrated performance superior to classical greedy algorithms.

Challenges of Variational Algorithms

Although variational quantum algorithms provide a practical path for the NISQ era, they face several fundamental challenges:

1. Barren Plateaus

This is the most severe theoretical challenge for variational quantum algorithms. Research shows that for random parameterized circuits of depth $O(\text{poly}(n))$ , the variance of the cost function gradient $\partial \langle H \rangle / \partial \theta_i$ decreases exponentially with the number of qubits $n$ :

$\text{Var}\left(\frac{\partial \langle H \rangle}{\partial \theta_i}\right) \sim \frac{1}{2^n}$

This means that as the circuit scale increases, the gradient becomes extremely small and is drowned out by noise—the optimizer cannot find a descent direction. This phenomenon is called barren plateaus, because the cost function landscape is as flat as a barren plateau, with no discernible gradient information.

Mitigation strategies include:

Using local cost functions (rather than global cost functions)
Designing problem-specific shallow ansätze
Adopting layerwise optimization strategies

2. Measurement Sampling Overhead

Estimating the energy expectation value $\langle H \rangle = \sum_k c_k \langle P_k \rangle$ requires measuring each term $\langle P_k \rangle$ . Estimating each $\langle P_k \rangle$ to precision $\epsilon$ requires $O(1/\epsilon^2)$ measurements (by the central limit theorem). If the Hamiltonian has $M$ terms, the total sampling complexity is $O(M/\epsilon^2)$ . For quantum chemistry problems, $M$ can be very large ( $O(n^4)$ ), leading to enormous measurement overhead.

Mitigation strategies include:

Grouping Commuting Pauli Strings: simultaneously measure commuting Pauli operator strings
Classical Shadows: use randomized measurements to obtain information about multiple observables at once

3. Circuit Depth vs. Expressibility Trade-off

Deeper circuits can represent more complex quantum states (higher expressibility), but are also more susceptible to noise (lower fidelity). Ansatz design needs to strike a balance between expressibility and noise robustness. Hardware-efficient ansätze are shallow and noise-robust, but may not be able to approximate the target ground state; chemistry-inspired ansätze like UCCSD have high expressibility, but their circuit depth may exceed the limits of NISQ devices.

Relationship Between Variational Algorithms and Fault-Tolerant Quantum Computing

Variational quantum algorithms are not a replacement for fault-tolerant quantum computing, but the core algorithmic paradigm of the transition period (the NISQ era). Their relationship can be summarized as follows:

Feature	NISQ Variational Algorithms	Fault-Tolerant Quantum Algorithms
Circuit depth	$O(1)$ or $O(\log n)$	$O(\text{poly}(n))$
Qubit count	$10^2\text{--}10^3$	$10^6+$
Error rate tolerance	$10^{-2}$	$10^{-4}$ or lower
Classical optimization	Required	Not required
Application scenarios	Quantum chemistry, optimization	Factorization, large-molecule simulation

VQE’s application in quantum chemistry is considered the most promising area for achieving practical quantum utility on NISQ devices. While classical methods (such as density matrix renormalization group DMRG, coupled cluster CCSD(T)) are very accurate for small molecules, they fail for strongly correlated systems (such as transition metal catalysts, the Hubbard model of high-temperature superconductors), where VQE may offer a new computational pathway.

From a broader perspective, variational quantum algorithms represent a “pragmatic turn” in quantum computing: rather than waiting for a perfect fault-tolerant quantum computer, leverage existing (imperfect) quantum hardware, combined with classical computing, to solve scientifically and practically valuable problems. This hybrid paradigm may be the primary way quantum computing generates real-world impact in the coming decade.

Summary: Variational quantum algorithms adopt a quantum-classical hybrid architecture, using parameterized quantum circuits for state preparation and a classical optimizer for parameter updates. VQE exploits the variational principle $\langle\psi|H|\psi\rangle \geq E_0$ to estimate ground-state energies, with important applications in quantum chemistry. QAOA solves combinatorial optimization problems by alternately applying a problem Hamiltonian and a mixer Hamiltonian. Variational algorithms face three major challenges: barren plateaus (exponentially vanishing gradients), measurement sampling overhead $O(1/\epsilon^2)$ , and the circuit-depth vs. expressibility trade-off. They are the most promising practical quantum computing paradigm of the NISQ era.

Connection to Quantum Computing: Variational quantum algorithms bridge current NISQ hardware and future fault-tolerant quantum computers. They show how quantum computing can generate practical value under noise and scale constraints. From VQE’s quantum chemistry applications to QAOA’s combinatorial optimization, variational algorithms transform abstract quantum mechanical principles into computational tools for solving real problems. Understanding the principles, advantages, and limitations of variational algorithms is key to evaluating whether quantum computing can achieve “quantum advantage” in the near term. Whatever the future development of quantum hardware, the variational optimization philosophy—solving complex problems through the synergy of quantum state preparation and classical optimization—will continue to play an important role in quantum computing.

5.5 Introduction to Hamiltonian Simulation

Problem statement: Given a Hamiltonian $H$ (describing the total energy of a quantum system), compute the time evolution operator $U(t) = e^{-iHt}$ and simulate its effect on an initial state. This is one of the most promising applications of quantum computing—for quantum chemistry (molecular ground-state computation), materials science (electronic structure), and high-energy physics (lattice gauge theory).

Why classical simulation is hard: $H$ acts on a system of $n$ qubits, so its matrix size is $2^n \times 2^n$ —exponential. But $H$ is typically sparse (e.g., in quantum chemistry, $H = \sum t_{pq} a_p^\dagger a_q + \sum v_{pqrs} a_p^\dagger a_q^\dagger a_r a_s$ ), involving only a few terms.

Trotter decomposition (Trotter-Suzuki decomposition—the most basic method):

If $H = \sum_{j=1}^m H_j$ , and each $H_j$ is easy to simulate (e.g., Pauli strings acting on only a few qubits), then $e^{-iHt} \approx \left(\prod_{j=1}^m e^{-iH_j t/N}\right)^N$ where $N$ is the number of Trotter steps, with error $O(t^2/N)$ .
Physical intuition: slice time $t$ into $N$ small segments $t/N$ , and within each segment approximately assume that the $H_j$ commute
Complexity: $O(m^2 t^2/\epsilon)$ to achieve precision $\epsilon$

Higher-order Trotter methods:

Second-order decomposition: $e^{-i(A+B)\Delta t} \approx e^{-iA\Delta t/2} e^{-iB\Delta t} e^{-iA\Delta t/2}$
Fourth-order decomposition: by nesting second-order decompositions, the error drops from $O(\Delta t^2)$ to $O(\Delta t^4)$

Post-Trotter methods (recent breakthroughs):

Quantum Signal Processing: achieves optimal $O(t + \log(1/\epsilon))$ complexity via the Quantum Singular Value Transformation (QSVT)
Taylor series method: expand $e^{-iHt}$ as a Taylor series, implemented via Linear Combination of Unitaries (LCU)
Quantum walk method: reformulate Hamiltonian simulation as a quantum walk problem

Applications:

Quantum chemistry: simulating the electronic structure of molecules $H_2$ , LiH, Fe $_2$ S $_2$ (already experimentally demonstrated at small scale)
Condensed matter physics: ground states and dynamics of the Hubbard model and t-J model
High-energy physics: simulation of the Schwinger model and lattice QED

Current limitations:

Practically useful quantum chemistry simulations require $10^6\text{-}10^8$ quantum gates, far beyond current hardware capabilities
The resource overhead after error correction remains enormous (potentially thousands of logical qubits running for thousands of hours)
The coupling between Trotter error and gate fidelity requires further study

Summary: Hamiltonian simulation aims to compute the time evolution operator $e^{-iHt}$ , and is the most promising application of quantum computing in quantum chemistry, materials science, and high-energy physics. Classical simulation is difficult due to the exponential matrix size, but Hamiltonians are typically sparse. Trotter decomposition splits the total Hamiltonian into a product of easily simulable terms—the most basic method; higher-order Trotter methods reduce error through symmetrized decompositions. Recent breakthroughs include Quantum Signal Processing (QSVT), the Taylor series method, and quantum walk methods, achieving better complexity. Current limitations are that practically useful simulation scales require far more gates than existing hardware can deliver, and the resource overhead after error correction remains enormous.

Connection to Quantum Computing: Hamiltonian simulation is one of the strongest candidates for a “killer application” of quantum computing. It directly leverages the natural evolution of quantum systems to simulate other quantum systems, avoiding the exponential storage and computation bottlenecks of classical computers. From Trotter decomposition to Quantum Signal Processing, the development of Hamiltonian simulation demonstrates how quantum algorithms, starting from basic physical intuition, achieve complexity breakthroughs through mathematical deepening. It is closely linked to variational quantum algorithms (such as VQE): VQE is used for finding ground-state energies, while Hamiltonian simulation is used for studying system dynamics. Understanding the principles and limitations of Hamiltonian simulation is key to evaluating whether quantum computing can deliver practical advantages in quantum chemistry and materials science.

Chapter 5 Summary

This chapter completes the knowledge puzzle of advanced quantum computing topics across five key dimensions:

§5.3.4 Quantum error mitigation (ZNE, PEC, virtual distillation) fills the core gap of “how to run algorithms when error correction is unavailable” in the NISQ era
§5.1–5.2 QFT circuit implementation and QPE constitute the algorithmic engine of Shor’s algorithm and quantum simulation, the technical core of quantum exponential speedup
§5.3 Noise models (Kraus operators, depolarizing/bit-flip/phase-flip/amplitude damping channels) provide the language for understanding the physical limitations of real quantum hardware
§5.4 Variational quantum algorithms (VQE, QAOA) demonstrate the practical value of the quantum-classical hybrid paradigm in the NISQ era
§5.5 Hamiltonian simulation, as a candidate for quantum computing’s “killer application,” connects algorithmic theory to real-world application scenarios

The common theme of these five topics is: the core challenges quantum computing faces in transitioning from theory to practice—noise, decoherence, error-correction overhead, and algorithmic design constraints. Having mastered these topics, the reader can now not only understand “how quantum computing works,” but also evaluate “when and in what way quantum computing will generate practical value.”

Appendix

Quantum Algorithms in Detail: From Principles to Circuit Implementation

Supplementary Material — Deepening and extension of §3.6 of the quantum computing primer (Part 3)

This document provides complete mathematical derivations, circuit constructions, complexity proofs, and worked examples for the five core quantum algorithms outlined in §3.6 (Introduction to Quantum Algorithms) of the tutorial. Readers should have completed Parts 1–3 of the tutorial and be familiar with complex numbers, linear algebra, qubits, quantum gates, quantum circuits, and the basic concepts of the Quantum Fourier Transform (QFT).

Part 5.1 (QFT Circuit Implementation) and Part 5.2 (Quantum Phase Estimation, QPE) will be directly referenced by Shor’s algorithm.

Deutsch-Jozsa Algorithm
Bernstein-Vazirani Algorithm (supplementary)
Simon’s Algorithm (supplementary)
Grover’s Search Algorithm
Shor’s Factoring Algorithm
Algorithm Complexity Comparison Table
References and Further Reading

1. Deutsch-Jozsa Algorithm

1.1 Problem Definition and Classical Complexity

Problem: Given a Boolean function $f: \{0,1\}^n \to \{0,1\}$ , with the promise that $f$ is either a constant function (for all $x \in \{0,1\}^n$ , $f(x)$ takes the same value) or a balanced function (outputs 0 for exactly half of the inputs and 1 for the other half). Determine whether $f$ is constant or balanced.

Classical complexity analysis (worst case):

Deterministic algorithm: in the worst case, requires $2^{n-1}+1$ queries. Because even if the first $2^{n-1}$ queries all yield the same result, one still cannot conclude that $f$ is constant—it is possible that the remaining $2^{n-1}$ queries all yield the opposite result, making $f$ exactly balanced. Only after querying the $(2^{n-1}+1)$ -th input and getting the same result can one be certain that $f$ is constant. Hence the deterministic query complexity is $\Theta(2^n)$ .
Randomized algorithm: if one accepts a probability of error, it can be more efficient. But the worst case still requires an exponential number of queries.

Quantum complexity: only 1 query. This was the first quantum algorithm to demonstrate an exponential speedup (albeit for an artificially constructed problem).

1.2 Oracle Construction

In quantum algorithms, the function $f$ is not passively queried as a “black box,” but is realized as a unitary operator via a quantum oracle. The oracle is a basic component of quantum circuits: it encodes the function $f$ as a reversible unitary transformation.

The standard Deutsch-Jozsa oracle implementation takes the phase oracle form:

U_f: \lvert x\rangle \lvert y\rangle \;\longmapsto\; \lvert x\rangle \lvert y \oplus f(x)\rangle

where $\lvert x\rangle$ is the $n$ -bit input register, $\lvert y\rangle$ is a single-bit output register, and $\oplus$ denotes addition modulo 2 (XOR).

Matrix representation: $U_f$ in the computational basis $\{\lvert x\rangle\lvert y\rangle\}$ is a diagonal matrix plus swap operations. Specifically, for each $x$ :

If $f(x)=0$ : $U_f\lvert x\rangle\lvert y\rangle = \lvert x\rangle\lvert y\rangle$ (unchanged)
If $f(x)=1$ : $U_f\lvert x\rangle\lvert 0\rangle = \lvert x\rangle\lvert 1\rangle$ , $U_f\lvert x\rangle\lvert 1\rangle = \lvert x\rangle\lvert 0\rangle$ (applies an $X$ gate on the output qubit)

Unitarity verification of $U_f$ : $U_f^2 = I$ , because two XOR operations restore the original state. $U_f$ is also a permutation matrix (exactly one 1 per row and column), so it is clearly unitary.

1.3 Phase Kickback Mechanism

Phase kickback is the core technique of the Deutsch-Jozsa algorithm and many other quantum algorithms. Its key insight is: preparing the oracle’s target qubit in the $\lvert-\rangle$ state causes the function value $f(x)$ to be “kicked back” into the phase of the input register.

Derivation:

Initialize the output register to $\lvert1\rangle$ and apply an $H$ gate, yielding:

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

Now examine the action of $U_f$ on $\lvert x\rangle\lvert-\rangle$ :

$U_f\lvert x\rangle\lvert-\rangle = \lvert x\rangle \cdot \frac{1}{\sqrt{2}}\big(\lvert0 \oplus f(x)\rangle - \lvert1 \oplus f(x)\rangle\big)$

Consider two cases:

Case A — $f(x) = 0$ : $\frac{1}{\sqrt{2}}(\lvert0 \oplus 0\rangle - \lvert1 \oplus 0\rangle) = \frac{1}{\sqrt{2}}(\lvert0\rangle - \lvert1\rangle) = \lvert-\rangle$

Case B — $f(x) = 1$ : $\frac{1}{\sqrt{2}}(\lvert0 \oplus 1\rangle - \lvert1 \oplus 1\rangle) = \frac{1}{\sqrt{2}}(\lvert1\rangle - \lvert0\rangle) = -\lvert-\rangle$

Combining both cases:

U_f\lvert x\rangle\lvert-\rangle = (-1)^{f(x)}\lvert x\rangle\lvert-\rangle

This is phase kickback: the function value $f(x)$ appears as $(-1)^{f(x)}$ in the global phase of the input register $\lvert x\rangle$ , while the output register $\lvert-\rangle$ is completely unchanged (and can be discarded). In other words, the oracle acts equivalently as:

U_f^{\text{phase}}: \lvert x\rangle \;\longmapsto\; (-1)^{f(x)}\lvert x\rangle

At this point the oracle has degenerated into a diagonal unitary matrix $U_f^{\text{phase}} = \text{diag}((-1)^{f(0\cdots0)}, (-1)^{f(0\cdots1)}, \ldots, (-1)^{f(1\cdots1)})$ .

Physical intuition: the output register $\lvert-\rangle$ plays the role of a “phase reference.” When the oracle attempts to flip $\lvert-\rangle$ (the $f(x)=1$ case), because the two components $\lvert0\rangle$ and $\lvert1\rangle$ of $\lvert-\rangle$ are flipped with opposite sign, the overall state acquires a $-1$ global phase. This phase, due to the reversibility of the gate, is “kicked back” onto the input register.

1.4 Complete Description of the Deutsch-Jozsa Algorithm

Circuit Diagram ( $n$ bits, standard notation)

|0⟩^⊗n —H^⊗n—•—H^⊗n—[M]
               |
|1⟩ —————H—— ⊕ ——————

where:

The upper $n$ lines are the input register, initialized to $\lvert0\rangle^{\otimes n}$
The lower line is the auxiliary qubit (output register), initialized to $\lvert1\rangle$
The line between $\bullet$ and $\oplus$ represents the $U_f$ oracle (a collection of controlled operations)
$[M]$ denotes measurement in the computational basis
$H^{\otimes n}$ denotes $n$ parallel $H$ gates

Step-by-step derivation

Step 0 — Initialization: $\lvert\psi_0\rangle = \lvert0\rangle^{\otimes n} \otimes \lvert1\rangle$

Step 1 — Apply $H$ to the auxiliary qubit: $\lvert\psi_1\rangle = \lvert0\rangle^{\otimes n} \otimes \lvert-\rangle$

Step 2 — Apply $H^{\otimes n} \otimes I$ to all $n+1$ qubits (i.e., $n$ parallel $H$ gates on the input register):

Recall the action of $H^{\otimes n}\lvert0\rangle^{\otimes n}$ : $H^{\otimes n}\lvert0\rangle^{\otimes n} = \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}\lvert x\rangle$

This is because $H\lvert0\rangle = \frac{1}{\sqrt{2}}(\lvert0\rangle + \lvert1\rangle)$ , and the tensor product expansion yields an equal superposition of all $2^n$ computational basis states. Hence:

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

Step 3 — Apply the oracle $U_f$ :

Using phase kickback:

$\lvert\psi_3\rangle = \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}(-1)^{f(x)}\lvert x\rangle \otimes \lvert-\rangle$

This is the critical step: a single oracle call simultaneously marks the function values of all $2^n$ inputs.

Step 4 — Apply a second $H^{\otimes n}$ to the input register:

We need the explicit form of $H^{\otimes n}\lvert x\rangle$ . Recall $H\lvert 0\rangle = \lvert+\rangle$ , $H\lvert 1\rangle = \lvert-\rangle$ . For $n$ bits, for a single basis state $\lvert x\rangle = \lvert x_1x_2\ldots x_n\rangle$ :

$H^{\otimes n}\lvert x\rangle = \frac{1}{\sqrt{2^n}}\sum_{z=0}^{2^n-1}(-1)^{x \cdot z}\lvert z\rangle$

where $x \cdot z = \sum_{i=1}^n x_i z_i \pmod{2}$ is the bitwise inner product (mod 2 addition).

Proof of this formula: $H\lvert x_i\rangle = \frac{1}{\sqrt{2}}(\lvert0\rangle + (-1)^{x_i}\lvert1\rangle)$ , therefore:

$H^{\otimes n}\lvert x_1\ldots x_n\rangle = \bigotimes_{i=1}^n\frac{1}{\sqrt{2}}(\lvert0\rangle + (-1)^{x_i}\lvert1\rangle) = \frac{1}{\sqrt{2^n}}\sum_{z_1,\ldots,z_n\in\{0,1\}}(-1)^{\sum_i x_i z_i}\lvert z_1\ldots z_n\rangle = \frac{1}{\sqrt{2^n}}\sum_{z=0}^{2^n-1}(-1)^{x \cdot z}\lvert z\rangle$

Now apply the second $H^{\otimes n}$ to the input register of $\lvert\psi_3\rangle$ :

$\lvert\psi_4\rangle = \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}(-1)^{f(x)}\left(H^{\otimes n}\lvert x\rangle\right) \otimes \lvert-\rangle$

$= \frac{1}{2^n}\sum_{x=0}^{2^n-1}(-1)^{f(x)}\sum_{z=0}^{2^n-1}(-1)^{x\cdot z}\lvert z\rangle \otimes \lvert-\rangle$

$= \sum_{z=0}^{2^n-1}\underbrace{\left(\frac{1}{2^n}\sum_{x=0}^{2^n-1}(-1)^{f(x)+x\cdot z}\right)}_{\text{amplitude } \alpha_z}\lvert z\rangle \otimes \lvert-\rangle$

Step 5 — Measure the input register:

Measuring $\lvert z\rangle$ yields an outcome $z \in \{0,1\}^n$ . The key question: can we determine from the measurement outcome whether $f$ is constant or balanced?

1.5 Correctness Proof

Theorem: In the above algorithm, if $f$ is a constant function, then with probability $1$ the measurement yields $z = 00\ldots 0$ ; if $f$ is a balanced function, the probability of measuring $z = 00\ldots 0$ is $0$ .

Proof:

Consider the amplitude $\alpha_0$ of $\lvert 00\ldots 0\rangle$ (corresponding to $z = 0$ ):

$\alpha_0 = \frac{1}{2^n}\sum_{x=0}^{2^n-1}(-1)^{f(x)}(-1)^{x\cdot 0} = \frac{1}{2^n}\sum_{x=0}^{2^n-1}(-1)^{f(x)}$

since $x \cdot 0 = 0$ for all $x$ .

Case 1 — $f$ is a constant function:

If $f(x) = 0$ for all $x$ , then $(-1)^{f(x)} = 1$ , $\alpha_0 = \frac{1}{2^n} \cdot 2^n = 1$
If $f(x) = 1$ for all $x$ , then $(-1)^{f(x)} = -1$ , $\alpha_0 = \frac{1}{2^n} \cdot (-2^n) = -1$

In both cases $|\alpha_0|^2 = 1$ , so the measurement yields $00\ldots 0$ with probability $1$ .

Case 2 — $f$ is a balanced function: Exactly half of the inputs have $f(x)=0$ and half have $f(x)=1$ . Therefore:

$\sum_{x=0}^{2^n-1}(-1)^{f(x)} = \frac{2^n}{2} \cdot (+1) + \frac{2^n}{2} \cdot (-1) = 0$

So $\alpha_0 = 0$ , and the probability of measuring $00\ldots 0$ is zero.

Corollary: if the measurement yields $z \neq 0$ , then $f$ must be balanced; if the measurement yields $z = 0$ , then $f$ must be constant. A single query, deterministic decision! $\blacksquare$

1.6 Worked Example: $n=2$ (Deutsch’s Algorithm)

For $n=2$ , the input is $\lvert x_1x_2\rangle$ , with $x \in \{0,1,2,3\}$ .

Example A: Constant function $f(x) = 0$

$x$	$f(x)$	$(-1)^{f(x)}$
00	0	+1
01	0	+1
10	0	+1
11	0	+1

State after step 3: $\lvert\psi_3\rangle = \frac{1}{2}\big(+\lvert00\rangle + \lvert01\rangle + \lvert10\rangle + \lvert11\rangle\big)\lvert-\rangle$

Step 4 (second $H^{\otimes 2}$ ):

$H^{\otimes 2}\lvert00\rangle = \frac{1}{2}(\lvert00\rangle + \lvert01\rangle + \lvert10\rangle + \lvert11\rangle)$ $H^{\otimes 2}\lvert01\rangle = \frac{1}{2}(\lvert00\rangle - \lvert01\rangle + \lvert10\rangle - \lvert11\rangle)$ $H^{\otimes 2}\lvert10\rangle = \frac{1}{2}(\lvert00\rangle + \lvert01\rangle - \lvert10\rangle - \lvert11\rangle)$ $H^{\otimes 2}\lvert11\rangle = \frac{1}{2}(\lvert00\rangle - \lvert01\rangle - \lvert10\rangle + \lvert11\rangle)$

$\lvert\psi_4\rangle = \frac{1}{2}\big(H^{\otimes 2}\lvert00\rangle + H^{\otimes 2}\lvert01\rangle + H^{\otimes 2}\lvert10\rangle + H^{\otimes 2}\lvert11\rangle\big)\lvert-\rangle$

Combining like terms, the coefficient of $\lvert00\rangle$ is: $\frac{1}{2}\left(\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+\frac{1}{2}\right) = 1$

The coefficients of the other $\lvert z \neq 0\rangle$ are 0. Therefore $\lvert\psi_4\rangle = \lvert00\rangle\lvert-\rangle$ , and the measurement inevitably yields $00$ .

Example B: Balanced function $f(x) = x_1$ (value of the first bit)

$x$	$f(x)$	$(-1)^{f(x)}$
00	0	+1
01	0	+1
10	1	-1
11	1	-1

State after step 3: $\lvert\psi_3\rangle = \frac{1}{2}\big(+\lvert00\rangle + \lvert01\rangle - \lvert10\rangle - \lvert11\rangle\big)\lvert-\rangle$

Step 4: $\lvert\psi_4\rangle = \frac{1}{2}\big(H^{\otimes 2}\lvert00\rangle + H^{\otimes 2}\lvert01\rangle - H^{\otimes 2}\lvert10\rangle - H^{\otimes 2}\lvert11\rangle\big)\lvert-\rangle$

Coefficient of $\lvert00\rangle$ : $\frac{1}{2}\left(\frac{1}{2}+\frac{1}{2}-\frac{1}{2}-\frac{1}{2}\right) = 0$

Coefficient of $\lvert10\rangle$ : $\frac{1}{2}\left(\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+\frac{1}{2}\right) = 1$

Therefore $\lvert\psi_4\rangle = \lvert10\rangle\lvert-\rangle$ , and the measurement yields $10$ (nonzero), confirming $f$ is a balanced function. Correct!

Example C: Balanced function $f(x) = x_1 \oplus x_2$ (XOR)

$x$	$f(x)$	$(-1)^{f(x)}$
00	0	+1
01	1	-1
10	1	-1
11	0	+1

Step 3: $\lvert\psi_3\rangle = \frac{1}{2}\big(+\lvert00\rangle - \lvert01\rangle - \lvert10\rangle + \lvert11\rangle\big)\lvert-\rangle$

Step 4, coefficient of $\lvert00\rangle$ : $\frac{1}{2}\left(\frac{1}{2}-\frac{1}{2}-\frac{1}{2}+\frac{1}{2}\right) = 0$

The measurement inevitably yields a nonzero result. Note that different balanced functions produce different $z$ patterns, but the algorithm only needs to check whether the outcome is all zeros.

1.7 Worked Example: $n=3$ Circuit

|0⟩ —H—•—H—[M]—
|0⟩ —H—•—H—[M]—
|0⟩ —H—•—H—[M]—
        |
|1⟩ —H—⊕——————

The input space $\{0,1\}^3$ has 8 elements.

Constant function example $f(x)=1$ : $\lvert\psi_3\rangle = \frac{-1}{\sqrt{8}}\sum_{x=0}^{7}\lvert x\rangle\lvert-\rangle$

$\lvert\psi_4\rangle = -\lvert000\rangle\lvert-\rangle$

Measured probability distribution: $P(000) = 1$ , $P(\text{other}) = 0$ .

Balanced function example $f(x) = x_1 \land x_2 \land x_3$ (AND of three bits, $f=1$ only when $x=111$ , otherwise $f=0$ ):

Is this function balanced? No—the AND function outputs 1 for only 1 out of 8 inputs and 0 for 7 inputs—it is neither constant nor balanced, and therefore falls outside the promise of the Deutsch-Jozsa problem. The Deutsch-Jozsa algorithm is only valid for functions satisfying the “constant or balanced” promise.

A valid balanced function example: $f(x) = x_1$ (depends only on the first bit). Then out of 8 inputs, half (the 4 with $x_1=0$ ) output 0, and half (the 4 with $x_1=1$ ) output 1.

1.8 Complexity Analysis

Quantum complexity:

Quantum gate count: $O(n)$ single-qubit gates ( $2n+1$ $H$ gates) + 1 oracle call
Circuit depth: $O(n)$ ( $H$ gates can be executed in parallel)
Total complexity: $O(n)$

Classical complexity (deterministic):

Worst case: $2^{n-1}+1$ queries
Exponential gap! For $n=100$ , classical requires $\sim 2^{99} \approx 6 \times 10^{29}$ queries (infeasible), while quantum requires only about 200 gates.

Important note: The problem solved by the Deutsch-Jozsa algorithm has the promise structure of “constant or balanced,” and the function is a promise problem rather than a general decision problem. It is not a “practical” algorithm, but it is the perfect pedagogical example of quantum algorithm design philosophy: superposition → parallel evaluation → interference → extraction of global information.

2. Bernstein-Vazirani Algorithm

2.1 Problem Definition

Problem: Given a function $f_s: \{0,1\}^n \to \{0,1\}$ of the form $f_s(x) = s \cdot x \pmod{2}$ , where $s \in \{0,1\}^n$ is a hidden bit string and $s \cdot x = \sum_{i=1}^n s_i x_i$ is the bitwise inner product. Find $s$ .

Classical complexity: query each bit individually. Set $x = 100\ldots 0$ to obtain $f_s(x) = s_1$ ; set $x = 010\ldots 0$ to obtain $s_2$ ; and so on. A total of $n$ queries are needed.

Quantum complexity: only 1 query.

2.2 Algorithm Circuit

The Bernstein-Vazirani algorithm is almost identical to the Deutsch-Jozsa algorithm; the only difference lies in how the measurement outcome is interpreted.

|0⟩^⊗n —H^⊗n—•—H^⊗n—[M] → s (read out directly!)
               |
|1⟩ —————H—— ⊕ ——————

where the oracle implements $U_{f_s}: \lvert x\rangle\lvert y\rangle \to \lvert x\rangle\lvert y \oplus (s \cdot x)\rangle$ .

2.3 Complete Mathematical Derivation

Steps 0–3 are exactly the same as in Deutsch-Jozsa. The state after the oracle call is:

$\lvert\psi_3\rangle = \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}(-1)^{s \cdot x}\lvert x\rangle\lvert-\rangle$

Step 4 — Apply the second $H^{\otimes n}$ :

Recall $H^{\otimes n}\lvert x\rangle = \frac{1}{\sqrt{2^n}}\sum_{z=0}^{2^n-1}(-1)^{x \cdot z}\lvert z\rangle$ . Therefore:

$\lvert\psi_4\rangle = \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}(-1)^{s\cdot x}\frac{1}{\sqrt{2^n}}\sum_{z=0}^{2^n-1}(-1)^{x \cdot z}\lvert z\rangle\lvert-\rangle$

$= \frac{1}{2^n}\sum_{z=0}^{2^n-1}\left(\sum_{x=0}^{2^n-1}(-1)^{(s\oplus z)\cdot x}\right)\lvert z\rangle\lvert-\rangle$

where $s \oplus z$ is the bitwise XOR. Note that the sum $\sum_{x}(-1)^{t\cdot x}$ equals $2^n$ if and only if $t = 0$ (since $(-1)^0 + (-1)^0 + \cdots = 2^n$ ), and is $0$ otherwise.

Therefore:

$\lvert\psi_4\rangle = \lvert s\rangle\lvert-\rangle$

Step 5 — Measure the input register, directly obtaining every bit of $s$ !

Intuitive explanation: quantum parallelism evaluates all inputs at once; interference constructs the Fourier-transformed form of the hidden bit string $s$ ; the second $H^{\otimes n}$ performs the inverse Fourier transform, focusing the information about $s$ onto a single quantum state.

2.4 Worked Example

Let $n=3$ , $s = 101$ (i.e., $f(x) = x_1 + x_3 \pmod{2}$ ).

State after the oracle call: $\lvert\psi_3\rangle = \frac{1}{\sqrt{8}}\sum_{x\in\{0,1\}^3}(-1)^{x_1 + x_3}\lvert x\rangle\lvert-\rangle$

Explicit expansion (only listing terms with $(-1)^{f(x)} = -1$ , i.e., inputs where $x_1+x_3$ is odd):

$x$	$(-1)^{f(x)}$
001	-1
010	+1
011	-1
100	-1
101	+1
110	-1
111	+1

After the second $H^{\otimes 3}$ , all amplitudes except $\lvert101\rangle$ interfere destructively, and the measurement yields $101$ .

2.5 Relationship Between Bernstein-Vazirani and Deutsch-Jozsa

BV is the “parameterized” version of DJ: DJ decides whether $f$ is constant or balanced; BV finds the hidden parameter $s$ of $f$
BV’s oracle structure is more specific (a linear function rather than an arbitrary constant/balanced function)
BV demonstrates the idea of quantum Fourier sampling: using the Fourier transform to convert hidden structure into measurable peaks
Both algorithms share the same circuit, but BV provides a stronger result (finding $s$ , not just classifying)

Complexity comparison:

Algorithm	Classical queries	Quantum queries	Speedup
Deutsch-Jozsa	$2^{n-1}+1$	1	Exponential
Bernstein-Vazirani	$n$	1	$n$ -fold

BV’s speedup is “linear” ( $n$ -fold), not exponential. But as a quantum algorithm design template, it has pedagogical importance comparable to DJ.

3. Simon’s Algorithm

3.1 Problem Definition

Problem: Given a function $f: \{0,1\}^n \to \{0,1\}^{n}$ (the output is also $n$ bits), with the promise that there exists a hidden nonzero bit string $s \in \{0,1\}^n$ such that for all $x, y \in \{0,1\}^n$ :

$f(x) = f(y) \iff y = x \oplus s$

i.e., $f$ is two-to-one, and the colliding pairs differ exactly by $s$ . Find $s$ .

Geometric understanding: the input space $\{0,1\}^n$ is partitioned into $2^{n-1}$ “pairs” $\{x, x\oplus s\}$ , with each pair sharing the same function value. The goal is to find the hidden period $s$ that determines this pairing structure.

Classical complexity: in the worst case, $\Theta(2^{n/2})$ queries are needed (by the birthday paradox).

Quantum complexity: $O(n)$ queries—an exponential speedup!

3.2 Simon’s Algorithm Circuit

The core idea of Simon’s algorithm shares a deep similarity with DJ/BV: superposition → oracle → Hadamard → measurement. But Simon requires multiple runs to collect linear equations.

Single-run circuit:

|0⟩^⊗n —H^⊗n—•—H^⊗n—[M] → random z
               |
|0⟩^⊗n ——————⊕—————      → discarded (measurement used for verification)

where the oracle $U_f: \lvert x\rangle\lvert y\rangle \to \lvert x\rangle\lvert y \oplus f(x)\rangle$ .

3.3 Step-by-Step Derivation

Step 0: $\lvert\psi_0\rangle = \lvert0\rangle^{\otimes n} \otimes \lvert0\rangle^{\otimes n}$

Step 1 — Apply $H^{\otimes n}$ to the first register: $\lvert\psi_1\rangle = \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}\lvert x\rangle \otimes \lvert0\rangle^{\otimes n}$

Step 2 — Apply the oracle: $\lvert\psi_2\rangle = \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}\lvert x\rangle\lvert f(x)\rangle$

Step 3 — Apply a second $H^{\otimes n}$ to the first register:

$\lvert\psi_3\rangle = \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}\left(\frac{1}{\sqrt{2^n}}\sum_{z=0}^{2^n-1}(-1)^{x\cdot z}\lvert z\rangle\right)\lvert f(x)\rangle$

$= \frac{1}{2^n}\sum_{z=0}^{2^n-1}\sum_{x=0}^{2^n-1}(-1)^{x\cdot z}\lvert z\rangle\lvert f(x)\rangle$

Step 4 — Measure the first register. The probability of measuring a particular $z$ is:

$P(z) = \left\|\frac{1}{2^n}\sum_{x=0}^{2^n-1}(-1)^{x\cdot z}\lvert f(x)\rangle\right\|^2$

Since $f$ is two-to-one, each $f(x)$ corresponds to two $x$ values: $x_0$ and $x_0 \oplus s$ . Therefore:

$P(z) = \left\|\frac{1}{2^n}\sum_{\text{each pair }\{x,x\oplus s\}}(-1)^{x\cdot z}\lvert f(x)\rangle\right\|^2$

For any “pair” $\{x, x\oplus s\}$ , its contribution is:

$\frac{1}{2^n}\left[(-1)^{x\cdot z} + (-1)^{(x\oplus s)\cdot z}\right]\lvert f(x)\rangle = \frac{1}{2^n}(-1)^{x\cdot z}\left[1 + (-1)^{s\cdot z}\right]\lvert f(x)\rangle$

Key:

If $s\cdot z = 1$ , then $1 + (-1) = 0$ , and the contribution of that pair is zero
If $s\cdot z = 0$ , then $1 + 1 = 2$ , and the contribution of that pair is nonzero

Thus, $P(z) > 0$ only when $s \cdot z = 0 \pmod{2}$ ; otherwise $P(z) = 0$ .

Conclusion: each run of Simon’s algorithm yields a random $z$ satisfying $s \cdot z = 0$ . In particular, $P(z=0) = 2^{-n+1}$ , $P(z=s) = 2^{-n+1}$ .

3.4 Recovering $s$ from Measurement Outcomes

A single run yields one $z$ satisfying $s \cdot z = 0$ . This is one linear equation in $s$ . Run $O(n)$ times, collecting $n-1$ linearly independent $z$ values:

$z_1 \cdot s = 0$ $z_2 \cdot s = 0$ $\vdots$ $z_{n-1} \cdot s = 0$

This constitutes a system of linear equations over $GF(2)$ . Solve for the nonzero solution $s$ (and the trivial solution $s=0$ ). Since $s \neq 0$ is the promise condition, we take the nonzero solution.

Required number of runs: in $GF(2)^n$ , the probability that $m$ randomly and uniformly chosen $n$ -dimensional vectors span an $(n-1)$ -dimensional subspace (the orthogonal complement of $s$ ) is:

$P(\text{success}) = \prod_{k=1}^{n-1}(1-2^{k-1-m})$

Taking $m = n + O(1)$ makes the success probability approach 1. Classical post-processing is completed in $O(n^3)$ (Gaussian elimination).

3.5 Worked Example: $n=2$ , $s = 11$

Function definition (example with the promise):

$x$	$f(x)$
00	01
01	10
10	10
11	01

Verification: $f(00)=f(11)$ , $f(01)=f(10)$ , and $00\oplus 11 = 11$ , $01\oplus 10 = 11$ . So $s=11$ .

Run 1: suppose $z = 11$ is measured. Equation: $11 \cdot s = s_1 + s_2 = 0 \pmod{2}$ .

Run 2: suppose $z = 10$ is measured. Equation: $10 \cdot s = s_1 = 0 \pmod{2}$ .

From $s_1 = 0$ and $s_1 + s_2 = 0$ we obtain $s_2 = 0$ . But this gives $s=00$ , contradicting the promise ( $s\neq 0$ ). What went wrong? The collected equations are not independent! In fact, the second equation $s_1=0$ already implies $s_1=0$ , and combined with the first equation yields $s_2=0$ , but we know $s=11$ .

This reveals a key point: the distribution of measurement outcomes $z$ in Simon’s algorithm is uniform (among those $z$ satisfying $s\cdot z=0$ ). It is possible that all sampled $z$ belong to the 1-dimensional subspace $\{00, 11\}$ —in that case we only obtain the single equation $s_1 + s_2 = 0$ , and need more runs.

Run 3: $z = 01$ is measured. Equation: $01 \cdot s = s_2 = 0$ .

Now $s_1=0, s_2=0$ still gives $00$ . Still a contradiction! This shows that all measured $z$ come from the orthogonal complement of $s$ , which is $\{00\}$ —if every measurement yields $00$ (probability is small but nonzero), we need even more runs.

In practice, we need at least $n-1=1$ independent nonzero equation to constrain $s$ . The orthogonal complement of $s$ is $(n-1)$ -dimensional, and measurements sample uniformly from it. The expected number of runs to find $n-1$ linearly independent vectors is $O(n)$ . Once we find a nonzero $s$ , we are done.

3.6 Complexity Analysis

Quantum complexity:

Per run: $O(n)$ gates + 1 oracle call
Number of runs: $O(n)$ (in expectation)
Total oracle calls: $O(n)$

Classical complexity:

Deterministic: $\Theta(2^{n/2})$ function evaluations (finding a collision via the birthday paradox)
Randomized: also requires $\Omega(2^{n/2})$

Exponential speedup: Simon’s algorithm was the first to demonstrate an exponential quantum speedup (more convincing than Deutsch-Jozsa’s “promise-based exponential” speedup, because the problem is more natural). It directly inspired Shor’s algorithm—Simon’s “hidden subgroup” framework directly generalizes to finite abelian groups, and Shor’s period finding is the generalization of Simon’s problem to the group $\mathbb{Z}$ .

3.7 Simon’s Problem and the Hidden Subgroup Problem

Simon’s problem is an instance of the Hidden Subgroup Problem (HSP) on the group $(\mathbb{Z}_2)^n$ :

Group $G = (\mathbb{Z}_2)^n$
Hidden subgroup $H = \{0, s\}$ (a subgroup of order 2)
The function $f$ is constant on the cosets of $H$
Goal: find a generator $s$ of $H$

The period-finding problem in Shor’s factoring algorithm corresponds to an instance of HSP on the group $\mathbb{Z}$ . This unified framework reveals the deep connection between Simon’s and Shor’s algorithms.

4. Grover’s Search Algorithm

4.1 Problem Definition

Problem: Among $N = 2^n$ unstructured data items, find the item satisfying a certain condition—the “marked” item. Assume there is a unique marked item $x^*$ , which can be tested via oracle queries.

Formalization: there exists an oracle function $f: \{0,1\}^n \to \{0,1\}$ , where $f(x) = 1$ if and only if $x = x^*$ (the marked item), and $f(x) = 0$ otherwise. Find $x^*$ by querying $f$ .

Classical complexity: sequential search requires on average $N/2$ queries, and worst-case $N$ queries.

Quantum complexity: $O(\sqrt{N})$ queries (roughly $\frac{\pi}{4}\sqrt{N}$ iterations), a quadratic speedup.

4.2 Oracle Construction

Similar to Deutsch-Jozsa, the Grover oracle is implemented via phase kickback:

$U_f\lvert x\rangle\lvert-\rangle = (-1)^{f(x)}\lvert x\rangle\lvert-\rangle$

For the marked item $x^*$ , $f(x^*) = 1$ , so a $-1$ phase is applied; for other $x$ , the phase is unchanged.

At the circuit level, the Grover oracle can be written as:

$U_{\text{oracle}} = I - 2\lvert x^*\rangle\langle x^*\rvert$

i.e., it applies a phase flip $(-1)$ to the marked state $\lvert x^*\rangle$ , while leaving all other states unchanged.

Verification: $(I - 2\lvert x^*\rangle\langle x^*\rvert)\lvert x^*\rangle = \lvert x^*\rangle - 2\lvert x^*\rangle = -\lvert x^*\rangle$ ; while for $\lvert x \neq x^*\rangle$ , $(I - 2\lvert x^*\rangle\langle x^*\rvert)\lvert x\rangle = \lvert x\rangle$ .

4.3 Mathematical Derivation of the Diffusion Operator

The second key component of Grover’s algorithm is the diffusion operator (also called “inversion about the mean”):

$U_{\text{diff}} = 2\lvert \psi\rangle\langle\psi\rvert - I$

where $\lvert\psi\rangle = H^{\otimes n}\lvert0\rangle^{\otimes n} = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\lvert x\rangle$ is the equal superposition of all basis states.

Why is it called “inversion about the mean”?

Let $a_x$ be the amplitude of $\lvert x\rangle$ . The action of $U_{\text{diff}}$ on the state $\sum_x a_x\lvert x\rangle$ is:

$U_{\text{diff}}\sum_x a_x\lvert x\rangle = (2\lvert\psi\rangle\langle\psi\rvert - I)\sum_x a_x\lvert x\rangle$

$= 2\lvert\psi\rangle\sum_x a_x\langle\psi\rvert x\rangle - \sum_x a_x\lvert x\rangle$

where $\langle\psi\rvert x\rangle = \frac{1}{\sqrt{N}}$ , so $\sum_x a_x\langle\psi\rvert x\rangle = \frac{1}{\sqrt{N}}\sum_x a_x = \sqrt{N}\cdot\bar{a}$ , with $\bar{a} = \frac{1}{N}\sum_x a_x$ being the average amplitude.

Therefore:

$U_{\text{diff}}\sum_x a_x\lvert x\rangle = 2\lvert\psi\rangle\sqrt{N}\bar{a} - \sum_x a_x\lvert x\rangle$

$= 2\sum_x \bar{a}\lvert x\rangle - \sum_x a_x\lvert x\rangle$

$= \sum_x (2\bar{a} - a_x)\lvert x\rangle$

This is precisely “inversion about the mean”: each amplitude $a_x$ is replaced by $2\bar{a} - a_x$ . If $a_x$ is below the mean, it is “boosted”; if above the mean, it is “suppressed.” The effect of this operation is: amplify amplitudes above the mean, shrink amplitudes below the mean.

Circuit implementation: $U_{\text{diff}} = H^{\otimes n} (2\lvert0\rangle\langle0\rvert - I) H^{\otimes n}$ , where $2\lvert0\rangle\langle0\rvert - I$ is the “zero-state phase flip”: it applies a $-1$ phase to $\lvert0\rangle^{\otimes n}$ and leaves other states unchanged.

Circuit for the complete diffusion operator:

|x⟩ —H^⊗n—(·)—H^⊗n—
           |
           X—•—X
             |
            X—•—X
               |
              ...
             X—•—X    (n pairs of X gates)
               |
           H—⊗n—H

The middle part $(2\lvert0\rangle\langle0\rvert - I)$ can be further decomposed as: flip all qubits (apply $X^{\otimes n}$ ), apply a multi-qubit controlled- $Z$ gate (phase flip on $\lvert11\ldots1\rangle$ ), and flip back.

4.4 Geometric Interpretation: Two-Dimensional Rotation

The most elegant mathematical explanation of Grover’s algorithm reduces the entire $2^n$ -dimensional space to a two-dimensional subspace. This is the key to understanding why Grover’s algorithm is so efficient.

Define two orthogonal states:

$\lvert\alpha\rangle = \frac{1}{\sqrt{N-1}}\sum_{x \neq x^*}\lvert x\rangle \quad \text{(equal superposition of unmarked items)}$

$\lvert\beta\rangle = \lvert x^*\rangle \quad \text{(the marked item)}$

Note that $\langle\alpha\rvert\beta\rangle = 0$ , and the initial state $\lvert\psi\rangle = H^{\otimes n}\lvert0\rangle$ can be written as:

$\lvert\psi\rangle = \frac{1}{\sqrt{N}}\lvert\beta\rangle + \frac{\sqrt{N-1}}{\sqrt{N}}\lvert\alpha\rangle = \sin\theta\lvert\beta\rangle + \cos\theta\lvert\alpha\rangle$

where $\theta = \arcsin(1/\sqrt{N})$ . For large $N$ , $\theta \approx 1/\sqrt{N}$ .

A Grover iteration consists of two steps:

Oracle: $U_{\text{oracle}} = I - 2\lvert\beta\rangle\langle\beta\rvert$ — a reflection about $\lvert\beta\rangle$
Diffusion: $U_{\text{diff}} = 2\lvert\psi\rangle\langle\psi\rvert - I$ — a reflection about $\lvert\psi\rangle$

The Grover iteration $G = U_{\text{diff}} \cdot U_{\text{oracle}}$ is a rotation: In the $\{\lvert\alpha\rangle, \lvert\beta\rangle\}$ plane, $G$ rotates the state by $2\theta$ radians:

$G^k\lvert\psi\rangle = \sin((2k+1)\theta)\lvert\beta\rangle + \cos((2k+1)\theta)\lvert\alpha\rangle$

Proof (by induction or direct geometric argument):

$U_{\text{oracle}}$ is a reflection about the $\lvert\beta\rangle$ axis (preserving $\lvert\beta\rangle$ and flipping its perpendicular component). $U_{\text{diff}}$ is a reflection about the $\lvert\psi\rangle$ axis. The composition of two reflections is a rotation, with the rotation angle equal to twice the angle between the two reflection axes.

The initial state $\lvert\psi\rangle$ makes an angle $\theta$ with $\lvert\alpha\rangle$ (since $\langle\psi\rvert\alpha\rangle = \cos\theta$ ). $U_{\text{oracle}}$ reflects $\lvert\psi\rangle$ to the point symmetric about $\lvert\beta\rangle$ , at angle $\theta$ from $\lvert\beta\rangle$ . $U_{\text{diff}}$ then reflects the result about the $\lvert\psi\rangle$ axis. The net effect of two reflections: a rotation by $2\theta$ radians.

Thus after $k$ iterations, the state’s angle is $(2k+1)\theta$ .

4.5 Derivation of the Optimal Number of Iterations

We want the amplitude of $\lvert\beta\rangle$ (the marked item) to be as large as possible after $k$ iterations.

$\langle\beta\rvert G^k\lvert\psi\rangle = \sin((2k+1)\theta)$

The condition for maximizing this amplitude:

$\sin((2k+1)\theta) \approx 1 \;\Longrightarrow\; (2k+1)\theta \approx \frac{\pi}{2}$

Hence the optimal number of iterations:

$k_{\text{opt}} = \left\lfloor\frac{\pi}{4\theta} - \frac{1}{2}\right\rfloor$

Since $\theta = \arcsin(1/\sqrt{N}) \approx 1/\sqrt{N}$ (for $N \gg 1$ ):

$k_{\text{opt}} \approx \left\lfloor\frac{\pi}{4}\sqrt{N}\right\rfloor$

Final amplitude:

$|\langle\beta\rvert G^{k_{\text{opt}}}\lvert\psi\rangle|^2 = \sin^2\left((2k_{\text{opt}}+1)\arcsin\frac{1}{\sqrt{N}}\right)$

When $k = k_{\text{opt}}$ , this value is close to 1. More precisely, the minimum failure probability is:

$P_{\text{fail}} = \cos^2\left((2k_{\text{opt}}+1)\arcsin\frac{1}{\sqrt{N}}\right) \leq \frac{1}{N}$

Example: $N=4$ , $\theta = \arcsin(1/2) = \pi/6$ . $k_{\text{opt}} = \lfloor \pi/(4\cdot\pi/6) - 1/2 \rfloor = \lfloor 1.5 - 0.5 \rfloor = 1$ . After 1 iteration, $\sin(3\theta) = \sin(\pi/2) = 1$ , and the marked item is found with probability 1.

Example: $N=8$ , $\theta = \arcsin(1/\sqrt{8}) \approx 0.3614$ rad. $k_{\text{opt}} = \lfloor \pi/(4\cdot 0.3614) - 0.5 \rfloor = \lfloor 2.17 - 0.5 \rfloor = 1$ . After 1 iteration, $\sin(3\theta) = \sin(1.0842) \approx 0.882$ , success probability $\approx 0.778$ . After 2 iterations, $\sin(5\theta) = \sin(1.807) \approx 0.971$ , probability $\approx 0.943$ .

4.6 Full Worked Example: $N=4$

$N=4$ ( $n=2$ qubits), with the marked item set to $x^* = 10$ (binary, i.e., decimal 2).

Initialization: $\lvert\psi_0\rangle = \lvert00\rangle$

First $H^{\otimes 2}$ : $\lvert\psi_1\rangle = \frac{1}{2}(\lvert00\rangle + \lvert01\rangle + \lvert10\rangle + \lvert11\rangle)$

Grover iteration 1 (the only iteration needed):

Step A — Oracle (marking $10$ ): $U_{\text{oracle}} = I - 2\lvert10\rangle\langle10\rvert$

$\lvert\psi_2\rangle = \frac{1}{2}(\lvert00\rangle + \lvert01\rangle - \lvert10\rangle + \lvert11\rangle)$

Step B — Diffusion:

First compute the mean $\bar{a} = \frac{1}{4}(1+1-1+1) = \frac{1}{2}$

Inversion about the mean: $a_x' = 2\bar{a} - a_x = 1 - a_x$

$x$	$a_x$ (after Oracle)	$a_x'$ (after Diffusion)
00	$1/2$	$1 - 1/2 = 1/2$
01	$1/2$	$1 - 1/2 = 1/2$
10	$-1/2$	$1 - (-1/2) = 3/2$
11	$1/2$	$1 - 1/2 = 1/2$

$\lvert\psi_3\rangle = \frac{1}{2}(\lvert00\rangle + \lvert01\rangle + 3\lvert10\rangle + \lvert11\rangle)$

After normalization (note $\frac{1}{4} + \frac{1}{4} + \frac{9}{4} + \frac{1}{4} = 3$ ):

$\lvert\psi_3\rangle = \frac{1}{\sqrt{12}}(\lvert00\rangle + \lvert01\rangle + 3\lvert10\rangle + \lvert11\rangle)$

Measurement: $P(x^* = 10) = \left(\frac{3}{\sqrt{12}}\right)^2 = \frac{9}{12} = \frac{3}{4}$

A $75\%$ probability of finding the marked item. Note that for $N=4$ , a single iteration already has high success probability. A second iteration (unnecessary) would raise it further.

In fact, $N=4$ is the most special case, because $\theta = \pi/6$ , $(2\cdot 1 + 1)\cdot\pi/6 = \pi/2$ , a perfect rotation to $\lvert\beta\rangle$ , and the success probability should be 100%. The $75\%$ above comes from the $a_x'$ expression; let us compute $U_{\text{diff}}$ more precisely:

$U_{\text{diff}} = H^{\otimes 2}(2\lvert00\rangle\langle00\rvert - I)H^{\otimes 2}$

Let us compute step by step:

$H^{\otimes 2}\lvert\psi_2\rangle$ : first compute the action of $H^{\otimes 2}$ on $\lvert\psi_2\rangle$ .

$\lvert\psi_2\rangle = \frac{1}{2}\begin{pmatrix}1\\1\\-1\\1\end{pmatrix}$

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

$H^{\otimes 2}\lvert\psi_2\rangle = \frac{1}{4}\begin{pmatrix}1+1-1+1\\1-1-1-1\\1+1+1-1\\1-1+1+1\end{pmatrix} = \frac{1}{4}\begin{pmatrix}2\\-2\\2\\2\end{pmatrix}$

Apply $(2\lvert00\rangle\langle00\rvert - I)$ : $2\lvert00\rangle\langle00\rvert - I = \text{diag}(1, -1, -1, -1)$

So: $\frac{1}{4}\begin{pmatrix}2\\-2\\2\\2\end{pmatrix} \xrightarrow{2\lvert00\rangle\langle00\rvert - I} \frac{1}{4}\begin{pmatrix}2\\2\\-2\\-2\end{pmatrix}$

Finally apply $H^{\otimes 2}$ :

$\lvert\psi_3\rangle = \frac{1}{8}\begin{pmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{pmatrix}\begin{pmatrix}2\\2\\-2\\-2\end{pmatrix} = \frac{1}{8}\begin{pmatrix}2+2-2-2\\2-2-2+2\\2+2+2+2\\2-2+2-2\end{pmatrix} = \begin{pmatrix}0\\0\\1\\0\end{pmatrix}$

Perfect! $\lvert\psi_3\rangle = \lvert10\rangle$ , probability 1 of finding the marked item. For $N=4$ , only 1 Grover iteration is needed to find the marked item with probability 1.

4.7 Worked Example: $N=8$ ( $n=3$ )

Marked item set to $x^* = 110$ (decimal 6).

Initialization: $\lvert\psi_0\rangle = \frac{1}{\sqrt{8}}\sum_{x=0}^{7}\lvert x\rangle$

1st iteration: Oracle flips the amplitude of $\lvert110\rangle$ from $1/\sqrt{8}$ to $-1/\sqrt{8}$ . Mean $\bar{a} = (7\cdot 1 + (-1))/8\sqrt{8} = 6/(8\sqrt{8}) = 3/(4\sqrt{8})$ . After inversion, the amplitude of $\lvert110\rangle$ becomes $2\cdot 3/(4\sqrt{8}) - (-1/\sqrt{8}) = (6/4 + 1)/\sqrt{8} = (5/2)/\sqrt{8} = 5/(2\sqrt{8})$ . Other amplitudes become $2\cdot 3/(4\sqrt{8}) - 1/\sqrt{8} = (3/2 - 1)/\sqrt{8} = 1/(2\sqrt{8})$ . Success probability $P = (5/(2\sqrt{8}))^2 = 25/32 \approx 0.781$ .

2nd iteration: Starting from $\lvert\psi\rangle = \frac{1}{2\sqrt{8}}(1,1,1,1,1,1,5,1)^T$ (amplitude vector before normalization). Oracle: flips the amplitude of $\lvert110\rangle$ to $-5$ (others unchanged). New mean $\bar{a}' = (7\cdot 1 + (-5))/(8\cdot 2\sqrt{8}) = 2/(16\sqrt{8}) = 1/(8\sqrt{8})$ . After inversion, $\lvert110\rangle$ amplitude becomes $2\bar{a}' - (-5/(2\sqrt{8})) = 1/(4\sqrt{8}) + 5/(2\sqrt{8}) = 11/(4\sqrt{8})$ . Other amplitudes become $2\bar{a}' - 1/(2\sqrt{8}) = 1/(4\sqrt{8}) - 1/(2\sqrt{8}) = -1/(4\sqrt{8})$ . Success probability $P = (11/(4\sqrt{8}))^2 = 121/128 \approx 0.945$ .

Thus for $N=8$ , 2 iterations achieve roughly 94.5% success probability. Consistent with the theoretical value $k_{\text{opt}} = \lfloor \pi\sqrt{8}/4 \rfloor = \lfloor 2.22 \rfloor = 2$ .

4.8 Optimality Proof: The BBBV Theorem

Question: does there exist a quantum search algorithm faster than $O(\sqrt{N})$ ?

BBBV Theorem (Bennett, Bernstein, Brassard & Vazirani, 1997): any quantum algorithm solving the unstructured search problem must call the oracle at least $\Omega(\sqrt{N})$ times.

Proof sketch (high-dimensional geometric argument):

Consider the state evolution of a quantum algorithm. The initial state is $\lvert\psi_0\rangle$ . After $T$ oracle calls $U_f$ and $T+1$ non-oracle unitary transformations $U_0, U_1, \ldots, U_T$ :

$\lvert\psi_T\rangle = U_T U_f U_{T-1} U_f \cdots U_1 U_f U_0\lvert\psi_0\rangle$

Define a sequence of “query states”: $\lvert\psi^t\rangle$ is the state after the $t$ -th oracle call. The key idea is to track how the amplitude of the marked item grows with the number of queries.

Introduce a “no-mark” oracle $U_0$ (never flips any phase), and define $\lvert\phi^t\rangle$ as the state sequence when $U_0$ is used in place of $U_f$ . Lemma: $|\langle\psi^t\rvert\phi^t\rangle| \geq 1 - 2t^2/N$ in some form—i.e., it is hard to distinguish whether the search space contains a marked item.

A more rigorous argument follows:

Define $\lvert\psi_k\rangle$ as the state after $k$ oracle queries. Define the oracle operation $O = I - 2\lvert x^*\rangle\langle x^*\rvert$ and the reference oracle $O_0 = I$ (no mark).

Consider the difference vector $\Delta_k = \lVert\lvert\psi_k\rangle - \lvert\phi_k\rangle\rVert$ , where $\lvert\phi_k\rangle$ uses $O_0$ .

One can show that each oracle call can increase $\Delta_k$ by at most $2/\sqrt{N}$ (because each oracle call can affect at most $O(1/\sqrt{N})$ of the amplitude). After $T$ queries:

$\Delta_T \leq \frac{2T}{\sqrt{N}}$

On the other hand, to successfully distinguish the marked and unmarked cases (i.e., to find the marked item), we need $\Delta_T = \Omega(1)$ . Hence $T = \Omega(\sqrt{N})$ .

Intuitive understanding: each oracle query can only “slightly” change the quantum state; $\sqrt{N}$ queries are needed to accumulate enough change to reliably locate the marked item. This is the optimality proof for Grover’s quadratic speedup.

4.9 Generalization to Multiple Marked Items

If there are $M$ marked items (rather than 1), Grover’s algorithm still works.

Define $N' = N/M$ , and the rotation angle $\theta' = \arcsin(\sqrt{M/N})$ . The optimal number of iterations is:

$k'_{\text{opt}} \approx \frac{\pi}{4}\sqrt{\frac{N}{M}} - \frac{1}{2}$

The success probability is close to 1. When $M = N/4$ , $k'_{\text{opt}} = 1$ , and a single iteration can find a marked item.

Special cases:

If $M > N/2$ , classical random guessing is already fast, and the quantum speedup diminishes
If $M$ is unknown, quantum counting can first estimate $M$ , then run Grover
Quantum counting itself is a combination of Grover iteration and QPE

5. Shor’s Factoring Algorithm

5.1 Problem Definition and Classical Complexity

Problem: Given an $L$ -bit composite number $N = pq$ (where $p,q$ are primes), find $p$ and $q$ .

Classical complexity (best known algorithm):

General Number Field Sieve (GNFS): $O\left(\exp\left((\log N)^{1/3}(\log\log N)^{2/3}\right)\right)$ , sub-exponential but super-polynomial
For large $N$ (e.g., RSA-2048, $L=2048$ ), classical algorithms are completely infeasible

Quantum complexity: $O((\log N)^3)$ , polynomial time! This is the fundamental threat to RSA encryption security.

5.2 From Factoring to Period Finding: Detailed Reduction

The core insight of Shor’s algorithm is to convert factoring into a period-finding problem. The reduction proceeds in the following steps:

Step 1: Rule out trivial cases

If $N$ is even, directly output the factor 2. If $N = a^b$ for some $a \geq 1, b \geq 2$ , factor directly. These cases can be decided in polynomial time.

Step 2: Randomly choose $a$

Randomly choose $a \in \{2, 3, \ldots, N-1\}$ . Compute $\gcd(a, N)$ . If $\gcd(a, N) > 1$ , a factor has already been found. Otherwise $a$ is coprime to $N$ .

Step 3: The period-finding problem

Consider the modular exponentiation function:

$f_{a,N}(x) = a^x \bmod N$

This function is periodic, because the finiteness of modular arithmetic guarantees the existence of a smallest $r > 0$ such that $a^r \equiv 1 \pmod{N}$ (a generalization of Fermat’s little theorem; $r$ is the order of $a$ in the multiplicative group $\mathbb{Z}_N^*$ ). The period $r$ is precisely the period of the function $f_{a,N}$ .

Step 4: Converting period $r$ to factors

Theorem: If $r$ is even and $a^{r/2} \not\equiv -1 \pmod{N}$ , then $\gcd(a^{r/2} - 1, N)$ and $\gcd(a^{r/2} + 1, N)$ are both nontrivial factors of $N$ .

Proof:

From $a^r \equiv 1 \pmod{N}$ we have $a^r - 1 \equiv 0 \pmod{N}$ .

If $r$ is even, the product of $a^{r/2} - 1$ and $a^{r/2} + 1$ is divisible by $N$ :

$(a^{r/2} - 1)(a^{r/2} + 1) = a^r - 1 \equiv 0 \pmod{N}$

If $a^{r/2} \not\equiv \pm 1 \pmod{N}$ , then $N$ shares common factors with $a^{r/2} \pm 1$ —these factors are precisely $p$ and $q$ . $\blacksquare$

Step 5: Handling failure

If $r$ is odd, or $a^{r/2} \equiv -1 \pmod{N}$ , choose another $a$ and repeat.

Success probability: for a randomly chosen $a$ , the probability of successfully finding a factor is at least $1 - 1/2^{k-1}$ (where $k$ is the number of distinct prime factors of $N$ ). For RSA keys (two distinct odd primes), $k=2$ , and the success probability is at least $1/2$ . Thus success is expected within $O(1)$ attempts.

Complete reduction example

$N = 15$ : randomly choose $a = 7$ . $\gcd(7,15)=1$ . Compute $f(x) = 7^x \bmod 15$ :

$x$	$7^x$	$7^x \bmod 15$
0	1	1
1	7	7
2	49	4
3	343	13
4	2401	1

Period $r = 4$ (even). $a^{r/2} = 7^2 = 49 \equiv 4 \pmod{15}$ , $4 \not\equiv \pm 1 \pmod{15}$ . Therefore:

$\gcd(7^2 - 1, 15) = \gcd(48, 15) = 3$ $\gcd(7^2 + 1, 15) = \gcd(50, 15) = 5$

Obtaining factors 3 and 5. ✓

5.3 Quantum Period Finding: Circuit Design

Period finding is the “quantum engine” of Shor’s algorithm; it uses Quantum Phase Estimation (QPE) to find the period of $f(x) = a^x \bmod N$ .

Overall circuit diagram (two registers):

|0⟩^⊗m —H^⊗m—•—•—•—•—•—•—•—•—H^⊗m—QFT†—[M]
               | | | | | | | |
|0⟩^⊗L ——————U U U U U U U U—————————[M]  (verification)
               a² a a¹ a⁸
               ⁸ ⁴ ²

Upper: $m = 2L$ qubit “counting” register ( $L = \lceil \log_2 N \rceil$ )
Lower: $L$ qubit “working” register
$U_a$ is the modular multiplication operator: $U_a\lvert y\rangle = \lvert ay \bmod N\rangle$
Controlled $U_{a^{2^j}}$ are the building blocks of modular exponentiation

Modular Exponentiation

Modular exponentiation $a^x \bmod N$ is the most expensive part of Shor’s algorithm. It is decomposed via the square-and-multiply method into a series of controlled modular multiplications:

$a^x \bmod N = a^{\sum_{j=0}^{m-1} x_j 2^j} \bmod N = \prod_{j: x_j=1} \left(a^{2^j} \bmod N\right) \bmod N$

The circuit implementation requires:

Precomputing $a^{2^j} \bmod N$ for $j = 0, 1, \ldots, m-1$ (can be done on a classical computer as preprocessing)
Using controlled modular multipliers $C\text{-}U_{a^{2^j}}$ : when the control qubit is $\lvert1\rangle$ , apply $U_{a^{2^j}}$
Cascading these controlled operations

Quantum resources: modular exponentiation requires $O(L^3)$ elementary gates (using classically-assisted modular multiplication algorithms) and $O(L)$ ancilla qubits.

Quantum Phase Estimation (QPE) for Period Finding

The detailed circuit implementation of QPE is in Part 5.2 of the tutorial. Here we outline its application in Shor’s algorithm:

Input register: initialized to $\lvert+\rangle^{\otimes m} = H^{\otimes m}\lvert0\rangle^{\otimes m}$ (a superposition state).

Working register: initialized to $\lvert1\rangle$ .

For each bit $j$ ( $0 \leq j < m$ ), apply the controlled $U_{a^{2^j}}$ operation:

$U_{a^{2^j}}\lvert y\rangle = \lvert a^{2^j} y \bmod N\rangle$

The core result of QPE is: after running the inverse QFT ( $QFT^\dagger$ ) on the counting register, the measurement yields an approximation $\tilde{\varphi}$ of the period $r$ :

$\tilde{\varphi} \approx \frac{k}{r}$

where $k$ is a random integer between $0$ and $r-1$ .

Key mathematical derivation: the eigenstates of $U_a$ include: $U_a\lvert u_s\rangle = e^{2\pi i s/r}\lvert u_s\rangle$ where $\lvert u_s\rangle = \frac{1}{\sqrt{r}}\sum_{j=0}^{r-1} e^{-2\pi i s j/r}\lvert a^j \bmod N\rangle$ .

The initial state $\lvert1\rangle$ can be expanded as a superposition of these eigenstates: $\lvert1\rangle = \frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}\lvert u_s\rangle$

Thus QPE measures the phase $s/r$ with probability $1/r$ . Extracting $r$ from $\tilde{\varphi}$ requires the continued fraction expansion.

5.4 Continued Fractions Algorithm

QPE outputs an $m$ -bit approximation $\tilde{\varphi}$ of $\varphi = k/r$ (an $m$ -bit binary fraction). We need to recover the denominator $r$ from $\tilde{\varphi}$ .

Continued fraction expansion: any rational number $\varphi$ can be uniquely represented as:

$\varphi = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{\ddots + \cfrac{1}{a_n}}}}$

denoted compactly as $[a_0; a_1, a_2, \ldots, a_n]$ .

Algorithm:

Starting from $\varphi_0 = \tilde{\varphi}$ , iterate:

$a_j = \lfloor \varphi_j \rfloor$ (take the integer part)
$\varphi_{j+1} = 1/(\varphi_j - a_j)$ (take the reciprocal of the fractional part)

At the $j$ -th step, the convergent $p_j/q_j$ (the $j$ -th convergent of the QFT measurement value $\tilde{\varphi}$ ) gives an approximation of $k/r$ :

$[a_0; a_1, \ldots, a_j] = \frac{p_j}{q_j}$

with the recurrence relations: $p_{-2} = 0,\; p_{-1} = 1,\; p_j = a_j p_{j-1} + p_{j-2}$ $q_{-2} = 1,\; q_{-1} = 0,\; q_j = a_j q_{j-1} + q_{j-2}$

Convergence theorem: if $\left|\frac{p}{q} - \varphi\right| < \frac{1}{2q^2}$ , then $p/q$ is a convergent of $\varphi$ .

Application to Shor’s algorithm: choose $m = 2L$ (i.e., $2\lceil\log_2 N\rceil$ ); the precision guarantee of QPE is:

$\left|\frac{k}{r} - \tilde{\varphi}\right| < \frac{1}{2^{m}} < \frac{1}{2r^2}$

Thus one of the convergents of $\tilde{\varphi}$ is $k/r$ . Check the denominator $q_j$ : if $a^{q_j} \equiv 1 \pmod{N}$ (or if the correct factorization is found), then $r = q_j$ .

Complete example: extracting the period from $\tilde{\varphi}$

Let $N=15$ , the true period $r=4$ , $k=1$ , so $\varphi = 1/4 = 0.25$ .

Suppose QPE outputs $\tilde{\varphi} = 0.2501$ (a small error). Continued fraction expansion:

$\varphi_0 = 0.2501$ , $a_0 = 0$
$\varphi_1 = 1/0.2501 \approx 3.9984$ , $a_1 = 3$
$\varphi_2 = 1/0.9984 \approx 1.0016$ , $a_2 = 1$
$\varphi_3 = 1/0.0016 = 625$ , $a_3 = 625$

Convergents:

$[0; 3] = 0 + 1/3 = 1/3$ → $r=3$ (check: $7^3 \bmod 15 = 13 \neq 1$ , not the period)
$[0; 3, 1] = 1/(3 + 1/1) = 1/4$ → $r=4$ (check: $7^4 \bmod 15 = 1$ , correct!)

Thus $r=4$ .

5.5 Complete Worked Example: Factoring 15

This is the most classic pedagogical example of Shor’s algorithm.

Parameters:

$N = 15$ , $L = 4$ (since $15 < 2^4 = 16$ )
$m = 2L = 8$ counting qubits
Randomly choose $a = 7$ ( $\gcd(7,15)=1$ )

Step 1: Rule out trivial cases. 15 is odd and not a perfect power.

Step 2: Precompute $7^{2^j} \bmod 15$ :

$j$	$2^j$	$7^{2^j} \bmod 15$
0	1	$7^1 \bmod 15 = 7$
1	2	$7^2 \bmod 15 = 4$
2	4	$7^4 \bmod 15 = 1$
3	8	$7^8 \bmod 15 = 1$
4	16	$7^{16} \bmod 15 = 1$
$\vdots$	$\vdots$	$\vdots$

Note that for $j \geq 2$ , $7^{2^j} \equiv 1 \pmod{15}$ .

Step 3: Prepare the counting register superposition.

$\lvert\psi_{\text{count}}\rangle = \frac{1}{\sqrt{256}}\sum_{x=0}^{255}\lvert x\rangle$

The working register is $\lvert1\rangle$ .

Step 4: Apply controlled modular multiplications.

Since $7^{2^j} \bmod 15 = 1$ for $j\geq2$ , only the controlled modular multiplications for $j=0,1$ have a nontrivial effect. Thus:

$\lvert\psi\rangle = \frac{1}{\sqrt{256}}\sum_{x=0}^{255}\lvert x\rangle \lvert 7^x \bmod 15\rangle$

Step 5: Apply the inverse QFT and measure.

Suppose the measurement yields $\tilde{\varphi} = 64/256 = 0.25$ (i.e., binary $0.01$ ).

Step 6: Continued fraction expansion.

$0.25 = [0; 4]$ → $r = 4$ .

Step 7: Verification and factoring.

$a^{r/2} \bmod N = 7^2 \bmod 15 = 49 \bmod 15 = 4$ . $\gcd(7^2 - 1, 15) = \gcd(48, 15) = 3$ ✓ $\gcd(7^2 + 1, 15) = \gcd(50, 15) = 5$ ✓

Possible historical difference: note that $a=7$ is used here. In actual quantum experiments (such as the photonic quantum implementation by Martin-López et al. 2012), the simpler $a=11$ is often used (because $11^2 \bmod 15 = 121 \bmod 15 = 1$ , period $r=2$ ), or $a=4$ (period $r=2$ ). The case $r=2$ is simpler because only one layer of controlled modular multiplication ( $j=0$ ) is needed.

5.6 Complexity Analysis and Resource Estimates

Quantum gate complexity

Subroutine	Gate complexity	Notes
Modular exponentiation	$O(L^3)$	L is the number of bits, using classical modular multiplication + quantum controlled operations
QFT / QFT†	$O(L^2)$	QFT on m = 2L bits
Total complexity	$O(L^3)$	= $O((\log N)^3)$

Total quantum gate count estimate (using RSA-2048 as an example, $L=2048$ ):

Modular exponentiation: roughly $2048^3 \approx 8.6 \times 10^9$ elementary gates
Ancilla qubits: roughly $4000$
Required physical qubits (accounting for error correction): millions

Classical vs. quantum complexity summary table

Operation	Classical complexity	Quantum complexity	Speedup
Integer factoring	$\exp(O((\log N)^{1/3}(\log\log N)^{2/3}))$	$O((\log N)^3)$	Exponential
Discrete logarithm	$\exp(O((\log p)^{1/3}(\log\log p)^{2/3}))$	$O((\log p)^3)$	Exponential
Elliptic curve discrete log	$O(\exp(\log p)^{1/3}(\log\log p)^{2/3})$	$O((\log p)^3)$	Exponential (breaks ECC)

Resource estimate references:

Number to factor	Bits	Classical GNFS time	Quantum gate count	Quantum time estimate*
15	4	Instant	~10³	Microseconds
21	5	Instant	~10⁴	Microseconds
143	8	Microseconds	~10⁶	Milliseconds
RSA-512	512	~10⁴ years	~10¹⁰	Hours
RSA-1024	1024	~10⁶ years	~10¹¹	Days
RSA-2048	2048	~10¹¹ years	~10¹²	Years

*Quantum time estimates are based on a physical gate rate of 1 MHz, highly idealized. In practice, error-correction overhead (roughly 10³–10⁴ times resource increase) must also be considered.

5.7 Threat Analysis of Shor’s Algorithm to RSA

Short term (<10 years): no threat. Requires millions of high-quality physical qubits, far beyond current levels.

Medium term (10–20 years): may threaten RSA-1024. Requires roughly 1 million physical qubits, with error-corrected gate fidelity > 99.9%.

Long term (20–30 years): threatens all RSA key lengths. NIST has already advanced PQC (Post-Quantum Cryptography) standardization; FIPS 203/204/205 were published in 2024.

Qubit resources: the optimized scheme of Gidney & Ekerå (2021) shows that factoring RSA-2048 requires roughly 2,000 logical qubits and roughly 20 million physical qubit gates, with a runtime of roughly 8 hours. This is far more optimistic than previous estimates (which required 10–100 times more resources), but the engineering implementation still faces enormous challenges.

6. Algorithm Complexity Comparison Table

Algorithm	Problem	Classical complexity	Quantum complexity	Speedup type	Practical application
Deutsch-Jozsa	Constant/balanced decision	$\Theta(2^n)$	$O(n)$	Exponential	Pedagogy
Bernstein-Vazirani	Hidden bit string	$\Theta(n)$	$O(1)$	Linear	Pedagogy
Simon	Hidden period ( $\mathbb{Z}_2^n$ )	$\Theta(2^{n/2})$	$O(n)$	Exponential	Pedagogy, inspired Shor
Grover	Unstructured search	$\Theta(N)$	$O(\sqrt{N})$	Quadratic	Database search, optimization
Shor	Integer factoring	Sub-exponential	$O((\log N)^3)$	Exponential	Breaking RSA

Speedup type descriptions:

Exponential speedup: quantum is exponentially faster than classical (advantage far exceeds a constant factor as problem size doubles)
Quadratic speedup: quantum is faster by a square-root factor
Linear speedup: quantum is faster by a constant factor

7. References and Further Reading

Original Papers

Deutsch, D. & Jozsa, R. (1992). “Rapid solution of problems by quantum computation”. Proceedings of the Royal Society A, 439(1907), 553–558.
Bernstein, E. & Vazirani, U. (1997). “Quantum complexity theory”. SIAM Journal on Computing, 26(5), 1411–1473.
Simon, D. R. (1997). “On the power of quantum computation”. SIAM Journal on Computing, 26(5), 1474–1483.
Grover, L. K. (1996). “A fast quantum mechanical algorithm for database search”. Proceedings of STOC 1996, 212–219.
Shor, P. W. (1997). “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”. SIAM Journal on Computing, 26(5), 1484–1509.
Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997). “Strengths and weaknesses of quantum computing”. SIAM Journal on Computing, 26(5), 1510–1523. (BBBV optimality proof)

Textbooks and Reviews

Nielsen, M. A. & Chuang, I. L. (2010). Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press. (Chapter 6: Quantum search algorithms; Chapter 5: QFT and Shor’s algorithm)
Kaye, P., Laflamme, R., & Mosca, M. (2007). An Introduction to Quantum Computing. Oxford University Press.
Mermin, N. D. (2007). Quantum Computer Science: An Introduction. Cambridge University Press.
Jozsa, R. (1997). “Quantum algorithms and the Fourier transform”. Proceedings of the Royal Society A, 454(1969), 323–337.

In-Depth Topics

Grover, L. K. (1998). “Quantum computers can search arbitrarily large databases by a single query”. Physical Review Letters, 79(23), 4709.
Boyer, M., Brassard, G., Høyer, P., & Tapp, A. (1998). “Tight bounds on quantum searching”. Fortschritte der Physik, 46(4-5), 493–506.
Brassard, G., Høyer, P., Mosca, M., & Tapp, A. (2002). “Quantum amplitude amplification and estimation”. Contemporary Mathematics, 305, 53–74. (Generalization of Grover)
Kitaev, A. Y. (1995). “Quantum measurements and the Abelian stabilizer problem”. arXiv:quant-ph/9511026. (HSP framework)
Gidney, C. & Ekerå, M. (2021). “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits”. Quantum, 5, 433. (Resource optimization milestone)
Beauregard, S. (2003). “Circuit for Shor’s algorithm using 2n+3 qubits”. Quantum Information and Computation, 3(2), 175–185.
Martin-López, E. et al. (2012). “Experimental realization of Shor’s quantum factoring algorithm using qubit recycling”. Nature Photonics, 6, 773–776. (First complete demonstration of Shor’s algorithm factoring 15)

Internal Tutorial References

Part 1.8: Mathematical form of the Discrete Fourier Transform (DFT)
Part 5.1: Detailed construction of the QFT circuit (controlled-phase gates, cascade structure)
Part 5.2: Quantum Phase Estimation (QPE) algorithm—the quantum engine of Shor’s algorithm

Document version: v1.0
Last updated: 2026-06-03
Associated tutorial: Quantum Computing Primer—From First Principles (Part 3.6, Part 5.1, Part 5.2)
Writing principles: Standard quantum computing notation, consistent with the mathematical and physical foundations of Parts 1–3 of the tutorial

Chapter 5: Advanced Topics