Today I feel like writing another one of my periodic more unpopular articles. I’m going to get a bit technical again.
You’ve probably all heard about something called a quantum computer1. It’s not just any old computer, see, it uses the magic quantum stuff.
What’s all the fuss about? It depends whether you read science fiction or science (although with covid it has been a bit more difficult to reliably distinguish the two). In science fiction terms a quantum computer is a magic MacGuffin that can basically do anything and everything the author wants it to2. The truth is a little less spectacular.
The Turing Machine (TM)
In order to understand the significance of this quantum development we have to go back to Alan Turing. Turing possessed a brilliant, brilliant mind. His treatment by the UK government (he was homosexual), despite playing a significant role toward victory in WWII, was nothing short of a disgrace; a national shame that ultimately robbed the world of one of its finest minds.
One of Turing’s great intuitions (and advances) was to develop the idea of something that is now known as a Turing Machine (TM). This is a theoretical device (although you can actually build one3) that performs a computation. In order to get at the essence of what computation is, Turing imagined an infinite tape consisting of some binary sequence that is fed into this TM. Depending on the internal ‘state’ of the machine, it could move the tape back and forth (or, equivalently, move itself back and forth along the tape), and/or re-write the bit (binary digit) on the tape, and change its internal state dependent on the received bit.
Schematically it looks like this
It may seem a bit surprising, but any computation that a computer can do can be done on one of these machines. It’s a bit of a nightmare to actually create one of these machines (on paper) even for a simple calculation.
Turing was trying to solve the Halting Problem, which is the problem of whether there exists an algorithm that is able to predict whether a general algorithm will stop or not. So if you’re given an algorithm is there a procedure for determining whether it will stop, and does this work for any algorithm (and arbitrary set of inputs) one might consider?
One example might be to consider Fermat’s Last Theorem (FLT - and before it was proven by an alternative method). This theorem states that there is no solution for n > 2 to the equation
where n, x, y and z are natural numbers (positive integers). We know there are solutions when n = 2. We probably recall Pythogoras’ Theorem from school. One example would be x = 3, y = 4 and z = 5, which could represent the lengths of the sides of a right-angled triangle with z being the hypotenuse. We can see, from Pythagoras, that the length of the hypotenuse is related to the lengths of the other two sides as
But if n = 3, say, could we find integers x, y and z that would work?
Suppose you wrote a computer program to run through all the possibilities; stepwise increasing n, x, y and z until it found a solution. Would it stop?
If you could run an algorithm that could answer this question, then you’ve settled the question of whether FLT is true or not.
We now know such a program to seek a solution for FLT wouldn’t stop (FLT has been proven to be true), but the Halting Problem is about whether there is a procedure (itself a computation) that would be able to answer this question for FLT and for any other algorithm we care to query.
Turing, using his TM, was able to show that such an overarching ‘decision’ algorithm does not exist.
But what he achieved was more than this - he formalized the whole notion of computation by demonstrating its equivalence to the running of one of these TM devices. Turing created a whole new way of answering questions about algorithms and computations.
It was an interesting time in mathematics. A few years before Turing developed his notions about computation, Kurt Gödel had asked (and answered) questions like whether it was possible to have true statements within some set of axioms that couldn’t be proven by using that set of axioms, or whether a certain set of axioms could be shown to be consistent and complete. Mathematicians, then, were starting4 to think deeply about the whole process of reasoning and logic.
Physicists Muscle in on the Action
And along comes Johnny Physicist a few decades later (we can be a bit slow on the uptake) in the figure of Richard Feynman.
With Feynman’s typical no-nonsense, cut to the core, approach he noticed something interesting about the Turing machine. Yes, you could theoretically build one of these Turing machines that could do any calculation (algorithm) - it’s called a Universal Turing Machine (UTM). But there’s a little something that has been missed here - and that something is quantum.
If there’s something missing, does that mean that the UTM is not quite so universal, after all?
Feynman noted that the whole conception of one of these machines rested on an implicit physical assumption. The thing the machine is said to work on is a tape with binary digits written on it - and that’s making an unwritten assumption (or a limitation) on something that is physical. What if we allowed those binary digits to be quantum in nature and to allow the machine to do operations permitted by quantum mechanics?
David Deutsch took these ideas further by developing a theory around a Universal Quantum Turing Machine, but it wasn’t until 1994 when Peter Shor lit the blue touchpaper and devised an algorithm that could be run on a quantum computer that could do, if we could only build one of these things, something quite extraordinary.
Reading, Riting and Rithmetic
What was the algorithm?
It was an algorithm to factor numbers.
Well, that sounds a bit underwhelming, doesn’t it? I can factor numbers too. A number like 24 can be written out into its prime factors as 2 x 2 x 2 x 3. Mathematicians have been doing this for some time you know. Indeed, it can be shown that any non-prime number (integer) can be written as a product of its prime factors.
This is so important it’s known as the Fundamental Theorem of Arithmetic - and it’s been known about for millennia (thanks, Euclid).
Ordinary computers can do this shit, so why do we need to do it on one of these blasted all-singing, all-dancing, quantum machines?
We’ll get to why in a bit, but first let’s understand why the process of factorization is, itself, important.
You may not have realized it, but there’s something a bit “off” about factorization. The flip side, the ‘inverse’ operation, is multiplication. If I gave you two large numbers and asked you to multiply them together
77,767,777 x 23,573,527 = ?
How long did that take you to do?
About 10 seconds, maybe, on a calculator.
It’s not immediately obvious, but the two numbers above here are prime numbers.
What about doing this the “other” way. Suppose I gave you a number and told you it was made up by multiplying 2 prime numbers together. Now your task is to factorize this number into a product of those 2 primes. Have a go. Here’s one
6,279,388,431,711,013
Found the prime factors yet? This example is trying to get across the idea that multiplication is ‘easy’, but factorization is much harder. Of course, one could write a program to quickly factor this number. So surely this difficulty is only apparent, because we’re not as used to factorization?
The number above has 16 decimal digits. It is indeed easy to write a factorization program that would find the answer (the two primes) in less than a second. But what if the number I wanted to factorize was 617 decimal digits long?
Our supposed “fast” factoring algorithm would really struggle. The best factoring algorithms we currently have would take trillions of years, to factor this number into its two primes. If we knew the two primes - multiplying them together would still be easy and very quick (on a computer).
It is not known, and currently an unresolved problem, whether we can develop significantly faster algorithms to solve this problem. The study of this kind of thing, how fast algorithms run, is important. To describe these things mathematicians and computer scientists talk about complexity classes of problems - which is about whether certain problems can be solved ‘quickly’ or not. In essence, they try to answer a question like “if I increase the input size, does the difficulty go up like the input size squared (say), or does it go up exponentially?”
The complexity class where the difficulty squares with the input size? One of the ‘easy’ classes. The complexity class where the difficulty is exponential in the input size? You’re in trouble - this is a ‘hard’ problem.
It isn’t known what complexity class factorization belongs in - it is thought to be in one of the ‘difficult’ ones5.
Don’t Lose the Will to Live Just Yet
Well isn’t that all just fine and dandy? What’s the point of this academic frippery?
As weird as it might seem, all of this has to do with security, with keeping our messages safe from prying eyes (and our financial transactions safe from criminals etc).
When we send a message to someone we’d kind of like it if only the people we want to receive the message are able to read it. How do we do that? The main technical way this is achieved is by encryption. We can think of this as a kind of mathematical shuffling that gets unshuffled at the (legitimate) receiver end, but there’s a nice physical analogy.
It’s like writing our message on a piece of paper and putting it in a box. We then lock the box. Now we can send it anywhere with peace of mind - because only those people who have a copy of the key can open the box. That’s the basic idea, but do you see the flaw here?
In order to send our messages securely, we already have to have sent a message (the key) securely. How do we get the key to other people securely?
This kind of security technique is known as private key encryption. The key has to remain private and known only to legitimate users.
In the 1970’s the idea of public key encryption was developed - and things like factorization played a big part.
To continue with the locked box analogy we do the same thing as before, but now we have a box with two keys. It has a special kind of lock. If we lock it with one key it has to be opened with another, partner, key. The idea here is that we can give everyone the ‘locking’ key - and if they want to send a secure message to us they can lock the box with this locking key. To unlock the box you need the ‘unlocking’ key - and that’s something only you have.
This technique is known as public key encryption. To send a secure message you just look up someone’s public key and use that to ‘lock’ the box.
The astute here will notice that we haven’t really ‘solved’ the key problem - we’ve just shifted it elsewhere. If I have a sensitive message I want to send to Nigel Nibblynuts, I will look for Nigel’s public key, but how can I be sure it really IS Nigel’s public key and not just some imposter posing as Nigel?
That’s a topic for another day.
The important thing to realize is that the security of much of the world’s electronic traffic fundamentally depends the technique of public key encryption. So how does it work?
Factoring All The Bits In
The asymmetry (in difficulty) of the multiplication/factorization system is what gives us the clue here. If there was some way to use a big number that was the product of two primes I could keep those 2 primes secret and give everyone else the big number. I’d ‘know’ that nobody could figure out, or use a computer to figure out, what those 2 primes I’ve chosen are. If it’s something I give to everyone - then this could be my public key.
Generating this big number is easy. Just choose 2 big prime numbers and multiply them together; this is a fast operation. Going the other way and ‘splitting’ the big number into the product of two primes - that’s not so easy at all.
Using the numbers in the above example I might choose the pair of primes (77767777, 23573527) to be my private key. I’d just multiply them together to give 1833260790839479. I could send everyone this big number (or place it in a public directory) so that they could use it - and I’d be happy that it’s going to take a long, long, long time6 for anyone to figure out which 2 primes I used to generate it.
Does an encryption algorithm that makes use of this kind of asymmetry in difficulty exist? Indeed it does - it’s the RSA public key algorithm invented by Rivest, Shamir and Adleman7. It is a really beautiful application of number theory (too complicated to include here), but fundamentally the security is based on the asymmetry in difficulty of multiplication and factorization.
The RSA algorithm is widely used to secure electronic traffic today. If you’re on the internet, you’re probably making use of it (unknowingly) lots of times every day.
Are You Shor About That?
With the publication of his quantum factoring algorithm8 Peter Shor threw an almighty quantum spanner in the works.
What Shor was able to show was that if you could build a quantum computer and run his algorithm then you could factor one of these big 617 decimal digit numbers into its 2 primes in a matter of seconds.
Seconds - not trillions of years.
Ouch! That’s something of a concern when public key systems are so deeply embedded in the electronic security infrastructure of the entire planet.
What he did was, essentially, to take one of the fastest factoring algorithms we have and to translate the fundamental part of that algorithm into the quantum world. The (classical) factoring algorithm makes use of something called a fast Fourier transform and it’s this part that Shor utilized. He used the insight that quantum mechanics (sort of) automatically does Fourier transforms - in other words, our world is built on something that does this in the blink of an eye using ‘physics’ not ‘maths’.
The important quantum feature he used was entanglement. If we’re going to take our tape in the (classical) Turing machine and replace them with quantum objects then we have to allow for the possibility that all of these quantum ‘bits’ can be entangled with one another.
I’m going to leave a fuller description of what entanglement is for a later date, but one way of thinking about it is that entanglement generates correlations that cannot be reproduced by classical systems. In a certain sense, there is more ‘information’ in the correlation between quantum objects than can exist in the correlation between classical objects.
The good news (or bad, depending on your perspective) is that quantum algorithms are so far quite limited. Apart from a couple of special cases, they can’t do anything a plain old classical computer can’t do. They can, in some cases, lead to a massive reduction in the theoretical computation time.
Shor’s quantum algorithm, then, is essentially not doing anything ‘different’ - what it’s doing is to change the complexity class of a given problem.
Another well-known quantum algorithm is Grover’s Algorithm which is a search algorithm that reduces the time by a square root factor. If you search a space consisting of n bits it will take 2 to the power of n steps.
For example, if you have to search something that’s 3 bits long - then you have 111, 110, 100, 101, 011, 010, 001, and 000 to search over. That’s 8 things to search, or 2 to the power of 3.
With Grover’s algorithm you can square root the time factor - a problem that would take 2 to the power of n steps on a classical machine can be done in 2 to the power of n/2 on a quantum machine. If, for example, you had to search a space of 4 bits you’d have to (classically) consider 16 steps. Grover’s algorithm could do the same search in only 8 steps*.
[*Subsequent edit : I hadn’t noticed I’d got this wrong. I don’t know what I was thinking. Probably not thinking very much at all. If you start with 4 bits to search, that’s 16 possibilities to search through, which is 2^4 = 16. Grover’s algorithm allows us to reduce this by a factor of a square root to give sqrt (2^4) = 2^(4/2) which of course equals 4! So in crypto terms, when doing an ‘exhaustive’ key search, you ‘square root’ the search space which means halving the effective key size].
This, too, has consequences for cryptography. For private key cryptography the security is based on the length of the key. For adequate security one should use algorithms that have a key size of at least 128 bits. It would take 2 to the power of 128 steps to search (and check) all the possible keys. With Grover’s algorithm you can do this with 2 to the power of 64 steps9.
What an Entangled Web we Weave
Quantum computing, then, is more than just an academic curiosity of limited application. It has the potential to really screw things up. The saving grace so far, as far as the world of electronic security goes, is that it’s damnably difficult to build one of these quantum machines. The problem is that entanglement is very sensitive to the environment. If you try to entangle large numbers of quantum objects together you have to keep them isolated to maintain that entanglement.
Even a very, very small interaction with an external environment will wash out that entanglement in a matter of micro, or even nano, seconds.
We have all the technical know-how to build a quantum computer - but we don’t know how to keep it sufficiently isolated from the environment so that it can actually do its job.
Your latest Amazon purchase is probably still secure.
For now.
Doesn’t everything sound soooooo much sexier when you put the word ‘quantum’ in front of it?
A bit like the magic MacGuffin of covid which appeared to be able to do anything and everything the government decided it could do. Things like killing people who bought non-essential items in a supermarket, for example.
Sort of. Technically, one needs an infinite tape to be able to perform every calculation (algorithm) you can think of.
“Starting to” is not quite the right description here. The (then) unsolved Halting Problem had been number 2 on Hilbert’s list of the 23 greatest unsolved mysteries of mathematics that he produced at the turn of the century. But the 1930’s certainly saw major progress in “reasoning about reasoning” with the ideas of Gödel, Turing (and others, like Church).
This is more thinking along the lines of “reasoning about reasoning”. It isn’t about whether some particular algorithm runs quickly or not, but whether the problem is such that ANY algorithm we could devise to solve it would be ‘fast’ or ‘slow’. Of course, if you are able to find a particular algorithm that runs ‘quickly’ then you’ve answered the question - but it would be nice to know whether one exists, in principle, before we spent our lives fruitlessly searching for that ‘quick’ algorithm.
Well, it would if I had a product of these two primes that was 617 digits long instead of just 16
The first public key encryption algorithm to be invented (by Whit Diffie, Martin Hellman and Ralph Merkle) was also based on the asymmetry of a mathematical problem (the knapsack problem). Another protocol for public key exchange (the Diffie-Hellman protocol) is based on the asymmetry of the discrete logarithm problem.
He also showed how to solve the discrete logarithm problem quickly using this quantum algorithm.
Key lengths of 64 bits are not secure against modern computing capability.
Well, your first sentence both made me laugh and dared me to read, understand, and post a comment that subtly demonstrated my brilliant comprehension of quantum computing. Alas, I seem to be operating on about a fourth grade level when it comes to these concepts (I know what a prime number is! And I’ve used a computer! And “quantum” is a great Scrabble word! Although…did I know that in fourth grade?)
(You actually did a fine job of explaining these comments to someone with a fourth grade intellect, although I was a bit uncomfortable with your quantum supremacist bias. I felt there were a few micro aggressions directed at the Classical Systems community. Perhaps some sensitivity training is in order.)
Although I spent my career in Engineering, my original degree was in Pure Mathematics and Computer Science. So, every word of that fine piece brough back 40 years of study and application of things like algorithmic complexity, number theory, cryptography etc. And Fourier analysis! It plays a key role in converting time series data into the frequency domain for determining the Doppler shift in radar targets. If only people like Fourier and Doppler could see the results of their work!
You write in a lucid and engaging manner that explains complex concepts very clearly. More, please.