Quantum algorithm implementation validation plan (review draft)¶

English · 简体中文

This document systematically plans oracq’s algorithm validation system: it first classifies all algorithms by “how correctness is judged”, then prescribes a standard witness technique for each class, and finally gives the all-algorithm validation matrix and an implementation roadmap. Review focus: whether the classification in section 2 is complete, whether the cross-cutting mechanisms in section 4 deserve infrastructure investment, and the stage split and priorities of section 5.

1. General validation principles¶

What is validated is the semantics of RIR programs. Algorithms are generators; witnesses must act on the generated program (executed through the reference simulator or a real backend), not on the generator’s internal data structures.
At least three layers of evidence per algorithm: structural validity (IR checks, signatures, contract properties), small-scale numerical witnesses (the reference simulator cross-checked against analytic solutions or classical references), and bindability (abstract declarations keep their semantics after being bound via bind).
Three-layer input-model consistency is this repository’s distinctive invariant: the abstract / gate / qram bindings of the same algorithm must produce consistent observable semantics (QRAM word-width quantization error is allowed, with an error bound stated).
Determinism first: probabilistic assertions must operate at the distribution level (closed-form expectations, support, moments); single sample threshold assertions are forbidden; simulations must use fixed seeds or exact state vectors.
The existing layering is kept: L0 static checks (ruff, layout, documentation warnings-as-errors) → L1 structure → L2 numerical witnesses (tests/core) → L3 cross-check catalog (applications/catalog.py) → L4 real backends (tests/integration, cross-checked on real uniqc/pysparq machines, no mocks) → L5 documentation doctests.

2. Algorithm classification (by how “correct” is judged)¶

Class	Acceptance criterion	Standard witness technique	Main risk
C1 exact discrete semantics	Output distribution / action unitary equal pointwise to a truth table or exact construction	Exhaustive all-input cross-checks on small instances; the unitarity identity W†W=I; exact recovery of null spaces / secret strings	Essentially no flakiness
C2 approximate continuous semantics	Action operator ≈ the target continuous function, with an explicit error bound	Compare within tolerance against classical references (analytic solutions / matrix exponentials / high-precision numerics); convergence scans: fit error vs degree/κ/Δt to the theoretical rate	Tolerance choice masking systematic error; numerical ill-conditioning (e.g. high-degree QSP synthesis)
C3 probability-distribution semantics	The output distribution equals the closed-form expectation (mean, variance, support)	Derive the distribution from exact state vectors and cross-check per-outcome probabilities against closed forms (Krawtchouk/binomial etc.); for QAE-style algorithms, verify the estimate falls inside the theoretical confidence interval	Sampling jitter → sample assertions forbidden, exact distributions only
C4 heuristic/optimization semantics	Strictly better than a random baseline, and small instances reach known optima / theoretical scores	Distribution-level comparison against the expectation of random guessing; exhaustive-optimum cross-checks on small instances; cross-checks of the theoretical score formulas	Boundary-assertion jitter (happened once for the C3-class DQI: assertGreater failed when exactly equal to the baseline)
C5 data-access layer	Pointwise-correct query semantics + three-layer binding consistency + uncomputation	Per-address truth-table cross-checks; abstract/gate/qram triple-binding consistency; LocalExit-enforced uncomputation checks; marginal-distribution checks for superposed queries	QRAM quantization error needs an explicit bound
C6 composition skeleton	Component contracts satisfied + correct end-to-end semantics on small instances + bind invariance	End-to-end simulation + identical results before and after binding + structural-property checks (register layout, Repeat not expanded)	Components individually correct but composed semantics misaligned (register-mapping errors)

3. All-algorithm validation matrix¶

Status: ✅ adequately witnessed; 🟡 witnessed but with gaps; ❌ no witness. Modules are listed by layer.

infrastructure / data-access layer (C5)¶

