According to University Lecturer Åsa Hirvonen, the recently developed quantum computer introduced in a scientific journal in the autumn of 2019, was successful in solving a very specifically defined problem. The computer cannot be used for factoring or simulating physical systems, which are specific tasks for which quantum computers are being developed. Another matter which appears to cause confusion is the fact that even if integer factorisation were possible, this does not yet mean that quantum computers could be applied to arbitrary classically difficult problems.
“There are no NP-complete problems for which a suitable quantum algorithm is known,” Hirvonen notes.
How is quantum supremacy defined?
Hirvonen points out that it is very difficult to prove with mathematical precision, that is, conclusively, that something cannot be solved classically in polynomial time. This is exactly why the P versus NP problem may be the biggest unsolved problem in computer science. It is the reason why quantum supremacy has not been defined as a theoretical result (such as ‘a quantum computer solves a problem in polynomial time unsolvable by classical computers in polynomial time’). Instead, quantum supremacy has a more practical definition: a quantum computer is used to solve a problem which would take known algorithms too long to solve by classical means – practically so long that no one would even bother to attempt it.
In fact, Hirvonen expects a protracted struggle during which quantum supremacy will be declared, after which it will be demonstrated that a classical computer is able to carry out the same calculation in almost the same time, after which more qubits are added.
“What all the fuss is about is that quantum computers are expected to be able to solve Shor’s algorithm, meaning that integers can be factored into their prime factors in polynomial time. Should this become possible, all cryptographic techniques currently widely in use would become useless,” Hirvonen says.
Hirvonen does not believe this will lead to disaster. Even though she modestly notes that she is not an expert in cryptography, she does assume that the development of new techniques is already well underway.
Introductory and continuation courses in quantum computing
Next autumn, the teaching programme of the Master’s Programme in Mathematics and Statistics will include two courses in quantum computing.
“On the introductory course, the very basic principles of quantum computing are introduced to students. On the continuation course, a closer look will be taken at a handful of selected topics, including error correction and quantum complexity theory,” says Hirvonen, who teaches the two courses.
Whereas classical computing is based on bits, which are either a one or a zero, quantum computing utilises qubits, which can represent a one or a zero, or a little bit of both. These are subjected to quantum operations, which correspond to the logic gates of classical computers.
The topic has a link to the courses in linear algebra offered in the first year of studies:
[Mathematically, a qubit is a unit vector in a complex two-dimensional inner product space, observed in relation to an orthonormal basis whose base vectors are called one and zero.]
In other words, two perpendicular vectors of length 1, named 0 and 1, are chosen, and their complex linear combinations (of length 1) are observed. These form the possible states of a qubit. However, the only observable states are the basic vectors 0 and 1. The strength of quantum computing is based on the qubits’ ability to assume a different state during computing, or superpositions of 0 and 1.
What can be computed in a reasonable time?
In any case, something unprecedented has already been achieved, and the quantum computer is challenging what is known as the extended Church-Turing thesis, according to which all models of computation are able to simulate each other within a polynomially bound overhead in time.
In a few minutes, it was able to complete a calculation which no available technique has been able to do so far. However, there is still dispute on the supremacy of the quantum computer, since the best possible classical algorithm may be yet to be discovered.
In an article published in Nature, the Google team claims that solving the problem would take 10,000 years for classical computers. On the other hand, IBM’s team of researchers say that it would only take a couple of days (with a supercomputer built by IBM). Technically, quantum supremacy will stand until someone actually completes the same calculation with classical means.