Hunt for Quantum Speedups Closes a Door But Opens a Window

Nov 11, 2020

Quantum computer scientists dream of finding exponential quantum speedups. These are techniques for solving computational problems that utilize the full promise of quantum computers to arrive at solutions much more quickly than any ordinary computer. But finding problems that yield to the unique power of quantum computers is only half the story.

“In general, we want to understand when you can have exponential quantum speedups—and also when it’s not possible,” says Daochen Wang (in photo), a third-year doctoral student in the Applied Mathematics & Statistics, and Scientific Computation program at the University of Maryland who is working in the Joint Center for Quantum Information and Computer Science (QuICS). “Both sides are important for understanding the power of quantum computers.”

So far, research points to big speedups requiring special kinds of problems. In particular, they require problems with structure, which could be provided by symmetry embedded within the problem or its solutions—symmetry that can be guaranteed ahead of time.

Take Shor’s algorithm, one of the most notable examples of a quantum speedup. It can break big numbers down into their prime factors faster than any known non-quantum algorithm. It does this by reformulating the problem of factoring into the problem of figuring out how frequently a particular mathematical function repeats (technically, it determines a parameter known as the function’s period). And the fact that this function is repetitive in this way proves to be the right kind of structure to allow for significant quantum speedup.

But sometimes too much symmetry can actually prevent speedups. In a paper presented this week at the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS), Wang and several colleagues have ruled out the possibility of exponential quantum speedups for problems with another kind of structure, resolving an open question posed in 2010. But they also showed that these problems are a final frontier of sorts—their symmetries are essentially the only barrier to exponential quantum speedups.

“Daochen found a beautiful way of bounding the power of quantum algorithms for problems with graph symmetry by generalizing previous work on problems with full permutation symmetry,” says Andrew Childs, a co-director of QuICS and a professor of computer science at the University of Maryland who, along with QuICS Fellow Carl Miller, advises Wang. “His insight finally cracked a problem that has resisted attack for almost a decade.” Wang ultimately discovered how to prove that a family of problems—problems exhibiting graph symmetries—would never succumb to an exponential quantum speedup.

A graph is a simple mathematical object, often visualized as a network of labeled nodes and the connections between them. Graph symmetry boils down to the following: If you relabel the nodes of a graph, it doesn’t really change anything fundamental about the graph itself. A graph captures the relationships between nodes via the connections, or edges, between them, and shuffling the names of the nodes doesn’t change this underlying structure.

Many computational problems can be posed about graphs. In order to prove that none of them allow for an exponential quantum speedup, the researchers studied them in the context of the quantum query complexity model. In the query complexity model, you’re given a function, an input to the function and the ability to peek at the input one bit at a time (in the quantum case these queries can be made in superposition). For graphs, this input is some kind of data that represents a particular graph.

Solving a problem in the query complexity model means evaluating the function on the given input: Is this graph bipartite? Are these two graphs the same? But the only thing that counts in the query model is the number of times you peek at the input bits (the number of “queries” that you make). In the query model, an exponential speedup corresponds to using exponentially fewer queries to solve the problem.

The query complexity model abstracts away the details of the function that you’re trying to compute, allowing researchers to get a cleaner picture of what’s possible without having to delve into the nitty gritty of how the function is implemented. “It’s like you don’t have the source code for that function,” says Childs. “You just know how to compute it.”

Wang, Childs and their colleagues proved that if a graph is represented in a standard way (using an adjacency matrix), then there can never be a quantum query algorithm that achieves an exponential speedup over a classical algorithm. Moreover, and somewhat surprisingly, they proved that graph symmetries are essentially the only symmetries that prevent exponential quantum speedups.

An additional discovery from the paper is that it matters how you choose to represent a graph. If you use something called an adjacency list—which lets you learn the neighbors of a given node instead of just whether two nodes are connected (as with an adjacency matrix)—then there are problems that do have exponential quantum speedups. And that’s fertile ground for researchers to search for new quantum speedups, says Childs.

“What this paper does is delineate, to some extent, where you can hope for exponential quantum speedup,” he says. “And this lets you better focus on the space where we should be looking for fast quantum algorithms.”

—Story by Chris Cesare

In addition to Childs and Wang, the new paper has four additional co-authors: Shalev Ben-David, a former QuICS Hartree Postdoctoral Fellow who is now an assistant professor of computer science at the University of Waterloo; András Gilyén, a postdoctoral researcher at the Institute for Quantum Information and Matter at Caltech; William Kretschmer, a graduate student in computer science at the University of Texas at Austin; and Supartha Podder, a postdoctoral researcher in mathematics and statistics at the University of Ottawa.