The problem is set in the model of decision tree complexity or query complexity and was conceived by Daniel Simon in 1994. Simon exhibited a quantum algorithm that solves Simon's problem exponentially faster and with exponentially fewer queries than the best probabilistic (or deterministic) classical algorithm. In particular, Simon's algorithm uses a linear number of queries and any classical probabilistic algorithm must use an exponential number of queries.
Because this problem assumes the existence of a highly-structured "black box" oracle to achieve its speedup, this problem has little practical value. However, without such an oracle, exponential speedups cannot easily be proven, since this would prove that P is different from PSPACE.
The following function is an example of a function that satisfies the required property for :
In this case, (i.e. the solution). Every output of occurs twice, and the two input strings corresponding to any one given output have bitwise XOR equal to .
For example, the input strings and are both mapped (by ) to the same output string . That is, and . Applying XOR to 010 and 100 obtains 110, that is
can also be verified using input strings 001 and 111 that are both mapped (by f) to the same output string 010. Applying XOR to 001 and 111 obtains 110, that is . This gives the same solution as before.
In this example the function f is indeed a two-to-one function where .
Intuitively, this is a hard problem to solve in a "classical" way, even if one uses randomness and accepts a small probability of error. The intuition behind the hardness is reasonably simple: if you want to solve the problem classically, you need to find two different inputs and for which . There is not necessarily any structure in the function that would help us to find two such inputs: more specifically, we can discover something about (or what it does) only when, for two different inputs, we obtain the same output. In any case, we would need to guess different inputs before being likely to find a pair on which takes the same output, as per the birthday problem. Since, classically to find s with a 100% certainty it would require checking up to inputs, Simon's problem seeks to find s using fewer queries than this classical method.
First, the algorithm starts with two registers, initialized to . Then, we apply the Hadamard transform to the first register, which gives the state
Query the oracle to get the state
Apply another Hadamard transform to the first register. This will produce the state
Finally, we measure the first register (the algorithm also works if the second register is measured before the first, but this is unnecessary). The probability of measuring a state is
This is due to the fact that taking the magnitude of this vector and squaring it sums up all the probabilities of all the possible measurements of the second register that must have the first register as . There are two cases for our measurement:
and is one-to-one.
and is two-to-one.
For the first case, since
since in this case, is one-to-one, implying that the range of is , meaning that the summation is over every basis vector. For the second case, note that there exist two strings, and , such that , where . Thus,
Furthermore, since , , and so
This expression is now easy to evaluate. Recall that we are measuring . When , then this expression will evaluate to , and when , then this expression will be .
Thus, both when and when , our measured satisfies .
Consider the simplest instance of the algorithm, with . In this case evolving the input state through an Hadamard gate and the oracle results in the state (up to renormalization):
If , that is, , then measuring the second register always gives the outcome , and always results in the first register collapsing to the state (up to renormalization):
Thus applying an Hadamard and measuring the first register always gives the outcome . On the other hand, if is one-to-one, that is, , then measuring the first register after the second Hadamard can result in both and , with equal probability.
We recover from the measurement outcomes by looking at whether we measured always , in which case , or we measured both and with equal probability, in which case we infer that . This scheme will fail if but we nonetheless always found the outcome , but the probability of this event is with the number of performed measurements, and can thus be made exponentially small by increasing the statistics.
Consider now the case with . The initial part of the algorithm results in the state (up to renormalization):
If , meaning is injective, then finding on the second register always collapses the first register to , for all . In other words, applying Hadamard gates and measuring the first register the four outcomes are thus found with equal probability.
Suppose on the other hand , for example, . Then measuring on the second register collapses the first register to the state . And more generally, measuring gives on the first register. Applying Hadamad gates and measuring on the first register can thus result in the outcomes and with equal probabilities.
Similar reasoning applies to the other cases: if then the possible outcomes are and , while if the possible outcomes are and , compatibly with the rule discussed in the general case.
To recover we thus only need to distinguish between these four cases, collecting enough statistics to ensure that the probability of mistaking one outcome probability distribution for another is sufficiently small.
Simon's algorithm requires queries to the black box, whereas a classical algorithm would need at least queries. It is also known that Simon's algorithm is optimal in the sense that any quantum algorithm to solve this problem requires queries.