Breaking Modern Encryption With a Toilet Roll: An Introduction to Quantum Computing

Thanks to COVID-19 virtualising the Microsoft Build conference this week, I got to attend it for the first time. There were many great talks but the ones of particular interest to me were on quantum computing. Microsoft is now entering the world of quantum computing with their Q-sharp programming language. We may not have commercially useful quantum computers yet but, when we do, Microsoft plans to have the tools ready to make use of them.

Inspired by those presentations, this blog will explain why quantum computing is useful; a subject which is still deeply misunderstood by many.

My Interest in Quantum Computing

My background is a little unusual in that my education was originally in quantum physics. I even published a physics paper with my PhD supervisor, and a fellow researcher 25 or so years ago. One benefit of that unfinished PhD was being exposed to exciting developments in quantum computing and quantum encryption. One of those developments was the invention of Shor’s Algorithm in 1994 (just two years before I put out that physics paper). Shor’s Algorithm sent waves through the academic community because it showed that, in theory, a quantum computer could break modern encryption. If a sufficiently powerful quantum computer could be created, no encryption would be safe. Arguably, it was Shor’s Algorithm and its implications that led to the commercial funding of the development of quantum computers from that time until now. Even though that was 25 years ago and there has been billions of dollars of investment since then, quantum computers still have a long way to go before they can crack modern encryption.

Modern Encryption

One would expect that the encryption methods that protect our secrets are based on some deep, mathematical concepts, inaccessible to all but mathematics professors but this is not true. A lot of modern encryption is based on one simple concept: it is much easier to multiple two numbers together to form a bigger number than to take the bigger number and work out the two numbers used (called factors).

For example, we know that 3 multiplied by 5 is 15 and, because most of us know our times tables, we can easily divine that the factors of 15 are 3 and 5. However, not as many of us can immediately reason that 221 is the product of 13 and 17. Scale this up and you have a system which can readily encrypt secrets but cannot be readily broken.

Factoring with a Toilet Roll

Is there a way we can try lots of potential solutions at once to find the factors of a number? One way is with resonances on a tube. We know that if we blow on a pan pipe, we hear a note. This is note is constructed of the resonant frequencies in the pan pipe tube.

The physics of tube resonance is well understood.

Image from http://www.ctgclean.com

So, if we have a tube of length 221/2 mm = 110.5mm (about the size of a toilet roll) this will resonate with tones of wavelength 13mm and 17mm among others (use inches if you prefer, it does not really matter although a 11 inch tube would be closer to a kitchen roll).

Now comes the clever part. Let us construct a sound using a synthesizer made up of tones of wavelength 1mm, 2mm, 3mm, and so on. We then play the sound through the tube and identify which tones resonate.

Unless we have pitch perfect hearing we might need some help identifying the wavelengths of the tones which resonate. We can do this with a spectrum analyzer. If you have ever seen a car stereo from the nineties you will be familiar with a spectrum analyzer. It looks like this:

Using a clever piece of mathematics called a Fourier transform, the spectrum analyzer takes the sound being produced by the toilet roll and breaks it up into its component tones. The resonating tones will be louder and appear as taller on the spectrum display.

Once we identify these resonant tones, we can convert them back to numbers and we have our factors. The algorithm looks something like this.

So what stops us pulling out a Moog Synthesizer, a toilet roll, an old car stereo, and unlocking the world’s secrets? The numbers we need to factor in modern encryption are really long i.e. a few hundred digits long. Using millimetres to define our wavelengths, we need a tube longer than the width of the observable universe to crack it. That is a lot of toilet paper!

Shor’s Algorithm

Shor resolves the problem by abandoning the toilet roll for a cleverly constructed mathematical function, and uses a quantum superposition instead of our synthesized wave. Otherwise, the process parallels our own.

While the mathematics is complex, the idea is very similar to ours. We convert the problem to something we can work with, throw multiple possible solutions at it at once in such a way that the actual solutions separate themselves out, we identify them using Fourier, and check they work.

Is Modern Encryption Dead?

The good news is we still have lots of time ahead of us before we need to overhaul modern encryption. While RSA encryption relies on the factoring problem described and can be tackled by Shor’s Algorithm, other encryption techniques, such as AES encryption are not. Even if we created a sufficiently powerful quantum computer, AES encryption remains strong.

This also leads to the second reason why modern encryption remains unchallenged; it is really hard to create a stable quantum computer. To date, the largest number factored by a quantum computer using Shor’s Algorithm is 291,311. In essence, to challenge modern cryptography, we need a quantum computer thousands of times more powerful than the best machine today and progress is slow.

So Why Are Quantum Computers Useful?

It may seem we have invented the mathematical equivalent of a Rube Goldberg machine, but the fact is this approach of throwing a spectrum of quantum states at a quantum toilet roll and seeing what comes out is much quicker than trying to crack the code with a normal computer. While it may take a normal computer more than the age of the universe to crack this type of encryption, a quantum computer of sufficient size can do it in hours. For encryption, there are still significant hurdles but it speaks to the potential of quantum computing.

The key here is quantum computers allow us to answer questions differently so problems, like this one, where there are lots of potential answers, can be tackled much more efficiently than with a classical (non-quantum) computer. It is for this reason that optimization problems, such as traffic routing, or delivery distribution lend themselves well to quantum computer algorithms.

Chemistry has its foundation in quantum mechanics but anything more complex than the hydrogen atom requires computer simulation to predict. To simulate and design novel molecules for drug manufacturing, it makes sense to use a computer rooted in a quantum world. While projects like Folding@home attempt to tackle the problem by stitching together a vast array of classical computers through the internet, a quantum computer could revolutionize the approach and rapidly accelerate the discover of elusive cures.

There are many applications waiting for quantum computers to become a reality but the fields are green and there is still much to be discovered. Even today, applying quantum algorithms on simulated quantum computers while not providing speed efficiencies, are proving to be superior to the classical algorithms and worth implementing. If you have problems which are computationally intensive, it may be worth considering quantum computing for the task.