When it comes to quantum computing (QC), after the quite real breakthroughs in hardware and some spectacular announcements under titles like “Quantum Supremacy“, the usual hype cycle has developed with a phase of vague and exaggerated expectations. I would like to briefly outline here why the enormous effort is being made in this area and what realistic expectations lie behind it.
To understand the fundamental differences between QC and Classical Computing (CC), we first need to take a step back and ask on what basis both computing paradigms operate. For the CC, the basis is the universal Turing machine expressed in the ubiquitous von Neumann architecture. This may sound a bit outlandish, but in principle it is easy to understand: An universal Turing machine abstracts the fact of programming any algorithm into a classical computer (universal) that is somehow (classically) algorithmically expressible (Turing machine).
The vast majority of “algorithms” that are implemented in practice are simple sequences of actions that react to external events such as mouse clicks on a web page, transactions in a web store or messages from other computers in the network. A very very small, but important, number of programs do what is generally associated with the word algorithm, which is to perform arithmetic operations to solve a mathematical problem. The Turing machine is the adapted thought model for programming these problems and leads to programming languages having the constructs we are used to: loops, branches, elementary arithmetic operations etc.
What is the computing paradigm for a quantum computer?
A quantum computer is built up of quantum states that can be entangled with each other and evolved via quantum gates. This is also a bit off the wall, but simply means that a quantum computer is set to have an initial (quantum) state that evolves in time and is measured at the end. The paradigm for a quantum computer is therefore the Schrödinger equation, the fundamental equation of quantum mechanics. Even without understanding the details, it should be clear that everyday problems are difficult to squeeze into the formalism of quantum mechanics and this effort probably does not bring any profit: Quantum mechanics is just not the adjusted model of thought for the most (“everyday”) problems and it is also not more efficient in solving them.
So what can you do with it?
The answer is very simple: QC is essentially a method for quantum computing. Now this sounds redundant, but it means that a quantum computer is a universal machine to calculate quantum systems. This vision, formulated by Richard Feynman way back in 1981, is still followed by the logic of research today. Thus, it is not surprising that publications on the subject dealing with applications are located either in quantum chemistry or in the basic research of physics .
Why does this matter?
Because the classical computer is very inefficient in calculating or simulating quantum systems. This inefficiency is basically due to the mathematical structure of quantum mechanics and will not be solved by classical algorithms, no matter how good they are. In addition to basic research issues, QC is likely to become important in the hardware of classical computers, where miniaturization is pushing the limits of designing transistors on chips using classical theories of electricity.
Besides, there are a lot of interesting connections to number theory and other various problems, which so far can be classified as interesting curiosities. Based on current knowledge, the connection to number theory alone could have a significant impact, because for historical reasons almost all practical asymmetric encryption schemes rely on algorithms that essentially assume (there is no proof) that prime number factorization cannot be solved efficiently with classical algorithms. Quantum computers can do this in principle but are far away from being able to do so in terms of hardware.