Simon's Algorithm

Simon's Algorithm

Simon's algorithm was the first quantum algorithm to demonstrate an exponential separation between quantum and classical query complexity, and it directly inspired Shor's factoring algorithm. It solves the following hidden-structure problem: given a function f from n-bit strings to n-bit strings that is guaranteed to be two-to-one with a hidden period s, meaning f(x) = f(y) exactly when y equals x or x XOR s, find the secret string s. Classically this requires on the order of 2^(n/2) queries because one must search for a colliding pair, but Simon's algorithm needs only about n quantum queries. This Cirq example implements the circuit: it prepares a superposition over all inputs, queries the oracle to entangle inputs with their function values, and applies Hadamard transforms so that each measurement yields a random bit string orthogonal to the hidden period s. Repeating this a linear number of times produces enough independent linear constraints to solve for s by Gaussian elimination on a classical computer. The script builds the oracle for a planted period, runs the quantum sampling circuit, collects the measurement results, and recovers s, providing a clear demonstration of the quantum query speedup that paved the way for Shor's algorithm.

Run it

pip install -r requirements.txt
python simon_algorithm.py

Source and license

Imported from examples/simon_algorithm.py in quantumlib/Cirq at v1.6.1, under the Apache License 2.0. Original authors: The Cirq Developers. The upstream LICENSE is included alongside this example.