Simon's Period Finding on a Quantum Annealer

2025/04/15 by Reece Robertson, Robertson, Reece, Emery Doucet +9 · 5 citations
Computer Science · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.2504.10771

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.

Citations

• VeloxQ: A Fast and Efficient QUBO Solver
• Introducing UNIQuE: The Unconventional Noiseless Intermediate Quantum Emulator
• A compact QUBO encoding of computational logic formulae demonstrated on cryptography constructions
• Simon's algorithm in the NISQ cloud
• On the Baltimore Light RailLink into the quantum future
• Solving rescheduling problems in heterogeneous urban railway networks using hybrid quantum-classical approach
• Effects of noise on performance of Bernstein-Vazirani algorithm
• Quantum bridge analytics I: a tutorial on formulating and using QUBO models
• Quantum Annealing for Prime Factorization
• High-fidelity adiabatic quantum computation using the intrinsic Hamiltonian of a spin system: Application to the experimental factorization of 291311
• Adiabatic Quantum Computing
• Prime factorization using quantum annealing and computational algebraic geometry
• A quantum-walk-inspired adiabatic algorithm for graph isomorphism
• Period Finding with Adiabatic Quantum Computation
• Graph isomorphism and adiabatic quantum computing
• Quantum Computer Science
• Quantum Algorithms and the Fourier Transform
• Algorithms for quantum computation: discrete logarithms and factoring

Cited by

• Thermodynamic significance of QUBO encoding on quantum annealers
• Fault-Tolerant Error Detection Above Break-Even for Multi-Qubit Gates

Related

• Experimental Realization of a One-way Quantum Computer Algorithm Solving Simon's Problem
• Noisy Simon Period Finding
• More period finding with adiabatic quantum computation
• Quantum Period Finding is Compression Robust
• Benchmarks for quantum computers from Shor's algorithm