⚛️ quantum physics

Solving a non-abelian hidden subgroup problem on a trapped-ion quantum computer: the power of the measurement basis

This paper demonstrates on a trapped-ion quantum computer that the success of solving the non-abelian hidden subgroup problem over $q$ -hedral groups critically depends on the measurement basis, with experimental results confirming theoretical predictions and, for specific parameters, surpassing the performance of optimized classical algorithms.

Original author: Oliver O'Brien

Published 2026-11-05

📖 4 min read🧠 Deep dive

CC BY 4.0

Original author: Oliver O'Brien

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the author. For technical accuracy, refer to the original paper. Read full disclaimer

Quantum computers promise to solve certain problems far faster than any machine we have built today, but the path to that speed is not a straight line. At the heart of this promise lies a mathematical challenge known as the hidden subgroup problem. Imagine a vast, complex maze where a secret path is hidden. A classical computer must wander through the maze, checking one corridor at a time, until it stumbles upon the pattern. A quantum computer, however, can explore many corridors simultaneously. For simple, orderly mazes, scientists have long known how to program a quantum machine to find the secret path instantly. But for mazes with a more tangled, irregular structure, the rules change. The quantum machine can still explore many paths at once, but reading the result requires a very specific kind of observation. If the observer looks at the wrong angle, the secret remains hidden, no matter how powerful the machine.

This uncertainty about how to look has been a major hurdle in the field. While the theory suggests that quantum computers could crack codes that protect the internet or solve complex puzzles in chemistry, the practical steps to do so for these irregular mazes have remained untested on real hardware. Researchers have debated which method of observation would work, but without a physical experiment, the answers were purely mathematical. Now, a team has taken the first step to settle this debate in the real world, moving from theory to a working quantum device to see which method actually reveals the hidden secret.

The researchers focused on a specific family of mathematical structures that sit right on the edge between problems that are easy to solve and those that are theoretically possible but practically difficult. They used a trapped-ion quantum computer, a machine that uses individual atoms held in place by electric fields to perform calculations. The team set up a series of experiments to test four different ways of measuring the quantum state after it had interacted with the hidden pattern. The first method, which is the standard approach for simpler problems, involved taking a quick, broad look at the result. The second and third methods were more sophisticated, involving a careful adjustment of the measurement angle to extract more detail, while the fourth method ignored the complex structure entirely to see if a simpler view would suffice.

The results were clear and decisive. The broad, quick look provided no useful information at all; the hidden secret remained completely invisible, confirming that this common approach fails for these complex structures. The method that ignored the complex structure also hit a hard ceiling; it could narrow down the possibilities to a group of candidates, but it could never pinpoint the exact secret, no matter how many times the experiment was repeated. However, the two sophisticated methods succeeded, but in very different ways depending on the specific shape of the problem. When the structure was large and complex, one specific measurement angle worked perfectly, revealing the secret with high confidence. When the structure was smaller, that same angle failed, but a different technique, which looked at pairs of related values, succeeded instead.

Perhaps the most striking finding was that the quantum machine, despite being noisy and imperfect, outperformed the best possible classical computer strategy for a small number of attempts. In a specific test case, the quantum device found the hidden secret with a higher probability than a classical algorithm could achieve, even though the classical algorithm had access to a perfect, error-free version of the problem. This did not mean the quantum computer was faster in terms of raw speed, but rather that it was more efficient at using the limited number of questions it was allowed to ask. The experiment proved that the theoretical predictions made years ago by mathematicians were correct: the choice of how to measure the quantum state is not just a minor detail, but the deciding factor between success and failure.

This work demonstrates that the power of quantum computing relies heavily on the precision of the final step. It is not enough to simply run the calculation; the observer must know exactly how to look at the result to see the answer. By showing that these theoretical strategies survive the messy reality of a physical quantum computer, the study provides a roadmap for future experiments. It confirms that with the right measurement technique, quantum devices can solve problems that are currently out of reach for classical machines, even before the technology is fully mature. The path forward is now clearer: the secret is not just in the calculation, but in the careful, deliberate act of observation.

Technical Summary: Solving a Non-Abelian Hidden Subgroup Problem on a Trapped-Ion Quantum Computer

Problem Statement
The Hidden Subgroup Problem (HSP) unifies many of the most significant quantum speed-ups, including Shor's algorithm for factoring (an abelian HSP). While the abelian HSP is efficiently solvable via weak Fourier sampling, the non-abelian HSP remains a major challenge. Efficient solutions for non-abelian groups are crucial for problems like graph isomorphism (symmetric group) and lattice-based cryptography (dihedral group). However, unlike the abelian case, no general efficient quantum algorithm exists for non-abelian HSP. The difficulty often lies in the choice of measurement basis; while some instances are "fully reconstructible" (solvable with polynomial quantum circuits and classical post-processing), others are only "information-theoretically reconstructible" (solvable with polynomial quantum circuits but requiring arbitrary, potentially exponential, classical post-processing).