Module	Contents	Status	Gaps and plans
oracles.py	XorDatabase, StatePreparation, SparseAccess, BlockEncoding across three layers	✅	Add a parametrized “triple-binding consistency” test (cross-check the same declaration binding by binding); each binding is currently witnessed independently
data_loading.py	QROM / Select-Swap	✅	Resource formulas already cross-checked; consider adding `qrom_cost` to catalog report attributes
mathfunc/	Classical functions → reversible circuits	✅	Add an explicit witness for the fixed-point quantization error bound
prepare_select.py	PREPARE/SELECT, alias	✅	alias’s clean_work=False is honestly documented; add alias triple-binding consistency

Exact discrete algorithms (C1)¶

Module	Algorithms	Status	Gaps and plans
oracle_algorithms.py	DJ/BV/Simon	✅	—
fourier.py	QFT, QFT addition	✅	—
arithmetic.py	Fixed-point add/sub/mul, Boolean networks	✅	—
number_theory.py	Modular multiplication, order finding	✅	The small-scale witnesses already note they do not extrapolate to full Shor
error_correction.py	Repetition codes	✅	—
walks.py	Coined cycle walk	✅	—
graph_walks.py	Adjacency oracle, Szegedy, MNRS	✅	The cycle’s failure has been verified as a theoretical result; adding Johnson graphs requires new witnesses (element distinctness)

Approximate continuous algorithms (C2)¶

Module	Algorithms	Status	Gaps and plans
transforms.py	Qubitization walk, QSVT sequence, OAA	✅	The sequence conventions are pinned by qsvt.py (pointwise agreement 1e-10)
qsvt.py	Phase synthesis, inversion, filtering, HS simulation, fixed-point search	✅	Convergence scans missing: batch curves of error vs degree/κ are not automated; the ill-conditioned synthesis-degree boundary (≳16) already has negative-case coverage: tests/core/test_qsvt.py:PhaseSynthesisTests.test_input_validation and TransformWitnessTests.test_transform_input_validation (covering parity violations, \|coeff\|>1, unsaturated endpoints, imaginary-part parity, ill-conditioned κ, degree 0, t=0, Δ≥1, odd/even degree violations, and similar scenarios)
hamiltonian.py	Trotter, Taylor, hamsim	✅	Trotter order-error-rate scans not done
sparse.py / block_encoding.py	Sparse BE, BE algebra	✅	—
qlss.py	CKS, Costa	🟡	Paradigm witnesses exist; missing an end-to-end cross-check case against the HHL paper’s reference values (could enter the catalog)
ode.py / lchs.py / cbmd.py / schrodingerization.py / carleman.py	ODE/PDE solvers	🟡	Each has witnesses; missing a unified “analytically solvable ODE family” convergence benchmark (the same problem through all solvers)
sde.py	Fokker–Planck	✅	OU-moment cross-checks; add an end-to-end catalog case for the SDE solver and LCHS
density.py	Purification, Gibbs	✅	Convergence scans added: tests/core/test_density.py:GibbsTests.test_error_convergence_decreases (error ∈ {0.4,0.2,0.1} monotone non-increasing + each step ≤ error, measured 5.6e-4/8.7e-5/8.7e-5) and test_error_bound_uniform_in_beta (β ∈ {0.2,0.5,1.0} grid, each point ≤ 0.1)
lowrank.py	DF/THC → BE	✅	α upper-bound tightness added: tests/core/test_lowrank.py:DoubleFactorizationTests.test_alpha_matches_closed_form_eigenvalues (independent 2×2 closed-form cross-check, places=10), test_df_alpha_tighter_than_pauli (DF α=1.4 ≤ Pauli α=1.5); ThcTests.test_thc_alpha_matches_hand_computed_bound (THC α=1.996 independent hand computation)

Probability-distribution algorithms (C3)¶

