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
★★★★☆
The Problem
Given a function with a hidden 'XOR-periodicity,' find the hidden period.
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.
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.