This work focuses on the $q$ -hedral groups ( $G = \mathbb{Z}_q \ltimes \mathbb{Z}_p$ ), which interpolate between the dihedral group ( $q=2$ ) and the affine group ( $q=p-1$ ). These groups represent a boundary where the HSP transitions between fully reconstructible and information-theoretically reconstructible regimes, depending on the relationship between $q$ and $p$ .

Methodology
The author implemented an end-to-end non-abelian HSP solver on the IonQ Forte trapped-ion quantum computer for primes $p \in \{3, 5, 7\}$ and various divisors $q$ of $p-1$ . The experimental protocol involved:

State Preparation: Creating a uniform superposition over the group elements.
Oracle Application: Applying a function $f_b(x, t) = \pi(x + \alpha^t b)$ invariant under the hidden subgroup $H_b$ , where $b$ is the secret to be found.
Quantum Fourier Transform (QFT): Performing a QFT over the non-abelian group $G$ .
Measurement Strategies: The study compared four distinct measurement strategies to evaluate their efficacy in recovering $b$ $b$ :
- Weak Fourier Sampling: Measuring only the irreducible representation (irrep) label.
- Strong Fourier Sampling (Adapted Basis): Measuring the irrep label and then performing a specific basis change (involving $H^T$ ) on the remaining register to extract $b$ .
- Strong Fourier Sampling (Adjacent Pairs): Measuring adjacent pairs of qubits (using a modified encoding where the exponent $t$ is stored directly) to distinguish $b$ from $-b$ .
- Forgetful Abelian Sampling: Treating the group as a direct product $\mathbb{Z}_q \times \mathbb{Z}_p$ and discarding non-abelian structure.

Key Contributions

Experimental Implementation: This is the first experimental demonstration of strong Fourier sampling and an end-to-end non-abelian HSP algorithm on a quantum device.
Circuit Optimization: The author constructed hardware-efficient circuits, including numerically synthesized QFT $_p$ circuits, an oracle via Fourier conjugation, and a Walsh-series synthesis for diagonal gates. These implementations used significantly fewer two-qubit gates than standard compiler synthesis.
Algorithmic Modification: A modification to the adjacent-pairs measurement was introduced, replacing the Hadamard gate ( $H$ ) with its transpose ( $H^T$ ). This resolves an ambiguity between $b$ and $-b$ present in the original Moore, Rockmore, Russell, and Schulman (MRRS) scheme, ensuring information-theoretic reconstructibility for all $q$ .
Benchmarking: The quantum results were compared against an exhaustively optimized, derandomized classical birthday algorithm.

Results
The experimental data, collected on a noisy intermediate-scale quantum (NISQ) device, aligned with theoretical predictions:

Weak Fourier Sampling: Confirmed to reveal no information about the hidden subgroup $b$ , as the irrep distribution is identical for all $b$ .
Adapted Basis Sampling: Successfully recovered $b$ with high probability for large $q$ (specifically $q=6$ for $p=7$ ), following the theoretical success probability of $(p-1)q/p^2$ . However, performance degraded for small $q$ .
Adjacent Pairs Sampling: Successfully recovered $b$ for small $q$ (specifically $q=2$ ), where the adapted basis failed. The $H^T$ modification successfully distinguished $b$ from $-b$ , whereas the standard $H$ gate did not.
Forgetful Abelian Sampling: Confirmed to be insufficient for full reconstruction. It could only identify the orbit of $b$ , plateauing at a success probability of $(p+q-1)/(pq)$, consistent with the inability to distinguish $b$ within the same orbit.
Quantum vs. Classical: For the case $p=7, q=6$ , the noisy quantum hardware achieved a higher success probability than the optimal classical strategy for up to three oracle queries. In noiseless simulations, the quantum algorithm exceeded 90% success probability with fewer queries than the classical algorithm.

Significance and Claims
The paper claims that the theoretical results of MRRS regarding the $q$ -hedral HSP survive on a noisy quantum device. The primary significance lies in demonstrating that the choice of measurement basis is not merely an asymptotic theoretical concern but a practical necessity for both full and information-theoretic reconstructibility.

The author emphasizes that even at small scales ( $p=7$ ), selecting the correct basis (e.g., adapted basis for large $q$ , adjacent pairs for small $q$ ) is critical. Conversely, using an incorrect basis (weak sampling or forgetful abelian sampling) prevents the success probability from reaching unity, regardless of the number of samples. The work establishes that a system known to be fully reconstructible can outperform an optimized classical algorithm in recovery probability for low query counts, even in the presence of hardware noise. This serves as a proof-of-principle that non-abelian HSP algorithms can be executed on current hardware, provided the measurement strategy is carefully tailored to the group structure.

Technical Summary: Solving a Non-Abelian Hidden Subgroup Problem on a Trapped-Ion Quantum Computer

More like this