For now lets be hopeful and assume that working quantum computers will be as available in the near future as classical computers are now. This hope is grounded in the many techniques that exist at the moment and could potentially be used if researchers find a way to scale them up [1].
The question is then what would we use them for?
This might seem like a weird question to ask, after all nobody predicted that computers that grew out of military research projects during the second world war would find their way into nearly all aspects of our life. However because algorithms for quantum computers exist already today [2] one can reasonably speculate about the classes of scientific problems that can be tackled with them.
Broadly speaking a quantum computer works by replacing the bits, units that can be either 1 or 0, in a classical computer by Quantum bits (Qbits) that can be a superposition of both. This is one of the fundamental consequences of quantum mechanics where objects might not be in a single defined state but rather a superposition of different states (think of Schrodingers cat). The idea is that the superposition represented by the Qbit allows computations to run more efficiently because many calculations can be done in parallel.
It is easy to imagine that it is much harder to control quantum systems than it is for classical systems. Thus it was not clear if quantum computers could ever be useful. Until 1994 that is. In this year Peter Shor developed a quantum algorithm that could drastically outperform any classical algorithm for the factorization of integers (see [3] for a broader introduction). Besides demonstrating that quantum computers can be useful this sparked the interest of the cryptography community, as factorization is at the heart of popular encryption techniques like RSA. A real quantum computer would thus drastically alter cryptography.
On the other hand an example where quantum computers might not outperform classical computers are optimization problems, i.e. finding the best solution to a problem with many variables and constraints. This limitation is due to the fundamental way in which quantum computers operate: To get the readout the quantum systems has to be brought from its initial state (input) to the final state (output) so slowly that no Qbit is kicked out of its lowest energy state. However the more complex the optimization problem becomes, the easier it is to disturb a Qbit [5]. To still get an accurate result for complex problems one has to operate the computer more and more slowly. The total calculation thus takes much longer and the speed gain compared to classical computers vanishes.
It is thus interesting to note that quantum computers will not be a panacea for problems in computational science. Which problems will be treated more efficiently with quantum computers than classical computers remains to be seen.
Stephan Koehler
[1] Ladd et al. “Quantum Computers”, Nature 464, 45 (2010)
[2] Childs and van Dam, “Quantum algorithms for algebraic problems”, Reviews of Modern Physics 82 , 1 (2010)
[3] Ekert and Jozsa, “Quantum computation and Shor’s factoring algorithm ”, Reviews of Modern Physics 68, 733 (1996)
[4] Fahri et al., “Performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs ”, Physical Review A 86, 052334 (2012)