Simon's Algorithm
Simon's algorithm solves the hidden subgroup problem for the group (Z₂)ⁿ. Given a function f: {0,1}ⁿ → {0,1}ⁿ that is either one-to-one or two-to-one, and if two-to-one then f(x) = f(x ⊕ s) for some hidden string s ≠ 0ⁿ, the algorithm finds s with exponential speedup over classical methods.
The algorithm requires only O(n) quantum operations to find the hidden period, while classical algorithms would require O(2^(n/2)) queries to find s.
This implementation builds the quantum circuit for Simon's algorithm and executes it on a specified quantum backend.
The algorithm uses a quantum oracle Uf that computes f(x) = f(x ⊕ s), where s is the hidden period and x is the input bit string.
Simon's Algorithm
Simon's algorithm solves the hidden subgroup problem for the group (Z₂)ⁿ.
Given a function f: {0,1}ⁿ → {0,1}ⁿ that is either one-to-one or two-to-one,
and if two-to-one then f(x) = f(x ⊕ s) for some hidden string s ≠ 0ⁿ,
the algorithm finds s with exponential speedup over classical methods.
The algorithm requires only O(n) quantum operations to find the hidden period,
while classical algorithms would require O(2^(n/2)) queries to find s.
This implementation builds the quantum circuit for Simon's algorithm
and executes it on a specified quantum backend.
The algorithm uses a quantum oracle Uf that computes f(x) = f(x ⊕ s),
where s is the hidden period and x is the input bit string.(add-oracle-fn hidden-period n-qubits)Build the quantum circuit for Simon's oracle Uf using linear algebra approach.
Creates an oracle that implements f(x) = A·x where A is a matrix such that A·s = 0. This guarantees f(x) = f(x ⊕ s) for the hidden period s, creating a valid 2-to-1 function.
The oracle works by:
Parameters:
Returns: A function that takes a quantum circuit and applies the Simon oracle Uf to it.
Build the quantum circuit for Simon's oracle Uf using linear algebra approach. Creates an oracle that implements f(x) = A·x where A is a matrix such that A·s = 0. This guarantees f(x) = f(x ⊕ s) for the hidden period s, creating a valid 2-to-1 function. The oracle works by: 1. Computing f(x) = A·x where A is an (n-1)×n matrix orthogonal to s 2. Each output bit j = sum_i A[j][i] * x[i] (mod 2) 3. Implemented as CNOT gates from input qubits to output qubits based on matrix A Parameters: - hidden-period: Vector of bits representing the hidden period s - n-qubits: Number of qubits in input register Returns: A function that takes a quantum circuit and applies the Simon oracle Uf to it.
(collect-simon-measurements backend
circuit
target-count
n-qubits
hidden-period
options)Efficiently collect measurements for Simon's algorithm using result-specs framework.
Simon's algorithm requires multiple runs to collect enough linearly independent equations to solve for the hidden period. This function uses the unified result extraction framework and leverages shot-based execution for efficiency.
Instead of running the circuit multiple times (each with many shots), this function runs the circuit once with all requested shots and extracts all unique measurement outcomes from the frequency data.
Parameters:
Returns: Vector of measurement bit vectors that are linearly independent.
Efficiently collect measurements for Simon's algorithm using result-specs framework. Simon's algorithm requires multiple runs to collect enough linearly independent equations to solve for the hidden period. This function uses the unified result extraction framework and leverages shot-based execution for efficiency. Instead of running the circuit multiple times (each with many shots), this function runs the circuit once with all requested shots and extracts all unique measurement outcomes from the frequency data. Parameters: - backend: Quantum backend to execute circuits on - circuit: The Simon's algorithm circuit to execute - target-count: Number of measurements needed (typically n-1 for n-qubit hidden period) - n-qubits: Number of qubits in the hidden period - hidden-period: The actual hidden period (for fallback orthogonal vector generation) - options: Execution options Returns: Vector of measurement bit vectors that are linearly independent.
(create-simon-oracle-matrix s)Create a matrix A for Simon's oracle such that A·s = 0. This creates a valid 2-to-1 function where f(x) = A·x satisfies f(x) = f(x ⊕ s).
Create a matrix A for Simon's oracle such that A·s = 0. This creates a valid 2-to-1 function where f(x) = A·x satisfies f(x) = f(x ⊕ s).
(gf2-add a b)Addition in GF(2) - equivalent to XOR
Addition in GF(2) - equivalent to XOR
(gf2-dot-product v1 v2)Dot product over GF(2) - sum of element-wise products mod 2
Dot product over GF(2) - sum of element-wise products mod 2
(gf2-find-null-space matrix)Find a non-trivial vector in the null space of a matrix over GF(2). Returns a vector that satisfies Ax = 0, or nil if only trivial solution exists.
Find a non-trivial vector in the null space of a matrix over GF(2). Returns a vector that satisfies Ax = 0, or nil if only trivial solution exists.
(gf2-find-pivot matrix col start-row)Find the first non-zero element in a column starting from row start-row
Find the first non-zero element in a column starting from row start-row
(gf2-gaussian-elimination matrix)Perform Gaussian elimination on a matrix over GF(2). Returns the matrix in row echelon form.
Perform Gaussian elimination on a matrix over GF(2). Returns the matrix in row echelon form.
(gf2-row-add row1 row2)Add row2 to row1 in GF(2) (XOR each element)
Add row2 to row1 in GF(2) (XOR each element)
(gf2-swap-rows matrix row1 row2)Swap two rows in a matrix
Swap two rows in a matrix
(simon-algorithm backend hidden-period)(simon-algorithm backend hidden-period options)Implement Simon's algorithm to find the hidden period of a function.
Simon's algorithm solves the hidden subgroup problem for the group (Z₂)ⁿ. Given a function f: {0,1}ⁿ → {0,1}ⁿ that is either one-to-one or two-to-one, and if two-to-one then f(x) = f(x ⊕ s) for some hidden string s ≠ 0ⁿ, the algorithm finds s with exponential speedup over classical methods.
This refactored version uses the unified result extraction framework for consistent measurement handling across all quantum algorithms.
Algorithm steps:
Parameters:
Returns: Map containing:
Example: (simon-algorithm [1 0 1] backend) ;=> Finds period [1 0 1]
Implement Simon's algorithm to find the hidden period of a function.
Simon's algorithm solves the hidden subgroup problem for the group (Z₂)ⁿ.
Given a function f: {0,1}ⁿ → {0,1}ⁿ that is either one-to-one or two-to-one,
and if two-to-one then f(x) = f(x ⊕ s) for some hidden string s ≠ 0ⁿ,
the algorithm finds s with exponential speedup over classical methods.
This refactored version uses the unified result extraction framework
for consistent measurement handling across all quantum algorithms.
Algorithm steps:
1. Initialize |0⟩ⁿ|0⟩ⁿ (input and output registers)
2. Apply Hadamard to input register: |+⟩ⁿ|0⟩ⁿ
3. Apply oracle Uf: |x⟩|y⟩ → |x⟩|y ⊕ f(x)⟩
4. Measure output register (collapses to some value)
5. Apply Hadamard to input register
6. Measure input register to get y such that s·y = 0 (mod 2)
7. Repeat to collect n-1 linearly independent equations
8. Solve system to find s using Gaussian elimination over GF(2)
Parameters:
- backend: Quantum backend implementing the QuantumBackend protocol to execute the circuit
- hidden-period: Vector representing the hidden period s (for oracle construction)
- options: Optional map with execution options (default: {:shots 1024})
Returns:
Map containing:
- :result - The computed period from measurements using linear solver
- :measurements - Collection of measurement outcomes from multiple runs
- :hidden-period - The actual hidden period (for verification)
- :found-period - The computed period from measurements using linear solver
- :success - Whether algorithm found a valid period
- :linear-system - The system of equations collected
- :execution-results - Results from all circuit executions
- :circuit - Description of the quantum circuit used
Example:
(simon-algorithm [1 0 1] backend) ;=> Finds period [1 0 1](simon-circuit hidden-period)Build the quantum circuit for Simon's algorithm.
Parameters:
Returns: A quantum circuit implementing Simon's algorithm using the provided hidden period.
Build the quantum circuit for Simon's algorithm. Parameters: - hidden-period: Vector of bits representing the hidden period s (for oracle construction) - n-qubits: Number of qubits in input register Returns: A quantum circuit implementing Simon's algorithm using the provided hidden period.
(solve-linear-system-gf2 equations n)Solve a system of linear equations over GF(2) (binary field).
Takes a matrix of equations where each row represents an equation y₁ · s = 0 (mod 2), and finds the hidden string s.
This function implements Gaussian elimination over GF(2) to find a vector in the null space of the coefficient matrix. In Simon's algorithm context, this finds the hidden period that satisfies all measurement equations.
Parameters:
Returns: A non-trivial solution vector s, or nil if system has no non-trivial solution
Example: (solve-linear-system-gf2 [[1 0 1] [0 1 1]] 3) ;=> [1 1 0] ; A vector that when dot-multiplied with each equation gives 0
Solve a system of linear equations over GF(2) (binary field). Takes a matrix of equations where each row represents an equation y₁ · s = 0 (mod 2), and finds the hidden string s. This function implements Gaussian elimination over GF(2) to find a vector in the null space of the coefficient matrix. In Simon's algorithm context, this finds the hidden period that satisfies all measurement equations. Parameters: - equations: Vector of bit vectors representing the linear system - n: Length of the hidden string Returns: A non-trivial solution vector s, or nil if system has no non-trivial solution Example: (solve-linear-system-gf2 [[1 0 1] [0 1 1]] 3) ;=> [1 1 0] ; A vector that when dot-multiplied with each equation gives 0
cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |