Module simon 

Simon’s algorithm.

Given a two-to-one (or one-to-one) Boolean function f : {0,1}^n → {0,1}^n with the promise f(x) = f(y) ⇔ y = x ⊕ s for some hidden period s ∈ {0,1}^n, Simon’s algorithm recovers s with O(n) quantum queries — an exponential speed-up over the Θ(2^{n/2}) classical lower bound. It is the historical precursor to Shor’s algorithm: a single run of the quantum circuit returns a uniformly random bit-string y satisfying y · s = 0 (mod 2), and after collecting n − 1 linearly independent such constraints the hidden string is fixed (up to the trivial all-zero solution when s = 0).

Circuit (on 2n qubits)

The first n qubits form the query register, the second n the output register (this crate is little-endian, so query bit i ↦ qubit i and output bit j ↦ qubit n + j):

1. Prepare H^{⊗n} on the query register.
2. Apply the oracle U_f|x⟩|0⟩ = |x⟩|f(x)⟩.
3. Apply H^{⊗n} on the query register again.
4. Measure the query register — the outcome y is orthogonal to s.

Classical post-processing

The sampled constraints are assembled into a binary matrix and reduced to row-echelon form over GF(2); the unique non-trivial vector in the kernel is the period s. recover_period_from_constraints exposes this solver independently of the quantum sampler.

Structs

SimonResult

Outcome of simon.

Functions

recover_period_from_constraints

Recover the hidden period s from a set of constraint vectors y (each satisfying y · s = 0 (mod 2)) over n bits.

simon

Run Simon’s algorithm to recover the hidden period of a two-to-one oracle.