I’m afraid I couldn’t follow. Too long since I used most of those terms or symbols.
Can anyone ELI5?
cut3•8mo ago
Claude summed it up like this:
The Hidden Subgroup Problem (HSP) is the mathematical framework that explains why quantum computers are so good at breaking encryption. Famous quantum algorithms like Shor's (for factoring numbers) and Simon's are all just different versions of solving the same underlying pattern-finding problem. The quantum "superpower" comes from using the Quantum Fourier Transform to reveal hidden mathematical patterns that classical computers can't efficiently find.
tylerhou•8mo ago
I think it would be hard to explain the details to a math undergraduate.
The high level point is that many algorithms for which quantum speedups are possible can be reduced to the Hidden Subgroup Problem, which requires a few weeks of a group theory course to understand.
almostgotcaught•8mo ago
No it wouldn't? "Given f that hides a subgroup, and an oracle for f, determine the subgroup".
The Wikipedia phrases it backwards (as do you): "quantum computers" don't solve the hidden subgroup problem, the quantum fourier transform, which "measures" f in parallel, can be used to solve the hidden subgroup problem efficiently. The QFT is the fundamental thing, not the HSP, and it's the building block for basically any/all useful quantum algorithms.
dist-epoch•8mo ago
That's very pedantic, like saying "computers don't solve integer addition, AND/OR/NOT/XOR gates solve it, those are the fundamental thing".
almostgotcaught•8mo ago
> That's very pedantic
Yes because we're talking about pure math here not popcorn and soda.
gsf_emergency•8mo ago
My attempt at less offensive analogies:
"Efficiency of hw arithmetic is not the bottleneck, lack of a poly time algo to factor prime numbers is"
&, the closely related
"Ability to reduce everything to HSP is not the bottleneck, lack of a scaleable implementation of qFT is"
tylerhou•7mo ago
Very late, but I meant it would be hard to summarize the details of the blog post (e.g. QFT implementation) even to the typical math undergraduate.
It's not hard to explain the problem, as most math undergraduates will have taken some group theory course. But even "subgroup" means nothing to most computer scientists (speaking from personal experience interacting with computer scientist academics).
FilosofumRex•8mo ago
A crude explanation might be like this - if you look at graphs of sin and cos, you'd instantly recognize their symmetries, but what if you're given the graph of a linear combination of them, and asked to decipher the coefficients?
Naively, you'd evaluate the functions at every point by trial & error until they much the shape of the given graph. Or use the symmetry of sin & cos to combine them constructively and destructively (peaks and valley) and to match the given shape.
FT & QFT are "shortcuts" that help to decipher the correct combination of basis functions.
rahulprasath•8mo ago
Can quantum computers solve hard problems that aren’t HSPs?
charleyc•8mo ago
Fantastic writeup! The exposition is extremely clear.
I particularly appreciate the choice of Simon's Algorithm as a "toy example" and the quick recap of character theory; both were very helpful for a non-QC person with an interest in this stuff.
aaaronic•8mo ago
Can anyone ELI5?
cut3•8mo ago
The Hidden Subgroup Problem (HSP) is the mathematical framework that explains why quantum computers are so good at breaking encryption. Famous quantum algorithms like Shor's (for factoring numbers) and Simon's are all just different versions of solving the same underlying pattern-finding problem. The quantum "superpower" comes from using the Quantum Fourier Transform to reveal hidden mathematical patterns that classical computers can't efficiently find.
tylerhou•8mo ago
The high level point is that many algorithms for which quantum speedups are possible can be reduced to the Hidden Subgroup Problem, which requires a few weeks of a group theory course to understand.
almostgotcaught•8mo ago
The Wikipedia phrases it backwards (as do you): "quantum computers" don't solve the hidden subgroup problem, the quantum fourier transform, which "measures" f in parallel, can be used to solve the hidden subgroup problem efficiently. The QFT is the fundamental thing, not the HSP, and it's the building block for basically any/all useful quantum algorithms.
dist-epoch•8mo ago
almostgotcaught•8mo ago
Yes because we're talking about pure math here not popcorn and soda.
gsf_emergency•8mo ago
"Efficiency of hw arithmetic is not the bottleneck, lack of a poly time algo to factor prime numbers is"
&, the closely related
"Ability to reduce everything to HSP is not the bottleneck, lack of a scaleable implementation of qFT is"
tylerhou•7mo ago
It's not hard to explain the problem, as most math undergraduates will have taken some group theory course. But even "subgroup" means nothing to most computer scientists (speaking from personal experience interacting with computer scientist academics).
FilosofumRex•8mo ago
Naively, you'd evaluate the functions at every point by trial & error until they much the shape of the given graph. Or use the symmetry of sin & cos to combine them constructively and destructively (peaks and valley) and to match the given shape.
FT & QFT are "shortcuts" that help to decipher the correct combination of basis functions.