How the non-Abelian Fourier transform and Quantum group theory pave the way for novel applications in quantum computing research
Machines in the early days of computers were specially constructed, room-sized collections of vacuum tubes intended to solve certain issues. It took innovative brains to develop new algorithms in addition to hardware upgrades to fully realize the potential of these ancient devices. Today, quantum computing is in a similar situation: although quantum hardware is advanced enough to start solving problems, scientists are actively looking for quantum algorithms that could have revolutionary uses, similar to how hashing and the fast Fourier transform revolutionized classical computing.
You can also read Alphabet Quantum Computing Stock Innovations & Investment
Theorists at IBM Research recently discovered a novel quantum algorithm that far outperforms the most advanced classical techniques currently in use. This finding makes use of a deep relationship between quantum physics and mathematics.
Fundamental Symmetries and Mathematical Structure
Mathematical rules regulate the structure of everything in nature, including atoms, planets, and people. At the atomic scale, its structure is regulated by quantum mechanics. Group theory, a branch of mathematics that examines collections of objects and the possible operations on them, can explain the “symmetries”—behaviors that make systems resistant to change—that are inherent in physics. The structure of quantum particles, which can be explained by group theory, offers a sophisticated way to investigate particles and, crucially, to use quantum computers to manipulate data.
Mathematicians utilize representation theory, which turns groups into tangible “representations,” such matrices (tables of numbers) and the operations that act on them, to understand abstract group theory. The transformation of quantum objects in accordance with a symmetry group is described by representation theory in quantum mechanics. Understanding these symmetries is a natural guiding concept for creating quantum algorithms since symmetry groups act on the space of solutions of a physical system.
You can also read Q-STAR and NQCP Unite to Advance Quantum Innovation
The Kronecker Coefficient Challenge
“The symmetric group,” which specifies how a deck of distinct cards is shuffled, is an example of a symmetry group. The sequence in which group elements, such as “swap cards at position 1 and 2”, are performed typically matters, demonstrating that the symmetric group is non-abelian.
Mathematicians can use matrices to depict these shuffles with representation theory. A representation is referred to as reducible if it can be converted into a block-diagonal form via a “basis change.” Irreducible representations are those that cannot be made this simple.
Determining the Kronecker coefficients is a particularly challenging challenge associated with these forms. These coefficients are the multiplicities that appear when the tensor product of two irreducible representations of the symmetric group decomposes into a new set of irreducible representations. Kronecker coefficient computation is a prime candidate for quantum speedups since it is categorized as “very, very, very difficult” on a classical computer.
You can also read Quantum Game Theory: Bridging Quantum Physics and Strategy
Associated with Quantum Complexity
There are significant parallels between the mathematical explanations of quantum particles and the challenge of computing Kronecker coefficients. The challenge of measuring the fundamental characteristics of particles in thermal equilibrium was examined in earlier work in 2022. It was shown that determining the available free energy for the most basic “2-local” example was QMA-hard.
The “quantum certificate” (proof for the answer) in a generalized form of this problem is the approximate number of linearly independent states that can be used. These issues were dubbed “quantum approximate counting” (QXC) problems by theorists.
The issue of counting Kronecker coefficients and other multiplicities of the symmetric group was found to fall into the QXC complexity class in 2024 by a team that included Vojtěch Havlíček. Havlíček and partner Martin Larocca developed a quantum algorithm to calculate the number of solutions after learning that quantum computers might effectively make progress in approximating them.
Non-Abelian Fourier Transform
Havlíček and Larocca used the quantum Fourier transform (QFT) to solve the challenge. Shor’s algorithm is based on the mathematical procedure known as QFT, which makes factoring tenfold faster than with traditional techniques. It breaks down quantum states into more straightforward ones with distinct symmetries.
The order of operations is important, though, because the symmetric group is non-abelian. According to Kristan Temme, head of the IBM Theory of Quantum Algorithms group, while phase estimation performs well on abelian structures, generalized phase estimation applications (for non-abelian groups) have generally resulted in disappointment. However, for specific input subsets, Havlíček found an algorithm that efficiently computes these multiplicities, including the Kronecker coefficients, using phase estimation for the non-abelian symmetric group.
Havlíček looked through the literature but was unable to locate a classical algorithm that was as efficient as this new quantum approach. He first conjectured that the algorithm displayed a super-polynomial speedup—likening the conventional approaches to cars and the quantum method to rocket ships.
You can also read Alphabet Quantum Computing Stock Innovations & Investment
Scrutiny and Remaining Speedup
The first audacious assertion garnered a lot of attention, especially from renowned Kronecker coefficient expert and skilled mathematician Greta Panova. After extensively examining the results, Panova presented a non-trivial improvement over the previous classical state-of-the-art technique, effectively disproving the conjecture of a super-polynomial speedup.
However, there was still an odd polynomial speedup. The quantum solution took n(4k2+1),, whereas the classical solution took n(2k+4) for a tunable parameter k.
- Quantum runs as n8 and classical runs as n17 if k is set to 2.
- Quantum runs asymptotically as n10 if k is set to 3, but classical takes n37.
As k increases, the difference develops quickly. This proved that the quantum algorithm seemed like a “quantum race car versus classical sedans” even now.
Even if additional work challenges this polynomial speedup, the work maintains symbolic relevance. According to Panova, the “Fourier transforms from quantum algorithms” create a new link between theoretical mathematics and quantum computing by giving mathematicians new ways to interpret these quantities and new structures.
Havlíček sees the study as a challenge to the community, arguing that it has consequences for other quantum algorithms if it doesn’t result in quantum speedups. This study supports IBM Research’s primary goal of identifying novel algorithmic tools that surpass the most effective classical techniques and pointing the way toward real-world applications where quantum computing may be extremely valuable. Havlíček is hopeful that the findings will contribute to the creation of new quantum algorithms.
You can also read Explainable AI-QAN for Clear, Accurate, Efficient Quantum AI
