Chapter 31: The Hidden Subgroup Problem and Beyond

31.1 The Abelian HSP: Unifying Deutsch-Jozsa, Simon, and Shor

The Hidden Subgroup Problem is defined as follows. Let $G$ be a finite group and $S$ a finite set. We are given a function $f : G \to S$ that is constant on left cosets of an unknown subgroup $H \leq G$ and distinct on different cosets. That is, $f(g_1) = f(g_2)$ if and only if $g_1 H = g_2 H$ (equivalently, $g_1^{-1} g_2 \in H$). The goal is to determine $H$.

Deutsch-Jozsa as an HSP

Recall the Deutsch-Jozsa problem: given $f : \{0,1\}^n \to \{0,1\}$ promised to be either constant or balanced, determine which. We can cast this as an HSP over the group $G = \mathbb{Z}_2^n$ (the additive group of $n$-bit strings under bitwise XOR).

• If $f$ is constant, then $f(x) = f(y)$ for all $x, y$, so the hidden subgroup is $H = G = \mathbb{Z}_2^n$ itself (the whole group).
• If $f$ is balanced, the hidden subgroup is $H = \{0^n\}$ (the trivial subgroup), since $f$ takes different values on distinct elements.

Determining whether $H$ is trivial or the whole group is exactly the Deutsch-Jozsa problem. The quantum algorithm uses Hadamard transforms - which are the Quantum Fourier Transform over $\mathbb{Z}_2^n$ - to identify $H$ in a single query.

Simon's Algorithm as an HSP

Simon's problem is even more directly an HSP. We are given $f : \{0,1\}^n \to \{0,1\}^n$ with the promise that there exists a secret string $s \in \{0,1\}^n$ such that $f(x) = f(y)$ if and only if $x \oplus y \in \{0^n, s\}$. The group is $G = \mathbb{Z}_2^n$, and the hidden subgroup is $H = \{0^n, s\}$ (or $H = \{0^n\}$ if $s = 0^n$, meaning $f$ is one-to-one).

Simon's algorithm uses Hadamard transforms and measurements to produce random vectors orthogonal to $s$. After $O(n)$ repetitions, we have enough equations to determine $s$ by Gaussian elimination. The exponential speedup over classical algorithms (which require $\Omega(2^{n/2})$ queries) comes from the quantum Fourier transform over $\mathbb{Z}_2^n$ concentrating amplitude on the orthogonal complement of $H$.

Shor's Algorithm as an HSP

Shor's factoring algorithm reduces to finding the order $r$ of an element $a$ modulo $N$: the smallest positive integer $r$ such that $a^r \equiv 1 \pmod{N}$. Define $f : \mathbb{Z} \to \mathbb{Z}_N^*$ by $f(x) = a^x \bmod N$. This function is periodic with period $r$, meaning $f(x) = f(y)$ if and only if $r \mid (x - y)$.

The group is $G = \mathbb{Z}$ (or, for practical purposes, $\mathbb{Z}_M$ for a sufficiently large $M$), and the hidden subgroup is $H = r\mathbb{Z}$ (the multiples of $r$). The Quantum Fourier Transform over $\mathbb{Z}_M$ concentrates amplitude at multiples of $M/r$, from which $r$ can be extracted using continued fractions.

The General Abelian HSP Algorithm

For any finite abelian group $G$, the HSP can be solved in polynomial time with the following algorithm:

1. Prepare the state $\frac{1}{\sqrt{|G|}} \sum_{g \in G} |g\rangle |0\rangle$.
2. Apply the oracle to obtain $\frac{1}{\sqrt{|G|}} \sum_{g \in G} |g\rangle |f(g)\rangle$.
3. Apply the Quantum Fourier Transform over $G$ to the first register.
4. Measure the first register. The result is a random element of the dual group $\hat{G}$ that annihilates $H$ (is trivial on $H$). Repeating $O(\log |G|)$ times and using classical post-processing determines $H$ uniquely.

