⚛️ quantum physics

Simon's Period Finding on a Quantum Annealer

This paper presents an adiabatic implementation of Simon's period-finding algorithm on D-Wave quantum annealers that overcomes the algorithm's traditional fragility by requiring only a constant number of samples, successfully solving problems with up to 298 qubits while comparing its runtime against classical approaches.

Original authors: Reece Robertson, Emery Doucet, Zakaria Mzaouali, Krzysztof Domino, Bartłomiej Gardas, Sebastian Deffner

Published 2026-10-27

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Reece Robertson, Emery Doucet, Zakaria Mzaouali, Krzysztof Domino, Bartłomiej Gardas, Sebastian Deffner

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the quest to understand how the universe computes, scientists have long looked to the strange rules of quantum mechanics for answers. Unlike the computers we use every day, which process information as a series of definite on or off switches, quantum machines can exist in a state of being both on and off at the same time. This peculiar ability allows them to explore many possibilities simultaneously, offering the theoretical promise of solving certain problems with incredible speed. Among the earliest and most famous of these quantum tricks is a method for finding hidden patterns, a task that is vital for breaking codes and securing digital information. For decades, the hope was that these quantum machines could outpace the best classical computers by finding these hidden patterns exponentially faster. However, the real world is messy. The delicate quantum states required for these calculations are easily disrupted by noise and interference, causing the machines to fail long before they can solve large, useful problems.

A team of researchers has now taken a different path to tackle this problem, moving away from the standard circuit-based approach that has struggled with noise. Instead, they turned to a type of quantum machine known as a quantum annealer, which works by slowly cooling a system down to its most stable energy state to find a solution. The researchers applied this method to a classic pattern-finding challenge, successfully running the experiment on hardware capable of handling nearly three hundred quantum bits. Their work demonstrates that this alternative approach is more resilient to the noise that plagues other quantum computers, allowing them to solve problems involving up to 298 qubits. Yet, despite this robustness, the study reveals a sobering reality: while the quantum machine is more durable, it is not yet faster than the best classical methods available today. The quantum approach still requires exponentially more time to solve larger problems, suggesting that for now, traditional computers remain the superior tool for this specific task.

The challenge the team set out to solve is known as Simon's problem, a puzzle that asks a computer to find a hidden shift in a set of data. Imagine a machine that takes a long string of zeros and ones as input and produces a different string as output. In this specific puzzle, the machine is designed so that two different inputs always produce the exact same output, and the difference between those two inputs is a secret, hidden pattern. Finding this secret pattern is the goal. In a perfect, noise-free world, a quantum computer could find this pattern very quickly by sampling the machine's output just a few times. However, in the real world, the noise makes the machine's output unreliable. If the computer cannot trust its own readings, it cannot distinguish the correct pattern from random errors. This fragility has limited the size of problems that gate-based quantum computers can solve to fewer than fifty qubits, a threshold far too small for practical applications.

To bypass this limitation, the researchers reformulated the problem to fit the specific strengths of a quantum annealer. Rather than trying to extract a single piece of information from a noisy measurement, they designed the problem so that the machine naturally settles into a state where two specific inputs are revealed together. They achieved this by adding a special penalty system to the problem's setup. This penalty acts like a guide, encouraging the machine to ignore all the random noise and focus only on the two inputs that match each other. By doing this, the researchers created a scenario where the machine's most stable state contains the solution directly. They tested this method on D-Wave quantum annealers, which are physical devices containing thousands of tiny loops of wire that act as quantum bits. The team successfully ran their algorithm on problems ranging from very small sizes up to a massive 298 qubits, a scale that would be impossible for the standard gate-based quantum computers currently in existence.

The results of the experiment were a mix of success and limitation. On one hand, the quantum annealer proved to be remarkably robust. It managed to find the correct hidden patterns in problems involving up to 298 qubits, a significant leap forward in the size of problems that can be tackled on noisy hardware. The researchers found that by carefully tuning the penalty parameters, they could ensure the machine consistently found the two matching inputs needed to solve the puzzle. This success highlights a key advantage of the annealing approach: it does not require the complex, error-free operations that gate-based machines need, making it much more tolerant of the imperfections found in today's technology. However, when the researchers compared the time it took for their quantum machine to solve these problems against a classical computer, the quantum machine did not win. The classical computer, using a specialized search method, solved the problems much faster.

The study showed that while the quantum annealer could handle larger problems than its gate-based cousins, the time it took to find the solution grew exponentially as the problems got bigger. In contrast, the classical computer's time grew much more slowly, following a quadratic pattern that kept it ahead for the sizes tested. The researchers observed that for the largest problems they attempted, the quantum machine began to fail more often, unable to reliably find the solution within a reasonable timeframe. This finding suggests that while the quantum annealer offers a way to push the boundaries of what is physically possible on noisy hardware, it has not yet achieved the speed advantage that was originally promised by quantum theory. The work serves as a clear demonstration that in the current era of noisy quantum devices, classical algorithms still hold the crown for efficiency, even as quantum machines prove they can be more durable in the face of interference.

Ultimately, this research provides a realistic picture of where quantum computing stands today. It confirms that new approaches, like using annealers to find hidden patterns, can overcome some of the noise that has stalled progress in other areas. The ability to solve problems with nearly three hundred qubits is a tangible achievement that expands the frontier of what these machines can do. However, the study also makes it clear that durability alone is not enough to beat classical computers. The exponential growth in time required to solve larger problems means that the quantum advantage has not yet been realized for this type of task. The path forward will likely require further improvements in hardware and new strategies to reduce the time it takes for these machines to find their answers, but for now, the classical computer remains the faster and more reliable choice.

