Simon Sampling

English · 简体中文

Category C1 · Module oracq.algorithms.basics.oracle_algorithms · Stage V1

Overview

Given a function \(f: \{0,1\}^n \to \{0,1\}^m\) promised to be two-to-one with a nonzero XOR period \(s\) (i.e. \(f(x) = f(y)\) if and only if \(y = x \oplus s\)), find the period \(s\). One quantum-side sample yields a uniformly random vector \(y\) satisfying \(y \cdot s = 0\) (GF(2) dot product): the circuit applies Hadamard to input, queries the oracle, entangles away the function value on output, then applies Hadamard to input again, collapsing input onto a constraint orthogonal to \(s\). After collecting about \(n - 1\) linearly independent samples, GF(2) elimination is done on the classical side — consistent with the repository’s and the algorithm catalog’s convention, elimination lives on the classical side and the quantum circuit is responsible only for sampling.

Interface and input model

simon_sample(function)
simon_nullspace(samples, width)

API entry points: simon_sample, simon_nullspace

• simon_sample(function): function must be an XorDatabase instance (input model FO: the two-to-one function’s truth table); other types raise ValidationError at generation time. The two-to-one promise is declared by the input_promise attribute and borne by the caller.

• simon_nullspace(samples, width): purely classical post-processing. samples is a list of integer samples encoded little endian, and width (1..64) is the secret string’s bit width; it returns a tuple of basis vectors of the GF(2) null space of the samples’ row space. When the samples exactly span \(s^\perp\), the null space is one-dimensional and its nonzero element is the period \(s\); when the samples are insufficient, multiple basis vectors are kept and the caller keeps sampling.

simon_sample returns an Operation with registers input: Bits(address_width) and output: Bits(data_width). Module attributes:

Attribute	Meaning
algorithm	"simon_sample"
input_promise	"two-to-one XOR period" (the two-to-one period promise)
readout_register	"input" (reading input alone yields one orthogonality constraint)

Implementation notes

The generation sequence is: H on all of input → the oracle invoked with the function prefix via invoke → H on all of input. The output register need not be measured early inside the circuit — reading out input is already a complete sample, and the function-value entanglement on output does not enter the decision. The oracle is kept as a module call. The elimination is implemented as bit-by-bit Gaussian elimination with pivot selection: for each bit, a row among the current rows with a 1 in that bit is found and swapped in as the pivot, then the bit is cleared in the other rows by XOR; the free variables are back-substituted one by one to obtain the null-space basis.

Applicability boundary: for functions that do not satisfy the two-to-one promise, neither the readout distribution nor the elimination result is guaranteed; out-of-range samples passed to simon_nullspace (not in \(0 .. 2^{\text{width}}-1\)) raise ValidationError at generation time.

Validation approach

Category C1 (exact discrete semantics; acceptance criterion in ../development/validation-plan.md §2): the sampling distribution and the elimination result must equal the closed-form construction pointwise. Three layers of evidence:

• Structure: tests/core/test_algorithm_expansion.py:AlgorithmExpansionTests.test_legacy_imports_reference_canonical_objects (matrix criterion).

• Numerical: AlgorithmExpansionTests.test_simon_sampling_and_rank_aware_postprocess — for the two-to-one function with period \(s = 3\), gate_database(2, 1, [0, 1, 1, 0]), the input distribution is cross-checked pointwise against \(p(0) = p(3) = 0.5\); the elimination gets three closed-form cross-checks: simon_nullspace([3], 2) == (3,) (samples spanning the null space), simon_nullspace([], 3) yielding 3 basis vectors (no samples), and simon_nullspace([1, 2, 4], 3) == () (samples already full rank, the null space contains only the zero vector).

• Binding: this algorithm has no independent binding witness (matrix criterion is —).

Known gaps and planned stages

No known gaps (the gap column of the validation matrix is —); stage V1.

Related links

• Same module: Deutsch–Jozsa query, Bernstein–Vazirani secret-string readout

• Source: src/oracq/algorithms/basics/oracle_algorithms.py

• API reference: Oracle query algorithms

• Validation matrix: Validation coverage matrix

Numerical validation

Paper-grade numerical validation script: tests/verification/verify_oracles.py (group D cases), artifact out/verification/oracles.json.

Experimental design: the two-to-one linear function with period exactly \(s\), \(f(x)=\mathrm{delete}_p(x\oplus x_p s)\) (\(p\) is the lowest set bit of \(s\); after construction, two-to-oneness and the period are self-verified by classical exhaustive enumeration). Widths 3–6 bit use a gate_database truth-table oracle, while 7–8 bit use a CNOT linear implementation of the same function (the truth table’s gate count grows with \(2^n\), so wide instances switch to the register-level path; the case parameters are annotated oracle: cnot_linear); each width takes \(s\in\{1,\ 2^n-1,\ (\texttt{0x9E37\ldots}\bmod 2^n)\mathbin{|}1\}\). The sampling distribution is compared phase-sensitively, amplitude by amplitude and by TVD, against the exact joint distribution (a support set of \(2^{2n-2}\) equal-amplitude basis states, with the phase \((-1)^{x_0\cdot y}\) given in closed form); then \(n-1\) linearly independent vectors are selected deterministically from each path’s own sampled support set and handed to simon_nullspace for elimination, requiring the null space to be exactly \(\mathrm{span}(s)\). There is also an insufficient-samples case (\(n-2\) independent samples): the null space stays two-dimensional and \(s\) lies in its span. Backend paths: reference and rir-pysparq, with originir-ext added for the dense small 3–5 bit instances.

Case	Scale	Path	Metric value
simon-sampling-recovery-w3	3 bit, support set 16	reference, rir-pysparq, originir-ext	max_error = 1.1e-16, tvd = 4.4e-16, recovered 6/6
simon-sampling-recovery-w4	4 bit, support set 64	same as above	max_error = 8.3e-17, tvd = 6.7e-16, recovered 6/6
simon-sampling-recovery-w5	5 bit, support set 256	same as above	max_error = 4.9e-17, tvd = 7.8e-16, recovered 6/6
simon-sampling-recovery-w6	6 bit, support set 1024	reference, rir-pysparq	max_error = 3.1e-17, tvd = 1.0e-15, recovered 6/6
simon-sampling-recovery-w7	7 bit, support set 4096	rir-pysparq	max_error = 1.7e-17, tvd = 1.1e-15, recovered 3/3
simon-sampling-recovery-w8	8 bit, support set 16384	rir-pysparq	max_error = 9.5e-18, tvd = 1.2e-15, recovered 3/3
simon-rank-deficiency-w4	4 bit, 2 independent samples	rir-pysparq	nullspace_dim = 2, secret_in_span = True

Reproduction command:

PYTHONPATH=src /path/to/backend/python tests/verification/verify_oracles.py

Artifact path: out/verification/oracles.json.