Simon's Algorithm

Abstract: We study a quantum algorithm known as Simon's algorithm, which 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 well-known factoring algorithm, and it served as inspiration for many of the seminal works in quantum computation that followed.

This notebook is aimed at users with some basic knowledge of quantum computing and quantum circuits.

Table of Contents

• Simon's Problem Statement
• Example for n=3
• Classical Complexity
• Quantum Algorithm for Simon's Problem
• Quantum Circuit
• Running Simon's Algorithm
• Classical Post-Processing
• Quantum Complexity
• Implementing Simon's Algorithm in Amazon Braket
• References
• Appendix
• Implementing an Oracle Function
• Implementing the Classical Post-Processing

Simon's Problem Statement:

Suppose we’re given a function that maps bit strings to bit strings along with the promise that for some unknown -bit string , and where means bitwise addition modulo 2.

Said another way, there exists an unknown string such that, . When is non-zero, the function is two-to-one as it maps exactly two inputs to every unique output.

The goal of Simon's problem is to determine if is one-to-one, or two-to-one, or equivalently to find the secret string .

Since we're given the promise that , this means that whenever . Thus, one way to solve this problem is to find two inputs to the function that produce the same output; is then the XOR of those two input strings. See [1] for more details.

Classical Complexity

To solve Simon's problem classically, one needs to find two different inputs and for which . As we saw above, one can then determine . How hard is it to find two distinct inputs that map to the same output, given the function as a black box? For -bit strings, there are possible inputs. Thus, in the worst case, one would need to check at most different inputs to find a pair that maps to the same output; this provides an upper bound on the required query complexity.

It turns out that a lower bound on the classical query complexity of Simon's algorithm can also be found: . Proving this lower bound requires a little more work and is outside the scope of this notebook, so instead we will just provide some intuition.

As mentioned above, the goal is to find a pair of input strings and that map to the same output string -- a collision. Finding a collision in a set is an instance of the well-known (generalized) birthday problem [2]: 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?" This latter question gets to the heart of solving Simon's problem classically: how many queries to the function do we need to make to guarantee that we find a collision, with high probability? In the case of the birthday problem, we would need enough people in the room so that when we generate all possible pairings of people, we would have about 365 possible pairs. That way, we'd have a good chance that at least one of those pairs of people share a birthday. Using this intuition, we need to query enough times to generate a set of pairs with roughly the same size as the number of possible inputs (). If we make queries to the function , we can generate pairs. Thus, we need to make queries such that to have a high probability of generating a collision, and therefore, .

Quantum Algorithm for Simon's Problem

Simon's algorithm is a scheme for solving the problem above using exponentially fewer queries to the function . In order for Simon's algorithm to work, one needs to be able to implement the unknown function using quantum logic. That is, given an input quantum state , one needs a unitary satisfying This unitary is an oracle for , and the goal is to query it as few times as possible to learn the secret string .

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 . A circuit for the quantum component of Simon's algorithm is shown below.

For a function acting on -bit strings, the circuit above acts on qubits, as needed for the definition of . Only the first qubits are measured; the remaining qubits are unused after the application of .

Running Simon's Algorithm

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 qubits produce an output bit string, which we denote by .

An analysis of the circuit above shows that each output bit string satisfies the following condition:

Let us now analyze the above circuit step-by-step:

1. Initialize all qubits in the state. That is, we start in the state . We will use the shorthand

2. Apply Hadamard gates to each of the first qubits, placing them in the equal superposition state: .

3. Apply the oracle , which computes the function into the last qubits, giving the state

4. Measure the last qubits, giving a random result . If is one-to-one, this output of corresponds to an input of . If is two-to-one, the output of corresponds to an input of either either or , where and are the two different inputs to that gave the same output . Hence we are left with the first qubits in the state;

   A. ,                    if is one-to-one; B. , where ,  if is two-to-one. 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.

5. Apply Hadamard gates to each of the first qubits. If is one-to-one, the state is mapped to where is the dot product between the two strings represented as vectors (modulo 2).

   Similarly, if is two-to-one, the state is mapped to .

6. Measure the first qubits.

   1. If is one-to-one, measurements return a random bit string uniformly chosen from .
   2. If is two-to-one, measurements return a random bit string such that , since otherwise the amplitude cancels out. Using the criterion for Simons problem (i.e,. ), we find that

   Thus, in both cases we obtain a random bit string such that .

Therefore, each time we run the quantum circuit above, we find a bit string that is orthogonal to the secret string .

Classical Post-Processing

From the measurement results , we can form a system of equations:

There are equations and unknowns (the elements of ). If we run the quantum part enough times so that we find independent equations, then we can solve these equations (using, e.g., Gaussian elimination) to recover the secret string . This is precisely the classical post-processing required: solve the system of equations found above to recover the string . We refer the interested reader to the Appendix for details.

Quantum Complexity

How many queries do we need to make to in the quantum case? Above we saw that we need to run the quantum part of the algorithm times to generate a system of equations. We need to find linearly independent equations for the system to be determined. Thus, we need at least queries to to find such a system. It is possible, however, that we will get the same measurement outcome on different runs of the quantum algorithm, so we would need to re-do those runs that do not produce distinct measurement outcomes. Fortunately, these repeated outcomes are unlikely, so we only need queries to the oracle .

Comparing the quantum and classical algorithms, we saw that the classical algorithm requires at least queries to , whereas the quantum algorithm requires only . Thus, we have established an exponential speedup by using the quantum algorithm above.

Implementing Simon's Algorithm in Amazon Braket

We also import a method called simons_oracle, which generates a circuit implementing an example oracle function. The code for simons_oracle is defined in the simons_utils.py module, and it is shown in the Appendix for completeness.

