After a Quantum Clobbering, One Approach Survives Unscathed
Kristina Armitage/Quanta Magazine
Introduction
Quantum computers get a lot of hype, but the truth is we’re still not sure what they’ll be good for. These devices leverage the peculiar physics of the subatomic world and have the potential to perform calculations that regular, classical computers simply can’t. But it’s proved difficult to find examples of any algorithms with a clear “quantum advantage” that enables performance beyond the reach of classical machines.
For most of the 2010s, many computer scientists felt one particular group of applications had a great shot at finding this advantage. Certain data-analysis calculations would be exponentially faster when they were crunched by a quantum computer.
Then along came Ewin Tang. As an 18-year-old recent college grad in 2018, she found a new way for classical computers to solve these problems, smacking down the advantage the quantum algorithms had promised. For many who work on quantum computers, Tang’s work was a reckoning. “One by one, these super exciting use cases just got killed off,” said Chris Cade, a theoretical computer scientist at the Dutch quantum computing research center QuSoft.
But one algorithm survived unscathed: a quantum twist on a niche mathematical approach for studying the “shape” of data, called topological data analysis (TDA). After a flurry of papers in September, researchers now believe that these TDA calculations lie beyond the grasp of classical computers, perhaps due to a hidden connection to quantum physics. But this quantum advantage may only occur under highly specific conditions, calling its practicality into question.
Seth Lloyd, a quantum mechanical engineer at the Massachusetts Institute of Technology who co-created the quantum TDA algorithm, remembers its origin vividly. He and fellow physicist Paolo Zanardi were attending a quantum physics workshop in an idyllic town in the Pyrenees mountains in 2015. A few days into the conference, they were skipping talks to hang out on the hotel patio as they tried to wrap their heads around a “crazy abstract” mathematical technique they had heard about for analyzing data.
Zanardi had fallen in love with the math underlying TDA, which was rooted in topology, a branch of mathematics concerned with features that remain when shapes are squashed, stretched or twisted. “This is one of those branches of mathematics which just percolates everything,” said Vedran Dunjko, a quantum computing researcher at Leiden University. “It’s everywhere.” One of the field’s central questions is the number of holes in an object, called a Betti number.
Topology can extend beyond our familiar three dimensions, allowing researchers to calculate the Betti numbers in four-, 10- and even 100-dimensional objects. This makes topology an appealing tool for analyzing the shapes of big data sets, which can also include hundreds of dimensions of correlations and connections.
Currently, classical computers can only calculate Betti numbers up to around four dimensions. On that Pyrenean hotel patio, Lloyd and Zanardi attempted to break that barrier. After about a week of discussion and scribbled equations, they had the bare bones of a quantum algorithm that could estimate the Betti numbers in data sets of very high dimensions. They published it in 2016, and researchers welcomed it into the group of quantum applications for data analysis that they believed had a meaningful quantum advantage.
Within two years, TDA was the only one that hadn’t been impacted by Tang’s work. While Tang admits that TDA is “genuinely different from the others,” she and other researchers were left to wonder to what degree its escape might have been a fluke.
Dunjko and his colleagues decided to take another shot at finding a classical algorithm for TDA that could knock out its quantum advantage. To do so, they attempted to apply Tang’s methods to this particular application, not knowing what would happen. “We really weren’t sure. There were reasons to believe that this one maybe survives the ‘Tangization,’” he recalled.
Survive it did. In results first posted as a preprint in 2020 and published this October in Quantum, Dunjko’s team showed that TDA’s survival was no fluke. To find a classical algorithm that could keep pace with the quantum algorithm, “you would have to do something different than just blindly applying Ewin Tang’s [process] to Seth Lloyd’s algorithm,” said Cade, one of the co-authors of the paper.
We don’t know for sure that classical algorithms can’t catch up with TDA, but we may get there soon. “Out of the four steps we need to make to prove this … maybe we’ve made three,” said Marcos Crichigno, a theoretical physicist at the startup QC Ware. The best evidence so far comes from a paper he posted last year with Cade showing that a similar topological calculation cannot be solved efficiently by classical computers. Crichigno is currently working to prove the same result for TDA specifically.
Crichigno suspects TDA’s resilience points to an inherent — and wholly unexpected — connection to quantum mechanics. This link comes from supersymmetry, a theory in particle physics that proposes a deep symmetry between the particles that make up matter and those that carry forces. It turns out, as the physicist Ed Witten explained in the 1980s, that the mathematical tools of topology can easily describe these supersymmetric systems. Inspired by Witten’s work, Crichigno has been inverting this connection by using supersymmetry to study topology.
“That’s nuts. That’s a really, really, really strange connection,” said Dunjko, who was not involved in Crichigno’s work. “I get goose bumps. Literally.”
This hidden quantum connection might be what set TDA apart from the rest, said Cade, who has worked with Crichigno on this. “This really is, in essence, a quantum mechanical problem, even though it doesn’t look like it,” he said.
But while TDA remains an example of quantum advantage for now, recent research from Amazon Web Services, Google and Lloyd’s lab at MIT has considerably narrowed the possible scenarios in which the advantage is most obvious. For the algorithm to run exponentially faster than classical techniques — the usual bar for a quantum advantage — the number of high-dimensional holes needs to be unthinkably large, on the order of trillions. Otherwise, the algorithm’s approximation technique simply isn’t efficient, wiping out any meaningful improvement over classical computers.
That’s “a tough set of conditions to find” in real-world data, said Cade, who was not involved in any of the three papers. It’s hard to know for sure if these conditions exist at all, so for now, we only have our intuition, said Ryan Babbush, one of the senior authors on Google’s study, and neither he nor Cade expects these conditions to be common.
Tang, now a doctoral student at the University of Washington, doesn’t think TDA is the practical quantum application the field is looking for, given these limitations. “I think the field as a whole has been reshaped” to move away from algorithm-hunting, she said. She expects that quantum computers will be most useful for learning about quantum systems themselves, not for analyzing classical data.
But the researchers behind the recent work don’t see TDA as a dead end. During a Zoom meeting between all the research teams after the recent preprints went up, “every single one of us had an idea of what to do next,” said Dunjko, who worked with Google’s team. Crichigno, for example, hopes that interrogating this connection between topology and quantum mechanics will yield more unexpectedly quantum problems that may be particularly suited to quantum computation.
There’s always the threat of a creative new classical approach doing what Tang and Dunjko couldn’t, and finally bringing down TDA. “I would not bet my house, nor my car, nor my cat,” that this won’t happen, Dunjko said. “But the story is not dead. I think that’s the main reason why I’m not worried at all.”