The key fact is that the QFT over any finite abelian group can be implemented efficiently (in polynomial time in $\log |G|$), because every finite abelian group decomposes as a direct product of cyclic groups (the fundamental theorem of finite abelian groups), and the QFT over a direct product is the tensor product of QFTs over the factors.

Beyond Factoring: Other Abelian HSP Applications

The abelian HSP framework extends to problems beyond those we have already studied:

• Discrete logarithm: Given $g^a \bmod p$, find $a$. This is an HSP over $\mathbb{Z}_{p-1}$.
• Pell's equation: Hallgren (2002) showed that finding the fundamental solution to $x^2 - Dy^2 = 1$ reduces to an HSP over a continuous (but still abelian) group, solvable in quantum polynomial time.
• Principal ideal problem and class group computation: These problems in algebraic number theory also reduce to abelian HSP instances.

31.2 The Non-Abelian HSP

When the group $G$ is non-abelian, the HSP becomes dramatically harder. The most tantalizing special case is the Graph Isomorphism problem: given two graphs $G_1$ and $G_2$, determine whether there exists a relabeling of vertices that transforms one into the other.

Graph Isomorphism as an HSP

Graph Isomorphism reduces to the HSP over the symmetric group $S_n$ (the group of all permutations of $n$ elements). Given two graphs $G_1, G_2$ on $n$ vertices, define $f : S_n \to \{\text{graphs}\}$ by $f(\pi) = \pi(G_1)$ (apply permutation $\pi$ to the vertices of $G_1$). If $G_1 \cong G_2$, then $f$ hides the subgroup $H$ of permutations that map $G_1$ to itself (the automorphism group); otherwise $H$ is trivial.

An efficient quantum algorithm for the HSP over $S_n$ would solve Graph Isomorphism in polynomial time. But despite decades of effort, no such algorithm is known.

Why the Non-Abelian Case Is Hard

The abelian HSP algorithm succeeds because the QFT over abelian groups has a clean structure: all irreducible representations are one-dimensional, so measuring in the Fourier basis gives direct information about the hidden subgroup. For non-abelian groups, the irreducible representations can be high-dimensional matrices, and the information about $H$ is spread across these matrix-valued Fourier coefficients in a much more complex way.

More specifically, the natural generalization of the abelian algorithm - prepare a coset state, apply the QFT over $G$, and measure - produces a random irreducible representation label. For the symmetric group $S_n$, strong negative results show that this "weak Fourier sampling" approach cannot efficiently distinguish many subgroups. Grigni, Schulman, Vazirani, and Vazirani (2004) and Moore, Russell, and Schulman (2005) showed that for Graph Isomorphism, even measuring the representation label gives exponentially little information.

Partial Progress

While the general non-abelian HSP is open, efficient quantum algorithms do exist for certain non-abelian groups:

• Dihedral groups $D_n$: The HSP over $D_n$ is related to the shortest vector problem in lattices. A subexponential-time quantum algorithm was given by Kuperberg (2005), and Regev (2004) gave a different subexponential approach. Polynomial-time algorithms remain elusive and are connected to deep questions in lattice-based cryptography.
• Some semidirect products: When $G = \mathbb{Z}_p \rtimes \mathbb{Z}_q$ for primes $p, q$, efficient algorithms exist in certain cases.
• Heisenberg group: The HSP over the Heisenberg group over $\mathbb{Z}_p$ can be solved efficiently.

It is worth noting that Babai (2016) gave a quasipolynomial-time classical algorithm for Graph Isomorphism, achieving $\exp((\log n)^{O(1)})$ time. This landmark result narrows the potential advantage of a quantum algorithm, though a polynomial-time solution (classical or quantum) remains unknown.

31.3 Quantum Walk Algorithms

