Re:Classical Cryptography Will Survive Quantum Computers
by urgoroger on Friday December 29, 2017 @05:43PM
(#16032533)
I 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.
Re:Classical Cryptography Will Survive Quantum Computers
by Robotbeat on Friday December 29, 2017 @09:36PM
(#16033487)
Indeed. One of the big caveats of quantum computing is that the results are usually probabilistic. This is doubly true for today's noisy qubits.
Re:Classical Cryptography Will Survive Quantum Computers
by red75prime on Friday December 29, 2017 @02:31PM
(#16031394)
Let's hope we will not find ultimate computational limitations of our Universe's physics instead.
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
This man's blog is fantastic: https://medium.com/@decodoku/latest ...with a usefully skeptical take here: 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.