Skip to content
Quantum.world

The Signal

Oliver O’Brien Tests Non-Abelian Hidden-Subgroup Methods on IonQ Forte

A preprint reports experiments using four measurement strategies for a non-abelian hidden subgroup problem on IonQ Forte. For one tested case, the hardware’s success probability exceeded that of an exhaustively optimised classical algorithm for up to three oracle queries.

Oliver O’Brien Tests Non-Abelian Hidden-Subgroup Methods on IonQ Forte

A preprint by Oliver O’Brien reports an experimental study of measurement strategies for a non-abelian hidden subgroup problem on IonQ Forte, a trapped-ion quantum computer. For p=7 and q=6, the hardware exceeded the success probability of an exhaustively optimised classical algorithm for up to three oracle queries. The preprint was submitted to arXiv on 4 November 2026.

The measurement basis matters for non-abelian groups

The hidden subgroup problem (HSP) provides a common framework for several quantum speed-ups. For abelian groups, weak Fourier sampling solves the problem efficiently. Non-abelian versions are relevant to problems including graph isomorphism and the unique shortest vector problem, which is connected to lattice-based cryptography. The preprint says no general efficient quantum algorithm is known for the non-abelian HSP, and that the choice of measurement basis is important.

O’Brien studies q-hedral groups, written as Zq ⋉ Zp. These groups lie between the dihedral group, at q=2, and the affine group, at q=p−1. The preprint describes the family as marking a boundary between cases that can be solved efficiently and cases that are only information-theoretically solvable. The experiments cover p=3, 5 and 7, with q values spanning the dihedral and affine extremes.

Four sampling strategies tested

On IonQ Forte, the study implements weak Fourier sampling; strong Fourier sampling in an adapted basis; strong Fourier sampling of adjacent pairs; and forgetful abelian sampling. The last method discards the non-abelian structure of the group. The experiments examine whether theoretical predictions for these approaches hold on a noisy quantum device.

The reported results follow different patterns across the methods. Weak Fourier sampling carries no information about the hidden subgroup. Sampling in the adapted basis succeeds for large q, while adjacent-pair sampling succeeds for small q, where the adapted-basis method fails. Forgetful abelian sampling does not reach unit success probability.

The preprint gives a success probability of (p−1)q/p² for adapted-basis sampling. For forgetful abelian sampling, it reports a plateau at (p+q−1)/(pq), because the method cannot distinguish b within an orbit. O’Brien also introduces a modification to the adjacent-pairs measurement: replacing H with HT removes an ambiguity between b and −b in the original scheme.

The comparison is about query count

For p=7 and q=6, the hardware’s success probability is higher than that of an exhaustively optimised, derandomised classical birthday algorithm for up to three queries. The preprint cautions that, at these small sizes, this comparison concerns query complexity, not computational speed-up.

The setup also relies on a third party to compile the hidden value b into the oracle circuit. The preprint says that b is used to construct the oracle, but not in decoding; the oracle is treated as a black box when counting queries. Some circuit elements that act only on registers later discarded are omitted, as detailed in the paper’s appendix.

The work reports a first experimental implementation of solving a non-abelian HSP on a quantum device, and describes the experiment as an end-to-end test of the measurement strategies. Its results offer a demonstration, at the tested group sizes and on a noisy device, of how the chosen basis affects the information obtained from measurements.

Sources

  1. arXiv
  2. arXiv

Related stories

Explore

More articles