Quantum Algorithms Database
Simon's Algorithm
Finds a hidden pattern (period) in a function exponentially faster than classical methods, directly inspiring Shor's Algorithm.
Year
1994
Inventor(s)
Daniel Simon
Speedup Type
Exponential Speedup
Difficulty
★★★★☆
Overview
Simon's algorithm finds a hidden bit string s in a function that is either one-to-one or two-to-one, where two inputs give the same output exactly when they differ by s. A classical computer, even a randomized one, needs about 2 to the n divided by 2 queries to find s, because it has to wait for two inputs to collide. A quantum computer needs only about n queries, which is an exponential separation that survives randomization.
That last point is what makes the algorithm historically important. It was the first problem on which quantum computers were shown to be exponentially faster than classical probabilistic computers, and it served as the direct inspiration for Shor's factoring algorithm.
The problem it solves
Given a function with a hidden 'XOR-periodicity,' find the hidden period.
History and background
Daniel Simon, then at the University of Montreal, wrote the paper in 1994 after a related submission to a conference was initially rejected. It was published at the IEEE Symposium on Foundations of Computer Science that year, in the same session as Shor's paper. Shor has said that Simon's idea of finding a hidden period with a Fourier transform over the group of bit strings led him to the period-finding approach for factoring.
Later work showed that Simon's algorithm is not only a theoretical curiosity. In 2010 and 2012, Kuwakado and Morii showed that it breaks the three-round Feistel construction and the Even-Mansour cipher when an attacker can query the cipher in superposition. In 2016, Kaplan, Leurent, Leverrier, and Naya-Plasencia extended the idea to attacks on several symmetric-key modes of operation, again assuming superposition queries.
How it works
Uses superposition and the structure of the problem to extract the hidden period using only a linear number of quantum queries, versus an exponential number classically.
The function f maps n-bit strings to n-bit strings with the property that f of x equals f of y if and only if y is x or x XOR s. Finding s classically requires finding a collision, which by the birthday paradox takes about the square root of 2 to the n queries.
The quantum circuit prepares a superposition of all inputs and computes f into a second register. Measuring the second register collapses the first register into an equal superposition of two inputs, x and x XOR s, for some random x. This state is not directly useful, because measuring it just gives x or x XOR s at random. But a Hadamard transform on that state interferes the two terms so that only strings y satisfying y dot s equal to 0 modulo 2 survive.
Each run therefore gives a random string y orthogonal to s. After about n minus 1 such strings, which are linearly independent with high probability, solving a system of linear equations modulo 2 recovers s. The quantum computer supplies the equations, and a classical computer solves them.
Step by step
- Prepare two registers of n qubits each, both in the state 0.
- Apply Hadamard gates to the first register to create an equal superposition of all 2 to the n inputs.
- Apply the oracle for f, which writes f of x into the second register.
- Measure the second register. This collapses the first register to a superposition of two inputs, x and x XOR s.
- Apply Hadamard gates to the first register and measure it, obtaining a string y with the property that y dot s is 0 modulo 2.
- Repeat the process about n times to collect n minus 1 independent strings y.
- Solve the linear system y dot s = 0 modulo 2 by Gaussian elimination to find s. If s is not the zero string, test it by checking that f of 0 equals f of s.
A worked example
Let n = 3 and s = 110. Then f gives equal outputs for pairs such as 000 and 110, 001 and 111, 010 and 100, and 011 and 101. Suppose the second-register measurement leaves the first register in the superposition of 001 and 111. A Hadamard transform and measurement then returns a string y with y dot 110 equal to 0 modulo 2, such as 000, 001, 110, or 111, each with equal probability.
Suppose the runs produce y = 001 and y = 110. The first gives the equation s3 = 0, and the second gives s1 plus s2 = 0 modulo 2, so s1 = s2. The nonzero solution is s = 110. Classically, you would have to query f on average several times before finding a collision.
Complexity and resources
| Item | Detail |
|---|---|
| Quantum queries | O(n), about n minus 1 successful runs |
| Classical queries | Omega of 2 to the n over 2, even for randomized algorithms |
| Classical post-processing | O(n cubed) for Gaussian elimination over the field with two elements |
| Qubits | 2n |
| Error | Exponentially small failure probability after O(n) repetitions |
What hardware it needs
- 2n qubits plus the oracle circuit. For small n it runs on current devices.
- A fault-tolerant implementation for large n, because the oracle must preserve coherence.
Applications
- Cryptanalysis of some symmetric constructions in the superposition-query model, such as three-round Feistel networks, Even-Mansour, and some message authentication modes.
- Teaching exponential separations between quantum and randomized classical computation.
- Serving as a building block in the hidden subgroup problem framework.
Limitations and caveats
- The structure of the function is highly specific, and real ciphers rarely give attackers superposition access to the encryption oracle.
- Superposition queries to a real cipher are not possible when it runs on classical hardware, so these attacks apply to idealized models.
- The oracle cost is not counted in the query model.
Common misconceptions
- It does not break AES or typical encryption used on the internet, because attackers cannot query them in superposition.
- It is not the same as Shor's algorithm. Simon's works over bit strings with XOR, while Shor's works over integers with modular arithmetic.
How it compares
- Deutsch-Jozsa and Bernstein-Vazirani show advantages against deterministic algorithms, while Simon's shows an advantage against randomized ones.
- Shor's algorithm generalizes the same strategy to the cyclic group of integers modulo N.
- The hidden subgroup framework places both as special cases of finding a hidden subgroup of an abelian group.
Real-world impact
Primarily of theoretical importance — Simon's problem directly inspired Peter Shor's approach to factoring, making it a key stepping stone in quantum algorithm history.
Why it matters
Simon's algorithm demonstrated that exponential quantum speedups can survive randomization, which was the decisive step toward believing in quantum advantage. Without it, Shor's algorithm might not have been discovered.
It also gave cryptographers an early warning. The attacks on Feistel and Even-Mansour constructions show that quantum attackers with superposition access are a different and stronger threat model, and the community now designs symmetric schemes with that model in mind.
Frequently asked questions
What problem does Simon's algorithm solve?
It finds a hidden bit string s such that f of x equals f of y exactly when x and y are equal or differ by s.
Why is Simon's algorithm important?
It was the first quantum algorithm shown to be exponentially faster than any randomized classical algorithm, and it inspired Shor's factoring algorithm.
How many queries does it need?
About n queries on a quantum computer, versus about 2 to the n over 2 on a classical one.
Can Simon's algorithm break real encryption?
Only in idealized models where an attacker can query a cipher in quantum superposition. It has no effect on standard internet encryption.
What is the role of the classical computer?
It solves the system of linear equations modulo 2 that the quantum runs produce, using Gaussian elimination.
Keep learning
- Related algorithm: Bernstein-Vazirani Algorithm
- Related algorithm: Deutsch-Jozsa Algorithm
- Related algorithm: Shor's Algorithm
- Related algorithm: Quantum Fourier Transform (QFT)
This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.