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 2 days ago | parent [-]

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 2 days ago | parent [-]

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

▲

William_BB a day ago | parent [-]

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.

▲

sgt101 14 hours ago | parent [-]

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

	▲	William_BB 13 hours ago \| parent [-]
		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.