# Simon

Simon's algorithm is the first real demonstration of quantum algorithms providing an exponential speedup over classical algorithm. Both [Deutsch](/algorithms/deutsch.md) and [Bernstein-Vazirani](/algorithms/bernstein-vazirani.md) algorithms that we have seen so far provide a linear speedup over classical algorithms going from O(n) to O(1).

### Objective

We are given an unknown function *f*, which is guaranteed to be map exactly two inputs to every unique output, using a hidden bitstring, b, such that :

$$f(x\_1)=f(x\_2) \hspace{5mm} \text{if}  \hspace{2mm}  x\_1 \oplus x\_2 = b$$​

So we want to identify b.

### Classical protocol

In the worst case, we have to query the function with $$2^{n-1} +1$$ different inputs (n is the number of bits in the input) i.e. checking just over half of all the possible inputs until we find two cases of the same output.

### Quantum protocol

The Simon oracle takes as input $$|x\rangle |0\rangle$$​and returns $$|x\rangle|\text{Perm}(x\oplus b)\rangle$$​where Perm is any fixed bitwise permutation. $$\text{Perm}(x\oplus b)$$​has the same value for two values of x that satisfy the [objective condition](#objective).

1. Prepare 2n qubits in $$|0\_n\rangle|0\_n\rangle$$, i.e n input and n output qubits.
2. Apply Hadamard gates to all input qubits. This create a equiprobable superposition of all possible input combinations, i.e $$|\psi\rangle = \sum |X\_k\rangle$$ up to some normalization constant.
3. Query the oracle with input qubits. The oracle effectively acts on all possible input combinations at the same time. The output is written on the output qubits using CNOT gates.
4. Apply Hadamard gates to the input qubits. This destructively interferes for all input states $$|X\_k\rangle$$where $$X\_k\oplus s$$ is odd and destructively interferes for all $$|X\_k\rangle$$where $$X\_k\oplus s$$ is even.
5. Measure all input qubits. The result is one of the possible $$X\_k$$ i.e. $$X\_k\oplus s=0$$.
6. If we repeat this experiment n times, we get n different values for $$X\_k$$. Solve the linear system of equations $$X\_{nk}\cdot s = 0$$ to find s.

### Expectation vs Reality

Simon algorithm is very similar to [Bernstein-Vazirani](/algorithms/bernstein-vazirani.md) and [Deutsch](/algorithms/deutsch.md) algorithm. Once again we have simply changed the definition of the oracle function making it much harder to solve. 

> The classical complexity required goes from O(n) in the BV algorithm to O(2^n) in the Simon problem. In comparison, the quantum complexity goes from O(1) to O(n), making this the first demonstration of a true **exponential** advantage of quantum computers over classical algorithms.

While Deutsch, BV and Simon algorithm's are important form a historical and theoretical perspective, they have little practical utility since each requires the existence of a very contrived oracle function.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://www.qswe.org/algorithms/simon.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.