AWS Quantum Technologies Blog
Exploring Simon’s Algorithm with Daniel Simon
Introduction
Customers exploring quantum computing often rely on existing algorithms to learn the basics or evaluate new services. Amazon Braket includes many such algorithms in its SDK and managed notebooks. In this post, we will explore one of the first quantum algorithms invented, and a new addition to our Amazon Braket examples: Simon’s algorithm. We first explain the theory behind the algorithm, and then we implement Simon’s algorithm from endtoend using Amazon Braket. Additionally, Daniel Simon (the inventor of Simon’s algorithm and a principal security engineer in AWS Cryptography) shares some historical insights and intuition about his namesake algorithm.
This blog is a companion article to the new Simon’s Algorithm example Jupyter notebook, which you can find by spinning up a hosted Amazon Braket notebook instance and looking in the example notebooks section, or by looking in the opensource amazonbraketexamples GitHub repository. Please read the notebook for deeper details. In the Amazon Braket examples GitHub repository, you can also find implementations of other seminal quantum algorithms.
Simon’s algorithm
Simon’s algorithm provided the first example of an exponential speedup over the best known classical algorithm by using a quantum computer to solve a particular problem. Originally published in 1994, Simon’s algorithm was a precursor to Shor’s wellknown factoring algorithm, and it served as inspiration for many of the seminal works in quantum computation that followed.
Simon’s problem:
Simon’s algorithm was designed to solve a particular mathematical problem:
Suppose we’re given a function f:{0,1}^{n}→{0,1}^{n} that maps bit strings to bit strings. We’re also given the promise that the function f either maps each unique input to a unique output, or maps two distinct inputs to one unique output, but we’re not told which. Mathematically, this means that f is either onetoone or twotoone, and that we are given the promise
for some unknown nbit string s∈{0,1}^{n}, and where ⊕ means bitwise addition modulo 2.
Said another way, there exists an unknown string s such that, for all input strings x, f(x)=f(x⊕s). When s is nonzero, the function is twotoone as it maps exactly two inputs to every unique output. When s is the zero string, the function is onetoone.
The goal of Simon’s algorithm is to determine if f is onetoone or twotoone, which we will do by directly finding the secret string s. As a matter of fact, it can be shown that finding s is mathematically equivalent to solving the original question in the oracle setting we are considering here.
Classical complexity
To solve Simon’s problem classically, one needs to find two different inputs x and y for which f(x)=f(y), since one can then determine s=x⊕y (where addition is done bitwise, mod 2), or otherwise show that no two inputs produce the same output.
How hard is it to find two distinct inputs that map to the same output, given the function f as a black box? For nbit strings, there are 2^{n} possible inputs. Thus, in the worst case, one would need to check at most 2^{n} different inputs to find a pair that maps to the same output; this provides an upper bound on the required query complexity. How about a lower bound? Classically, it can be shown that we need to check Θ(2^{n/2}) inputs, which still scales exponentially in the size of the problem. The intuition behind this lower bound comes from the (generalized) birthday problem: within a group of people, what is the probability that two of them share the same birthday? One can turn this problem around and ask “how many people do we need in a room to ensure that the probability that at least two of them share a birthday is greater than some fixed number?” It turns out that you need a number of people given by roughly the square root of the number of possible birthdays (i.e., 365). For Simon’s problem, this means you need to check about Θ(2^{n/2}) inputs.
Quantum algorithm for Simon’s problem
Simon’s algorithm is a scheme for solving the preceding problem using exponentially fewer queries to the function f. In order for Simon’s algorithm to work, one needs to be able to implement the unknown function f using quantum logic. In other words, we need a unitary operator U_{f} that encodes the action of the function f as a transformation on quantum states. Specifically,
For our purposes, we can safely assume that the unitary U_{f} is given to us as a black box (an “oracle”), and that we don’t know how it works, but we do know that it implements the preceding transformation. One benefit of the oracle model is that we don’t need to know how the oracle works — we just have to trust that it does. The Simon’s Algorithm notebook provides an implementation of a commonly used example oracle for f, as well as a detailed explanation of how and why it works.
Quantum circuit
Simon’s algorithm involves both quantum and classical components. The quantum part of Simon’s algorithm is used to query the oracle efficiently, while the classical component is used to process measurement results and determine the hidden string s. A circuit for the quantum component of Simon’s algorithm is shown here.
For a function f acting on nbit strings, the circuit above acts on 2n qubits, as needed for the definition of U_{f}. Only the first n qubits need to be measured; the remaining qubits are unused after the application of U_{f}.
The mathematical details
In order to understand how this quantum circuit solves the problem with exponentially fewer queries to the function f than a classical algorithm, we need to dive a bit deeper into the math.
To solve Simon’s problem, one needs to run the quantum circuit above several times. After each run of the circuit, the measurements of the first n qubits produce an output bit string, which we denote by z.
An analysis of the circuit above shows that each output bit string z satisfies the following condition:
Let’s see why this is the case, by analyzing the above circuit stepbystep. Full mathematical details for these steps are available in the accompanying notebook.

 Initialize all qubits in the 0⟩ state.
 Apply Hadamard gates to each of the first n qubits, placing them in the equal superposition state.
 Apply the oracle U_{f}, which computes the function f into the last n qubits.
 Measure the last n qubits, giving a random result f(x). If f is onetoone, this output of f corresponds to an input of x. If f is twotoone, the output of f corresponds to an input of either x or y=x+s, where x and y are the two different inputs to f that gave the same output f(x)=f(y). Note that this step is not strictly necessary, since we do not need the measurement result, but we include it as it makes the analysis easier.

 Apply Hadamard gates to each of the first n qubits. If f is onetoone, the state x⟩ is mapped to