Classical random walks are a foundational algorithmic tool: a particle starts at some node of a graph and moves randomly to neighboring nodes. Random walks power algorithms for satisfiability, graph connectivity, approximation algorithms, and even Google's PageRank. Quantum walks replace the random transitions with quantum evolution, enabling interference effects that can dramatically speed up exploration.

Discrete-Time Quantum Walks

A discrete-time quantum walk on a graph requires a "coin" space in addition to the position space. At each step, the walker first applies a "coin operator" (a unitary on the coin space) and then a "shift operator" that moves the walker to a neighboring node conditioned on the coin state. The walk proceeds by alternating coin and shift operations.

Consider a quantum walk on the integer line $\mathbb{Z}$. The state is $|\psi\rangle = \sum_x (\alpha_x |L\rangle + \beta_x |R\rangle)|x\rangle$, where $|L\rangle, |R\rangle$ are the coin states (left and right). The coin operator is typically the Hadamard gate:

The shift operator moves the walker: $S|L\rangle|x\rangle = |L\rangle|x-1\rangle$ and $S|R\rangle|x\rangle = |R\rangle|x+1\rangle$. One step of the walk is $U = S \cdot (C \otimes I)$. After $t$ steps, the state is $U^t |\psi_0\rangle$.

The key property: while a classical random walk on the line spreads as $\sqrt{t}$ (standard deviation growing as the square root of steps), a quantum walk spreads linearly in $t$. This quadratic speedup in spreading is the basis for quantum walk search algorithms.

Continuous-Time Quantum Walks

An alternative formulation uses continuous-time evolution. The adjacency matrix $A$ of a graph (or its Laplacian $L$) serves as a Hamiltonian, and the walk is the evolution $e^{-iAt}$. No coin space is needed. Continuous-time quantum walks were introduced by Farhi and Gutmann (1998) and have found applications in:

• Spatial search: Childs and Goldstone (2004) showed that continuous-time quantum walks can search certain graphs (including the hypercube and $d$-dimensional lattices for $d \geq 5$) in optimal $O(\sqrt{N})$ time.
• NAND tree evaluation: Farhi, Goldstone, and Gutmann (2007) gave a quantum walk algorithm that evaluates balanced NAND trees in $O(\sqrt{N})$ time, providing a provable polynomial speedup over any classical algorithm.
• Exponential speedup for graph traversal: Childs et al. (2003) showed that a continuous-time quantum walk can traverse certain carefully constructed graphs exponentially faster than any classical random walk.

Quantum Walk Search (Szegedy Framework)

Mario Szegedy (2004) developed a general framework that quantizes any classical Markov chain into a quantum walk, providing a generic quadratic speedup for search. If a classical random walk finds a marked item in expected time $T$, the corresponding quantum walk finds it in $O(\sqrt{T})$ time (under certain conditions on the spectral gap). Szegedy's framework underpins the qubitization technique used in advanced Hamiltonian simulation (Chapter 33).

The sandbox above illustrates the coin-flip-then-conditional-shift structure of a discrete-time quantum walk. The coin qubit q[0] is flipped by Hadamard gates, and the position qubits q[1..2] are conditionally updated. Note: this circuit demonstrates the structure schematically. A full quantum walk on a 4-node cycle would require more sophisticated position-conditional shift operations (e.g., controlled increment/decrement modulo 4 on the position register). Run it multiple times and observe the probability distribution over positions - unlike a classical random walk, quantum interference produces a non-uniform distribution, a hallmark of quantum walks.

31.4 The HHL Algorithm

Solving systems of linear equations $Ax = b$ is perhaps the most ubiquitous computational task in science and engineering. Classical algorithms (Gaussian elimination, conjugate gradient, etc.) require time polynomial in the dimension $N$ of the matrix. The HHL algorithm (Harrow, Hassidim, and Lloyd, 2009) offers an exponential speedup - but with caveats so significant that they fundamentally change what "solving" means.

The Algorithm

