Quantum Algo: Simon Algorithm

How to find the period of a function?

11 min readJul 9, 2021

--

In the previous article, Bernstein-Vazirani Algorithm shows us a linear speedup in the query model to find the secret string.

In this article, we discuss about Simon Algorithm which gives us an exponential speedup in the query model to find the patterns in the functions.

The setup:

In Simon’s problem we are given a function from n-bit strings to n-bit strings and also given the promise as shown in below fig 1.

Here a is a secret string and ⊕ denotes bitwise addition modulo 2. In other words, the values of f repeat themselves in some pattern and the pattern is determined by a. we call a the period of f. The goal of the Simon Algorithm is to determine a if f is two-to-one. we discuss about this with the below example.

Example: Let’s consider n = 3, a = 101. Then we are going to have the following requirements on f as shown in below fig 2:

From the above example, notice that if a = (n times zero) as shown in below fig3, then the function is one-to-one. Otherwise the function is two-to-one (meaning that there are exactly two inputs produce the same output).

Classical solution:

Consider the function as shown in below fig4, with the secret string a = 110 defined by the table of values as shown in below fig5.

The above mentioned table as shown in fig5 follows the Simon’s property as mentioned in the above fig1.

Suppose we first send the input x1 = 010 and then the input x2 = 100. As can be seen in the table, both inputs produce the same output.

we can verify the secret string a satisfies a = x1 ⊕ x2 (x1, x2 be matching inputs) from fig1 and fig5. which can be seen as x1 = x2 ⊕ a then rewriting as x1 ⊕ x2 = x2 ⊕ a ⊕ x2 which gives us secret string a. (x2 ⊕ x2 = 0 and a ⊕ 0 = a for more idea on XOR).

It’s not hard to see that this always the case i.e; we can always find a by finding a “collision pair” or “matching pair” if inputs x and y.

We now know that we can compute a there by solving Simon’s problem, by finding a collision pair. The question is

How many queries does it take to find a collision pair?

one thing we could do is just query every value of the function f .Then we could look through and surely find a matching pair.

How many queries does this take?

Well, f is a function on bit strings of length n, there are 2 power n (2^n) total such bit strings. Thus we can solve Simon’s problem classically at most 2 power n (2^n) queries as shown in fig6.

Can we do better than this?

Yes, there is a Quantum Algorithm that solves with O(n) queries, an exponential improvement!

Well the proof is Simon Algorithm. We will check this claim.

Simon Algorithm:

from the fig1, we have two inputs x and y with integers being 0, 1 repeating for n times which can be shown in the below fig7

where |x, y⟩ goes to |x, y ⊕ f(x)⟩, Uf is again its own inverse.

Note: Here we are not considering phase kick-back according to Simon’s Algorithm, we are using Born rule.

With the above considerations the circuit becomes as shown in below fig8

From above fig8, we see a familiar pattern. There are two multi-dimensional registers, the upper (which we consider as A register or the data register), and the lower (which we consider as B register or the target register).

This is almost identical to the circuits of our recent algorithms, with the following changes:

The target channel is “hatched,” reflecting that it has n component lines rather than one.
We are sending “n qubit |0⟩” as shown in fig8 into the target register instead of a |1⟩.
We seem to be doing a measurement of both output registers rather than ignoring the target.

The data register in the circuit is identical in both logic and intent with the Deutsch-Jozsa and Bernstein-Vazirani circuits. It sets up quantum parallelism by producing a perfectly mixed entangled state, enabling the oracle to act on f(x) for all possible x, simultaneously.

Analysis:

We discuss the behavior of the waveform at the particular intervals as shown in the above fig9.

sending n-qubit |0⟩ to both the registers i.e: data register and target register as shown in the fig9 and the |ψ0⟩ is represented as shown in the below fig10.

We can see the output state of this Hadamard operator as the nth order x-basis. It reminds us that not only do Hadamard gates provide quantum parallelism but double as a Z ↔ X basis conversion operator.

After the setting |y⟩ = |0⟩ and sending the inputs through the Oracle Uf which becomes |y ⊕ f(x)⟩ to |f(x)⟩ as shown in below fig12.

fig12: After applying the Oracle function f

