This talk by Christopher Monroe gives a good overview of the state of the art in the Quantum Computing field. Below there are two paragraphs describing prospects for breaking encryption and the overview of current research.
We can do parallel computing. With three qubits there are eight states and they have eight weightings here and these eight parameters follow a wave equation, that’s where all the math is, and we can get eight answers. Now, eight is pretty trivial. We can do that calculation on any classical computer of course, but with three hundred qubits, just three hundred atoms, two to the power three hundreds is more than the number of particles in the universe, so that’s the magic of exponential. Nobody’s wowed here. This is more for a non physicist audience, but you know, getting access to those two to the 300 pieces of data is the subtle thing, and of course the bad news is, even with just three qubits, when you measure the output of this beautiful parallel processor, you get only one answer, and it’s random.
It’s as though you had no idea what the input was. A one-to-one function is probably not going to work very well in the quantum computer and most of what we compute today is one-to-one functions. So, keep that in mind.
The final piece of good news was codified by many folks including David Deutsch. He thought long and hard about entanglement before it was fashionable, and these founders in the 80s and 90s showed that there can be quantum interference. This quantum interference is very hard to draw, I’ve tried to depict it with these orange dots on blue lines. These blue things are supposed to be waves. You can get massive interference where all the answers cancel except one or maybe a few but not exponentially many and then when you measure it, and you may have to do it a few times, not exponentially many times, and when you have three hundred qubits you know there’s no way to deal with all of those inputs. The magic is in these gates, in these operations. That’s the trick and it’s very vague. I hinted earlier there are not so many applications that work here.
Well, the killer app has been known for almost 25 or 30 years now and it does hit on the topic of security and it’s probably underlies why quantum computing is so important to many governments throughout the world. That application is factoring numbers.
Factoring classically, nobody’s proven this but we believe that factoring is exponentially hard in the size of the input, and factoring numbers, while it might seem esoteric, is of course the reason why data is secure according to many very simple, remarkably simple encryption algorithms including the RSA algorithm, Rivest-Shamir-Adleman. It’s beautiful mathematics, it is about two lines, but when you want to send a secret, you’re making public a huge number that nobody can factor because it has a thousand digits and we’re relying on the hardness of factoring. Peter Shor, this watershed event in the mid-90s, he showed that a quantum computer, if built, with perfect operations and perfect quantum behavior would be able to factor large numbers in sub exponential time, actually polynomially with the input. Now, truth be told, the polynomial scaling is not great, it goes like the cube of the number of bits. So, if you have a thousand-bit number, you need about a billion, actually there’s a pre-factor, it’s a thousand times the number of bits cubed, you need about a trillion operations. That implies that you need a part per trillion errors on each individual operation. And that’s why none of us – maybe there are some folks up in Fort Meyers, they’re still thinking about this – but none of us are really worried about Shor’s algorithm happening tomorrow. Maybe in 30 years. Who knows? Who can predict anything in 30 years?
But this is a long-term problem and the way it works, and again, this is a really high level, the way it works is when you encode the number you want to factor, like 39, into a quantum computer, you need at least six bits to do this because two to the sixth is 64, and you store a superposition, and you do Shore’s prescription, and you end up with a quantum wave function that’s just a superposition of these two numbers, and then you measure it and you get one of the factors.
It’s been a very high-level view of how Shor’s algorithm works but it points to one of the commonalities of all quantum computations and that is they produce a simple answer from a maze of combinations. Classically factoring a big number, you basically have to test all the prime numbers up to the cube root of the number at hand.
Getting into the laboratory, there are many quantum systems that we could think of to build these types of hardware’s, quantum computers and so forth.
Anything that any lab that needs to use quantum entanglement or many-body physics to study their system is a candidate to think about building devices. I would say however that the two at the top here shaded in red are only the ones so far that have been built into systems, meaning that these are systems sort of like a Turing machine where we can think about abstracting away the hardware and unleash the power of these devices, even though they’re very small still.
Other platforms are still in the research stage, some more promising than others. Topological qubits in particular is very researchy, but it’s beautiful condensed matter physics. The idea is that the qubit can be stored in a different space in the topology of a circuit.
There’s wonderful research going on in all of these fields, but I would say these two are currently being built into systems composed of dozens of qubits which embarrassingly is still pretty small, but dozens is better than one or two. And if you’re building dozens, you’re getting an idea how to scale. You’re learning that the whole system is more than just a sum of its parts.
Alan Tatourian 