Simon's algorithm was the first discovered algorithm to exhibit an exponential speedup when compared with the fastest classical algorithm. It also served as an inspiration to Shor’s wellknown factoring algorithm.
Simon's algorithm assumes the existence of an unknown function from nbit strings to nbit strings that either maps each unique input to a unique output or maps exactly two distinct inputs to one unique output. The problem that needs to be solved is to determine which kind of function it is.
We will refer to this function as an Oracle since the function is unknown. In the classical case, naively, we can solve the problem by making repeated queries. In the worst situation, 2^(n1) + 1 queries may be required to determine the type of Oracle, assuming the first 2^(n1) queries to return all different results. There are slightly faster classical approaches to the problem, but even those scale exponentially with n.
Mathematically the condition above implies that the function is either onetoone or twotoone and that given any two values x, y such that f(x) = f(y) it means there is a unique n bit string s such that x + y = s for all pairs of x and y that are mapped to same output value. Here by addition, we mean bitwise addition. If 's' is zero then the function is onetoone otherwise is twotoone.
On a quantum computer, each time we make a measurement in the n input qubits we determine a nbit string z for which s * z = 0. By repeating the measurement approximately 'n' times, until we obtain a system on 'n' independent equations with 'n' unknowns, we can subsequently solve and determine 's'.
Considering the circuit in our example composed of three input qubits and a three ancilla qubits our simulator indicates that for a circuit using a onetoone Oracle we observe that we can measure any possible result. The only possible value for 'b' to satisfy this condition is 0. For a two to one Oracle, after extracting 3 independent equations and solving its we find the solution to be 110 or 011 depending on bit ordering we prefer to use.
