Simon's Period Finding on a Quantum Annealer
arXiv:2504.10771 · doi:10.1109/QCE65121.2025.00030
Abstract
Dating to 1994, Simon's period-finding algorithm is among the earliest and most fragile of quantum algorithms. The algorithm's fragility arises from the requirement that, to solve an n qubit problem, one must fault-tolerantly sample O(n) linearly independent values from a solution space. In this paper, we study an adiabatic implementation of Simon's algorithm that requires a constant number of successful samples regardless of problem size. We implement this algorithm on D-Wave hardware and solve problems with up to 298 qubits. We compare the runtime of classical algorithms to the D-Wave solution to analyze any potential advantage.
Submitted on World Quantum Day, 14 April 2025
References in corpus (8)
- Adiabatic Quantum Computing
- Quantum Algorithms and the Fourier Transform
- Graph isomorphism and adiabatic quantum computing
- A quantum-walk-inspired adiabatic algorithm for graph isomorphism
- Period Finding with Adiabatic Quantum Computation
- Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise
- Solving rescheduling problems in heterogeneous urban railway networks using hybrid quantum-classical approach
- Simon's algorithm in the NISQ cloud