Technical Summary: Simon's Period Finding on a Quantum Annealer

Problem Statement
Simon's algorithm, a foundational quantum algorithm for finding the hidden period $s$ of a two-to-one function $f: \{0, 1\}^n \to \{0, 1\}^{n-1}$ , is historically significant for its potential exponential speedup over classical methods. However, the algorithm is notoriously fragile in Noisy Intermediate-Scale Quantum (NISQ) environments. Traditional gate-based implementations require fault-tolerant sampling of $O(n)$ linearly independent values to construct a system of equations solvable for $s$ . In the presence of noise, distinguishing valid samples from noise becomes difficult, and the classical post-processing required to solve the resulting noisy Boolean equation system often destroys any quantum advantage. Current gate-based implementations fail for problems exceeding approximately 50 qubits (or 10 qubits if swap gates are required).

Methodology
The authors propose an adiabatic formulation of Simon's algorithm executed on D-Wave quantum annealers. Instead of encoding the hidden subgroup property directly (which leads to a degenerate ground state containing all valid oracle evaluations), the authors reformulate the problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem.

Oracle Construction: They define a specific oracle where the $i$ -th output bit is the XOR of adjacent input bits ( $f(x)_i = x_i \oplus x_{i+1}$ ). This structure allows for a straightforward QUBO encoding using ancilla qubits to represent the AND operation required for XOR logic.
QUBO Formulation: The base QUBO (Equation 5) encodes the logic of the oracle. However, sampling from its degenerate ground state is equivalent to querying the oracle with a random input, offering no advantage over classical random guessing.
Penalty Modification: To isolate the solution, the authors introduce penalty parameters ( $p_i$ ) on the output qubits (Equation 6). This modification breaks the degeneracy of the ground state, isolating a specific pair of input states ( $z, z'$ ) that map to a single, fixed output.
Sampling Strategy: The goal of the annealing process is to sample both states from this isolated degenerate ground state pair. Finding these two inputs directly yields the hidden period $s = z \oplus z'$ , bypassing the need for linear algebra post-processing.
Hardware Implementation: The QUBO was embedded onto D-Wave Advantage 5.4 (Pegasus topology) and Advantage2 Prototype 2.6 (Zephyr topology). The problem structure allows for direct embedding without additional swap operations or ancillary qubits beyond those required for the logic.

Key Contributions

Adiabatic Reformulation: The paper presents a novel QUBO encoding of Simon's problem that shifts the computational burden from post-processing to the annealing process itself.
Noise Resilience: By avoiding the requirement to collect $O(n)$ linearly independent samples, the method reduces the information extraction burden on the quantum system, allowing the algorithm to function in noisy environments where gate-based versions fail.
Scalability Demonstration: The authors successfully implemented and solved Simon's problems with input registers up to $n=100$ (totaling 298 qubits including output and ancilla registers) on D-Wave hardware. This extends the solvable frontier for Simon's problem beyond the limits of current gate-based devices.

Results

Success Rates: The algorithm's success rate depends heavily on the calibration of penalty parameters. A "balanced" assignment of alternating signs for penalties ( $p_i = 2(-1)^{i+1}$ ) was found to be optimal, preventing the system from favoring one ground state over the other due to noise bias.
Scaling Behavior:
- For small problem sizes ( $n \leq 40$ ), the success rate per shot follows a Gaussian decay.
- For larger sizes ( $n > 40$ ), the success rate decays exponentially.
- Consequently, the expected runtime (number of shots required to sample the ground state pair twice) scales exponentially with problem size.
Comparison with Classical Solvers:
- The adiabatic approach was benchmarked against a classical tree-decomposition QUBO solver (D-Wave Ocean SDK) and a novel classical solver, VeloxQ.
- The classical solvers demonstrated quadratic asymptotic scaling in runtime.
- The quantum annealer's runtime scaled exponentially.
- In the tested range ( $n \in [2, 50]$ ), the classical solvers (particularly VeloxQ) consistently outperformed the D-Wave hardware, solving instances that the quantum annealer failed to solve (e.g., $n \geq 12$ ).

Significance and Claims
The paper claims that this adiabatic implementation represents an improvement over gate-based implementations in terms of noise tolerance, successfully solving problems with up to 298 qubits on quantum hardware. This pushes the practical limit of Simon's algorithm on current quantum devices significantly further than gate-based approaches.

However, the authors are modest regarding the computational advantage. They explicitly state that while the method is more robust to noise than the traditional circuit model, the asymptotic scaling of the adiabatic algorithm is exponential, whereas efficient classical algorithms scale quadratically. Therefore, in the current NISQ era, this approach does not yet provide a quantum speedup over classical methods for this specific problem. The work serves as a proof-of-concept that adiabatic quantum computing can handle structured hidden subgroup problems in noisy environments, but it corroborates prior findings that classical algorithms remain superior for solving these specific QUBO formulations at the current state of hardware technology. Future work suggested includes testing the algorithm with different hidden strings (more complex QUBOs) to verify if the performance trends hold.

Technical Summary: Simon's Period Finding on a Quantum Annealer

More like this