Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem

Understand

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.