Researchers have successfully used a quantum algorithm to solve a complex century-old mathematical problem long considered impossible for even the most powerful conventional supercomputers.
The achievement has direct applications in fields including particle physics, material science, and data transmission.
“Is there a computational problem that has an efficient quantum algorithm but no efficient randomized algorithm? Quantum computing is driven by the belief that the answer is yes,” said the researchers in a new study.
Factoring group representations
The work was conducted by Martín Larocca, a scientist at Los Alamos National Laboratory, and Vojtěch Havlíček, a researcher at IBM.
In a paper published in Physical Review Letters, they demonstrate that quantum computers can “factor group representations,” a foundational task in several scientific disciplines.
“Computer scientist Peter Shor showed that quantum computers can factor integers,” Larocca explained, referencing a famous discovery in the field. “Here, we’re showing they also allow us to factor symmetries.”
The problem is conceptually similar to finding the prime factors of a number, like breaking down 12 into 2, 2, and 3. Scientists use group representations to describe all the possible arrangements or transformations of a system, such as atoms in a crystal.
These representations can be broken down into their fundamental building blocks, known as “irreducible representations.”
For classical computers, finding these blocks and counting them (“multiplicity numbers”) becomes an exceedingly difficult task for complex systems.
Example of quantum advantage
The new research shows that an algorithm using quantum Fourier transforms can perform this factorization efficiently.
“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,” highlighted the researchers in a press release.
This success is a clear example of “quantum advantage,” where quantum computers can solve meaningful problems that are intractable for classical machines.
“This is the essence of quantum computing research,” Larocca said. “We want to find quantum algorithms that display speedups over classical algorithms.”
“We identify a class of problems in representation theory that admit efficient quantum algorithms, study what makes these problems intractable classically, and find a parameter regime with a potential quantum speedup,” added the study.
Several real-world implications
The ability to efficiently factor group representations is important for several real-world tasks.
For instance, the method is used in particle physics for the calibration of sensitive particle detectors. In data science, it is applied to develop and implement robust error-correcting codes for data storage and transmission.
The technique is also critical in material science for understanding the properties of materials, which aids in the design of new ones.
This research contributes to the ongoing effort to identify the specific problems where quantum computers can offer a distinct advantage over classical ones.
“The challenge for quantum computing at this moment is straightforward,” Larocca concluded. “We want to know what quantum computers are good at.”