History of quantum computing

History of quantum computing

Jonas Stein

Quantum mechanics and quantum computing: major scientific revolutions

The discovery of quantum mechanics led to one of the greatest scientific revolutions of the 20th century. As a fundamental theory in physics, it describes the properties of atomic and subatomic matter. 
The extent of recent research achievements now points to a second quantum revolution. One of the key quantum technologies is quantum computing, which uses quantum mechanical effects to solve complex problems. This discovery is due to Richard Feynman, who discovered in 1982 that quantum computers could efficiently simulate quantum systems. To date, there are no known efficient traditional algorithms in the problem area of quantum simulation. 
The big difference between classical computers and quantum computers is the use of quantum bits instead of the usual bits. These “qubits” are the quantum mechanical equivalent of a classical bit. A qubit is a two-state system and is in a so-called superposition as long as it is not being measured. This means that it is simultaneously in both of the two possible states and only measuring it causes it to disintegrate with a certain probability into either one state or the other. A possible physical realization of a qubit is a photon whose polarization is measured using two orthogonal polarization directions.

Two approaches to quantum computing: gate and annealer

The two main approaches to implementing a quantum computer are, firstly, the quantum gate computer and, on the other hand, the quantum annealer as an approximative implementation of the concept of adiabatic quantum computation. Quantum gate computers perform calculations similar to classical computers by switching quantum gates (instead of the logic gates used in classical computing). Quantum annealers are a completely different form of quantum computers and are inspired by the metallurgical process of annealing. The applied principle is that physical and especially quantum mechanical systems always strive for the energetic minimum.
Despite the different architectures, both systems are equivalent in terms of the computing time required to solve algorithmic problems: any algorithm running on a quantum gate computer can be executed at the same time (worst-case scenario, the number of gates used is increased by a constant factor) on a quantum annealer and vice versa. In order to solve any problem with a quantum annealer, it is necessary to reformulate it as a quadratic optimization problem without constraints. Moreover, the optimization variable must be encoded as a binary number, creating a so-called QUBO problem.

Quantum algorithms and suitable problems

Since the first idea of a quantum computer, quantum-based solution algorithms (algorithms quantum computers can execute) have been developed for certain problems. These quantum algorithms are demonstrably faster than any classical algorithm for these problems could ever be. Furthermore, quantum computers can efficiently solve problems that the current state of the art of classical computers cannot solve. This includes, for example, the problem of finding the prime factorization of very large numbers, on which nearly all common encryption methods are based. As soon as the capacity of quantum computers has increased sufficiently, virtually all the information sent over the internet today could be decrypted. Quantum-safe encryptions have already been developed to prevent that from happening, but it will take several years before such encryption methods can be used across the board. 
In particular, the new quantum technologies offer far-reaching opportunities: Quantum communication and quantum cryptography can be used to develop an interception-proof quantum internet.
In 2019, for the first time, a problem was solved on a quantum computer faster than on the best available supercomputer at the time. This experimental proof of quantum supremacy involved a problem far from any practical applications; however, with ever-expanding quantum computers, it will be increasingly possible to solve such problems as well.
One question that arose shortly after the development of quantum computers was: Do quantum computers solve problems (exponentially) faster than classical computers? The hope that quantum computers could efficiently solve NP-hard problems has not been fulfilled, at least so far. Although there are algorithms that provide an exponential speedup, such as Peter Shor’s prime factorization algorithm, all of these problems are in the complexity class of NP-intermediate problems.

Construction of a quantum computer

Since the early 2000s, the construction of quantum computers has progressed rapidly. The first quantum computer with two qubits was constructed in 1998, followed by the market launch of the first commercial quantum computer in 2011, manufactured by the company D-Wave Systems. 128-qubit quantum annealers could be purchased from them for 10 million euros. Currently, D-Wave Systems is one of the few companies offering the hardware. Most other companies, including IBM and Rigetti, only sell computing time on their quantum gate computers. The number of qubits on the largest quantum gate computers is currently about 70, while the quantum annealers from D-Wave Systems already have more than 5,000 qubits. This is mainly because quantum annealers are physically easier to produce than quantum gate computers. The main problem with constructing quantum computers is decoherence, a process whereby a quantum object loses its quantum mechanical properties and “decays” into a classical object. This happens because qubits always interact with their environment, even if that is not desired within a quantum computer. Therefore, most quantum processing units (QPUs), depending on the processor architecture, must be cooled to a temperature close to absolute zero (0 Kelvin) and shielded electromagnetically. Especially the individual cooling of each individual qubit is currently causing major problems.

Outlook

It will be several years before quantum gate computers have a sufficient number of qubits to be used profitably in practical applications. The scientific consensus does not expect that to happen before 2025. But even when that time comes, it is unlikely that all problems will be solved solely on quantum computers. Hybrid algorithms that combine the advantages of both systems are much more likely.