Simon's problem asks for the hidden string promised by exactly when . It is the hidden subgroup problem on with hidden subgroup .
Simon's algorithm prepares hidden-subgroup coset states, applies the quantum Fourier transform over , and samples vectors satisfying over . Repeated samples and Gaussian elimination recover with oracle queries and polynomial computation.
Articles by others on the same topic
Simon's problem, often referred to in the context of computer science and quantum computing, specifically relates to a problem introduced by computer scientist Daniel Simon in 1994. The problem is a demonstration of the power of quantum computation over classical computation and serves as a foundational example illustrating how quantum algorithms can solve certain problems more efficiently than any classical algorithm.