4 ms·
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 c
by tylerhou 1y 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 1y agoNo 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 1y agoThat's very pedantic, like saying "computers don't solve integer addition, AND/OR/NOT/XOR gates solve it, those are the fundamental thing".
- almostgotcaught 1y ago> That's very pedantic Yes because we're talking about pure math here not popcorn and soda.
- gsf_emergency 1y agoMy 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 1y agoVery 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).