Simon's problem
Problema de Simon
- Date
- 1994 · confidence high
- Place
- Montreal, Quebec, Canada
- Credited to
- Daniel R. Simon
- Field
- Knowledge & symbols
What was discovered
Problem formulated by Daniel R. Simon proving an exponential separation between quantum and classical computation in the query model; its quantum algorithm directly inspired Shor's algorithm.
What it led to
- Direct inspiration for Shor's algorithm
- Boost to quantum complexity theory
- Pioneering example of provable quantum advantage