Advanced Quantum Algorithms
for Cryptography

What Is the HSP?

The Hidden Subgroup Problem (HSP) is one of the most structurally important problems in quantum computing. Given a group G and a function f : G → S that is constant on each coset of some hidden subgroup H ≤ G and distinct on different cosets, the task is to identify H. Most major quantum speedups can be expressed as instances of this problem.

Abelian HSP — the solved case: For finite abelian groups, Kitaev's algorithm (a generalisation of Shor's approach) solves the HSP efficiently in polynomial time using the Quantum Fourier Transform. Integer factorisation, the discrete logarithm problem, and Simon's period-finding problem are all abelian HSP instances. This is precisely why RSA, Diffie-Hellman, and ECC fall to quantum computers.

Non-abelian HSP — the open frontier: No general efficient quantum algorithm exists for non-abelian groups. Two major open problems reduce to non-abelian HSP instances: graph isomorphism (via the symmetric group S_n) and the Shortest Vector Problem on lattices (via the dihedral group D_n). If an efficient quantum algorithm for the dihedral HSP were found, it would break lattice-based post-quantum cryptosystems including Kyber and Dilithium — currently considered the most likely replacements for RSA.

Why the HSP Boundary Defines Post-Quantum Security

The NIST PQC standardisation process implicitly rests on the belief that the non-abelian HSP is hard for quantum computers. Lattice problems (LWE, SVP, CVP) are reducible to dihedral HSP instances; code-based problems connect to HSP over certain symmetric groups; isogeny-based constructions (before SIKE's classical break) involved related algebraic structures.

Crucially, no structure analogous to the periodicity that the QFT exploits in abelian groups has been found for dihedral or symmetric groups. Researchers have explored Fourier sampling and black-box approaches, but quantum algorithms for these groups remain either subexponential or exponential in time — insufficient to break deployed systems. The dihedral HSP sits at the exact fault line between quantum-broken and quantum-safe cryptography.

Period Finding Without the QFT

Simon's algorithm (1994) predates Shor's and inspired it directly. Given a function f : {0,1}ⁿ → {0,1}ⁿ with a hidden period s (so f(x) = f(x ⊕ s) for all x), the algorithm recovers s with O(n) quantum queries — an exponential improvement over the Ω(2^n/2) queries any classical algorithm requires.

Cryptographic impact: Simon's algorithm can break Even-Mansour and FX-construction schemes — the structural foundations underlying several real-world block cipher modes — in the quantum superposition query model (Q2 model). Researchers have shown that the “Grover Meets Simon” algorithm combines both techniques to attack FX constructions with whitened keys, and the subsequent Alg-PolyQ2 algorithm further reduces query complexity.

A subtlety: The Q2 model assumes the adversary can query the cipher in quantum superposition — a physically demanding requirement. In the more conservative Q1 model (classical queries, quantum post-processing), Simon's attacks do not apply. Whether Q2-model attacks are physically realistic against deployed ciphers is an active research and standards debate. NIST's symmetric algorithm selections do account for quantum access considerations.

From Random Walks to Quantum Coherence

A quantum walk is the quantum analogue of a classical random walk: rather than a walker moving probabilistically through a graph, the walker exists in a superposition of positions, with probability amplitudes evolving coherently. This interference structure produces faster mixing and hitting times than any classical random walk, yielding polynomial-to-quadratic speedups for search problems over structured spaces.

Collision finding: The BHT algorithm (Brassard, Høyer, Tapp) uses quantum walks to find collisions in a hash function in O(N^1/3) time — a cubic-root speedup over the classical birthday bound of O(N^1/2). For a 256-bit hash, this reduces effective collision resistance from 2¹²⁸ classical to approximately 2⁸⁵ quantum queries. This is why NIST recommends SHA-3-384 or SHA-512 for long-term quantum security rather than SHA-256.

Claw finding and discrete log: Quantum walk algorithms also speed up claw-finding problems — instances of the form “find x, y such that f(x) = g(y)” — relevant to attacks on signature schemes. Combined with Grover's oracle construction, quantum walks allow more efficient search over certain structured cryptographic spaces than Grover's alone.

Current limits: Quantum walk speedups are polynomial, not exponential. They narrow security margins but do not break primitives outright. No quantum walk algorithm is known to threaten LWE-based or hash-based post-quantum standards.

Harrow–Hassidim–Lloyd (2009)

The HHL algorithm solves a system of N linear equations Ax = b in poly(log N, κ) time — an exponential speedup over classical methods that require O(N√κ) time, where κ is the condition number of A. The speedup appears dramatic: a trillion-variable system, classically requiring days, could in principle be approached in seconds.

Cryptanalytic relevance: Many attacks on symmetric ciphers involve solving large systems of linear equations over finite fields. Algebraic cryptanalysis (XL algorithm, Gröbner basis methods) generates such systems from cipher structure; if HHL could accelerate these, it would pose a genuine threat to AES and similar constructions. Simon's algorithm also uses quantum linear algebra as a subroutine.

The fine print — why HHL is not yet a cryptographic weapon: HHL's exponential speedup applies only to the quantum output — it returns a quantum state encoding x, not the classical vector x itself. Reading out all N components classically costs O(N) measurements, eliminating the speedup. The matrix A must be sparse and well-conditioned (small κ). Loading classical input data requires quantum RAM (qRAM), which remains a major unresolved hardware challenge. For cryptanalysis, the matrices arising from cipher structure are often dense and poorly conditioned — exactly the cases HHL handles poorly.

What Chen's Algorithm Attempted and Why It Mattered

On April 10, 2024 — the opening day of the 5th NIST PQC Standardisation Conference — Yilei Chen (Tsinghua University) posted a preprint claiming a polynomial-time quantum algorithm for the Learning with Errors (LWE) problem with certain modulus-to-noise parameters. Using two novel techniques — complex Gaussian functions with imaginary variance in quantum algorithm design, and a windowed Quantum Fourier Transform with complex Gaussian windows — the algorithm claimed to solve GapSVP and SIVP within polynomial approximation factors. No polynomial-time quantum algorithm had previously been known for these problems.

The stakes: A valid polynomial-time quantum algorithm for LWE would have placed Kyber (FIPS 203) and Dilithium (FIPS 204) in a precarious position, potentially vulnerable to a modest further improvement in approximation factor. It would have undermined the foundations on which the entire PQC migration is being built.

The bug: Within ten days, Hongxun Wu and independently Thomas Vidick identified a fundamental error in Step 9 — an operation that assumed knowledge of the value (b*) the algorithm was trying to compute, introducing a circular dependency. Chen acknowledged: “Step 9 of the algorithm contains a bug, which I don't know how to fix.” The claim was withdrawn.