New Quantum Algorithm Factors Numbers With One Qubit
A new quantum algorithm flies in the face of intuition.
Celsius Pictor for Quanta Magazine
Introduction
Quantum computers still can’t do much. Almost every time researchers have found something the high-tech machines should one day excel at, a classical algorithm comes along that can do it just as well on a regular computer. One notable exception? Taking apart numbers. In 1994, the mathematician Peter Shor devised an algorithm that would let quantum computers factor big numbers exponentially faster than classical machines. That speedup matters because a fast-factoring algorithm could render most data-encryption methods useless. For more than 30 years, researchers have been trying to boost and guard against the power of future quantum computers.
But Shor’s factoring algorithm also has limitations: The bigger the number you want to factor, the bigger and better the quantum computer you need. Cracking an encryption scheme would require a quantum computer running Shor’s algorithm on hundreds of thousands of efficient quantum bits, or qubits. Today’s machines are nowhere close.
But a paper posted to the scientific preprint site arxiv.org describes how to factor any number with considerably fewer qubits: just one. In the new work, researchers show how to factor an integer of any size with a single qubit and three components known as oscillators — readily available devices typically associated with other quantum technology, like optics systems.
To be clear, it’s not a practical advance: The process requires exponentially more energy than a million-qubit quantum computer. But it does illuminate new ways of solving these kinds of problems. “This departs from the typical way we think about computing — and not just quantum computing, but classical computing as well,” said Ulysse Chabaud, a computer scientist at the École Normale Supérieure in Paris who did not work on the new approach. “This seems crazy, if not impossible.”
Good Oscillations
Ultimately, the new approach works because of how it encodes information. Classical computers use bits, which can take one of two values. Qubits, the quantum equivalent, can take on multiple values, because of the vagaries of quantum mechanics. But even qubits, once measured, can take on only one of two values, a 0 or a 1.
But that’s not the only way to encode data in quantum devices, say Robert König and Lukas Brenner of the Technical University of Munich. Their work focuses on ways to encode information with continuous variables, meaning they can take on any values in a given range, instead of just certain ones.
From left: Lukas Brenner, Libor Caha and Robert König, along with Xavier Coiteux-Roy (not pictured), devised a novel but impractical way to factor any integer with a single qubit.
C. Hohmann/Munich Center for Quantum Science and Technology
In the past, researchers have tried to improve on Shor’s algorithm for factoring by simulating a qubit using a continuous system, with its expanded set of possible values. But even if your system computes with continuous qubits, it will still need a lot of them to factor numbers, and it won’t necessarily go any faster. “We were wondering whether there’s a better way of using continuous variable systems,” König said.
They decided to go back to basics. The secret to Shor’s algorithm is that it uses the number it’s factoring to generate what researchers call a periodic function, which has repeating values at regular intervals. Then it uses a mathematical tool called a quantum Fourier transform to identify the value of that period — how long it takes for the function to repeat. From there, some straightforward algebra can reveal the original number’s factors.
When König and Brenner tried to think of another continuous approach to factoring, they quickly thought of quantum oscillators, which produce a repeating pattern that can take on any continuous value after being measured (unlike qubits). Those patterns act like a built-in quantum Fourier transform, said König.
“Lukas and I started talking about this hybrid qubit-oscillator system,” König said. But they had only vague ideas, so the pair brought in their colleagues Libor Caha and Xavier Coiteux-Roy to design a quantum algorithm based on this system.
After a few months, König’s team proved that in a system using quantum oscillators instead of qubits, the dynamics of those physical components could indeed perform the mathematical work of factoring — without having to simulate the discrete values of qubits. The single qubit in their system reads and organizes information in the oscillators but doesn’t perform the actual computation, as qubits do in other quantum computers. Like Shor’s algorithm, the new approach factors integers in a reasonable amount of time.
The work also points to new possibilities for implementing continuous methods in quantum computing. “This paper is saying, by using operations that feel very reasonable, they managed to achieve something that feels completely unreasonable,” Chabaud said. “This is a pretty cool thing, and I was very enthusiastic when the results came out.”
Shor Enough
But this method also has a catch: The larger the number to be factored, the more energy the oscillators require to do the math. As a result, factoring a large number uses only one qubit, but it requires a near-unthinkable amount of energy. “If I give you a big number to factor, you have to harness the energy of multiple stars just to be able to run the algorithm, let alone control everything that happens,” Chabaud said.
For Aram Harrow, a physicist at the Massachusetts Institute of Technology, that renders the new result useless. “I can’t see how it would ever make sense to do your entire calculation this way.”
But the Munich group is already working on modifying the energy cost by fine-tuning the number of oscillators and how they function. “Maybe with more oscillators you can get away with less energy,” König said.
And factoring is just one example of how to apply this new computing approach; the team is looking for others. “We can try to translate any quantum computation to the setup,” König said. “It doesn’t have to be Shor’s algorithm.” His team has shown that qubits don’t have to be the only engine of computation, with oscillators playing the role of basic information carriers. And it’s possible that other components already present in quantum devices could also be leveraged to perform computations.
“For me, this is the true novelty of this paper,” Chabaud said. “You can actually run interesting algorithms using continuous variable systems.”
