Implications of Quantum Computing

You have read about Grover’s algorithm that gives us a quadratic speedup for search in unsorted data sets or more generally for NP-hard problems. But this is, of course, not the only application.

Quantum Fourier Transform

An important tool in digital signal processing is the Digital Fourier Transform (DFT). What it does is to take a single period of a periodic signal as an input and to decompose it into its spectrum. In music for example, when you play a single tone on an instrument, this tone consists not only of the fundamental frequency - its pitch -, but also of a number of harmonics. The relative weight of these harmonics determine the timbre of the instrument.

But, doesn’t representing a signal as a weighted superposition of certain frequencies sound really much like quantum computing already? And indeed - there is the Quantum Fourier Transform, which is a quantum algorithm for solving the inverse DFT. However, to really see its potential let’s go back one step again.

Shor’s algorithm

In 1994, Peter Shor published two algorithms for Quantum Computers. The first and lesser known one speeds up the computation of discrete logarithms. The much more famous one, however, deals with factorization, i.e. decomposing a given non-prime number into its factors.

Shor’s factorization algorithm follows a probabilistic Monte-Carlo approach. You start by choosing a random number between 1 and the composite number n. This is the stochastic part. I am again leaving out the actual math here, but we know that we could efficiently calculate a factor of n, if we only knew the order of our random number in relation to n. And this is exactly where the Quantum Fourier Transform comes into play.

In the end, the factorization of large numbers can be achieved in O((log n)3). Traditional methods in contrast have an exponential runtime behavior.

Factorization and Cryptography

Exponential growth is something that is not too intuitive for most of us. So let’s have a look at an example. Think of a number with 10 digits, such as 1 billion, and of how fast you would be able to find all the dividers of that number. We assume that we have a computer that can do this within 1 second. Hopefully, this sounds fair to you.

Now, we take a number with three times as many digits - so 20 more digits. With exponential runtime behavior we would need some time in the dimension of 1 second * 1020 for the same task. Does this number look scary? Well - it is more than 200 times the age of our universe.

This is the exact basic principle behind the RSA public/private-key encryption. It is also based upon the difficulty of factorization and uses key lengths of several thousand bits to make it theoretically impossible to break them via brute force approaches. Although there exist more efficient algorithms for factorization today, none of them can do it in polynomial runtime as the Shor algorithm can.

To sum up, in addition to all the beneficial applications of Quantum Computing that we can think of, it also poses a threat to current security mechanisms based upon algorithms such as RSA.