Skip to content

Simon's Algorithm

The Simon's algorithm [1] is one of the basic quantum algorithms that demonstrates an exponential speed-up over its classical counterpart, in the oracle complexity setting. The algorithm solves the so called Simon's problem:

  • Input: A function \(f: [0,1]^N \rightarrow [0,1]^N\).

  • Promise: There is a secret binary string \(s\) such that $$ f(x) = f(y) \iff x\oplus y \in {0, s}, \tag{1} $$ where \(\oplus\) is a bitwise xor operation.

  • Output: The secret string \(s\), using a minimal number of queries of \(f\).


Note that the condition on \(f\) implies that it is 2-to-1 if \(s \neq 0^N\), and 1-to-1 otherwise. Herefter we refer to a function \(f(x)\) that satisfies the condition in Eq. (1) as a "Simon's function".

Problem hardeness: The Simon's problem is hard to solve with a classical, deterministic or probabalistic, approaches. This can be understood as follows: determining \(s\) requries finding a collision \(f(x)=f(y)\), as \(s = x\oplus y\). What is the minimal number of calls for measuring a collision? If we take the deterministic approach, in the worst case we will need \(2^{N-1}\) calls. A probablistic approach, in the spirit of the one that solves the Birthday problem [2], has a slightly better scaling of \(O(2^{N/2})\) queries.

The quantum approach requires \(O(N)\) queries, thus, introducing an exponential speedup.

Next, we define the Simon's algorithm, which has a quantum part and a classical postprocess part. Then, we run the algorithm on two different examples of a Simon's function: one that can be defined with simple arithmetic, and another that has a shallow implementation. A mathematical explanation of the algorithm is provided at the end of this notebook.

Figure 1. The Simon's algorithm is comprised of two quantum blocks. The main part of the algorithm is the oracle which implements the Simon's function f(x).

How to Build the Algorithm with Classiq

The Quantum Part

The quantum part of the algorithm is rather simple, calling the quantum implementation of \(f(x)\), between two calls of the hadamard transform. The call of \(f\) is done out-of-place, onto a quantum variable \(y\), whereas only the final state of \(x\) is relevant to the classical post-process to follow.

from classiq import Output, QCallable, QNum, allocate_num, hadamard_transform, qfunc


@qfunc
def simon_qfunc(f_qfunc: QCallable[QNum, Output[QNum]], x: QNum):

    res = QNum("res")
    hadamard_transform(x)
    f_qfunc(x, res)
    hadamard_transform(x)

The Classical Postprocess

The classical part of the algorithm includes the following post-processing steps: 1. Finding \(N-1\) samples of \(x\) that are linearly independent, \(\{y_k\}^{n-1}_{1}\). It is gurenteed that this can be acheived with high probability, see the technical details below. 2. Finding the string \(s\) such that \(s \cdot y_k=0 \,\,\, \forall k\), where \(\cdot\) refers to a dot-product mod 2 (polynomial complexity in \(N\)).

For these steps we use the Galois package, which extends numpy to finite field operations.

# !pip install galois
import galois
import numpy as np

# here we work over boolean arithmetics - F(2)
GF = galois.GF(2)

We define two classical functions for the first step:

# The following function checks whether a set contains linearly independet vectors


def is_independent_set(vectors):
    matrix = GF(vectors)
    rank = np.linalg.matrix_rank(matrix)
    if rank == len(vectors):
        return True
    else:
        return False


def get_independent_set(samples):
    """
    The following function gets samples of n-sized strings from running the quantum part and return an n-1 x n matrix,
    whose rows forms a set if independent
    """
    ind_v = []
    for v in samples:
        if is_independent_set(ind_v + [v]):
            ind_v.append(v)
            if len(ind_v) == len(v) - 1:
                # reached max set of N-1
                break
    return ind_v

For the second step we simply need to solve a linear set of equations. We have \(N-1\) equations on a binary vector of size \(N\). It has two solutions, one of them is the trivial solution \(0^N\), and the other gives us the secret string \(s\). The Galois package handles this task as follows:

def get_secret_integer(matrix):

    gf_v = GF(matrix)  # converting to a matrix over Z_2
    null_space = gf_v.T.left_null_space()  # finding the right-null space of the matrix
    return int(
        "".join(np.array(null_space)[0][::-1].astype(str)), 2
    )  # converting from binary to integer

