org.soulspace.qclojure.application.algorithm.simon — org.soulspace/qclojure 0.1.0-SNAPSHOT

gf2-add clj

(gf2-add a b)

Addition in GF(2) - equivalent to XOR

gf2-dot-product clj

(gf2-dot-product v1 v2)

Dot product over GF(2) - sum of element-wise products mod 2

gf2-find-null-space clj

(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.

gf2-find-pivot clj

(gf2-find-pivot matrix col start-row)

Find the first non-zero element in a column starting from row start-row

gf2-gaussian-elimination clj

(gf2-gaussian-elimination matrix)

Perform Gaussian elimination on a matrix over GF(2). Returns the matrix in row echelon form.

gf2-row-add clj

(gf2-row-add row1 row2)

Add row2 to row1 in GF(2) (XOR each element)

gf2-swap-rows clj

(gf2-swap-rows matrix row1 row2)

Swap two rows in a matrix

simon-algorithm clj

(simon-algorithm hidden-period backend)

(simon-algorithm hidden-period backend 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.

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:

• hidden-period: Vector representing the hidden period s (for oracle construction)
• backend: Quantum backend implementing the QuantumBackend protocol
• options: Optional map with execution options (default: {:shots 1024})

Returns: Map containing:

• :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-algorithm-legacy clj

(simon-algorithm-legacy hidden-period n-qubits)

Legacy Simon's algorithm implementation for simulation only.

This is the original implementation that works without a backend, useful for testing the linear algebra components.

Parameters:

• hidden-period: Vector representing the hidden period s
• n-qubits: Number of qubits in input register

Returns: Map containing simulation results

simon-circuit clj

(simon-circuit hidden-period n-qubits)

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.

simon-oracle-circuit clj

(simon-oracle-circuit hidden-period n-qubits)

Build the quantum circuit for Simon's oracle Uf.

Creates an oracle that implements f(x) = f(x ⊕ s) for a hidden period s. For simulation purposes, this creates a simple oracle where f(x) maps x to a deterministic output, with f(x) = f(x ⊕ hidden-period).

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.

solve-linear-system-gf2 clj

(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:

• 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