QC — Simon’s algorithm

Say, our measurement is 110.With this measure, the superposition of the first register becomes:Time to apply 3 Hadamard gates again..The Hadamard operation is defined as:where ⟨x, z⟩ is the bitwise addition modulo 2 and ⊕ is similar to exclusive or..x1 · z1 is simply a bitwise multiplication.Below, we demonstrate how the first qubit is transformed under a Hadamard gate.Notice that some of the sign of the amplitude has changed due toFor example,We repeat the gates two more times and getSourceThe superposition is (before applying the Hadamard gates above)It can be written asIf we take a measurement after the Hadamard gates, our measured z will fulfill the relation below (proof later).where zi is the corresponding qubit of z..Our measurements will produce one of the following values :The measurement |000⟩ gives us no useful information in solving the problem but the last three measurements produce three equations with three unknowns.Therefore it can be solved and the solution for a is either 011 or 000..We know f(x) = f(x+0) is not the solution we are looking for..Therefore a = 011.Here is the quantum circuit we get:Let’s work out the Math a little bit more..After the Oracle function, the two register becomes:Next, we measure the second register and the first register becomes:Because it is from another source, in the proof below, y is actually the z before and z is actually x0..Next..we apply Hadamard gates with the result defined as:Here is the result applied to the first register.Consider the case where a · y = 1, it turns out this is a destructive interference which cancels each other out..The calculation indicates that there is zero chance for measuring a · y = 1.Since a · y = 1 or 0..So a · y = 0.And the probability of each measurement equals the square of the amplitude above, i.e.With enough measurements, we can get n linear equations and solve the value of a below since measurement only occur when a · y = 0.NextThis is the final algorithm before we discuss one of the most famous quantum algorithm, Shor’s algorithm..Stay tuned.. More details

Leave a Reply