Next we provide two different examples of Simon's function, and run the Simon's algorithm to find their secret string.


Example: Arithmetic Simon's Function

An example of a valid \(f(x)\) function that satisfies the condition in Eq. (1) is: $$ f(x) = \min(x, x\oplus s). $$ Clearly, we have that \(f(x\oplus s) = \min(x\oplus s, (x\oplus s)\oplus s)=\min(x\oplus s, x)=f(x)\).

Implementing of the Simon's Function

We define the function, as well as a model that applies it on all computational basis states to illustrate that it is a two-to-one function.

from classiq import CInt, Output, QNum, create_model, hadamard_transform, qfunc
from classiq.qmod.symbolic import min


@qfunc
def simon_qfunc_simple(s: CInt, x: QNum, res: Output[QNum]):
    res |= min(x, x ^ s)

Let us run it with \(N=5\) and \(s={'}00110{'} (\equiv 6)\), starting with a uniform distribution of \(|x\rangle\) over all possible states:

from classiq import Constraints, allocate, execute, show, synthesize

NUM_QUBITS = 5
S_SECRET = 6


@qfunc
def main(x: Output[QNum], res: Output[QNum]):
    allocate(NUM_QUBITS, x)
    hadamard_transform(x)
    simon_qfunc_simple(S_SECRET, x, res)


qmod = create_model(main, constraints=Constraints(optimization_parameter="width"))

# synthesize
qprog = synthesize(qmod)

# vizualize
show(qprog)

# execute
result = execute(qprog).result()
Opening: https://platform.classiq.io/circuit/61cffecc-7617-4bb7-b554-4ec59239f1ae?version=0.41.0.dev39%2B79c8fd0855

By plotting the results we can see that this is two-to-one function:

import matplotlib.pyplot as plt

my_result = {
    sample.state["x"]: sample.state["res"] for sample in result[0].value.parsed_counts
}
fig, ax = plt.subplots()
ax.plot(my_result.keys(), my_result.values(), "o")
ax.grid(axis="y", which="minor")
ax.grid(axis="y", which="major")
ax.grid(axis="x", which="minor")
ax.grid(axis="x", which="major")
plt.xlabel("$x$", fontsize=16)
plt.ylabel("$f(x)$", fontsize=16)
plt.yticks(fontsize=16)
plt.xticks(fontsize=16)
ax.minorticks_on()

png

Running the Simon's Algorithm

Taking \(N\) number of shots gurentees getting a set of \(N-1\) independet strings with high probability (assuming a noiseless quantum computer), see technical explanation below. Moreover, increasing the number of shots by a constant factor provides an exponential improvment. Below we take \(50*N\) shots.

from classiq import allocate_num
from classiq.execution import ExecutionPreferences


@qfunc
def main(x: Output[QNum]):

    allocate(NUM_QUBITS, x)
    simon_qfunc(lambda x, res: simon_qfunc_simple(S_SECRET, x, res), x)


qmod = create_model(
    main,
    constraints=Constraints(optimization_parameter="width"),
    execution_preferences=ExecutionPreferences(num_shots=50 * NUM_QUBITS),
)
from classiq import write_qmod

write_qmod(qmod, "simon_example")

We Synthesize and execute to obtain the results

qprog = synthesize(qmod)
result = execute(qprog).result()
samples = [
    [int(k) for k in key] for key in result[0].value.counts_of_output("x").keys()
]
matrix_of_ind_v = get_independent_set(samples)
assert (
    len(matrix_of_ind_v) == NUM_QUBITS - 1
), "Failed to find an independent set, try to increase the number of shots"
quantum_secret_integer = get_secret_integer(matrix_of_ind_v)
print("The secret binary string (integer) of f(x):", S_SECRET)
print("The result of the Simon's Algorithm:", quantum_secret_integer)
assert (
    S_SECRET == quantum_secret_integer
), "The Simon's algorithm failed to find the secret key."
The secret binary string (integer) of f(x): 6
The result of the Simon's Algorithm: 6

Example: Shallow Simon's Function

