6.3 Simon's algorithm: problem statement and implementation

Simon's algorithm tackles a problem involving a secret string and a special function. It showcases quantum computing's power by solving it exponentially faster than classical methods. This efficiency stems from exploiting quantum superposition and interference.

The algorithm's implementation involves preparing quantum states, querying an oracle function, and measuring results. It demonstrates a clear quantum advantage, requiring only O(n) queries compared to classical algorithms' Ω(2^(n/2)) queries.

Simon's Algorithm: Problem Statement and Implementation

Problem statement of Simon's algorithm

• Involves finding a secret string $s$ given a function $f$ that is either one-to-one or two-to-one with a specific property
• For a two-to-one function, any two distinct inputs $x$ and $y$ satisfy $f(x) = f(y)$ if and only if $x \oplus y = s$, where $\oplus$ denotes bitwise XOR (exclusive OR)
• Solves the problem exponentially faster than the best known classical algorithm
  • Classical algorithm requires $\Omega(2^{n/2})$ queries to $f$ ($n$ is the input size)
  • Simon's algorithm solves the problem with only $O(n)$ queries to $f$ and $O(n^3)$ additional quantum gates
• Demonstrates quantum advantage by solving a problem more efficiently using a quantum algorithm compared to the best known classical algorithm (exponential speedup)

Periodic functions in Simon's problem

• In Simon's problem, the function $f$ is periodic (repeating pattern) if it is two-to-one
• Periodicity is defined by the secret string $s$
  • For any two distinct inputs $x$ and $y$, $f(x) = f(y)$ if and only if $x \oplus y = s$
• The periodicity of $f$ allows Simon's algorithm to find the secret string $s$ efficiently by exploiting quantum superposition (multiple states simultaneously) and interference (constructive and destructive)

Implementation of Simon's algorithm

1. Prepare a uniform superposition over all input states by applying Hadamard gates to $n$ qubits initialized to $|0\rangle$
2. Query the oracle function $f$ using the superposition state as input, mapping $|x\rangle|0\rangle$ to $|x\rangle|f(x)\rangle$
3. Measure the second register (output of $f$) and discard it, collapsing the state to a superposition of inputs that map to the same output under $f$
4. Apply Hadamard gates to the remaining $n$ qubits
5. Measure the $n$ qubits to obtain a random $n$-bit string $y$, which is guaranteed to be orthogonal (perpendicular) to the secret string $s$ under the bitwise dot product
6. Repeat steps 1-5 for $O(n)$ iterations to obtain a set of linearly independent strings $y_i$
7. Solve the system of linear equations $y_i \cdot s = 0$ to find the secret string $s$

Performance vs classical solutions

• Simon's algorithm has a quantum query complexity of $O(n)$
  • Requires $O(n)$ queries to the oracle function $f$
  • Additional $O(n^3)$ quantum gates for the Hadamard transforms and measurements
• Best known classical algorithm for Simon's problem has a query complexity of $\Omega(2^{n/2})$, exponentially worse than Simon's algorithm
• Provides an exponential speedup over classical algorithms for this specific problem
• Demonstrates the potential of quantum algorithms to outperform classical algorithms for certain tasks (integer factorization, database search)
• Laid the foundation for more practical quantum algorithms, such as Shor's algorithm for factoring integers (cryptography implications)