Curator's Take
AI Commentary
This article marks the first experimental realization of a non‑abelian hidden subgroup problem on a trapped‑ion processor, confirming that the choice of measurement basis—not just circuit depth—can be the decisive factor for quantum speed‑ups in problems such as graph isomorphism and lattice‑based cryptography. By testing weak, strong (adapted), adjacent‑pair, and forgetful sampling strategies on the IonQ Forte device, the authors show that theoretical predictions about when information can be extracted survive realistic noise levels, and even surpass an optimally tuned classical algorithm for a three‑query instance. The work demonstrates a concrete pathway toward quantum algorithms that exploit group structure beyond the abelian case, while reminding readers that scaling to larger groups will still demand improvements in qubit count and error rates.
— Mark Eatherly
Summary
The hidden subgroup problem (HSP) unifies many of the best-known quantum speed-ups. For abelian groups it is solved efficiently by weak Fourier sampling, but for non-abelian groups, which include the cases relevant to graph isomorphism and lattice-based cryptography, the right measurement basis is crucial and often unknown. We experimentally study the HSP over the $q$-hedral groups $\mathbb{Z}_q \ltimes \mathbb{Z}_p$, which interpolate between the dihedral and affine groups and mark a boundary between instances that are efficiently solvable and those that are only information-theoretically solvable. On the IonQ Forte trapped-ion quantum computer, with $p \le 7$, we implement weak Fourier sampling, strong Fourier sampling in an adapted basis, strong Fourier sampling of adjacent pairs, and forgetful abelian sampling. We demonstrate that the theoretical predictions of Moore, Rockmore, Russell and Schulman survive on a noisy device: weak sampling reveals nothing about the hidden subgroup, the adapted basis succeeds for large $q$, adjacent pairs succeed for small $q$, and forgetful sampling saturates below unit success. For $p=7$, $q=6$, the hardware exceeds the success probability of an exhaustively optimised classical algorithm for up to three oracle queries.