On the IonQ Forte trapped-ion quantum computer, researchers have demonstrated a potential quantum speed-up by exceeding the success probability of a classical algorithm for solving a specific hidden subgroup problem. The work focuses on q-hedral groups, which represent a critical boundary between problems solvable with quantum computers and those only solvable in theory.

Oliver O’Brien of the University of Cambridge and colleagues implemented four measurement bases, weak Fourier sampling, strong Fourier sampling in an adapted basis, strong Fourier sampling of adjacent pairs and forgetful abelian sampling, to determine the most effective approach for these non-abelian groups. For p = 7 and q = 6, the hardware outperformed the classical algorithm for up to three oracle queries, validating theoretical predictions about the power of tailored quantum algorithms on noisy devices.

Trapped Ions Tackle Non-Abelian Hidden Subgroup Problem

The IonQ Forte trapped-ion quantum computer distinguished between hidden subgroups within q-hedral groups using a measurement strategy tailored to the group’s structure, a feat previously challenging for quantum algorithms. This work builds on the established efficiency of weak Fourier sampling for abelian groups, but acknowledges its limitations when applied to the more complex non-abelian cases critical to fields like cryptography. The q-hedral groups were selected as a testbed because they represent an intermediate complexity, bridging the gap between solvable and theoretically solvable, but practically intractable, problems.

The experimental design revealed predictable performance differences between the measurement bases, confirming theoretical predictions regarding their suitability for various q-hedral group configurations. Weak sampling, as expected, proved insufficient to reveal the hidden subgroup, while the adapted basis succeeded when the divisor q was large, and sampling adjacent pairs performed well when q was small.

Forgetful abelian sampling achieved saturation below a success rate of one, demonstrating a defined performance limit. “We demonstrate that the theoretical predictions of Moore, Rockmore, Russell and Schulman survive on a noisy device,” the researchers state in their paper. The ability to surpass classical algorithms, even for a limited number of queries, is significant because the non-abelian hidden subgroup problem underpins the security of several cryptographic systems.

The researchers note that many interesting problems, including graph isomorphism and the unique shortest vector problem can be reduced to the non-abelian HSP, making efficient quantum solutions highly desirable. While the current demonstration is limited to specific parameters (p ≤ 7), it validates the approach and suggests a pathway towards tackling more complex instances.

q-Hedral Groups Define Solvability Boundaries for HSP

The boundary between quantumly solvable and theoretically solvable problems became clearer with recent experiments on q-hedral groups, a family of non-abelian groups interpolating between dihedral and affine structures. This work establishes a link between theoretical predictions and performance on a noisy device, validating the approach for exploring the complexity of non-abelian HSPs. The experimental design focused on how carefully selecting a measurement basis impacts the ability to fully or even theoretically reconstruct the hidden subgroup, a challenge particularly acute for non-abelian groups.

The q-hedral groups, defined for each prime p and divisor q of p-1, were chosen because they represent a known transition point between efficiently solvable and information-theoretically solvable instances. This allowed for a direct comparison of different quantum algorithms and their effectiveness in extracting the hidden subgroup information.

The group’s elements are defined as pairs (x,α^t) where x is in $Z_{p}$ , t is in $Z_{q}$ . α has order q, with a specific group action governing their combination. Results showed that weak Fourier sampling, as predicted, failed to reveal any information about the hidden subgroup, confirming its inadequacy for non-abelian problems.

Future work will likely explore other non-abelian groups and investigate more sophisticated measurement techniques, such as entangled measurements or Kuperberg’s sieve, to further push the boundaries of quantum computation for solving these challenging problems. The data, code and circuits supporting this work are publicly available, facilitating further research and validation by the wider quantum computing community.

Weak, Strong, and Forgetful Fourier Sampling Strategies

The q-hedral groups, used in recent experiments, provided a testing ground for different quantum measurement strategies, specifically examining how well each could reveal a hidden subgroup. Strong Fourier sampling, however, demonstrated varying degrees of success depending on the chosen basis and the value of q. Using an adapted basis, the method successfully identified the hidden subgroup for larger values of q, aligning with theoretical predictions that this approach scales favorably.

