Exponential challenges
But it is actually not that hard to find a problem that can checkmate even the most powerful computers.
The key is to realize that the number of operations required of the computer to perform a calculation scales very differently for various types of problems.
For example, if you add up numbers, the number of operations grows linearly with the size of the numbers (n).
The calculation 317,456 + 467,084 requires roughly twice as many operations as 317 + 467.
If we instead multiply the same numbers by each other, the number of operations for the common arithmetic method will then grow quadratically (n2) with the number of digits in the numbers.
The travelling salesman problem
It is thus a more complex task to multiply numbers than add up numbers, and it is therefore also a more time-consuming calculation for the computer.
Computers can keep up and perform the task efficiently as long as the number of operations does not grow too heavily with the size of the problem.
But for some types of calculations, the number of operations increase exponentially (an) or worse, and this is where even the most powerful computers fall short. The calculation time becomes dramatically longer for bigger and bigger problems.
An example is ‘The travelling salesman problem’: The computer is fed a list of cities and their distances from each other, and is asked to find the shortest route that goes through all cities once and returns to the point of departure.
If there are only 10 cities to visit, there are 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 3,628,800 options for the computer to examine and choose from.
It takes time, but it can be done. If you add just three more cities to the route, there are over six billion options. The travelling salesman problem is relevant for, for example, logistics companies, and they typically have much more than 13 destinations on their routes, making the problem extremely complicated to solve.
The quantum computer constitutes both new technology and a completely new way of looking at the world
What makes the quantum computer special is precisely its potential to solve some of the problems that, due to their complexity, are practically unsolvable with ordinary computers.
This is possible because it works with a more advanced information concept than ordinary computers.
The basis of our current digital information technology, and thus the computer as we know it, is the so-called information unit called a ‘bit (binary digit), which can assume the values 0 or 1. In the quantum computer, the counterpart is a ‘qubit’ (quantum bit)—a two-level quantum mechanical system.
A qubit has two states at the same time, perhaps?
In the hardware of an ordinary computer, the abstract bit is made up of a small electronic circuit, and, correspondingly, the qubit is also a small physical system in the quantum computer.
But where the bit can only be in the states corresponding to ‘0’ and ‘1’, the qubit has more options. Its more complex state is described by the formula:But where the bit can only be in the states corresponding to ‘0’ and ‘1’, the qubit has more options. Its more complex state is described by the formula:
|ψ⟩=α|0⟩+β|1⟩
If you measure the qubit, you always get one result or the other, |0⟩ or |1⟩.
But before that, it is in a superposition of the two.
In popular terms, it is often said that the qubit can be in both one and the other state at the same time.
We can only say something about the probabilities
Quantum mechanics is the cause of many puzzles and especially the possibility of superposition states, so essential for the qubit, is a source of much confusion.
The Copenhagen interpretation, created, in particular, by Niels Bohr and Werner Heisenberg, avoids some of the problems by understanding quantum states, as shown in the above formula, as being solely an expression of the probabilities of a given measurement result.
The quantum state contains everything there is to say about the system, but it does not represent the physical object itself. Therefore, we are not to understand it as if the qubit is in both states at the same time. It would be more correct to say that it is neither one nor the other until it has been measured. Only at that moment does the state randomly collapse into one or the other.
And the only thing we can make predictions of is the probabilities of the two measurement results, which can be found by calculating respectively |α|2 and |β|2.
