Prime factorization is one. Another is an asymptotically faster Fourier transform.
There are several tricks in signal processing that have faster analogs in a quantum implementation. Those cool tricks are the foundation of much more complicated transformations and algorithms.
There is an entire complexity class you can read up in: Bounded Quantum Polynomial Time (BQP).
AnyOldName3@lemmy.world 5 days ago
In theory, quantum computing should be faster once hardware that’s faster is available, and only if the problem you’re trying to solve is in BQP, which isn’t that much of what computers are used for. Progress has been slow, but continuous, so the gap between simulating a quantum computer and actually using one has been shrinking. In October last year, Google’s Willow chip was verified to have achieved quantum advantage, i.e. done something that could be checked externally faster than a classical computer could have. It was only 13,000x faster, and in one specific task, which isn’t really enough to change the world, but ten or twenty years ago it was still thought to be fairly plausible that the physics might not be right and even if the practical problems were solved, they still wouldn’t work.
Even if quantum computers get ludicrously fast, they’re still not going to be especially common, and they’ll be a piece of specialised equipment, more like an electron microscope than a home PC. Most people just don’t need to do any stuff that’s in BQP, so don’t care if they can do it faster. If you’re a company, university or government body that needs to do one of the very specific things that will be faster, though, they’ll be indispensable.
technocrit@lemmy.dbzer0.com 4 days ago
Useless, contrived task.
Eheran@lemmy.world 4 days ago
But that is the thing: was it actually faster or did they just spend 10’000 hours optimizing that side and 0 hours optimizing the normal calculation?