Simon's Period Finding on a Quantum Annealer
Reece Robertson, Emery Doucet, Zakaria Mzaouali, Krzysztof Domino, Bartłomiej Gardas, Sebastian Deffner · 2025
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.