I mean, considering that no quantum computer has ever actually factored a number, a speedup on tiny numbers is still impressive :P
I mean, considering that no quantum computer has ever actually factored a number, a speedup on tiny numbers is still impressive :P
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.
Quantum computing is cool, but a lot of the people who were hyping it last year were absolute charletons. They were promosing things that quantum computers couldn't even do theoretically let alone next year. Even the more down to earth claims were stuff we are still 10-40 years away from presented as if its going to happen next month.
Quantum computers are still cool and things worthy of research. Its going to be a very long road though. Where we are with quantum computers is like equivalent to where we were with regular computers in the 1800s.
The hype people just make everything suck and should be ignored.
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.
> 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.
Good description. Commercial fusion power seems to be in the same category currently.
The next step once you have enough thinkers working on the problem is to start pretending that commercial success is merely a few years away, with 5 or 10 years being the ideal number.
The problem is that it's an exponential slowdown on large numbers.
Hey hey, 15 = 3*5 is factoring.
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.
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
would other mersenne numbers admit the same trick? if so, factoring 2047 would be really interesting to see. it's still well within the toy range, but it's big enough that it would be a lot easier to believe that the quantum computer was doing something (15 is so small that picking an odd number less than sqrt(15) is guaranteed to be a correct factorization)