Given an $N \times N$ Hermitian matrix $A$ and a vector $b$, HHL produces a quantum state $|x\rangle$ proportional to $A^{-1}b$. The algorithm proceeds as follows:

1. State preparation: Encode $b$ as a quantum state $|b\rangle = \sum_i b_i |i\rangle$ (assuming $b$ is normalized).
2. Quantum Phase Estimation (QPE): Apply QPE with the unitary $e^{iAt}$ to extract the eigenvalues $\lambda_j$ of $A$ into an ancilla register. After this step, the state is approximately $\sum_j \beta_j |\lambda_j\rangle |u_j\rangle$, where $|u_j\rangle$ are eigenvectors of $A$ and $\beta_j = \langle u_j | b \rangle$.
3. Controlled rotation: Apply a rotation conditioned on the eigenvalue register to map $|\lambda_j\rangle \to \frac{C}{\lambda_j}|\lambda_j\rangle$ (for a normalization constant $C$). This encodes $A^{-1}$ in the amplitudes.
4. Uncompute QPE: Reverse the phase estimation to disentangle the eigenvalue register.
5. Measure: Post-select on the ancilla being in the correct state. The remaining state is $|x\rangle \propto A^{-1}|b\rangle$.

The runtime is $O(\text{poly}(\log N, \kappa, 1/\epsilon))$, where $\kappa = \lambda_{\max} / \lambda_{\min}$ is the condition number of $A$ and $\epsilon$ is the desired precision. This is exponentially faster than the $O(N)$ classical lower bound - in the dimension $N$.

The Caveats

The HHL algorithm has become a case study in the importance of reading the fine print of quantum speedup claims. Here are the critical caveats:

• Input problem: The algorithm requires the vector $b$ to be loaded into a quantum state $|b\rangle$. If $b$ is given as a classical vector, this loading step alone can take $O(N)$ time, completely negating the exponential speedup. HHL is most useful when $|b\rangle$ is produced by a preceding quantum computation or has special structure (e.g., uniform superposition) that allows efficient preparation.
• Output problem: The algorithm produces the quantum state $|x\rangle$, not the classical vector $x$. Reading out all $N$ components of $x$ requires $O(N)$ measurements, again negating the speedup. HHL is useful when you need only a few properties of $x$ (such as $\langle x | M | x \rangle$ for some observable $M$), not the full vector.
• Sparsity requirement: The matrix $A$ must be $s$-sparse (at most $s$ non-zero entries per row) for the Hamiltonian simulation $e^{iAt}$ to be efficient. Dense matrices require different techniques.
• Condition number dependence: The runtime scales polynomially with $\kappa$. Ill-conditioned systems ($\kappa \gg 1$) are expensive. Many real-world systems have condition numbers that grow polynomially with $N$, which can reduce the exponential speedup to a polynomial one.

Applications and Significance

Despite these caveats, HHL has been enormously influential. It spawned the entire field of quantum machine learning, since many ML algorithms reduce to linear algebra. Key applications include:

• Quantum recommendation systems: Kerenidis and Prakash (2016) proposed a quantum algorithm based on HHL for recommendation systems. However, Tang (2019) later "dequantized" this algorithm, giving an efficient classical algorithm inspired by the quantum one - a cautionary tale.
• Finite element methods: When the stiffness matrix is sparse and well-conditioned, HHL can accelerate classical PDE solvers - though the input/output bottleneck remains challenging.
• Quantum chemistry: Computing properties of molecular ground states, where the input and output are naturally quantum (Chapter 33).

31.5 QSVT: A Unifying Framework

In 2019, Gilyen, Su, Low, and Wiebe introduced the Quantum Singular Value Transformation (QSVT), a framework so powerful that it has been called a "grand unification" of quantum algorithms. QSVT provides a single algorithmic primitive that subsumes Grover's search, quantum phase estimation, HHL, Hamiltonian simulation, and amplitude amplification as special cases.

From QSP to QSVT

