Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup
9 comments
·July 3, 2025matus_barany
How does someone learn about problems like these? Is this being taught at universities (Advanced abstract algebra) or where would you recommend learning about such things?
William_BB
A standard undergraduate quantum computing course should suffice. Most of them would follow Nielsen and Chuang's book.
krastanov
Quantum Information Science classes now exist at most universities. If you have average linear algebra and probability theory knowledge, it is relatively easy to jump into them (without physics background). The Scott Aaronson lecture notes are pretty great: https://www.scottaaronson.com/qclec.pdf
sgt101
I guess this makes it more likely that Shores algorithm will actually work on real hardware? Although that hardware is a long way away?
freetonik
It's been already demonstrated that Shor's algorithm works on real hardware. Generally, AFAIK there aren't many doubts that known algorithms like Shor's or Grover's wouldn't work for some reason.
thesz
> It's been already demonstrated that Shor's algorithm works on real hardware.
No, there was no such demonstration.
Quote from https://eprint.iacr.org/2015/1018.pdf:
As pointed out in [57], there has never been a genuine implementation of Shor’s algorithm. The only numbers ever to have been factored by that type of algorithm are 15 and 21, and those factorizations used a simplified version of Shor’s algorithm that requires one to know the factorization in advance. In [13,15] the authors describe how a different algorithm that converts integer factorization to an optimization problem can be used to factor significantly larger integers (without using advance knowledge of the factors). However, the optimization problem is NP-hard and so presumably cannot be solved in polynomial time on a quantum computer, and it is not known whether or not the sub-problem to which integer factorization reduces can be solved efficiently at scale. So most experts in the field prefer to gauge progress in quantum computing not by the size of numbers factored (which would lead to a very pessimistic prognosis), but rather by certain engineering benchmarks, such as coherence time and gate fidelity.ForOldHack
Wow. Just wow.
thesz
Note the "we demonstrate quantum speedup for sufficiently small w," w being Hamming distance of the period to find.
Complete quote: "...we demonstrate an algorithmic quantum speedup for a variant of Simon’s problem where the hidden period has a restricted Hamming weight . For sufficiently small values of ..."
If we know that hidden period is exactly k bits away, we can generate C(k,n) samples, which puts us into polynomial complexity class in classical case, not exponential.
So, hold you "wow"s.
> we caveat the speedup result we find by noting that [...] the oracle we construct in this work can be efficiently simulated by a classical computer.
T_T
You could replace the quantum chip with a classical signal processor decoding the gates to perform, feeding them to a Clifford simulator, and it would solve the problem just fine. They're just arbitrarily declaring that the classical computer isn't allowed to do the thing that solves the problem fast, because that would "violate the black box condition", despite the fact that their quantum compilation and error mitigation pipeline also has to violate the black box condition.
As with many quantum papers, you should ignore the headline and just focus on how large the circuits are:
> Our current implementation of Simon’s problem requires roughly 400 two-qubit gates (after compilation) and 60 qubits
So a few hundred gates. A few times smaller than random circuit sampling experiments from 2019, though much cheaper to verify and simulate.