1. Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem
- Author
-
Singkanipa, P., Kasatkin, V., Zhou, Z., Quiroz, G., and Lidar, D. A.
- Subjects
Quantum Physics - Abstract
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., Comment: 39 pages, 29 figures, v3: significantly updated with new results and revised. Now includes a formal proof that the limited-weight Hamming problem exhibits an exponential speedup even subject to noise. Expanded statistical analysis further confirms the experimentally observed exponential speedup
- Published
- 2024