Module	Algorithms	Status	Gaps and plans
estimation.py	QPE, QAE, quantum counting, Hadamard/SWAP test	✅	The QAE confidence-interval claim is unwitnessed (only the point estimate is verified)
search.py	Grover, amplitude amplification	✅	—
integration.py	Heinrich summation/integration	✅	Closed-form mean cross-check + heinrich_rate parametric validation already witnessed (tests/core/test_integration.py:SumPreparationTests / QuantumSumTests / RateTests)
gradient.py	Jordan gradient	✅	Exact on linear + perturbed convergence already witnessed (tests/core/test_gradient.py:GradientTests.test_perturbed_linear_concentrates_with_grid_bits includes the failure-probability decay rate q_{m+1} ≤ 0.34·q_m)
qpca.py	QPCA, density-matrix exponentiation	✅	Eigenvalue readout peak cross-check + Δt first-order error rate already witnessed (tests/core/test_qpca.py:DensityMatrixExponentiationTests / QpcaTests)

Heuristic/optimization algorithms (C4)¶

Module	Algorithms	Status	Gaps and plans
variational.py	QAOA-MaxCut, VQE, ansatz	✅	One-sided witness; add the strong witness of “reaching the optimal cut on small instances”
dqi.py	DQI	✅	Pointwise distribution cross-check against closed forms (Krawtchouk); the identity-decoder baseline assertion was fixed to allow boundary equality

Application layer¶

Module	Contents	Status	Gaps and plans
qfvm.py / qham/	QFVM, QHAM	✅	Catalog cross-checks already exist
catalog.py / gallery.py	33-case cross-check catalog	✅	New algorithms (qsvt inversion, graph_walks search, data_loading, integration, qpca) not yet registered

4. Cross-cutting validation mechanisms (infrastructure investments)¶

Invariant test library (new proposal, tests/core/witness.py or similar):
- assert_unitary(program): W†W=I on the reference simulator (sampled basis states).
- assert_uncomputation(program, work_regs): work-qubit restoration (reusing the LocalExit mechanism).
- assert_bind_invariant(abstract_program, bindings): the bindings of the same open declaration produce consistent semantics (error bound parameterized).
- assert_block_equals(be, matrix, alpha): cross-check of the BE’s (0,0) block. Benefit: witnesses for new algorithms go from “each hand-rolls its own” to declarative composition, with a unified regression yardstick.
Determinism policy (codified): every probabilistic assertion must be a closed-form cross-check against the exactly simulated distribution; when the theoretical value lands exactly on the assertion boundary, use ≥/≤ with a numeric tolerance — strict inequalities are not allowed (the DQI boundary case was fixed this way).
Convergence-scan framework: provide parameter-scan tooling for C2 algorithms (error vs degree/κ/Δt), asserting the fitted slope ≥ a lower bound on the theoretical rate; store results as JSON for validation.json to aggregate.
Resource-estimation cross-checks: for every module providing a cost function (qrom_cost, the QSP degree formula, Trotter step counts), the generated program’s structural properties must agree with the cost formula (checked in both directions).
Catalog registration rule: once a new algorithm is finished it must register catalog cases (gate/qram input variants) and be wired into the real-backend cross-checks of tests/integration (no mocks).

5. Implementation roadmap¶

Stage	Scope	Prerequisite
V1	Invariant test library (4 assertion primitives) + witnesses for the in-flight modules (density/gradient/lowrank/integration/qpca) filled in per the matrix (done, 0.x iteration)	None
V2	Convergence-scan framework + convergence benchmarks for the qsvt/hamsim/ODE solvers wired into validation.json	V1
V3	Register the new algorithms in the catalog (qsvt inversion, MNRS search, Select-Swap, Heinrich integration, QPCA) + extend the real-backend cross-checks in tests/integration	V1
V4	Roll out triple-binding consistency parametrized tests (oracles/prepare_select/graph_walks/data_loading)	V1

6. Relation to existing acceptance¶

validation.md / validation.json remain the per-version acceptance records; once this plan lands, the V1–V4 deliverables are written into them by version. The algorithm coverage workboard (algorithm-coverage.md) records “what is implemented” while this document records “how correctness is proven”; the two correspond line by line.