We now define the secret string, :

Circuit Definition

We now define the quantum circuit for Simon's algorithm:

1. Apply Hadamard gates to the first -qubits.

2. Query the oracle (i.e., the gate). In this example, the oracle is defined dynamically, based on our chosen value of . You can try experimenting with different values of (with differing lengths).

3. Apply Hadamard gates to the first -qubits.

Now run the circuit

We need enough shots to obtain linearly independent bit strings in the output measurements. We have chosen 4n shots in the example below, just to be on the safe side.

Analyze the results

We can retrieve the measurement results on all qubits as follows:

Aggregate the results

The measurements are performed on all qubits, but we are only interested in the first qubits. Thus, we need to aggregate the results by ignoring the measurement outcomes on the last qubits:

In practice, we only need the measurement results (i.e., the bit strings, not the counts) from the first qubits. These measurement outcomes correspond to bit strings that satisfy the equations:

With these linear equations in hand, we can use classical post-processing to solve for the unknown string .

Note that we may have too many bit strings in the above, since we ran the quantum task with shots just to be safe. In this case, not all of the bit strings will be linearly independent. Moreover, the all-zeros string may also be an outcome, but this bit string satisfies the equations above trivially, so we exclude it if needed.

At this stage, the quantum portion of Simon's algorithm is complete. Any remaining steps are just classical postprocessing, which we cover in the Appendix.

References

[1] Wikipedia: Simon's Problem

[2] Wikipedia: Birthday Problem

[3] Wikipedia: Computing a kernel by Gaussian elimination

[4] StackExchange: Sympy: Solving Matrices in a finite field

---

Appendix

Implementing an Oracle Function

In order to run the algorithm, we will need a unitary function that we can use as an oracle to query the function .

There are many possible ways of implementing a function with the desired property that . We will pick one implementation that is commonly used in example code, and we will try to give some intuition for why this oracle works.

Classical Intuition Behind the Function

Generating a function that is one-to-one is conceptually straightforward, as any such function of the bit strings will just be a permutation of the inputs. Generating a two-to-one function is a little trickier, though there are many ways to do it. The goal is to define a function that splits the inputs into two groups, such that one element from each group maps to the same output (i.e., must be in one group, while must be in the other group.)

We will implement one simple choice for , in which we define the split based on the value of one of the bits in the string. In this way, exactly half of the inputs will have that bit with value , while the other half will have that bit with value .

Our approach will be to choose a flag bit in the input bit strings that we will use to split the inputs. We then the input string with whenever the flag bit is . With this definition, half of the input strings will be untouched, while half of the strings will be 'ed with . Clearly, this function does nothing to the all-zeros string , since any choice of the flag bit will always be . Thus, we need to ensure that our definition also maps the string to the all-zeros string . In other words, we need to ensure that our flag bit is when the input string is . One way to ensure the function acts correctly on the input is to just define the flag bit to be the first bit in the string that is equal to . For example, if , we can choose the flag bit to be the second bit. Concretely: where is the bit of , and is the flag bit in .

We leave it as an exercise to the reader to verify that this definition works for any input string size (i.e., for inputs , and that it is in fact two-to-one, rather than many-to-one. Note that the function defined in this way is not a general two-to-one function, but it is simple a choice that is easy to implement both classically and as a quantum circuit.

Quantum Implementation of

We now define the unitary using the @circuit.subroutine functionality of the Amazon Braket SDK. The following code was imported from the simons_utils.py module, and is shown below for reference.

In the quantum setting, we first copy the input register into some ancillary qubits: We then perform the quantum analog of , which means we apply an gate to the qubit whenever the bit of is . However, we only apply this gate when the flag qubit is also . Thus, our gate becomes a gate between the flag qubit on the input register, and the qubit on the output.

from braket.circuits import Circuit, circuit

@circuit.subroutine(register=True)
def simons_oracle(secret_s: str):
    """
    Quantum circuit implementing a particular oracle for Simon's problem. Details of this implementation are
    explained in the Simons Algorithm demo notebook.

    Args:
        secret_s (str): secret string we wish to find
    """
    # Find the index of the first 1 in s, to be used as the flag bit
    flag_bit=secret_s.find('1')
    
    n=len(secret_s)
    
    circ = Circuit()
    # First copy the first n qubits, so that |x>|0> -> |x>|x>
    for i in range(n):
        circ.cnot(i, i+n)
    
    # If flag_bit=-1, s is the all-zeros string, and we do nothing else.
    if flag_bit != -1:
        # Now apply the XOR with s whenever the flag bit is 1.
        for index,bit_value in enumerate(secret_s):
            
            if bit_value not in ['0','1']:
                raise Exception ('Incorrect char \'' + bit_value + '\' in secret string s:' + secret_s)
                
            # XOR with s whenever the flag bit is 1.
            # In terms of gates, XOR means we apply an X gate only whenever the corresponding bit in s is 1.
            # Applying this X only when the flag qubit is 1 means this is a CNOT gate.
            if(bit_value == '1'):
                circ.cnot(flag_bit,index+n)
    return circ

Implementing the Classical Post-Processing

We will now solve the system of linear equations above using Gaussian elimination. We first convert the results into matrix form, then we use sympy's Matrix.rref() method to transform the matrix into reduced row echelon form.

Generate a matrix from the bit string outputs. We first check that we have sufficiently many output strings to be able to solve the system of equations. If not: output and error and re-run the algorithm.

Now solve the system by finding the kernel of . We do this using Gaussian elimination on the augmented matrix to bring it to row echelon form. Converting the solution to numbers , we can then read off the solution from the last row of the reduced matrix. See [3] and [4] for more details.