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.
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:
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()
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:
The function \(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
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),}(-1)^{x\cdot y
P(|y\rangle) \propto \left| \sum^{2^N-1}_{x=0}(-1)^{x\cdot y} |f(x)\rangle_N \right|^2.
P(|y\rangle) \propto \left| \sum_{f(x) \in imag(f)} \left[ (-1)^{x\cdot y} + (-1)^{(x\oplus s )\cdot y} \right]|f(x)\rangle_N \right|^2. $$ Finally, if we assume by negation that \(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).