Conversely, strong Fourier sampling of adjacent pairs proved more effective for smaller values of q, highlighting a detailed relationship between the measurement basis and the problem’s parameters. This result suggests a potential quantum speed-up on a real, noisy device, a step toward demonstrating the practical advantages of quantum computation.

The experimental setup involved drawing weak Fourier samples from forgetful abelian circuits, where the irrep distribution remained consistent regardless of the hidden subgroup, confirming the method’s inability to extract relevant information. Data analysis further revealed that the probability of recovering the hidden subgroup b varied significantly depending on the sampling method. Plots comparing the adapted basis, adjacent pairs, and forgetful abelian sampling showed that the adapted basis consistently outperformed the other methods for q = 6, while adjacent pairs performed better for q = 2.

The forgetful abelian sampling method consistently lagged behind, emphasising its limitations in solving this particular instance of the hidden subgroup problem. The team did not employ zero noise extrapolation for these plots, opting instead to focus on the raw performance of each method with a limited number of oracle queries, providing a direct comparison of their effectiveness.

Adapted Basis Sampling Succeeds for Large q Values

Strong Fourier sampling using an adapted basis proved most effective at identifying hidden subgroups within q-hedral groups when the value of q was larger, a finding that builds on theoretical work predicting the optimal measurement strategy for these complex non-abelian hidden subgroup problems. The experimental work, conducted with the IonQ Forte trapped-ion quantum computer, revealed a clear performance advantage for this method over alternatives like adjacent-pairs sampling and forgetful abelian sampling as q increased. For p = 7, q = 6, the hardware exceeds the success probability of an exhaustively optimised classical algorithm for up to three oracle queries.

Analysis of the post-measurement state following an irrep label measurement showed that the adapted basis method correctly identified the hidden subgroup with a probability scaling with q/p, indicating a robust signal even in the presence of experimental imperfections. The forgetful abelian sampling method, however, consistently plateaued at a success probability of (p + q-1)/(pq), highlighting its limitations in distinguishing between potential solutions within an orbit.

The study also showed that noiseless simulations of the quantum hardware achieved over 90% success probability with fewer queries than classical algorithms, further supporting the potential for quantum speed-up in solving these problems. The experimental results provide a direct comparison of the four measurement strategies, revealing a clear trade-off between their effectiveness depending on the value of q. These findings contribute to a growing body of evidence suggesting that quantum computers can, in principle, outperform classical algorithms in solving certain computational tasks, even on current, imperfect hardware.

IonQ Forte Hardware Exceeds Classical Performance

This outcome is particularly notable given the challenges of maintaining quantum coherence in a noisy environment, and it validates key theoretical predictions regarding the behaviour of these algorithms. The experimental setup involved running 62 circuits on the IonQ Forte between October 9th and 12th, 2026, each with 2,048 shots, alongside additional gate-folded copies for a total of 153,600 shots.

The team deliberately restricted their experiments to prime numbers p = 3, 5, and 7, acknowledging that larger primes would introduce excessive noise and obscure the signal. To ensure a fair comparison, they developed an exhaustively optimised classical algorithm, searching for the query sequence that maximised the probability of correctly decoding the hidden subgroup b.

Experimental Verification of MRRS Theoretical Predictions

Q-hedral groups were experimentally explored using the IonQ Forte trapped-ion quantum computer. This investigation focused on verifying predictions regarding the optimal measurement basis for tackling these non-abelian groups. Forgetful abelian sampling, which disregards the non-abelian nature of the group, consistently plateaued in performance, failing to achieve unit success probability.

Analysis of the post-measurement state revealed that the expectation value of the least significant bit varies as sin(mπ/pb + π/8)^2, a deviation from the original MRRS prediction of sin(mπ/pb)^2, but still allowing for subgroup identification. The success of strong Fourier sampling with an adapted basis highlights the importance of tailoring the measurement basis to the specific problem structure.

The researchers found that the number of elements in an orbit, pq/(p + q-1), limits the maximum achievable success probability, regardless of the number of samples collected. This limitation highlights the information-theoretic constraints inherent in decoding the hidden subgroup and the impact of basis choice on reconstruction accuracy.

👉 More information
🗞 Solving a non-abelian hidden subgroup problem on a trapped-ion quantum computer: the power of the measurement basis
✍️ Oliver O'Brien
🧠 ArXiv: https://arxiv.org/html/2611.06716v1

More like this