Genel Simon programı

Status: proposed Revision: 1 (2026-08-11) Feature flag: experimental.genericSimon=true Depends on: NM-RFC-0010 generic XorOracle<N,M>, NM-RFC-0012 typed collection and GF(2), and a separately approved measured statevector product range Implementation gate: the section 12 review record and the separate measured statevector range decision are mandatory before implementation Does not change: the five-qubit statevector ceiling, fixed Algorithm Pack 0.3 Simon fixture, oracle verification tiers, or hardware claims

1. Purpose

N/M already has the three ingredients adjacent to Simon's algorithm, but it does not yet have one honest generic Simon product:

1. NM-RFC-0010 names the required XorOracle<N,N> shape;
2. NM-RFC-0012 carries ordered measurement rows and solves bounded GF(2) systems; and
3. Algorithm Pack 0.3 contains a fixed teaching circuit for hidden mask 11.

Those facts do not compose into Simon<N>. A standard Simon instance needs 2N data/output qubits, repeated independent executions, a promise check, and rank-aware classical post-processing. At the current five-qubit statevector ceiling, the first non-degenerate size N = 3 already needs six qubits.

This RFC defines the artifacts and fail-closed gates for a future generic implementation. Revision 1 creates no parser rule, runtime path, capability entry, package export, Playground control, or statevector-ceiling increase.

2. Scope

The first implementable slice is deliberately narrow:

• compile-time N only, with N >= 3;
• an exact-version package export whose oracle is XorOracle<N,N>;
• disjoint input and output registers;
• user-supplied clean ancillas under NM-RFC-0010;
• a two-to-one Simon promise with one non-zero hidden mask;
• one circuit execution producing one ordered BitVec<N> row;
• a bounded host/tooling plan that repeats the kernel under one recorded seed;
• GF(2) rank, nullspace, and recovered-mask evidence; and
• local statevector execution only in the first published ready range.

The RFC does not add runtime-sized registers, compressed one-output-qubit oracles, adaptive unbounded sampling, noisy execution, general reversible classical compilation, or a scalability claim.

3. Oracle and promise contract

The algorithm accepts only a named, exact-version XorOracle<N,N>. It does not introduce SimonOracle<N> or weaken the existing oracle type split.

For one hidden mask s:

s != 0^N
f(x) = f(y) iff y = x or y = x xor s

The promise is an algorithm call-site precondition, not a new type. A monomorphized package must carry an nm-simon-promise@0.1 artifact containing:

• exact package specifier and export name;
• concrete N;
• canonical oracle source and specialization digests;
• verification tier and verification evidence digest;
• an exhaustive promise-check digest for every x in 0..2^N-1;
• whether all output pairs have exactly two preimages; and
• the verifier version and tolerance policy.

The published artifact must not disclose s to the algorithm runner. Test and review fixtures may retain the expected mask in a separate, access-controlled answer artifact. The promise verifier may recover a candidate mask internally, but acceptance is based on the complete pair relation, not on a few examples.

Revision 1 permits exhaustive promise verification only for a later approved ready range with N <= 5. Larger N requires a new proof artifact and RFC revision; silent sampling is not a substitute.

4. Quantum kernel

The generic quantum kernel is conceptually:

prepare |0^N>|0^N>
H on every input qubit
apply XorOracle<N,N>
H on every input qubit
measure_all input -> BitVec<N>

The output register is not measured for the row carrier. Tracing it out is part of the Simon interference semantics and is not permission to compress it to one qubit. The kernel has exactly 2N + A qubits, where A is the declared user-supplied ancilla count. Every ancilla must satisfy the restoration contract of NM-RFC-0010.

One invocation emits one ordered row. Repeating this circuit is an experiment operation, not an in-circuit runtime loop and not one sample histogram.

5. Bounded run plan

The orchestrator input is nm-simon-plan@0.1:

{
  "format": "nm-simon-plan",
  "version": "0.1",
  "oracle": "package.example@1.2.3::hidden_mask",
  "size": 3,
  "attempts": 12,
  "seed": 23,
  "backend": "browser-statevector"
}

