Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem
arXiv:2401.07934 · doi:10.1103/PhysRevX.15.021082
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 . For sufficiently small values of 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 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.
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
References in corpus (49)
- Quantum Computing in the NISQ era and beyond
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Mechanics helps in searching for a needle in a haystack
- Quantum algorithm for solving linear systems of equations
- Quantum computational advantage using photons
- Dynamical Decoupling of Open Quantum Systems
- Noisy intermediate-scale quantum (NISQ) algorithms
- Dynamical suppression of decoherence in two-state quantum systems
- Error mitigation for short-depth quantum circuits
- Strong quantum computational advantage using a superconducting quantum processor
- Quantum algorithms: an overview
- Exponential algorithmic speedup by quantum walk
- Defining and detecting quantum speedup
- Quantum advantage in learning from experiments
- Benchmarking an 11-qubit quantum computer
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
- Quantum advantage with shallow circuits
- Symmetrizing Evolutions
- Using Parity Kicks for Decoherence Control
- Quantum critical dynamics in a 5000-qubit programmable spin glass
- Complete 3-Qubit Grover Search on a Programmable Quantum Computer
- Demonstration of fidelity improvement using dynamical decoupling with superconducting qubits
- Demonstration of a scaling advantage for a quantum annealer over simulated annealing
- Experimental quantum speed-up in reinforcement learning agents
- Suppression of crosstalk in superconducting qubits using dynamical decoupling
- Dynamical decoupling for superconducting qubits: a performance survey
- Scaling advantage in quantum simulation of geometrically frustrated magnets
- Application-Oriented Performance Benchmarks for Quantum Computing
- Quantum advantage with noisy shallow circuits in 3D
- Arbitrarily Accurate Pulse Sequences for Robust Dynamical Decoupling
- Quantum factoring, discrete logarithms and the hidden subgroup problem
- Phase transition in Random Circuit Sampling
- Efficient Long-Range Entanglement using Dynamic Circuits
- Quantum Crosstalk Robust Quantum Control
- Demonstration of algorithmic quantum speedup
- Quantum-enhanced data classification with a variational entangled sensor network
- Boundaries of quantum supremacy via random circuit sampling
- Quantum Fourier Transform using Dynamic Circuits
- Experimental quantum advantage with quantum coupon collector
- A programmable three-qubit superconducting processor with all-to-all connectivity
- Experimental benchmarking of an automated deterministic error suppression workflow for quantum algorithms
- Optimized Dynamical Decoupling via Genetic Algorithms
- Quantum advantage for computations with limited space
- Qudit Dynamical Decoupling on a Superconducting Quantum Processor
- Dissipative Dynamics of Graph-State Stabilizers with Superconducting Qubits
- Experimental demonstration of quantum advantage for NP verification with limited information
- Process tomography of Robust Dynamical Decoupling in Superconducting Qubits