Solving a non-abelian hidden subgroup problem on a trapped-ion quantum computer: the power of the measurement basis
Abstract
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 ℤq ltimes ℤ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 ≤ 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.
Related
- The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem
- "I don't have a good metric for what other people think:" Unpacking the double empathy problem in neurodivergent physics problem-solving
- Solving the MAX-k-CUT problem for hypergraphs with quantum computing
- A simple solution to the monopole problem: SU(5) GUT with symmetry breaking into special subgroup
- Alignment of the amplitudes of stored states for solving the associative memory problem using quantum annealing
BibTeX
@misc{obrien2026solving,
title = {{Solving a non-abelian hidden subgroup problem on a trapped-ion quantum computer: the power of the measurement basis}},
author = {Oliver O'Brien},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.06716},
eprint = {2611.06716},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.06716},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Solving a non-abelian hidden subgroup problem on a trapped-ion quantum computer: the power of the measurement basis
AU - Oliver O'Brien
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.06716
UR - https://arxiv.org/abs/2611.06716
AB - 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 ℤ_q ltimes ℤ_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 ≤ 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.
ER -