Projects Gallery

Project Details:

Simon's Algorithm
Actions:

Simon's algorithm was the first discovered algorithm to exhibit an exponential speed-up when compared with the fastest classical algorithm. It also served as an inspiration to Shor’s well-known factoring algorithm.

Simon's algorithm assumes the existence of an unknown function from n-bit strings to n-bit 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^(n-1)  + 1 queries may be required to determine the type of Oracle, assuming the first 2^(n-1) 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 one-to-one or two-to-one 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 one-to-one otherwise is two-to-one.

On a quantum computer, each time we make a measurement in the n input qubits we determine a n-bit 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 one-to-one 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.

 Circuit Name Qubits Modified One to One Oracle 6 22-06-11 08:42 Simon's Algorithm One to One 6 22-07-13 14:57 Simon's Algorithm Two to One 6 22-07-13 14:58 Two to One Oracle 6 22-06-11 08:42