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.
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.
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.
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.
charleyc|9 months ago
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.
lowdanie|9 months ago
unknown|9 months ago
[deleted]
aaaronic|9 months ago
Can anyone ELI5?
FilosofumRex|9 months 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.
tylerhou|9 months 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.
cut3|9 months 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.
rahulprasath|9 months ago