Complexity of Simon's problem in classical sense

Hans Zantema

Simon's problem is a standard example of a problem that is exponential in classical sense, while it admits a polynomial solution in quantum computing. It is about a function $f$ fo…