Researchers at UC Santa Barbara have built a quantum processor that can factor a composite number – in this case the number 15 – into its constituent prime factors, 3 and 5.
While the math may not be much of an achievement, performing it successfully is an important step towards factoring much larger numbers, with implications for cryptography and cybersecurity.
“What is important is that the concepts used in factoring this small number remain the same when factoring much larger numbers,” says Andrew Cleland, a professor of physics at UCSB.
“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.”
Factoring very large numbers is central to cybersecurity protocols, such as RSA encryption.
“Anytime you send a secure transmission – like your credit card information – you are relying on security that is based on the fact that it’s really hard to find the prime factors of large numbers,” says former doctoral student Erik Lucero, now at IBM.
Factoring something like RSA Laboratory’s largest published number – which contains over 600 decimal digits – would take longer than the age of the universe, he says. A quantum computer, though, could reduce this to an hour or so.
“A quantum computer can solve this problem faster than a classical computer by about 15 orders of magnitude,” says Lucero.
“This has widespread effect. A quantum computer will be a game changer in a lot of ways, and certainly with respect to computer security.”
The team designed and fabricated a quantum processor to map the problem of factoring the number 15 onto a purpose-built superconducting quantum circuit. They chose the number 15 because it’s the smallest composite number that satisfies the conditions appropriate to test Peter Shor’s prime factoring algorithm – it’s a product of two prime numbers, and not even.
The quantum processor was implemented using a quantum circuit composed of four superconducting phase qubits and five microwave resonators.
“After repeating the experiment 150,000 times, we showed that our quantum processor got the right answer just under half the time,” says Lucero. “The best we can expect from Shor’s algorithm is to get the right answer exactly 50 percent of the time, so our results were essentially what we’d expect theoretically.”
The next step, according to Lucero, is to increase the quantum coherence times and go from nine quantum elements to hundreds, then thousands – and even millions.
“Now that we know 15=3×5, we can start thinking about how to factor larger – dare I say – more practical numbers,” he says.
