Quantum Speedups: A Guided Tour Through Abelian Structure and Its Limits

MY OWN PARAPHRASE. A plain-language stretch of the argument, not the official abstract from the thesis itself.

The central question is one that's easy to blur: what actually separates a genuine quantum speedup from one that only looks like a speedup because of how the problem was set up? The thesis answers it by putting two things side by side: the algorithms where the advantage is real, and one famous case where it wasn't.

The first half builds the machinery and then spends it. Three algorithms line up as a chain of increasing structure. Bernstein–Vazirani is the opener: a single query recovers a hidden bit-string, because the Hadamard transform is really a Fourier transform over the group of bit-strings, and it turns a pattern hidden in the phases into something you can just read off. Simon is the keystone. It hides a whole subgroup rather than one string, its gap over any classical algorithm is exponential, and unlike Shor that gap is provable outright, with no unproven assumptions. Shor is the payoff everyone knows: factoring, through period finding, in polynomial time. But its advantage is conditional, resting on the belief that factoring is classically hard rather than on a clean separation.

What makes these three one story instead of three tricks is a single object: the characters of finite abelian groups. The Hadamard transform and the Quantum Fourier Transform are the same operation on two different groups. The technical core of the thesis is one lemma, proved in full. Measure a coset state after that transform and out comes a uniform sample from the "dual" of the hidden subgroup. Recovering Simon's secret and reading Shor's period are both that lemma plus ordinary classical bookkeeping. That proof is what lifts the thesis above a survey: not a retelling, but one mechanism worked out to the bottom.

Then it pushes on the limits, in two directions. The method stops the moment the group stops being abelian: the same idea aimed at graph isomorphism or at lattice problems runs straight into questions that are still open. And structure can fail in a second, sneakier way. In 2018 Ewin Tang showed that a quantum recommendation algorithm long cited as an exponential speedup could be matched classically, once the classical side is granted the same kind of sampling access to the data the quantum side had quietly assumed. The speedup lived in the input model, not in the problem.

So the thesis argues for a distinction. Quantum advantage does need structure (Simon and Shor make that case), but not every structure sitting inside a quantum algorithm is something only a quantum computer can exploit. Algebraic structure in the problem is one thing; a generous assumption about how you're allowed to touch the data is another. Tang doesn't touch Shor: factoring stays hard and the abelian speedups still stand; he sharpens what the word "speedup" has to mean. The take-away: advantage needs the right kind of structure, meaning genuinely quantum-exploitable algebra rather than classical information smuggled in through a powerful input model.

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.

Map and microscope. Scott Aaronson asked the same question broadly in a 2022 survey: how much structure a huge quantum speedup really needs. This thesis isn't a retelling of it. Aaronson draws the map; the thesis picks one square on it, the finite abelian hidden-subgroup problem, and works it out under a microscope, with the Fourier-sampling lemma proved rather than cited.

One argument, held tight. It's a literature study, so the contribution is in the synthesis and the exposition plus that one proved core. To stay a single argument it deliberately leaves things at the door: quantum error correction, the wider quantum-machine-learning zoo, the full non-abelian theory. Roughly 7,500 words, English, formal paper form, supervised at Utrecht University.

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.