Quantum Processor Calculates That 15 = 3×5 (With Almost 50% Accuracy!)

For the first time, a functional solid-state quantum computer has completed a fairly simple math problem, factoring a prime number into its constituent parts. The solution itself isn’t that great an accomplishment — it was the number 15 — but it’s a major leap for quantum computers, because it’s a step toward factoring much larger numbers. Factoring very large numbers very quickly is crucial for cybersecurity.

Researchers led by PhD graduate Erik Lucero of the University of California-Santa Barbara built a quantum processor to map the number 15. The team built a quantum circuit made of four superconducting qubits, which are the logic gates of a quantum system, on top of a substrate made of sapphire. It also contained five microwave resonators. The fabrication itself was a breakthrough, because organizing nine separate quantum pieces required very precise, automated construction methods. The qubits were entangled and verified using quantum experiments. Then the team used this circuit to factor 15 using Peter Shor’s factoring algorithm. That code says for any given integer N, the computer must find its prime factors. But it does this quantum-fast, finding the solution exponentially faster than the quickest known classical factoring algorithm.

Why is this important? Quantum computers could greatly improve cybersecurity by enabling much more complex encryption than is possible with classical systems. The most common form of encoding is called RSA encryption, and it’s based on the fact that it is very hard to factor large prime numbers. The product of two large prime numbers serves as the key for encryption, and the prime factors themselves are secret. To solve the code, a classical computer system has to crunch a series of numbers. This can take a long time, especially as the prime numbers get very large.

With the fastest classical factoring algorithm, factoring the 600-digit, largest-ever RSA encryption number would take longer than the age of the universe. This system could theoretically do it in an hour.

Lucero and colleagues ran the experiment 150,000 times, and the processor got the right answer 48 percent of the time. Shor’s algorithm holds that a quantum system will get the right answer exactly half the time, so this is actually pretty good. The next step is to improve quantum coherence and build more complex circuits, so the computer can solve much larger factoring problems.

The paper appears in this week’s issue of Nature Physics.

UCSB