I mean, considering that no quantum computer has ever actually factored a number, a speedup on tiny numbers is still impressive :P

▲

dehrmann 6 hours ago | parent | next [-]

I didn't get the quantum hype last year. At least with AI, you can see it do some impressive things with caveats, and there are bull and bear cases that are both reasonable. The quantum hype training is promising the world, but compared to AI, it's at the linear regression stage.

	▲	dekhn 6 hours ago \| parent [-]
		It's a variation of nerd snipe. https://xkcd.com/356/ People get taken by the theoretical coolness and ultimate utility of the idea, and assume it's just a matter of clever ideas and engineering to make it a reality. At some point, it becomes mandatory to work on it because the win would be so big it would make them famous and win all sorts of prizes and adulation. QC is far earlier than "linear regression" because linear regression worked right away when it was invented (reinvented multiple times, I think). Instead, with QC we have: an amazing theory based on our current understanding of physics, and the ability to build lab machines that exploit the theory, and some immediate applications were a powerful enough quantum computer built. On the other side, making one that beats a real computer for anything other than toy challenges is a huge engineering challenge, and every time somebody comes up with a QC that does something interesting, it spurs the classical computing folks to improve their results, which can be immediately applied on any number of off-the-shelf systems.

▲

adgjlsfhk1 5 hours ago | parent | prev | next [-]

The problem is that it's an exponential slowdown on large numbers.

▲

Tyr42 7 hours ago | parent | prev [-]

Hey hey, 15 = 3*5 is factoring.

▲

ashivkum 7 hours ago | parent [-]

my understanding is that they factored 15 using a modular exponentiation circuit that presumes that the modulus is 3. factoring 15 with knowledge of 3 is not so impressive. Shor's algorithm has never been run with a full modular exponentiation circuit.

	▲	Strilanc 21 minutes ago \| parent [-]
		The very first demonstration of factoring 15 with a quantum computer, back in 2001, used a valid modular exponentiation circuit [1]. The trickiest part of the circuit is they compile conditional multiplication by 4 (mod 15) into two controlled swaps. That's a very elegant way to do the multiplication, but most modular multiplication circuits are much more complex. 15 is a huge outlier on the difficulty of actually doing the modular exponentiation. Which is why so far 15 is the only number that's been factored by a quantum computer while meeting the bar of "yes you have to actually do the modular exponentiation required by Shor's algorithm". [1]: https://arxiv.org/pdf/quant-ph/0112176#page=15