The processor in question. Image: UCSB
A fully-functional quantum computer should be able to take on those 601 digits in minutes. “A quantum computer can solve this problem faster than a classical computer by about 15 orders of magnitude,” said Erik Lucero, the lead author of a new paper in Nature Physics describing the processor. “This has widespread effect. A quantum computer will be a game changer in a lot of ways, and certainly with respect to computer security.” Basically, a quantum computer up against classical encryption is like a truck-mounted battering ram against a rotting wood door.
Lucero’s computation was a bit smaller than 601 digits; instead, his computer found the constituent prime factors of 15, of which there are a whopping two, 2 and 5. That’s fine actually, given that the processor he used only had four qubits (like transistors) and five microwave resonators to work with, and that just controlling those elements is challenge enough. Understand that while nine is a small number, quantum computing involves computations happening in parallel — rather than computations happening one at a time, they’re happening all at once (sort of). Part of Lucero et al’s accomplishment here is that their computing architecture could potentially scale up to the full-on quantum computers of the future, e.g. when a processor has millions of quantum elements working on a problem instead of nine.
“Now that we know 15=3×5, we can start thinking about how to factor larger — dare I say —more practical numbers,” Lucero said.
The research team’s processor performed something called Shor’s algorithm. Which is a clever way of incorporating some structure/order into prime factorizations by using what’s known as the period (how often a sequence repeats) of a certain mathematical function. The algorithm would work for classical computing somewhat, but still not anywhere near enough to solve prime factorization problems in a reasonable amount of time. But Shor’s algorithm finds good use in quantum computing, getting past the mess that results from trying to parse large-scale factorizations with parallel processing. In any case, the combination of the two is all kinds of destructive for this most difficult math problem. Well, kind of — it’s actually only right about half the time, which, when you’re guessing encryption keys, perhaps isn’t too shabby.
In any case, death lurks for classical encryption. So is that the end of digital secrets? Hardly. Quantum encryption is gearing up for life beyond theory just as quantum computing is. “[Quantum encryption] is not only harder to break, but it allows you to know if someone has been eavesdropping, or listening in on your transmission,” Lucero noted. “Imagine someone wiretapping your phone, but now, every time that person tries to listen in on your conversation, the audio gets jumbled. With quantum cryptography, if someone tries to extract information, it changes the system, and both the transmitter and the receiver are aware of it.”
So I guess we’ll just be back where we started — with a more or less secure method of communicating/guarding secrets — only it’ll probably be a lot more expensive.