Researchers in California have designed and built a quantum processor capable of factoring 15 into its primes — with major implications for computer security.
Quantum computing is famous for its potential to obliterate current cryptographic techniques. Much of cryptography today relies on the lack of processing power in classical computers to factor a very large number into its primes. Each factorisation would have to be performed sequentially, and when you are dealing with a sufficiently large number, the calculation becomes all but impossible.
Consider RSA Laboratory's largest published number. This number contains over 600 decimal digits. Factoring it with a classical computer would take longer than the age of the universe. However, quantum computing can in theory get around this obstacle by running all the necessary calculations in parallel. An encryption key would be laid bare in a stroke.
"A quantum computer can solve this problem faster than a classical computer by about 15 orders of magnitude," said Erik Lucero, a former doctoral student at the University of California Santa Barbara, now working at IBM's research labs. "This has widespread effect. A quantum computer will be a game-changer in a lot of ways, and certainly with respect to computer security."
However, making this all work in the real world is not trivial. Quantum computing by its nature is riddled with errors: it is at best probabilistic, and extremely vulnerable to perturbations in the environment.
So much so that it is genuinely impressive that Lucero and other researchers at the University of California Santa Barbara have now demonstrated a processor that can factor a number into its primes – 48 percent of the time.
"Fifteen is a small number, but what's important is we've shown that we can run a version of Peter Shor's prime-factoring algorithm on a solid-state quantum processor. This is really exciting and has never been done before," Lucero notes in the university's announcement.
Andrew Cleland, a professor of physics at UCSB and a collaborator on the experiment, said: "What is important is that the concepts used in factoring this small number remain the same when factoring much larger numbers."
He added: "We just need to scale up the size of this processor to something much larger. This won't be easy, but the path forward is clear."