I’m thinking about quantum computers today.
Quantum computers are supposed to be “better” than ordinary digital computers in that they’re able to solve, in polynomial time, many problems that an ordinary digital computer can only solve in exponential time. This has enormous practical implications: notably, many cryptographic methods are based on the fact that there are mathematical problems that can only be solved in exponential time, rendering it impractical to break an encryption key by computer using any “brute force” method. However, if a quantum computer could solve the same problem in polynomial time, a “brute force” method may be practical.
But the thing is, quantum computers are not exactly unique in this respect. Any good old analog computer from the 1950s can also solve the same problems in polynomial time. At least, in principle.
And that’s the operative phrase here: in principle. An analog computer, which represents data in the form of continuous quantities such as lengths, currents, voltages, angles, etc., is limited by its accuracy: even the best analog computer rarely has an accuracy better than one part in a thousand. Not exactly helpful when you’re trying to factorize 1000-digit numbers, for instance.
A quantum computer also represents data in the form of a continuous quantity: the (phase of the) wave function. Like an analog computer, a quantum computer is also limited in accuracy: this limitation is known as decoherence, when the wave function collapses into one of its eigenstates, as if a measurement had been performed.
So why bother with quantum computers, then? Simple: it is widely believed that it is possible to restore coherence in a quantum computer. If this is indeed possible, then a quantum computer is like an analog computer on steroids: any intermediate calculations could be carried out to arbitrary precision, only the final measurement (i.e., reading out the result) would be subject to a classical measurement error, which is not really a big issue when the final result, for instance, is a yes/no type result.
So that’s what quantum computing boils down to: “redundant qubits” that can ensure that coherence is maintained throughout a calculation. Many think that this can be done… I remain somewhat skeptical.