COMPLETED BACHELOR'S THESIS · UTRECHT UNIVERSITY
Quantum Speedups: A Guided Tour Through Abelian Structure and Its Limits
When does a separation between quantum and classical algorithms amount to a substantive computational advantage? The thesis studies two roles of structure: algebraic structure extracted through quantum Fourier sampling, and low-rank structure already exposed by an input-access model.
01 · ABSTRACT
THESIS SUMMARY · Based on the final version completed in July 2026.
A separation between quantum and classical algorithms supports a substantive claim of computational advantage only when both sides solve the same problem, receive comparable access to the input, and are evaluated using the same computational resource. The thesis formalises this as a comparison framework with three components: problem, access model and resource measure — (P, A, R).
The first part applies that framework to algebraic structure. In the abelian hidden-subgroup problem, quantum Fourier sampling transforms coset states into samples from the annihilator of the hidden subgroup. This mechanism connects the character-sampling structure of Bernstein–Vazirani to the exponential quantum query advantage in Simon's problem. Shor's order-finding procedure follows the same general Fourier-sampling principle, although its separation from classical computation remains conditional on the classical difficulty of factoring or order finding.
The analysis also marks a boundary: hidden algebraic structure by itself does not guarantee an efficient quantum algorithm. Moving from finite abelian groups to the non-abelian hidden-subgroup problem introduces representation-theoretic complications, and important applications such as graph isomorphism remain unresolved.
The second part studies structure supplied through data access. Ewin Tang's classical recommendation-system algorithm shows that, when a classical algorithm receives sample-and-query access comparable to that assumed by the quantum algorithm, it can exploit the same low-rank matrix structure with polylogarithmic dependence on the matrix dimensions. Under those comparable assumptions, the previously claimed exponential separation disappears.
The resulting boundary is therefore not simply quantum versus classical computation. It is the boundary between structure extracted by a computational procedure and structure already made available by the input model. A convincing speedup claim must show that its advantage comes from the algorithm itself, rather than from an asymmetry in the problem definition, data access or resource accounting.
02 · THE ROUTE
Bernstein–Vazirani, the opener
The simplest appearance of the mechanism: phase kickback encodes a hidden bit-string into a character state, and a final Hadamard transform recovers it with one quantum query. The separation is linear, not exponential.
Simon, the keystone
The cleanest hidden-subgroup instance and the unconditional result at the centre of the thesis: O(n) quantum queries versus Ω(2n/2) classical queries in the bounded-error query model.
Shor, the payoff
Order finding supplies the quantum core of factoring in polynomial time. Unlike Simon's oracle separation, the claimed exponential advantage remains conditional because no superpolynomial classical lower bound for factoring or order finding is known.
Fourier sampling, the common mechanism
The thesis proves the Fourier-sampling lemma for Simon's group, (ℤ/2ℤ)n: transforming a coset state yields a uniform sample from the subgroup's annihilator. It then states the corresponding theorem for finite abelian groups.
The abelian boundary, where the method stops
The moment the group stops being abelian, characters no longer suffice. The same approach applied to graph isomorphism or to lattice problems runs into problems that are still open. That is the natural edge of the first half.
Tang's dequantization, the second movement
Structure can also break through the input model. A quantum recommendation algorithm's exponential edge vanishes once a classical algorithm is granted comparable sampling access, so the advantage was in the assumptions, not the problem.
03 · FRAMING & SCOPE
A speedup isn't a property of a problem alone. It's a property of a problem together with how you're allowed to access the input and what you're counting as the cost. Written out, that's a triple (problem, access model, resource measure), and the access model turns out to be the variable everyone forgets to state. A fair comparison has to hand both sides the same access, and a lot of the thesis is about taking that seriously.
From the broad question to one framework. Aaronson and Ambainis ask how much structure is needed for large quantum speedups. The thesis narrows that question to two concrete settings: Fourier sampling for finite abelian hidden subgroups, and dequantization of recommendation systems under sample-and-query access.
A literature thesis with a technical core. The contribution lies in the synthesis, the explicit (P, A, R) comparison framework and the detailed derivation of Fourier sampling for Simon's group. To keep one coherent argument, the thesis limits its treatment of non-abelian methods and the wider quantum-machine-learning literature. The completed thesis is in English, formal paper form and carries 7.5 EC at Utrecht University.
04 · WHY THIS TOPIC
It's the one subject that uses both halves of my degree at once. The hidden-subgroup problem is group theory at heart, straight from the abstract algebra in my mathematics minor, while the question of what counts as a genuine speedup is complexity theory, the part of AI and computer science I keep coming back to.
And the framing earns its keep for AI specifically. Quantum machine learning attracts more confident claims per paper than almost any nearby field, and Tang's result is the sharpest available tool for testing them: you can't judge a quantum advantage in ML without stating, symmetrically, how each side is allowed to reach the data. Working out where that boundary actually runs felt more useful than adding one more algorithm to either side of it.