Trapped ions solve a hard subgroup problem, testing quantum speed-up

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. The IonQ Forte trapped-ion quantum computer distinguished between hidden subgroups within q-hedral groups using a measurement…