Simon's Algorithm

Part of Womanium Quantum + AI 2024 program

Definition

Simon's algorithm provides an exponential speed-up compared to known classical solutions to the same problem. The problem that algorithm solves has practical uses in the analysis of certain crypto-systems and inspired many other algorithms such as Shor's factoring algorithm.

Problem

The problem defines a function $f$ as:

f : {0, 1}^{n} \to {0, 1}^{n}

With the promise that:

\begin{matrix} f (x) = f (x \oplus s), s \in {0, 1}^{n} \\ o r \\ f (x) = f (y) \Leftrightarrow (x \oplus y) \in {0^{n}, s} \end{matrix}

The goal of the problem is to determine the secret string $s$ , in the least number of queries of $f$ .

Bitwise XOR

The symbol $\oplus$ represents the bitwise XOR operation.
It can also be said that it is a bitwise addition modulo 2.

The problem can also be defined as determining whether a function is two-to-one or one-to-one, in which case we need to determine whether $s$ is the zero string $0^{n}$ or not.

Classical Solution

Classically we would have either a deterministic or a probabilistic solution, where our goal is to find $x_{1}$ and $x_{2}$ such that $f (x_{1}) = f (x_{2})$ , then we can get $s$ , by applying bitwise xor on $x_{1}$ and $x_{2}$ .

s = x_{1} \oplus x_{2}

Deterministically, we would need to cover a large area of the search space to be able to tell whether such strings exist or not, this would usually require $2^{n - 1} + 1$ queries (one over half).

Probabilistically, we would cover a "large enough" area to solve the problem with high certainty, but less than 100% certainty.

The best classical solution has a complexity of $O (2^{n / 2})$ .

Simon's Algorithm

The proposed algorithm has two parts, a classical part and a quantum part. The quantum part works with a complexity of $O (n)$ , to obtain n-1 linearly independent equations. Then we solve the linear system classically. Note that the string $0^{n}$ will always be a solution but we need to determine if it's the only solution or not.

SA.png|600

We define the oracle $U_{f}$ as the oracle the implements the function $f$ such that

U_{f} (| x ⟩ | y ⟩) = | x ⟩ | f (x) \oplus y ⟩

We also define

N = 2^{n}

Let's start by applying the quantum part of the algorithm.

\begin{aligned} {| 0 ⟩}^{\otimes n} {| 0 ⟩}^{\otimes n} & \overset{H^{\otimes n} I^{\otimes n}}{\to} \frac{1}{\sqrt{N}} \sum_{x \in {0, 1}^{n}} | x ⟩ {| 0 ⟩}^{\otimes n} \\ \overset{U_{f}}{\to} \frac{1}{\sqrt{N}} \sum_{x \in {0, 1}^{n}} | x ⟩ {| f (x) \oplus 0 ⟩}^{\otimes n} \\ = \frac{1}{\sqrt{N}} \sum_{x \in {0, 1}^{n}} | x ⟩ {| f (x) ⟩}^{\otimes n} \end{aligned}

Now we measure the second half of the qubits, the one that we stored the oracle result in. We will observe a random result to one of the inputs $x$ .

Let's assume we observe the result of $f (z)$ for some $z \in {0, 1}^{n}$ . Now we study the result and what we know about it based on whether the function is two-to-one or one-to-one.

Two-To-One ( $s \neq 0^{n}$ )

If the function is two-to-one then we know that two states could've resulted in the same outcome which are the state $z$ and $z \oplus s$ , therefore we can represent the state of the system as:

\frac{1}{\sqrt{2}} (| z ⟩ + | z \oplus s ⟩)

Then after applying the Hadamard gate the system state will change to:

\begin{array}{r} \frac{1}{\sqrt{2}} (| z ⟩ + | z \oplus s ⟩) \overset{H^{\otimes n}}{\to} \frac{1}{\sqrt{2 N}} \sum_{y \in {0, 1}^{n}} ((- 1)^{z \cdot y} + (- 1)^{(z \oplus s) \cdot y}) | y ⟩ \end{array}

We know that $z \cdot y = (z \oplus s) \cdot y$ , because if $z \cdot y \neq (z \oplus s) \cdot y$ then $(- 1)^{z \cdot y} + (- 1)^{(z \oplus s) \cdot y} = 0$ , this implies that all states would have a measurement probability of 0% which is impossible.

Using $z \cdot y = (z \oplus s) \cdot y$ we get:

\begin{aligned} z \cdot y & = (z \oplus s) \cdot y \\ z \cdot y & = (z \cdot y) \oplus (s \cdot y) \\ s \cdot y & = 0 \end{aligned}

Now we apply that as such

\begin{aligned} (- 1)^{z \cdot y} + (- 1)^{(z \oplus s) \cdot y} & = (- 1)^{z \cdot y} + (- 1)^{(z \cdot y) \oplus (s \cdot y)} \\ = (- 1)^{z \cdot y} + (- 1)^{z \cdot y} \\ = 2 (- 1)^{z \cdot y} \end{aligned}

Let's plug that back in the system state

\begin{aligned} ∴ & \frac{1}{\sqrt{2 N}} \sum_{\begin{array}{c} y \in {0, 1}^{n} \\ s \cdot y = 0 \end{array}} ((- 1)^{z \cdot y} + (- 1)^{(z \oplus s) \cdot y}) | y ⟩ \\ = & \frac{1}{\sqrt{2 N}} \sum_{\begin{array}{c} y \in {0, 1}^{n} \\ s \cdot y = 0 \end{array}} 2 (- 1)^{z \cdot y} | y ⟩ \\ = & \frac{2}{\sqrt{2 N}} \sum_{\begin{array}{c} y \in {0, 1}^{n} \\ s \cdot y = 0 \end{array}} (- 1)^{z \cdot y} | y ⟩ \end{aligned}

Therefore, all strings that satisfy $s \cdot y = 0$ will have an equal probability of measurement. The probability of measuring a particular string $y$ that satisfies $s \cdot y = 0$ is

{(\frac{2}{\sqrt{2 N}})}^{2} = \frac{4}{2 * 2^{n}} = \frac{1}{2^{n - 1}}

But the probability of measuring any string $y$ that satisfies the condition is 1.

One-To-One ( $s = 0^{n}$ )

If the function $f$ is a one-to-one function it implies that the measured result is the outcome of just one of the states, which will not change our representation of the system.

Now we apply the Hadamard gate

\begin{array}{r} | z ⟩ \overset{H^{\otimes n}}{\to} \frac{1}{\sqrt{N}} \sum_{y \in {0, 1}^{n}} (- 1)^{z \cdot y} | y ⟩ \end{array}

This means that all states have an equal probability of being measured.

< Prev | Next: Numbers and Adders >

Definition

Problem

Classical Solution

Simon's Algorithm

Two-To-One (s≠0n)

One-To-One (s=0n)

Two-To-One ( $s \neq 0^{n}$ )

One-To-One ( $s = 0^{n}$ )