The story begins with Quantum Signal Processing (QSP), developed by Low and Chuang (2017). QSP considers a single-qubit signal rotation $R(\theta)$ and asks: by interleaving $R(\theta)$ with programmable "signal processing" rotations, what functions of $\theta$ can we realize? The remarkable answer: any polynomial (subject to certain parity and boundedness constraints).

More precisely, given a signal operator $W$ that encodes a value $a \in [-1, 1]$ as $W = \begin{pmatrix} a & \sqrt{1-a^2} \\ \sqrt{1-a^2} & -a \end{pmatrix}$, and a sequence of "processing angles" $\phi_0, \phi_1, \ldots, \phi_d$, the QSP sequence

realizes a matrix whose top-left entry is a degree-$d$ polynomial in $a$, $P(a)$. The angles $\phi_k$ act as "dials" that can be tuned to implement any desired polynomial transformation.

QSVT generalizes this from scalars to matrices. Given a block encoding of a matrix $A$ (a unitary $U$ such that a specific block of $U$ equals $A/\alpha$ for some normalization $\alpha$), QSVT applies a polynomial transformation $P$ to the singular values of $A$. If $A = \sum_k \sigma_k |u_k\rangle\langle v_k|$ is the singular value decomposition, then QSVT produces a block encoding of $\sum_k P(\sigma_k) |u_k\rangle\langle v_k|$.

How QSVT Unifies Quantum Algorithms

The power of QSVT lies in the choice of polynomial $P$:

• Hamiltonian simulation: Choose $P(\sigma) \approx e^{-i\sigma t}$ (approximating the exponential by a polynomial). This yields the qubitization approach to Hamiltonian simulation with optimal $O(t + \log(1/\epsilon))$ query complexity.
• Matrix inversion (HHL): Choose $P(\sigma) \approx 1/\sigma$ (approximating the reciprocal function). This gives the HHL algorithm.
• Amplitude amplification (Grover): Choose $P$ to be a Chebyshev polynomial that amplifies a small amplitude to near unity. This recovers Grover's quadratic speedup.
• Phase estimation: Choose $P$ to approximate a step function that distinguishes eigenvalues above and below a threshold.
• Quantum eigenvalue threshold: Choose $P$ to project onto eigenvalues in a desired range, useful for ground state preparation.

The only ingredient that changes between these algorithms is the polynomial - and the angles $\phi_k$ that implement it. The quantum circuit structure (alternating between the block encoding oracle and single-qubit rotations) remains the same.

Block Encodings

A block encoding of a matrix $A$ is a unitary $U$ such that $\langle 0^a | U | 0^a \rangle = A / \alpha$ (up to projections onto ancilla qubits), where $\alpha \geq \|A\|$ is a normalization factor. Block encodings can be constructed from:

• Sparse matrix access oracles (for sparse Hamiltonians)
• Linear combinations of unitaries (LCU) decompositions
• Density matrix exponentiation
• Outputs of other quantum algorithms

The block encoding abstraction cleanly separates the "data access" problem (how to load $A$ into the quantum computer) from the "computation" problem (what polynomial to apply). QSVT handles the computation; the block encoding handles the access.

Practical Implications

QSVT has several advantages over ad hoc quantum algorithm design:

• Optimal query complexity: QSVT-based algorithms often achieve provably optimal query complexity (the minimum number of uses of the input oracle).
• Modularity: The block encoding and polynomial transformation are independent modules. Improving either one improves the whole algorithm.
• New algorithms: By choosing novel polynomials, QSVT enables new algorithms that were not apparent from the individual algorithm perspective. For example, fractional queries, quantum walks with polynomial spectral processing, and eigenvalue filtering.

QSVT represents a maturation of quantum algorithm design from a collection of clever tricks to a systematic engineering discipline. Just as classical algorithm design benefits from unifying frameworks (dynamic programming, linear programming, convex optimization), quantum algorithm design now has QSVT as a foundational framework.