3 ms·
It turns out, though, that those few problems are pretty common. FFT is O(d log d) classically, and O((log d)^2) Quantum mechanically. Gaussian elimination (u
by Robotbeat 9y ago
It turns out, though, that those few problems are pretty common.
FFT is O(d log d) classically, and O((log d)^2) Quantum mechanically.
Gaussian elimination (used to find eigenvectors and eigenvalues) is O(d^3) or O(s * d^2) for classical (non-sparse and sparse, respectively) versus O((log d)^2) for Quantum.
(And similar speed up for Matrix inversion.)
FFT? Matrix inversion? Gaussian elimination? Super common. And in the case of Gaussian elimination, it gets pretty hard pretty fast.
You're right that we still have to scale with proper error correction, but the fact that quantum error correction is possible is very good news for the future of quantum computing. And the best, ~50-bit quantum computers are approaching what is needed for a fully error corrected qubit, although proper connectivity needs some work.
So you're right to be wary of the current status of quantum computing, but I think you're wrong about Moore's Law, here. Qubits can be and are made with photolithographically scalable techniques today with error rates that approach what's needed for error correction, even taking into account some of the problems that integration causes for integration. And, in fact, error correction is what enables us to scale quantum computing (although there are still some calculations we can do without error correction).
I do think we're pretty close to a threshold, here, with quantum computing. We are probably under one or two years away from "quantum supremacy," if you accept having a quantum computer too sophisticated to reliably simulate classically.
Some resources:
Google talk about Quantum computing engineering work being done at MIT Lincoln:
https://www.youtube.com/watch?v=Jgc20Xc8IpA https://www.youtube.com/watch?v=Jgc20Xc8IpA
This man's blog is fantastic:
https://medium.com/@decodoku/latest https://medium.com/@decodoku/latest
...with a usefully skeptical take here:
https://medium.com/@decodoku/quantum-computing-is-not-as-close-as-you-might-have-heard-e26ad533409 https://medium.com/@decodoku/quantum-computing-is-not-as-clo...
We aren't 3 years away from breaking encryption using Shor's Algorithm. We're probably at least a decade away. But there ARE a bunch of uses for quantum computing that don't require as many qubits. A few hundred physical qubits is still enough to do things that wouldn't be feasible with classical computing.
- red75prime 9y agoLet's hope we will not find ultimate computational limitations of our Universe's physics instead.
- urgoroger 9y agoI want to add that quantum FFT performs the transform on the amplitudes in the n-qubit state. Thus its output is an n-qubit state with the amplitudes matching the fourier tranforms. We cannot actually directly extract the amplitudes of the resulting state (which is the actual transformed values) from the system, since a measurement collapses the state of the system. While some people have figured out how to used the result of the quantum FFT to do useful things (e.g. Shor's algorithm), it does not actually provide us with the transformed values in the traditional sense as the classical algorithm does.
- Robotbeat 9y agoIndeed. One of the big caveats of quantum computing is that the results are usually probabilistic. This is doubly true for today's noisy qubits.