6 ms·
The Quantum Algorithm Zoo website[0] gives some examples of problems where the quantum algorithm is much faster than the classical one. My own view is that for
by mabbo 4y ago
The Quantum Algorithm Zoo website[0] gives some examples of problems where the quantum algorithm is much faster than the classical one.
My own view is that for a lot of (but not all[1]) problems for which we have a quantum algorithm improvement, we maybe already have a heuristic that gets us 95% of the way there just as quickly. So the application of a QC on these problems is buying us a massive speedup, but only if you need to get the perfect, optimal answer. And sometimes you do!
[0]https://quantumalgorithmzoo.org/ https://quantumalgorithmzoo.org/
[1]Factoring large primes is a good counter example.
- inasio 4y agoAn issue highlighted there is that there are very few algorithms where you have an exponential advantage vs classical hardware
- sudosysgen 4y agoI mean, even just going from n2 to n1.5 is huge.
- rdlw 4y agoIt's nice if you can do it in software, but this necessarily requires hardware. Any algorithm can be sped up by a constant factor with specialized hardware: for example, addition is 2n if you need to perform an addition with an optional carry for each digit. With specialized hardware, 64-bit numbers can be added in one operation, which makes the algorithm n/32. This kind of improvement is nice, but it would mean that quantum computers are no moe exciting than video cards. Edit: This is a result of the linear speedup theorem. https://en.wikipedia.org/wiki/Linear_speedup_theorem https://en.wikipedia.org/wiki/Linear_speedup_theorem
- refulgentis 4y agoI don't know if this sort of analogy illuminates, seems rather it hides. If we assume quantum computing is the same as SIMD, yeah, I wouldn't be excited either.
- rdlw 4y agoWhat I mean is that I would consider quantum computing a failure if it took us "from n2 to n1.5". That would make it the same as SIMD or parallel computing. I still think that linear-time factoring or sorting could be revolutionary, but only if enough interesting problems can be reduced to them. I'm holding out hope for a fast quantum SAT3 solver, at that point it will just be a waiting game until you can get an expansion card for solving NP-hard problems.
- macksd 4y ago> no more exciting than video cards Um... That seems like a pretty high bar to me, actually. Are you forgetting about how much they've done to speed up the training of quite a lot of deep-learning models? And really the only competition is TPUs and other dedicated chips that, at the end of the day, are also just chips optimized for matrix operations. The graphics in state of the art video games? Were I fan of crypto, mining rigs? That's some pretty impactful tech right there.
- rdlw 4y agoYes, but... we already have that. If quantum computing only provides a linear speedup, that can already be done with a conventional ASIC. I don't think it's a high bar for quantum computing to provide something that is not already commonly available. The real boon comes from at least quadratic runtime improvements. To be clear, I'm not saying that linear speedup is an innovation comparable to the video card, I'm saying it _is_ a glorified video card or ASIC.
- orlp 4y agoI think there's a formatting miscommunication here. The person you're replying to meant going from n^2 -> n^1.5, which isn't just a linear speedup. E.g. processing 1000 elements with an n^2 algorithm requires a million operations, with n^1.5 only ~31.5k. Processing a million elements goes from a trillion ops to a billion, a 1000x improvement.
- rdlw 4y agoHa! That explains a lot, I hadn't even considered it. Yes, a change like that would be massive, and I've just been fighting a guy I made up.
- sudosysgen 4y agoThat's not true. GPUs give a speedup of O(1) (which is the smallest of Amdahl's law's maximum and the GPU number of SIMD lanes). Going from n2 to n1.5 is not a linear speedup, it's a polynomial speedup.
- rdlw 4y agoI agree with you, but I was misled by the formatting of your comment. I thought you were saying 2×n -> 1.5×n, but now I see you mean n^2 -> n^1.5.
- sudosysgen 4y agoSorry for taking this unfortunate shortcut!
- thowieuroweiu4 4y agowhile BQP vs P is all nice and good, afaik, the scaling just isn't there yet on the hardware. one, the noise is too high, two the bits are too low, and apparently we don't have error correction whatsoever. i remember that even the 'factoring of 15' on a quantum computer uses some special hacks (that needs the answer) to code it in.