At the state |ψ3⟩, measure the second register. A certain value of f(x) will be observed. Because of the setting of the problem as shown in fig1, the observed value f(x) could correspond to two possible inputs: x and y=x ⊕ a. Therefore the first register becomes as shown in below fig13.

Note: Measurements on Register A and Register B commute. Therefore, order of measurements doesn’t matter.

where we omitted the second register since it has been measured.

Continuing under the assumption that we measure an one value of f(x) at the B register output, thus collapsing both registers, we go on to work with the resulting superposition |ψ3⟩ in the A register. Let’s track its progress as we apply the Hadamard gate to it as shown in below fig 14.

The Hadamard on the individual terms and simplify the expression as shown in below fig15.

Keeping these simplified expression back to |ψ4⟩ as shown in below fig16.

The expression in the parentheses is seen to be as shown in below fig17.

so we can omit all those 0 terms which correspond to z · a = 1 (mod 2), leaving the |ψ4⟩ as shown in the below fig18.

Note that the sum is now over only 2^(n-1) , or exactly half, of the original 2^n after omitting zero terms.

First run analysis:

with the obtained condition z · a = 0 (mod 2), we can say that all of the vectors in the final A register superposition are orthogonal to a(because of dot product being zero). so we can now measure that mixed state and get some information.

We don’t know which z among the 2^(n-1) z’s we will measure -that depends on the collapse, and they’re all equally likely. However, we just showed that they’re all orthogonal to a.

In a single application of the circuit “O(1)”, we have found our first z, with z ⊥ a. We would like to find n − 1 such vectors, all linearly independent as a set, so we anticipate sampling the circuit several more times.

Producing “n−1” Linearly Independent Vectors:

What we showed is that we can find a vector orthogonal to a in a single application of our circuit. We need, however, to find not one, but n − 1, linearly-independent vectors, z, that are orthogonal to a.

Does repeating the process n − 1 times do the trick?

Doing so would certainly manufacture as shown in below fig19.

however, that’s not quite good enough. Some of the Zk might be a linear combination of the others or even be repeats. For this to work, we’d need each one to not only be orthogonal to a, but linearly independent of all the others as well. This can be achieved by Gaussian Elimination.

Gaussian Elimination and Back Substitution:

Conveniently, both remaining classical tasks are addressed by an age old and well documented technique in linear algebra for solving systems of linear equations called “Gaussian elimination with back substitution”. Consider, a system of linear equations as shown in below example 1.

the above system of linear equations are symbolized by the matrix of its constant coefficients, as shown in below example 1.1.

example 1.1: matrix representation of the above linear equations

there’s no requirement that the system shall have the same number of equations as unknowns; the fewer equations, the less you will know about the solutions.

Gaussian elimination, which produces a matrix with 0's in the lower left triangle,

In augmented form, the example 1.1 becomes as shown in below example 1.2

row echelon form, in which everything below the “diagonal” is 0, as in below example 1.3.

reduced row echelon form, which is echelon form with the additional requirement that the first non-zero element in each row be 1, as shown in below example 1.4.

Restoring the transformed matrix equation as shown in below example 1.5.

example 1.5: Restoring the transformed matrix equation

which can be solved immediately to give z = -4/5

back substitution, which uses that matrix to solve the system of equations as best we can, meaning that if there are not enough equations, we might only get relations between unknowns, rather than unique numbers.

back-substituting to obtain gives y = 4 (which actually follows trivially in this example) and then again back-substituting in x + y + z = 3 to find x = -1/5

classical part:

Initialize a set W to the empty set. W will eventually contain a growing vectors. Use a classical algorithm(Gaussian Elimination and Back Substitution) to determine whether or not z is linearly dependent on the vectors in W. If it is independent, add that particular z to W. which solves the systems of n equations for a.

classically O(n²) + quantumly O(n) = O(n³).

implement Simon’s Algorithm:

we will generate an Oracle(Uf) for function f(x) and it’s period a, using cirq and qiskit. Using cirq will define Gaussian elimination and back substitution where as using qiskit calculating system of equations by individually.

implement Simon Algorithm using Cirq:

import the required modules as shown in below cirq1.