Quantum computers tackle a century‑old math puzzle

Los Alamos National Laboratory researcher Martín Larocca and Vojtěch Havlíček, a researcher at IBM, have shown that quantum computers can crack a family of complex problems involving group representations, which are sets of matrices that embody an abstract group, and that have stumped today’s greatest supercomputers. This discovery offers more evidence of quantum advantage, and it buoys the need for the nation to establish itself as a global leader in quantum computing.

“The challenge for quantum computing at this moment is straightforward,” said Larocca, a scientist and the paper’s first author. “We want to know what quantum computers are good at, so we looked at a set of problems that we know to be intractable to classical computers."

In a paper published by Physical Review Letters, Larocca and Havlíček show that quantum computers can be used to “factorize” group representations into their indivisible building blocks, called irreducible representations. These problems are used widely in scientific fields ranging from engineering to particle physics and beyond.

In a larger sense, insights like those found in this paper are guiding researchers’ current understanding of what quantum computers are capable of.

“This is the essence of quantum computing research,” Larocca said. “We want to find quantum algorithms that display speedups over classical algorithms.”

Solving the unsolvable

The field of quantum computing is in a race on two fronts: the first, to develop the hardware that can make large-scale quantum computers a reality; the second, to explore the quantum advantage — problems for which quantum computing is faster, more efficient, or more accurate than classical computing. It is in this latter category that Larocca’s paper offers valuable insights.

Whenever scientists describe the different ways something can be rearranged — atoms in a crystal, qubits in a circuit, pixels in an image — they often reach for the group representation, the set of all possible swaps of an item. A group representation turns those abstract swaps into concrete matrices that computers can then manipulate. For example, every time physicists describe how a particle can spin, vibrate or trade places with its neighbors, they use group representations.

Just as any whole number can be broken into its prime factors (the number 12, for example, can be equally divided by 1, 2, 3, 4 and 6), any group representation is capable of being broken into its core building blocks, called “irreducible representations.” But even the fastest classical supercomputers are stumped when it comes to solving these problems — especially when it comes to multiplicity numbers, which count how many times each building block appears in the problem.

The new paper uses quantum Fourier transforms, a family of quantum circuits that compile certain group-theoretic transforms, including the well-known discrete Fourier transform, which decomposes discrete time signals into its frequency components. With this, Larocca and Havlíček were able to factor several common group representations. 

When scientists calibrate particle‑physics detectors, they rely on factoring group representations to find these multiplicity numbers. Error-correcting codes, used in data transmission and storage, also rely on this technique. The method is also critical in advanced material design.

“Computer scientist Peter Shor showed that quantum computers can factor integers,” Larocca said. “Here, we’re showing they also allow us to factor symmetries.”

The research was published in the journal Physical Review Letters.

Paper: “Quantum Algorithms for Representation-Theoretic Multiplicities.” Physical Review Letters.

DOI: https://doi.org/10.1103/k5tx-xtr3

Funding: This work was funded by the Center for Nonlinear Studies at Los Alamos National Laboratory and by the Laboratory Directed Research and Development (LDRD) program.

LA-UR-25-28431