Multiverse 2.357

Did Google do something amazing, again? Should we even care? Is this the beginning of the end? Do we need to worry about quantum computers breaking our encryption? For the answers to these and a down-to-earth explanation of what it all means, please read on.

First of all we don’t know if Google did indeed achieve quantum supremacy. We won’t know for sure for some time to come. TL;DR – if they did, it really doesn’t change anything that will affect online commerce, cryptocurrency, encrypted communications or anything people are worried about. This is all about proving whether or not there are things can be computed with these machines once we get better at building them that cannot be computed by quantum simulators – a.k.a. conventional computers. That’s the short answer, a slightly longer one follows.

“Quantum supremacy is the potential ability of quantum computing devices to solve problems that classical computers practically cannot.” – Wikipedia

This will all sound familiar to computer scientists, who are used to hearing about the classic P = NP problem. That’s just a fancy way to say that the boundaries of what is and is not computable are not entirely clear. P and NP are two sets of problems and it’s not clear whether they are the same set or not. Similarly it’s not clear if there exist problems that can be solved in a fixed amount of time by a quantum computer that cannot by a traditional computer. Everyone seems to think that there are these problems but it’s not easy to prove it by actually finding one.

One example usually held up as a likely candidate is based on Shor’s algorithm. Peter Shor was a mathematician who was considering quantum computers in the 1990s and came up with an algorithm to factor large numbers more efficiently than algorithms we run on our current computers. Why is this such an important undertaking?

We currently factor large numbers in basically the same way that has been passed down from the ancient Greeks. A rough description of the algorithm is to divide into the large number each prime from 2 up to the square root of the large number. This is a variation of a method of finding primes called the Sieve of Eratosthenes. Start with 2, eliminate all multiples, then same with 3. Four has been eliminated already so continue with 5, and so on.

Shor came up with an algorithm that will factor large numbers more efficiently, in fact in polynomial time (a finite amount of time regardless of data size) but requires a quantum computer. Factoring large numbers is important, because modern cryptography often depends on the difficulty of doing so. RSA encryption specifically, depends on a large number with two large prime factors being extremely difficult to factor. Newer techniques for encrypting data do not depend on prime factorization. i.e. if I have a 1000 digit number whose only factors are two 500-digit primes, good luck factoring it.

So to cut to the chase, Shor’s algorithm is not the kind of thing we can run on quantum computers anytime soon. It is very sensitive to noise, which is a huge challenge in quantum computation. If you’re using electrons to compute something, the impact of a single cosmic ray can disrupt the computation.

Also it’s important to note that this algorithm requires a fairly powerful (by today’s standards) machine, with lots of qubits, and that’s an extremely difficult thing to produce. Add to that the need for huge numbers of redundant qubits for error correction and the problem becomes overwhelming. Error rates in current quantum computers is on the order of 0.1 (ten percent) so you need to either repeat the operations or do them multiple times in parallel.

To make matters worse still, these are probabilistic operations, so by definition you need to perform them multiple times to have confidence in the result. I think you see the dilemma – this is not the kind of algorithm we’ll be able to use any time soon.

It is important to consider problems like this however, since the goal is to identify a previously intractable problem that can be solved efficiently by quantum computers. Shor’s algorithm does this, but in this case it has not been proven that factoring large numbers can’t also be accomplished by classical computers. Perhaps nobody has yet figured out a technique for doing so but one does exist. Sooner or later either such a technique will be found or it should be proven to be impossible if this problem is the one to demonstrate quantum supremacy.

Quantum computing is an exciting field that holds much promise. I don’t understand the physics in any detail, but it is possible to program these devices without a deep understanding of how they work. I plan to explore several closely related topics in quantum computing in future posts here so guess what – stay tuned!