In the second example we take a Simon's function that was presented in a recent paper [3]: Take a secret string of the form \(s=0^{N-L}1^L = \underbrace{00\dots0}_{N-L}\underbrace{1\dots111}_{L}\), and define the 2-to-1 function: $$ f_{s}(|x\rangle_N) = \underbrace{|x_0\rangle |x_1\rangle \dots |x_{N-L-1}\rangle}{N-L} |0\rangle \underbrace{|x. $$ The function }\oplus x_{N-L}\rangle \dots |x_{N-1}\oplus x_{N-L}\rangle}_{L-1\(f\) operates as follows: for the first \(N-L\) elements we simply "copy" the data, whereas for the last \(L\) elements we apply a xor with the \(N-L\) element. A simple proof that this is indeed a 2-to-1 function is given in Ref. [3].

Comment: Ref. [3] employed further reduction of the function implementation (reducing the \(N\)-sized Simon's problem to an \((N-L)\)-sized problem), added a classical post-process of randomly permutating over the result of \(f(x)\) to increase the hardness of the problem, as well as included some NISQ analysis. These steps where taken to show an algorithmic speedup on real quantum hardware.

Implementing of the Simon's Function

The first \(N-L\) "classical copies", \(|x_k,0\rangle\rightarrow |x_k x_k\rangle\), can be implemented by \(CX\) gates. The xor operations, \(|x_k,0\rangle\rightarrow |x_k, x_k \oplus x_{N-L}\rangle\), can be implemented by two CX operations, one for a "classical copy" of \(x_k\), followed by a \(CX\) operation to apply a xor with \(x_{N-L}\).

from classiq import CX, QArray, QBit, repeat


@qfunc
def simon_qfunc_with_bipartite_s(
    partition_index: CInt, x: QArray[QBit], res: Output[QArray[QBit]]
):

    allocate(x.len, res)

    repeat(x.len - partition_index, lambda i: CX(x[i], res[i]))
    repeat(
        partition_index - 1,
        lambda i: (
            CX(
                x[x.len - partition_index + 1 + i],
                res[x.len - partition_index + 1 + i],
            ),
            CX(x[x.len - partition_index], res[x.len - partition_index + 1 + i]),
        ),
    )

Below we take a specific example, and plot \(f(x)\) for all possible \(x\) values:

NUM_QUBITS = 6
PARTITION_INDEX = 4


@qfunc
def main(x: Output[QNum], res: Output[QNum]):
    allocate(NUM_QUBITS, x)
    hadamard_transform(x)
    simon_qfunc_with_bipartite_s(PARTITION_INDEX, x, res)


qmod = create_model(main, constraints=Constraints(optimization_parameter="width"))

# synthesize
qprog = synthesize(qmod)

# vizualize
show(qprog)

# execute
result = execute(qprog).result()

# plot the f(x)
my_result = {
    sample.state["x"]: sample.state["res"] for sample in result[0].value.parsed_counts
}
fig, ax = plt.subplots()
ax.plot(my_result.keys(), my_result.values(), "o")
ax.grid(axis="y", which="minor")
ax.grid(axis="y", which="major")
ax.grid(axis="x", which="minor")
ax.grid(axis="x", which="major")
plt.xlabel("$x$", fontsize=16)
plt.ylabel("$f(x)$", fontsize=16)
plt.yticks(fontsize=16)
plt.xticks(fontsize=16)
ax.minorticks_on()
Opening: https://platform.classiq.io/circuit/c9184a7a-af13-4a42-9fa9-c7457ce35f89?version=0.41.0.dev39%2B79c8fd0855

png

Running the Simon's Algorithm

As in the first example, we take \(50*N\) shots.

@qfunc
def main(x: Output[QNum]):

    allocate(NUM_QUBITS, x)
    simon_qfunc(lambda x, res: simon_qfunc_with_bipartite_s(PARTITION_INDEX, x, res), x)


qmod = create_model(
    main, execution_preferences=ExecutionPreferences(num_shots=50 * NUM_QUBITS)
)

write_qmod(qmod, "simon_shallow_example")

We synthesize and execute to obtain the results

qprog = synthesize(qmod)
show(qprog)
result = execute(qprog).result()
samples = [
    [int(k) for k in key] for key in result[0].value.counts_of_output("x").keys()
]
Opening: https://platform.classiq.io/circuit/af819a46-e820-471f-9c62-65af85eccd18?version=0.41.0.dev39%2B79c8fd0855
matrix_of_ind_v = get_independent_set(samples)
assert (
    len(matrix_of_ind_v) == NUM_QUBITS - 1
), "Failed to find an independent set, try to increase the number of shots"
quantum_secret_integer = get_secret_integer(matrix_of_ind_v)
s_secret = int("1" * PARTITION_INDEX + "0" * (NUM_QUBITS - PARTITION_INDEX), 2)
print("The secret binary string (integer) of f(x):", s_secret)
print("The result of the Simon's Algorithm:", quantum_secret_integer)
assert (
    s_secret == quantum_secret_integer
), "The Simon's algorithm failed to find the secret key."
The secret binary string (integer) of f(x): 60
The result of the Simon's Algorithm: 60

Technical Notes

Below we provide some technical details about the quantum and classical parts of the Simon's algorithm

The Quantum Part

Following the three blocks of the algorithm: $$ |0\rangle_N |0\rangle_N \rightarrow \frac{1}{2^{N/2}}\sum^{2^N-1}{x=0}|x\rangle_N |0\rangle_N \rightarrow \frac{1}{2^{N/2}}\sum^{2^N-1}|x\rangle_N |f(x)\rangle_N \rightarrow \frac{1}{2^{N}} \sum^{2^N-1}{y=0} |y\rangle_N \left( \sum^{2^N-1} |f(x)\rangle_N \right), $$ and we measure the first register }(-1)^{x\cdot y\(|y\rangle\). First, we treat the case that \(f(x)\) is a 2-to-1 function. The claim is that for any measured state \(y\), we must have that \(y\cdot s=0\). To see this, calculate the probability of measuring some state \(|y\rangle\): $$ P(|y\rangle) \propto \left| \sum^{2^N-1}{x=0}(-1)^{x\cdot y} |f(x)\rangle_N \right|^2. $$ Now, change the sum to run over the image of \(f(x)\) instead of over all \(x\in [0,2^{N}-1]\). Since for any \(f(x)\) there are two sources in the domain, \(x\) and \(x\oplus s\), we can write $$ P(|y\rangle) \propto \left| \sum \right]|f(x)\rangle_N \right|^2. $$ Finally, if we assume by negation that } \left[ (-1)^{x\cdot y} + (-1)^{(x\oplus s )\cdot y\(y\cdot s =1\) then the above expression is evaluted to zero, and we get a contradiction that \(y\) was measured. Hence, for any measured \(y\) we have \(y\cdot s =0\).

If \(s=0^N\), we still measure a set of \(N-1\) independent \(y\) with high probability (each \(y\) with \(1/2^N\) probability).

The Classical Part

We have a set of possible \(y\) values that can be measured, each with the same probability of \(1/M\), where \(M\) is the set size. In the case that \(s=0^N\) we have \(M=2^N\), whereas for \(s\neq 0^N\) the set size is \(M=2^{N-1}\). The probability to measure a set of \(N-1\) linearly independent binary strings \(y\) can be calculated as follows (see also the Birthday problem [2]): For the first string we just require that we do not pick \(y=0^N\), so \(P(y_0)=1-1/M\). Then, for the next string, we require that it is not in \(\left\{a_0 y_0\,\,\,| a_0=0,1\right\}\), thus \(P(y_1)=(1-2/M)\). The following string is required not to be picked out of \(\left\{a_0 y_0+a_1y_1\,\,\,| a_0, a_1=0,1\right\}\). We can continue with this procedure up to \(y_{N-1}\) to get $$ P_{\rm independent} = \left{\begin{array}{l l} \Pi^{2^{N-2}}{k=0} \left(1-2^k/2^{N}\right) & \text{, if } f(x) \text{ is 1-to-1},\ \Pi^{2^{N-2}} \end{array} \,\,\,\,\, \geq \Pi^{\infty}_{k=1}\left(1-\frac{1}{2^k}\right) \approx 0.2887 \geq 1/4. \right. $$ If we repeat the experiment } \left(1-2^k/2^{N-1}\right) & \text{, if } f(x) \text{ is 2-to-1\(K\) times then the probability to measure an independent set improves exponentially.

References

[1]: Simon's algorithm (Wikipedia)

[2]: Birthday problem (Wikipedia)

[3]: Singkanipa P., et al. "Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem." arXiv preprint arXiv:2401.07934 (2024).