Edit | turnip
In order for Valeria Saggio (a quantum physicist at the Massachusetts Institute of Technology) to start a computer in her former Vienna lab, she needed a special crystal; the crystal was probably the size of her fingernail. Saggio would gently place it into a small copper box, a miniature electric oven, and heat the crystals to 77 degrees Fahrenheit. Then she would turn on the laser and bombard the crystal with a beam of photons.
This crystal, at this precise temperature, splits some of these photons into two photons. One of them will go straight into a light detector and its journey is over; the other will go into a tiny silicon chip— a quantum computing processor. Tiny instruments on a chip can drive photons along different paths, but in the end there are only two outcomes: the right way and many the wrong way. Based on the results, her processor can choose another path and try again.
The sequence feels more like Rube Goldberg than Windows, but the goal is for quantum computers to teach themselves a task: find the right way out. For Saggio, the project is akin to trapping a robot in a maze. The computer must learn the correct path without having to know in advance where to turn. It's not that hard —an ordinary classic computer can force a break by trying dead ends and lucky guesses. But Saggio wondered, "Can quantum mechanics help?" Last year, her team proved it.
It's a cool experiment, but this work also answers the long-standing question of whether quantum physics offers a real advantage for machine learning, a subfield of artificial intelligence that allows computers to find and apply patterns in data. Physicists and computer scientists have long been looking for evidence of this "quantum acceleration."
In another study published in July 2021, IBM researchers demonstrated that quantum computers can learn to classify data, a task that no classical computer would ever do. The two studies touched on different branches of machine learning, but they reveal a similar story: where appropriate, quantum machine learning can surpass classical algorithms.
"Until a few years ago, I thought physicists and computer scientists lived in parallel worlds." Eleni Diamanti, an expert in quantum communications at the Sorbonne University in Paris, says, "This is a real paradigm shift."
A Natural Marriage
Much of AI, especially machine learning, comes down to automating and improving tedious tasks. "Machine learning is about getting computers to do useful things without explicit programming." Vedran Dunjko, a researcher in quantum information at Leiden University and co-author of the Saggio study, said. Computers can learn from photos labeled "cats" or "dogs" and then quickly classify new photos into the correct species; other algorithms will find subtle patterns that help doctors diagnose cancer in medical scans.
Over the past decade, researchers have begun to theorize about how quantum computers affect machine learning. A unique advantage of quantum computers is a phenomenon called superposition. Classical bits switch between 0 and 1, and "qubits" can be a complex combination of the two. Quantum algorithms can use superposition to reduce the number of computational steps required to come up with a correct answer.
It turns out that some machine learning tasks are particularly suitable for this kind of work. In 2013, two studies showed how quantum computers can accelerate some of the "unsupervised" learning tasks, in which algorithms must discover patterns on their own. This approach is promising, but only theoretical, and impossible to implement with the technology of the time. "Many of these machine learning protocols require technologies that are already implemented but not yet available." Diamanti said.
The researchers argue that quantum computing is not a complete replacement for classical computing, but a tool that complements it. Each type of computer has its advantages, and if researchers can find specific areas where quantum computers excel, they hope to gain an advantage. The goal now is to find algorithms that use quantum physics to solve problems in a different way (and better) than classical computers. Getting quantum computers to surpass traditional machines means finding AI problems that boil down to mathematical operations consistent with quantum physics.
Kristan Temme, a physicist at IBM, says, "Instead of forcing yourself to try to solve your biggest problem," researchers should find opportunities to "eventually pay more attention to the smallest details." Finding a natural combination between AI mathematics and quantum computational physics is key to real-life quantum machine learning.
Kernel Trickery
Temme speaks with experience. In 2019, his team at IBM found a classic example of a problem solving they thought was compatible with quantum physics — a technique for statistics that involves something called a kernel.
A kernel is a measure of how closely two data points are relative to a particular feature. Imagine a simple dataset of three items: BLUE, RED, and ORANGE. If you think of them as colors, RED and ORANGE are neighbors. However, if you look at the number of characters, BLUE is located between RED and ORANGE. The kernel is like a lens, allowing algorithms to classify data in different ways to find patterns that help distinguish future inputs. Implementing them, Temme says, is a trick to recast information from a new perspective, enabling you to zero out strong relationships that would otherwise be hidden in your data.
The kernel is not intrinsically related to quantum physics. But quantum computers process data in a similar way, so Temme suspects his team could design a quantum algorithm for the kernel. Especially for supervised learning problems—the system learns from a set of labeled data—the combination can be good at learning and applying patterns.
Temme, along with his IBM colleague Srinivasan Arunachalam, and Yunchao Liu, an intern at the University of California, Berkeley, set out to prove that quantum accounting could surpass classical algorithms.
In the summer of 2020, they walked back and forth on Zoom, charting and speculating on how to use kernel tricks to prove that quantum computers could facilitate supervised learning. "Those debates were really heated." Temme said, "We're all looking at each other in those little blue boxes." Finally, they found a way to make the kernel glow.
Cryptographers sometimes use one-way mathematical operations — operations that easily output a number but can't reveal the process by reverse engineering. For example, a "discrete logarithm" depends on a particular operation that takes two numbers—we call them a and x—and returns the result of an unpredictable bounce as a and x change. (The algorithm raises a to the power of x, divides it by some other number, n, and outputs the remainder.) Classic computers cannot crack the output string to find x.
The Temme team showed how to learn to find patterns hidden in the seemingly random output produced by discrete logarithmic problems by using quantum cores. The technique uses kernels and overlays to reinterpret data points and quickly estimate how they compare between them. Initially the data appeared random, but quantum methods found the right "lens" to reveal its patterns. Data points that share some key features are no longer randomly distributed, but are clustered together as neighbors. By making these connections, quantum cores can help systems learn how to classify data.
"You can see that everything has fallen into their place." Temme recalls that the method made quantum computers more than 99 percent accurate.
"I really like this paper." Quantum machine learning expert Maria Schuld (In 2019, Schuld's team showed that the kernel is valuable for quantum AI.) "It fundamentally solves the problem that people have been struggling with for a long time in quantum machine learning," he said.
For Schuld, the novelty of Temme's work is that it proves that quantum computers do something unsolvable on classical computers. "I think for the first time they did it convincingly." She said.
Training a Quantum Learner
While Temme's core-based acceleration is still too new to be proven in real-world experiments, theories that fuse quantum mechanics and another type of learning have more time to grow into something real.
Back in 2016, Vedran Dunjko helped outline the theory of why quantum mechanics can enhance reinforcement learning. In reinforcement learning, the training system rewards the algorithm when it makes the right choice. Rewards act as a statistical boost, making learners more likely to make the right choice next time. The framework provides boosting for computers in games such as Go and chess.
In 2018, Dunjko and quantum information expert Sabine Wölk argued that a well-known quantum search algorithm could use overlays to evaluate and select a range of correct choices faster than classical computers. Wölk was invited to Vienna to speak on the idea, and Valeria Saggio attended. She realized that her photon-based quantum computer setup could help prove the idea. "We see, in fact, that it is possible to implement something with our quantum processors." She said.
Reinforcement learning boils down to one question: How will computers explore their possible options? Classic computers can process options sequentially. But superposition allows quantum computers to zoom in on promising paths.
Saggio's quantum nanophoton chip transmits information through photons and their paths through the chip. Each path encodes different information, and each path can send light to a different exit. In fact, Saggio chose an exit as the "correct" exit and then tried to train the chip to emit light in this way. If the learner makes the wrong choice, a 0 pops up on Saggio's Python terminal; a 1 for success.
To get the quantum chip to quickly find the right path, Saggio and her collaborators used a quantum search algorithm. On the first run, the computer will have the same probability of choosing any path. However, once a learner stumbles upon the right choice, the reward comes into play. The physics at each bend in the optical path are adjusted to entice learners to make more correct choices — solutions that are amplified in quantum circuits.
The acceleration is obvious, and the quantum chip learns 63% faster than classical computers. "Finally there are a lot of 1s." Saggio said, "We are very happy."
Lucas Lamata, a quantum machine learning expert at the University of Seville, said it's crucial that the chip doesn't just go through faster trial-and-error cycles. "The novelty of this paper is that they show an acceleration in learning. [This is] an important breakthrough." Quantum mechanics enables systems to learn in fewer steps. In this sense, it experimentally demonstrates what Temme's theoretical acceleration promises: quantum physics can outwit—not just outperform—classical computing.
"It allows you to prove that you don't have to wait for a full-size quantum computer." Diamanti says, "You can gain an advantage from quantum resources. You can already show it on some of the missions today."
Quantum Leaps Ahead
As quantum physics finally proves that machine learning can be improved, many in the field are eager to see more experimental demonstrations in the coming years.
"Now we know that quantum advantage is possible." Saggio said she would like to see "a more realistic learning scenario." The researchers speculate that quantum reinforcement learning could be applied to chess and natural language algorithms, as well as decoding brain signals in neural interfaces and personalizing complex cancer treatment plans.
But technical limitations make experiments difficult. "The problems we can actually analyze are too small." Schuld says that's why it's important to find a situation that fits perfectly into a quantum framework, as the new work did.
The relationship between quantum mechanics and artificial intelligence also brings benefits in both directions. Scientists are now using classical machine learning to improve our understanding of quantum physics. For example, AI algorithms can optimize the fine tuning of quantum circuits, and the most vexing parts of quantum experiments can prevent errors and save time. Machine learning also helps physicists detect quantum entanglement and identify new phases of matter.
"There's this wonderful synergy." Dunjko said, "We are far from exploring all possible connections. There's a lot of new stuff to discover."
Related: https://www.quantamagazine.org/ai-gets-a-quantum-computing-speedup-20220204/