Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup | Hacker News Reader

Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup

journals.aps.org

37 pointsboilerupnc13 comments

> 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.

whether they claim to possess a high fidelity magic state is also relevant.

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?

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

A standard undergraduate quantum computing course should suffice. Most of them would follow Nielsen and Chuang's book.

I guess this makes it more likely that Shores algorithm will actually work on real hardware? Although that hardware is a long way away?

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.

> 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.

As the poster above mentioned, it's widely accepted that Shor works. We simply don't have hardware to run the full version.

The quantum papers on "factorization as optimization" are borderline scams though. I wouldn't put those papers in the same sentence as Shor.

>it's widely accepted that Shor works. We simply don't have hardware to run the full version.

I can't quite get this - surely until we have an execution on the proper hardware we can't accept that it works? There are engineering problems to resolve before we can be confident - perhaps they can be easily resolved, but so far they haven't.

I would be very curious to learn what the barriers to a demonstration of Shores on an arbitrary 8bit prime are...

It's mathematically sound and the quantum primitives it uses are well understood.

The limiting factor in practice, as with everything quantum, is noise. You are right -- we don't know for certain until it's implemented. I suppose it's part of a bigger question: whether quantum computing will work at all. My knowledge of quantum hardware is limited, so I can't really comment more on this.

Wow. Just wow.

https://en.wikipedia.org/wiki/Hidden_subgroup_problem

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.

Reply on news.ycombinator.com