Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden
  Subgroup Problem
Simon's problem is to find a hidden period (a bitstring) encoded into an
unknown $2$-to-$1$ function. It is one of the earliest problems for which an
exponential quantum speedup was proven for ideal, noiseless quantum computers,
albeit in the oracle model. Here, using two different $127$-qubit IBM Quantum
superconducting processors, we demonstrate an algorithmic quantum speedup for a
variant of Simon's problem where the hidden period has a restricted Hamming
weight $w$. For sufficiently small values of $w$ and for circuits involving up
to $58$ qubits, we demonstrate an exponential speedup, albeit of a lower
quality than the speedup predicted for the noiseless algorithm. The speedup
exponent and the range of $w$ values for which an exponential speedup exists
are significantly enhanced when the computation is protected by dynamical
decoupling. Further enhancement is achieved with measurement error mitigation.
This constitutes a demonstration of a bona fide quantum advantage for an
Abelian hidden subgroup problem.
P. Singkanipa V. Kasatkin Z. Zhou G. Quiroz D. A. Lidar