Simon's problem

Simon's problem is a computational problem in computational complexity theory and quantum computing that is proven to be solved exponentially faster on a quantum computer than on a classical one. It was conceived by Daniel R. Simon in 1994 and is set in the model of decision tree complexity or query complexity. A function is accessed as a black box and is promised to be either one-to-one or two-to-one, with two inputs giving the same value exactly when they differ by a fixed hidden string of bits; the task is to tell which case holds, or to find the hidden string, using the fewest evaluations of the function. Simon's quantum algorithm uses a linear number of queries where any classical probabilistic algorithm needs an exponential number, which yields an oracle separation between the classes BPP and BQP, and it served as the inspiration for Shor's algorithm. Because it assumes a highly structured oracle, the problem has little practical value of its own.