where x·z is the dot product between the two strings represented as vectors (modulo 2).
Similarly, if f is twotoone, the state (x⟩+y⟩)/√2 is mapped to

 Measure the first n qubits.
If f is onetoone, measurements return a random bit string z uniformly chosen from {0,1}^{n}.
If f is twotoone, measurements return a random bit string z such that x·z=y·z mod 2, since otherwise the amplitude (−1)^{(x·z)}+(−1)^{(y·z)} cancels out. Using the criterion for Simons problem (f(x)=f(y)⟹x=y⊕s), we find that
 Measure the first n qubits.
Thus, in both cases we obtain a random bit string z such that s·z=0.
Therefore, each time we run the quantum circuit above, we find a bit string z that is orthogonal to the secret string s.
Classical postprocessing
From the measurement results {z_{1},…,z_{k}}, we can form a system of equations: {z_{k}·s=0 mod 2}.
There are k equations and n unknowns (the elements of s). If we run the quantum part enough times so that we find n independent equations, then we can solve these equations (using, for example, Gaussian elimination) to recover the secret string s. This is precisely the classical postprocessing required: solve the system of equations found above to recover the string s. If you’re interested in deeper details, refer to the appendix of the notebook.
Quantum complexity
Running the above quantum circuit O(n) times is sufficient to give n linearly independent equations, which we can use to solve for s. Therefore, Simon’s algorithm can be solved using O(n) queries to U_{f}. Since the classical algorithm requires Ω(2^{n/2}) queries, this establishes an exponential speedup of the quantum algorithm.
Implementation on Amazon Braket
We first import a method called simons_oracle
implemented in the amazonbraketexamples repository. This method implements a particular quantum oracle for a secret function f. We explain this specific function and its quantum implementation in the notebook appendix. The simons_oracle
method accepts a secret string s
, which we choose at the start. Our goal is to recover this same string s
.
# Implemented in NBI / example notebook utils from simons_utils
import simons_oracle
s = '101011' # Secret string
n = len(s)
circ = Circuit()
# Apply Hadamard gates to the first n qubits
circ.h(range(n))
# Apply the Oracle for f. See NBI / notebook for implementation
circ.simons_oracle(s)
# Apply Hadamard gates to the first n qubits
circ.h(range(n))
print(circ)
This code snippet generates the following circuit:
T : 0 1  2 3456 q0 : HCCCCCH      q1 : HCH       q2 : HCH        q3 : HCH         q4 : HCH          q5 : HCH           q6 : XX         q7 : X        q8 : XX      q9 : X     q10 : XX   q11 : XX T : 0 1  2 3456
We now run the circuit using the Amazon Braket local simulator 4n times. We choose the number of shots to be 4n so that, with high probability, we will obtain at least n linearly independent samples that we can use to solve for s.
# Sets the device to run the circuit on
device = LocalSimulator()
# Run the circuit 4n times, should be sufficient to get n independent bit strings
task = device.run(circ, shots=4*n)
And that’s it! The rest of the algorithm is purely classical. As explained in the preceding classical postprocessing section, these measurement outcomes define a set of linear equations, which we can solve to recover the classical string s
. If you want to run the full example yourself, you can find the code in the Simon’s Algorithm notebook in the Amazon Braket examples repository. The examples in this repository also come preinstalled on Amazon Braket notebooks to help you get started quickly.
Conclusion
Simon’s algorithm was a key contribution to the early foundations of quantum information theory and quantum computation. Today, this algorithm is often taught to students of quantum information theory as part of the core curriculum, since its simple implementation can be covered in the span of a single lecture. However, the simplicity of the algorithm belies its significance, as the conceptual ideas discovered in Simon’s algorithm can also be found through a number of today’s advanced quantum algorithms.