Table of Contents
- Introduction
- Problem Overview
- Classical vs Quantum Approach
- Mathematical Formulation
- The Oracle Promise
- Simon’s Problem Statement
- High-Level Idea of Simon’s Algorithm
- Oracle Structure and Functionality
- Input and Output Qubit Registers
- Quantum Circuit Overview
- Step-by-Step Execution
- Initial State and Superposition
- Oracle Application and Entanglement
- Measurement of Output Register
- Collapse and Hidden Information
- Final Hadamard Transform on Input
- Interference and Orthogonality
- Solving the Linear Equations
- Number of Queries Required
- Quantum Speedup Analysis
- Geometric and Algebraic Intuition
- Simon’s Algorithm vs Bernstein-Vazirani
- Qiskit Implementation Example
- Limitations and Real-World Impact
- Conclusion
1. Introduction
Simon’s Algorithm was the first to demonstrate an exponential separation between classical and quantum computation. It laid the groundwork for later breakthroughs such as Shor’s Algorithm and provided early evidence of quantum advantage.
2. Problem Overview
Simon’s problem asks us to find a hidden binary string \( s \in \{0,1\}^n \) that characterizes a special function’s behavior.
3. Classical vs Quantum Approach
- Classical deterministic approach: Requires \( \Omega(2^{n/2}) \) queries
- Quantum approach: Solves with O(n) queries
This exponential gap makes Simon’s algorithm a landmark in quantum computing.
4. Mathematical Formulation
Let \( f: \{0,1\}^n \rightarrow \{0,1\}^n \) be a function such that:
\[
\forall x, x’: f(x) = f(x’) \iff x = x’ \oplus s
\]
That is, the function is 2-to-1, and \( s \) is the period or hidden string we want to find.
5. The Oracle Promise
The oracle \( f \) is guaranteed to satisfy:
- If \( s = 0^n \): function is one-to-one
- Otherwise: \( f(x) = f(x \oplus s) \) and only these two share output
This “promise” distinguishes Simon’s algorithm from general function learning.
6. Simon’s Problem Statement
Find the secret string \( s \) given query access to a black-box function \( f \) satisfying the above conditions.
7. High-Level Idea of Simon’s Algorithm
The algorithm uses:
- Superposition to query multiple inputs at once
- Interference to encode \( s \)
- Measurement + linear algebra to extract \( s \) from sampled bitstrings orthogonal to it
8. Oracle Structure and Functionality
The oracle \( U_f \) acts as:
\[
U_f |x\rangle|0\rangle = |x\rangle|f(x)\rangle
\]
It entangles input and output registers based on the secret period \( s \).
9. Input and Output Qubit Registers
- Input: \( n \) qubits initialized to \( |0\rangle \)
- Output: \( n \) qubits initialized to \( |0\rangle \)
Total: \( 2n \) qubits used.
10. Quantum Circuit Overview
- Apply Hadamard to input qubits
- Apply oracle \( U_f \)
- Measure output register
- Apply Hadamard again to input
- Measure input register
- Repeat to gather \( n-1 \) independent equations
11. Step-by-Step Execution
Initial state:
\[
|\psi_0\rangle = |0\rangle^{\otimes n} \otimes |0\rangle^{\otimes n}
\]
12. Initial State and Superposition
After applying Hadamard to the input:
\[
|\psi_1\rangle = \frac{1}{\sqrt{2^n}} \sum_{x} |x\rangle |0\rangle
\]
13. Oracle Application and Entanglement
Apply the oracle:
\[
|\psi_2\rangle = \frac{1}{\sqrt{2^n}} \sum_x |x\rangle|f(x)\rangle
\]
Each input becomes entangled with its output.
14. Measurement of Output Register
Measurement collapses the output state to some \( f(x_0) \). The input register is now in a superposition of:
\[
\frac{1}{\sqrt{2}}(|x_0\rangle + |x_0 \oplus s\rangle)
\]
15. Collapse and Hidden Information
The measurement restricts the input state to a 2-dimensional subspace defined by the period \( s \).
16. Final Hadamard Transform on Input
Apply Hadamard again to input:
\[
H^{\otimes n} \left( \frac{|x\rangle + |x \oplus s\rangle}{\sqrt{2}} \right)
\]
Using identity:
\[
H^{\otimes n} |x\rangle = \frac{1}{\sqrt{2^n}} \sum_y (-1)^{x \cdot y} |y\rangle
\]
Results in:
\[
\frac{1}{\sqrt{2^{n+1}}} \sum_y \left[ (-1)^{x \cdot y} + (-1)^{(x \oplus s) \cdot y} \right] |y\rangle
\]
17. Interference and Orthogonality
Only those \( y \) for which \( s \cdot y = 0 \mod 2 \) remain with non-zero amplitude. Each measurement yields a \( y \) such that:
\[
y \cdot s = 0 \mod 2
\]
18. Solving the Linear Equations
After collecting \( n – 1 \) independent such \( y \), solving the linear system over \( \mathbb{F}_2 \) yields the secret string \( s \).
19. Number of Queries Required
Expected number of iterations to find \( n – 1 \) linearly independent vectors is O(n).
20. Quantum Speedup Analysis
- Quantum: O(n)
- Classical: Requires \( \Omega(2^{n/2}) \) queries
This provides exponential speedup.
21. Geometric and Algebraic Intuition
Each query reveals a hyperplane orthogonal to \( s \). With enough hyperplanes, the only vector satisfying all orthogonality constraints is \( s \).
22. Simon’s Algorithm vs Bernstein-Vazirani
- BV: Dot product function \( f(x) = a \cdot x \)
- Simon: 2-to-1 mapping with hidden XOR mask
- BV needs 1 run, Simon needs O(n) runs but solves exponentially harder problem
23. Qiskit Implementation Example
from qiskit import QuantumCircuit, Aer, execute
from qiskit.visualization import plot_histogram
n = 3
qc = QuantumCircuit(2*n, n)
# Step 1: Hadamard on input
qc.h(range(n))
# Step 2: Oracle
# Sample oracle with s = 101: f(x) = f(x ⊕ 101)
qc.cx(0, n+0)
qc.cx(2, n+0)
# Step 3: Hadamard on input
qc.h(range(n))
# Step 4: Measure input
qc.measure(range(n), range(n))
backend = Aer.get_backend('qasm_simulator')
result = execute(qc, backend, shots=1024).result()
counts = result.get_counts()
print(counts)24. Limitations and Real-World Impact
Simon’s problem is contrived and has limited direct application. However, it:
- Demonstrates exponential quantum speedup
- Inspired Shor’s factoring algorithm
25. Conclusion
Simon’s Algorithm is a pivotal quantum algorithm that showcases exponential advantage over classical methods. It uses clever entanglement and measurement strategies to infer hidden structure from a black-box function — a fundamental example of the quantum computing paradigm shift.