Machine Learning Gets a Quantum Speedup
In Valeria Saggio’s Vienna lab, she directed a laser of single photons into a special quantum circuit to show how the vagaries of quantum physics can improve machine learning.
Valeria Saggio
Introduction
For Valeria Saggio to boot up the computer in her former Vienna lab, she needed a special crystal, only as big as her fingernail. Saggio would place it gently into a small copper box, a tiny electric oven, which would heat the crystal to 77 degrees Fahrenheit. Then she would switch on a laser to bombard the crystal with a beam of photons.
This crystal, at this precise temperature, would split some of those photons into two photons. One of these would go straight to a light detector, its journey finished; the other would travel into a tiny silicon chip — a quantum computing processor. Miniature instruments on the chip could drive the photon down different paths, but ultimately there were only two outcomes: the right way, and the many wrong ways. Based on the result, her processor could choose another path and try again.
The sequence feels more Rube Goldberg than Windows, but the goal was to have a quantum computer teach itself a task: Find the right way out. For Saggio, a quantum physicist who moved to the Massachusetts Institute of Technology a few weeks ago, the project was akin to sticking a robot in a maze. The computer must learn the right path without any prior knowledge of where to turn along the way. It’s not too hard a chore — a normal classical computer could brute-force its way through dead ends and lucky guesses. But Saggio wondered, “Can quantum mechanics help?” She and her collaborators showed last year that it can.
It’s a cool experiment, but the work also answers a long-running question about whether quantum physics offers any real advantage to machine learning, the subfield of artificial intelligence that allows computers to find and apply patterns in data. Physicists and computer scientists have long been on the hunt for evidence of such “quantum speedups.” In a separate study, published in July, IBM researchers proved that quantum computers can learn to classify data in a task that is infeasible for any classical computer. The two studies tackle different branches of machine learning, but they reveal a similar story: Given the right circumstances, quantum machine learning can outmaneuver classical algorithms.
Once single photons entered Saggio’s nanophotonic processor, there was only one “correct” way out, but many wrong ones. By pairing classical reinforcement learning, which rewards right choices, with the time-saving power of quantum superpositions, she proved that machine learning can benefit from the use of quantum computing.
Valeria Saggio
“Until a few years ago, I would think that physicists and computer scientists were living in parallel worlds,” said Eleni Diamanti, a quantum communication expert at Sorbonne University in Paris who was not involved in either study. Now here they were, working together. “It’s a real change of paradigm.”
A Natural Marriage
Much of AI, and machine learning in particular, comes down to automating, and improving on, tedious tasks. “Machine learning is about getting computers to do useful things without explicit programming,” said Vedran Dunjko, a quantum information researcher at Leiden University and a co-author of Saggio’s study. A computer can learn from photos labeled “cat” or “dog,” then quickly sort new pictures into the correct species; other algorithms find subtle patterns that help doctors diagnose cancers on medical scans.
In the past decade, researchers began to theorize how quantum computers might influence machine learning. One unique advantage of quantum computers is a phenomenon called superposition. Where classical bits each toggle between 0 and 1, “qubits” can be a complex combination of both. Quantum algorithms can use superpositions to cut down on the number of computational steps needed to arrive at a correct answer.
Some machine learning tasks, it turns out, are uniquely suited for this kind of work. In 2013, two studies showed how quantum computers could speed up some “unsupervised” learning tasks, where the algorithm must discover patterns on its own. The approach was promising, but theoretical, and impossible to carry out with the tech of the time. “Lots of these machine learning protocols require technology that is getting there, but is not available yet,” said Diamanti.
Researchers think of quantum computing not as a tool that completely replaces classical computing, but as one that complements it. Each type of computer has its strengths, and researchers expect to get an edge if they can find the particular areas where quantum computers excel. The goal is now to find algorithms that use quantum physics to solve problems in a different way — a better way — than a classical computer. And getting quantum computers to outlearn traditional machines means finding AI problems that boil down to mathematical operations congruous with quantum physics.
“Rather than forcefully trying to take on your biggest problem,” said Kristan Temme, a physicist with IBM, researchers should find opportunities that “end up being more in the subtle details.” Finding those natural marriages between the math of AI and the physics of quantum computing is the key to real-life quantum machine learning.
Kernel Trickery
Temme speaks from experience. In 2019, his team at IBM found what they considered a prime example of a problem-solving method compatible with quantum physics — a sort of trick used in statistics, involving something called kernels.
A kernel is a measure of how related two data points are with respect to a particular feature. Think of a simple data set containing three items: BLUE, RED and ORANGE. If you examine them as colors, RED and ORANGE are neighbors. But if you look at the number of characters, BLUE sits between RED and ORANGE. Kernels are like lenses that allow an algorithm to classify data in different ways to find patterns that help distinguish future inputs. Implementing them is a trick to recast information in a new light, Temme said, allowing you to zero in on strong relationships otherwise hidden in data.
Samuel Velasco/Quanta Magazine
Kernels have no inherent connection to quantum physics. But quantum computers manipulate data in a similar way, so Temme suspected that his team could design a quantum algorithm for kernels. And for supervised learning problems in particular — where the system learns from a set of labeled data — the combo could excel at learning and applying patterns.
Temme, along with his IBM colleague Srinivasan Arunachalam and Yunchao Liu, an intern from the University of California, Berkeley, set out to prove that a quantum kernel algorithm could eclipse a classical one. In the summer of 2020 they went back and forth over Zoom, drawing diagrams and speculating about how to use the kernel trick to prove that quantum computers can boost supervised learning. “Those were really heated debates,” Temme said. “We’re all looking at each other in those little blue boxes.” Finally, they landed on a way to make the kernels shine.
Cryptographers sometimes use unidirectional math operations — ones that will easily output a number but cannot be reverse-engineered to reveal the process. For example, a “discrete logarithm” depends on a particular operation that takes two numbers — we’ll call them a and x — and returns results that bounce around unpredictably as a and x change. (The algorithm raises a to the xth power, divides it by some other number n, and outputs the remainder.) Classical computers can’t crack the string of outputs to find x.
Temme and his team showed how, by using quantum kernels, one can learn to find the pattern hiding in the seemingly random output produced by the discrete log problem. The technique uses kernels and superpositions to both reinterpret the data points and quickly estimate how they compare to one another. Initially the data appears random, but the quantum approach finds the right “lens” to reveal its pattern. Data points that share some key trait no longer appear randomly distributed, but come together as neighbors. By making these connections, the quantum kernels help the system learn how to classify the data.
“You could see all the things falling into their place,” Temme recalled. The method allows the quantum computer to exceed 99% accuracy.
“I really liked the paper,” said Maria Schuld, a quantum machine learning expert not involved in the IBM study. (In 2019, Schuld’s team showed that kernels would be valuable for quantum AI.) “It resolves something fundamental methodologically that people were struggling with for a long time in quantum machine learning.”
To Schuld, the novelty of Temme’s work is that it proves the quantum computer does something unsolvable on a classical computer. “I think they did it convincingly and for the first time,” she said.
Training a Quantum Learner
While Temme’s kernel-based speedup is still too new to have been demonstrated in a practical experiment, theories that fuse quantum mechanics and another type of learning have had more time to grow into something real.
Back in 2016, Vedran Dunjko helped outline the theory of why quantum mechanics could enhance reinforcement learning. In reinforcement learning, the training system rewards the algorithm when it makes the correct choice. The reward acts as a statistical nudge, making the learner more likely to choose correctly the next time. This framework has supercharged computers in games like Go and Chess.
In 2018, Dunjko and fellow quantum information expert Sabine Wölk argued that a well-known quantum search algorithm could use superpositions to evaluate and choose a sequence of correct choices more quickly than a classical computer. Wölk was invited to Vienna to give a talk on the idea, which Valeria Saggio attended. She realized her photon-based quantum computer setup could help demonstrate the idea. “We saw that it was possible, actually, to implement something with our quantum processor,” she said.
Saggio worked on a complicated setup of lasers, crystals and quantum processors to demonstrate how a quantum search algorithm helps a computer navigate an optical “maze” more quickly — in fewer steps — than a classical one.
Courtesy of Valeria Saggio
Reinforcement learning boils down to a question: How will the computer explore its possible choices? A classical computer can go through the options sequentially. But superpositions allow a quantum computer to amplify the promising paths. The group began to craft a demonstration.
Saggio’s quantum nanophotonic chip communicates information via photons and the path they take through the chip. Each path encodes a different message, and each path may send the light to a different exit. In effect, Saggio chose one of the exits to be the “correct” one, then tried to train the chip to send light out that way. If the learner made the wrong choices, a 0 would pop up on Saggio’s Python terminal. Successes got a 1.
To make the quantum chip find the right path quickly, Saggio and her collaborators used a quantum search algorithm. On the first run, the computer would have an equal probability of choosing any path. But once the learner stumbled onto the right one, the reward kicked in. The physics at each bend in the light’s path adjusted to entice the learner into making more right choices — solutions became amplified in the quantum circuit.
The speedup was clear. The quantum chip learns about 63% faster than a classical computer could. “In the end it was a lot of 1s,” Saggio said. “We were happy.”
Crucially, the chip is not just moving through faster cycles of trial-and-error, said Lucas Lamata, a quantum machine learning expert at the University of Seville. “The novelty in this paper is that they show a speedup in learning. [It’s] an important breakthrough.” Quantum mechanics makes the system learn in fewer steps. In that sense, it shows in an experiment what Temme’s theoretical speedup promised: Quantum physics can outwit — not just outrun — classical computing.
“It allows you to show that you don’t have to wait for the full-scale quantum computer,” Diamanti said. “You can get the advantage out of quantum resources. You can already show it for some tasks today.”
Quantum Leaps Ahead
With quantum physics conclusively shown to improve machine learning, many in the field are eager to see more experimental demonstrations in the coming years.
“Now that we know that it’s possible to have a quantum advantage,” said Saggio, she expects to see “more realistic learning scenarios.” Researchers speculate that quantum reinforcement learning might help with anything from chess and natural language algorithms to decoding brain signals in neural interfaces and personalizing complex treatment plans for cancer.
But technological limits make experiments difficult. “The problems that we can analyze practically are too small,” Schuld said. That’s why it’s important to find situations that fit neatly into a quantum framework, as the new work did.
The relationship between quantum mechanics and artificial intelligence is also paying dividends in both directions. Scientists are now using classical machine learning to improve our understanding of quantum physics. AI algorithms can optimize the fine-tuning of quantum circuits, for example, which can prevent errors and save time during the most headache-inducing parts of quantum experiments. Machine learning has also helped physicists detect quantum entanglement and recognize new phases of matter.
“There’s this beautiful synergy,” said Dunjko. “We’ve still nowhere near explored all the possible connections. There are many, many new things to be discovered.”
