[Latexpage]
The idea of a quantum computer first arose in the late $20^{th}$ century. Richard Feynman was the first person to think of using the special quantum properties to solve difficult mathematical problems. A lot of progress has already been achieved. “Let’s see what the future of quantum computers has to offer.”
A basic understanding of quantum computers
All computers work in basically the same way. They receive an input of data, manipulate the data in some way and finally give an output. Quantum computers are no different. But what makes them so special? Quantum computers make use of a special state that particles can achieve called quantum superposition. A quantum superposition is a special state in quantum physics, in which for instance an electron can spin in the two possible directions, spin up and spin down, at the same time. This seems strange at first. How can something be in multiple states at the same time? Since electrons are difficult to grasp for the human brain, a better example is Schrödinger’s cat. Schrödinger thought of a cat in a box with a device with a probability of killing the cat. The box would be closed and there would be no way to detect the state that the cat is in. The two states that the cat could take on are $\ket{Dead}$ and $\Ket{Alive}$. Since there is no way of knowing in which state the cat is, Schödinger posed the cat must be both $\Ket{Dead}$ and $\Ket{Alive}$ at the same time. The only way of knowing which state the cat has taken on is by looking inside the box. Such a state is called a quantum superposition. The fact that quantum computers can take on multiple states at the same time can be used to do multiple calculations at the same time. The number of calculations that can be done at the same time grows exponentially. This makes a 40-quantumbit or 40-qubit quantum computer more than a trillion or $10^{12}$ times faster than a 40-bit regular computer. Quantum computers can also make use of a special quantum state called quantum entanglement. If two particles are entangled to each other they behave in a special way. Let’s say we have two electrons that are entangled. If it is not known whether the electrons are spin up or spin down and we measure one of the two electrons, we know the direction it spins in, but because the electrons are entangled we also know that the other electron spins in the same direction. This can be used to program, for example ‘If’ statements. The last quantum state that quantum computers make use of is quantum interference. Quantum outputs are given with a certain probability assigned by the program. Since quantum states are waves of probabilities, they can be mathematically interpreted as sine waves. To manipulate these sine waves, the quantum interference property is used and the computer will give the desired answer.
Shor’s algorithm
Shor’s algorithm is an algorithm used to factor numbers into their prime factors. Its starts with a random guess that may share factors with the number you want to factor. If it does, then you are done. However most of the times it does not. What Shor’s algorithm does is basically use the initial guess ‘g’ and create a better guess.
We can use Euclid’s algorithm to check whether our initial guess shares a factor with the number N, where N is a number consisting of two primes $’p’$ and $’q’$ multiplied together.
We take for example N=697=17*41 and g=34 and then Euclid’s algorithm works as follows.
\begin{align*}{}
& 697=20*34+17 \\
& 34=2*17+0 \\
\end{align*}
Hence,
\begin{equation*}
gcd\left(g,N\right)=gcd\left(34;697\right)=17
\end{equation*}
In this case we were lucky and found one of the prime factors of N, namely $17$, but most of the times we are not so fortunate and have to do more work. If the prime factors of N have been found we the RSA encryption can be broken and we are done.
A key insight Peter Shor uses in his algorithm, is the insight that if you increase powers of a number and you calculate the result $(mod\; N)$, you will find a repeating pattern of numbers.
For example, we take N=15 and g=7 then
\begin{align*}
& 7^0\equiv1\; (mod\; 15) \\
& 7^1\equiv7\; (mod\; 15) \\
& 7^2=49\equiv4\; (mod\; 15) \\
& 7^3=343\equiv13\; (mod\; 15) \\
& 7^4=2401\equiv1\; (mod\; 15) \\
& 7^5=16807\equiv7\; (mod\; 15) \\
& 7^6=117649\equiv4\; (mod\; 15) \\
& 7^7=823543\equiv13\; (mod\; 15) \\
& 7^8=5764801\equiv1\; (mod\; 15)
\end{align*}
We also know that $gcd(7;15)=1$, hence the initial guess of $g=7$ does not share any prime factors with $N=15$. We do know that a repeating pattern exists and can make use of that. Since we know that $7^4\equiv 1\; (mod\; 15)$, we can rewrite this to find $7^4-1\equiv0\; (mod\; 15)$. Finally we know $(7^{\frac{4}{2}}+1)(7^{\frac{4}{2}}-1)=(7^2+1)(7^2-1)\equiv0\; (mod\; 15)$.
From this we can conclude that $(7^2+1)(7^2-1)=k*15$ for some $k\in\mathbb{N}$. Therefore 15 must share factors with $7^2+1$ or $7^2-1$ or in the best case one with both. To check this we use Euclid’s algorithm again. If we are unlucky and the number N shares factors with only one of the improved guesses, we take another initial guess and start over. If we are lucky and N shares one factor with each of the numbers we can determine the prime factors, $’p’$ and $’q’$, of N and we are done.
This method of finding the prime factors of a number is very time costly for ordinary computers, because every single calculation has to be done separately. Quantum computers on the other hand are specially made to do multiple calculations at the same time. You give an array of numbers as an input and the quantum computer can calculate all the modular values at once. Then the only thing we need to know is the frequency of the pattern, because then we know when the $1 (mod\;N)$ will appear for the second time. To find the frequency, quantum interference patterns with a special Fourier transformation are used. The improved guesses are given by $g^{\frac{f}{2}}+1$ and $g^{\frac{f}{2}}-1$ with $g$ the initial guess and $f=\frac{1}{p}$ with $p$ the frequency of the pattern.
What is the current phase that we are in
A lot of progress has already been made. Big companies like Google, IBM and Honeywell have already invested a lot of money with the future of quantum computers in mind. The truth is sadly, that we have not yet acquired a stable quantum computer. The companies are also racing to get the most qubits. Google is the current leader with 72 qubits. This is a lot already, but to break most current RSA encryptions, at least 5000 qubits are required. This means quantum computers may pose a threat to our data security. But since we have not reached the levels of sophistication needed to break RSA encryptions consistently, for the time being, our data is quite save.