Rules:

• size must equal the oracle specialization and is compile-time fixed;
• attempts is fixed before execution, lies in N..8N, and is at most 64;
• the seed is required and drives circuit executions in stable order;
• noise, mitigation, provider fallback, and hardware targets are rejected;
• each attempt records its ordered row, not only a histogram; and
• cancellation returns no successful recovery claim.

The runner may stop executing after rank N - 1 is reached, but the report must record requested and executed attempts. It may not silently extend the plan.

6. GF(2) post-processing

Every retained row y represents y dot s = 0 (mod 2). The existing bounded GF(2) solver is applied to the ordered row matrix.

The result is successful only when:

• the row rank is exactly N - 1;
• the nullspace has dimension exactly one;
• the unique non-zero nullspace vector passes the complete promise artifact; and
• recomputation from the retained rows yields the same result digest.

Rank deficiency is inconclusive, not a wrong mask and not an engine error. An inconsistent system, zero candidate, or promise mismatch is a verification failure.

7. Run artifact

nm-simon-run@0.1 contains:

• plan identity and canonical plan digest;
• exact oracle/package/promise binding;
• requested and executed attempts;
• ordered rows and their row digests;
• rank after each executed attempt;
• final rank and nullspace dimension;
• recovered mask only when the result is successful;
• outcome: recovered, inconclusive, cancelled, or failed;
• backend, runtime, seed, source, and specialization provenance; and
• strict integrity metadata.

The artifact stores no package credential, account token, raw browser session, or hidden expected-answer fixture.

8. Ready range

No executable range is published by revision 1. A later implementation may advertise a ready range only after all of these are true:

1. a separate measured statevector product decision permits at least six qubits without changing this RFC by implication;
2. N = 3 runs end to end with a real XorOracle<3,3> and no compressed output;
3. the complete promise verifier, kernel, ordered collection, GF(2) solve, and report reader agree across Core, CLI, Worker, and UI;
4. maximum-bound resource and cancellation tests pass; and
5. documentation prints the exact ready range next to every runnable example.

An implementation may publish N = 3 only. It must not infer N = 4 or N = 5 from available memory without retained performance and verification evidence.

9. Diagnostics

inconclusive rank is a typed result and does not use an error diagnostic.

10. Security and resource limits

• Readers reject unknown fields and unsupported versions.
• Package resolution is exact-version only and source digests are verified.
• Source, plan, row count, row width, artifact bytes, and execution time are bounded before allocation.
• The runner accepts no executable JavaScript, callback, network URL, or dynamic package registry response inside a plan.
• A failing promise never falls back to the fixed Pack 0.3 fixture.
• A requested QPU target never falls back to a simulator and is outside this RFC.

11. Acceptance

• N = 3 promise-positive, promise-negative, rank-complete, rank-deficient, zero-mask, tampered-row, and cancelled fixtures exist.
• Core, CLI, Worker, and UI produce byte-equivalent canonical reports.
• Seeded reruns reproduce the ordered row sequence.
• Package/source/promise drift fails before quantum execution.
• The fixed algorithms.simon2@0.3 teaching entry remains explicitly non-generic.
• Capability, runtime protocol, and Playground controls remain unchanged while this RFC is proposed.

12. Required review record

Approval must record reviewer identity, date, rationale, and a retained review artifact for every row. A merge, prototype, passing test, or local UI is not approval. Until all rows and the separate measured statevector decision are approved, no feature flag, parser/runtime surface, package export, capability, or Playground control may be added.

13. Implementation sequence

1. Approve the oracle promise and artifact review record.
2. Approve and publish the separate measured statevector product range.
3. Implement strict plan/promise/run readers without execution.
4. Implement the one-row kernel and ordered collection composition.
5. Compose the existing GF(2) solver and rank-aware report.
6. Add CLI/Worker/Test Explorer evidence surfaces.
7. Publish an exact measured ready range; otherwise keep the capability absent.