Tipli oracle'lar ve genel algoritmalar

• Status: proposed
• Revision: 3 (2026-07-29) — supersedes revisions 1 and 2
• Target contract: 0.2.0-experimental
• Feature flag: experimental.genericOracles=true
• Owners: language, runtime, compiler, tooling
• Depends on: NM-RFC-0001 module visibility, NM-RFC-0002 exact versioned imports, NM-RFC-0005 typed classical values, NM-RFC-0007 function results
• Does not change: stable N/M 0.1 parser, the N/M Algorithm Pack 0.2 fixed teaching circuits, or the N/M Algorithm Pack 0.3 discovery entries

Experimental implementation status

An experimental reference implementation landed on 2026-07-29 behind the closed-world experimental.genericOracles=true negotiation flag. It lowers generic source to a concrete circuit before runtime and exposes the same explicit opt-in through the core parser, CLI, worker protocol, MCP, LSP, VS Code, and browser Playground surfaces. The implementation includes exact-version Grover primitives, Tier A/Tier B verification, algorithm precondition checks, bounded modifiers, provenance carriers, and fail-closed diagnostics NM-ORACLE-001 through NM-ORACLE-020.

This note does not promote the RFC or the capability: the RFC remains proposed, the feature remains disabled by default, and cross-platform, performance, fuzzing, accessibility, and named-review promotion gates remain open in the capability manifest.

Revision 3 change log

Revision 2 resolved the verification contradiction but left four contract gaps. Revision 3 closes them:

1. Algorithm preconditions were unverified. XorOracle<N,M> guarantees only the XOR shape. Bernstein–Vazirani additionally requires an affine f, and Deutsch–Jozsa requires the constant-or-balanced promise; a valid CCNOT body can break either precondition silently. New §9.6 defines these as call-site preconditions with NM-ORACLE-018/019/020.
2. The XorOracle Tier B check was magnitude-only and would have accepted |x>|y> -> -|x>|y XOR f(x)>. §9.2 now checks the complex value, which is required for consistency with §11.3.
3. phase_kickback contradicted three of this RFC's own rules. It is removed from contract 0.2; its correct static-adapter form is specified in §23.5.
4. Generic Grover's N <= 5 was a backend ceiling, not a ready range. Diffusion needs an (N-1)-controlled Z, which exceeds the two-control limit at N >= 4. New §6.5 requires a normative ancilla-free, exact-version package.algorithms.grover_primitives@0.2 with closed concrete specializations; without it the turnkey range is N <= 3.

Revision 2 change log

Revision 1 contained a contradiction: it allowed large-N generic algorithms while also requiring every monomorphized oracle to be verified through its full 2^n x 2^n matrix. A 100-qubit XorOracle<99,1> would require 2^200 matrix elements, so the two requirements could not hold together.

Revision 2 resolves this and tightens several related decisions:

1. Verification is split into two tiers selected by oracle class, not by N (§9). Structural verification is exact and N-independent; exhaustive numeric verification is bounded by a verification ceiling.
2. Verification limits and execution limits are separated and never conflated (§9.5, §12).
3. The single Oracle<N> type is replaced by XorOracle<N,M> and PhaseOracle<N> (§7).
4. Numeric comparison uses a frozen tolerance and yields a discrete identity artifact; floating-point exactness is never claimed (§9.4).
5. ctrl is limited to two controls in this contract, and global phase under ctrl is specified (§11).
6. Scope, honest N ranges, and deferred work are stated explicitly (§5, §23).

1. Summary

N/M Algorithm Pack 0.2 intentionally ships bounded circuits for Deutsch–Jozsa, Bernstein–Vazirani, Swap Test, Hadamard Test, two-bit Phase Estimation, three-qubit phase-flip correction, the nine-qubit Shor error-correcting code, and one Ising Trotter layer. Those entries are executable and testable today, but their oracle, unitary, register size, or error model is fixed.

This RFC defines the next language boundary:

1. two typed oracle values — XorOracle<N,M> and PhaseOracle<N> — that can be passed to a generic algorithm;
2. compile-time integer generics for QReg<N> and BitVec<N>;
3. a two-tier verification model that proves each oracle satisfies its declared contract;
4. checked adjoint, bounded ctrl, and positive integer pow modifiers;
5. deterministic monomorphization before runtime or target lowering;
6. explicit diagnostics when a program requests behavior outside the bounded proposal.

The proposal does not make circuits dynamically sized at runtime and does not claim hardware execution, asymptotic speedup, or support for arbitrary unitary matrices.

2. Motivation

The current reusable circuit type accepts a concrete QReg<K> plus angle arguments. It cannot express "run this algorithm with this caller-provided oracle." As a result:

• the Grover stdlib entry freezes one marked state;
• Deutsch–Jozsa freezes one balanced function;
• Bernstein–Vazirani freezes one secret string;
• Phase Estimation freezes one unitary and its powers;
• reusable amplitude amplification and Simon-style programs cannot state their real dependency;
• callers can copy circuit bodies, but the compiler cannot prove that the copied oracle satisfies the convention the algorithm assumes.

A typed oracle contract makes the dependency visible in the type system and in the generated IR. Compile-time generics prevent one package per register width without introducing unbounded runtime allocation.

The type split matters for correctness, not only documentation. A single Oracle<4> cannot say whether q[3] is an input qubit or a bit-flip output qubit. Passing an XOR-convention oracle to an algorithm that requires a phase convention produces a silently wrong result. XorOracle<N,M> and PhaseOracle<N> make that a type error.

3. Goals

• Pass named, statically resolved oracle declarations to algorithms.
• Prove that an oracle body satisfies its declared convention.
• Preserve qubit ownership and reject overlapping register views.
• Instantiate all generic sizes and oracle symbols before simulation/export.
• Produce source-mapped diagnostics at the declaration and call site.
• Keep CLI, Worker, Playground, LSP, VS Code, QASM 3 sidecar, and package surfaces version-aligned.
• Make unsupported composition fail closed.

4. Non-goals

• Runtime-sized quantum registers.
• Closures, anonymous quantum functions, reflection, or dynamic dispatch.
• Recursive algorithms or recursive oracle calls.
• Fractional or negative pow in the first contract.
• ctrl beyond arity two, and any multi-controlled synthesis in the compiler. The bounded cases are supplied as library circuits instead (§6.5).
• Automatic synthesis from an arbitrary truth table or matrix.
• General reversible compilation of classical source.
• Automatic ancilla cleanup when the author did not provide an uncompute path.
• Coercion between oracle kinds (§7.3, §23.5).
• Quantum Phase Estimation over a generic unitary (§23.2).
• Simon's algorithm (§23.1).
• Pulse-level control or provider calibration lookup.
• A claim that a simulator run proves physical quantum advantage.

5. Scope and honest limits

This is a type-safety capability, not a scalability capability. It exists so that a caller-supplied oracle can be checked against the convention an algorithm assumes. It does not raise any execution ceiling.

The executable ranges implied by the current runtime are:

A backend ceiling is not a ready range. The ceiling says what the simulator can hold; the ready range says what a caller can actually run without writing their own gate decomposition. Every user-facing surface must quote the ready range, not the ceiling.

For Grover the two differ by a wide margin, because of two constraints that are independent of the backend ceiling:

• Tier B verification width. Every PhaseOracle<N> is Tier B (§9.3), and NM_ORACLE_VERIFICATION_MAX_WIDTH = 5 (§9.2). At N >= 6 a phase oracle is rejected by NM-ORACLE-016 during verification, not during execution.
• The §6.5 primitive set, which covers N in {2,3,4,5} only, because diffusion needs an (N-1)-controlled Z that this contract does not synthesize (§6.5, §11.2).

Both land at 5. Raising the statevector ceiling therefore does not widen Grover's ready range. Non-Clifford DJ/BV is different: it is verified by Tier A, which is N-independent (§9.1), so there the backend ceiling really is the binding constraint.

These follow from two existing constants that this RFC does not change:

• playgroundRuntimeLimits.maxQubits = 14 (lib/nm/diagnostics.ts), applied as the statevector ceiling in lib/nm/parser.ts;
• nmStabilizerMaxQubits = 100 (lib/nm/stabilizer-engine.ts), available only to Clifford-eligible programs.

Raising the statevector ceiling is explicitly out of scope for this RFC. When this scope decision was made, the runtime stored amplitudes as a Complex[] object array and the ceiling was 5. Two independent work items have since landed: NM-016 replaced the internal representation with split Float64Array lanes, and a separate change raised playgroundRuntimeLimits.maxQubits from 5 to 14. Neither was driven by this RFC, and neither widens Grover's ready range, for the reasons above. The numbers in the table above are restated from those constants; they are not a commitment made by this RFC, and this RFC must not be cited as evidence that any particular product ceiling is ready.

Documentation, gallery copy, and diagnostics must state the executable range for the concrete instantiation. A generic type parameter must never be presented as evidence that every N is runnable.

6. Proposed source model

6.1 Oracle declaration

xor_oracle parity_101(x: QReg<3>, out: QReg<1>) {
  CNOT(x[0], out[0]);
  CNOT(x[2], out[0]);
}

phase_oracle marked_101(q: QReg<3>) {
  X(q[1]);
  H(q[2]);
  CCNOT(q[0], q[1], q[2]);
  H(q[2]);
  X(q[1]);
}

An oracle declaration is a named operation over its entire declared register set. Contract 0.2 does not accept measurement, reset, noise, sampling, expectation, training, classical mutation, qubit allocation, or nested runtime control in the body.

The gate set contains no CCZ; a doubly-controlled phase flip is written with H-conjugation around CCNOT, as above. §9.3 accounts for this.

6.2 Generic algorithm declaration

algorithm bernstein_vazirani<const N: Int>(
  x: QReg<N>,
  out: QReg<1>,
  oracle f: XorOracle<N, 1>
) -> BitVec<N> {
  X(out[0]);
  H(out[0]);
  H(x[0..N - 1]);
  f(x, out);
  H(x[0..N - 1]);
  return measure_all(x[0..N - 1]);
}

N is a compile-time value. The compiler resolves the register width, ranges, index expressions, loop bounds, return width, and oracle type before producing executable IR.

6.3 Calling a generic algorithm

module recover_secret;

fn main() -> Result<BitVec<3>, Error> {
  let x: QReg<3> = qreg[3];
  let out: QReg<1> = qreg[1];
  let secret = bernstein_vazirani<3>(x, out, oracle: parity_101);
  return ok(secret);
}

Omitting <3> may be accepted only when a single value can be inferred from the concrete register and oracle types. Ambiguous inference is an error.

6.4 Generic Grover carrier

algorithm grover<const N: Int, const R: Int>(
  q: QReg<N>,
  oracle mark: PhaseOracle<N>
) {
  H(q[0..N - 1]);
  for r in 0..R - 1 {
    mark(q);
    diffusion<N>(q);
  }
}

The iteration count R is an explicit const parameter. The const generic grammar (§7.5) deliberately cannot express floor(pi/4 * sqrt(2^N)), and this RFC does not extend the grammar with square-root or floor intrinsics. Keeping the grammar closed and checkable is worth more than computing R for the caller; supplying a suboptimal R lowers success probability rather than producing a silently wrong answer.

diffusion<N> is a closed standard-library facade supplied normatively by §6.5. It must resolve to a concrete checked circuit before oracle verification; contract 0.2 does not add a general generic-circuit declaration kind.

The first contract does not allow a runtime oracle value to be stored in an array, returned, or selected with if.

6.5 Multi-controlled phase flips in the standard library

Both diffusion<N> and any PhaseOracle<N> that marks a specific basis state require an (N-1)-controlled Z. The ctrl language modifier is limited to two controls and performs no synthesis (§11.2), so:

• N = 2 needs CZ — native;
• N = 3 needs CCZ, written H(t); CCNOT(a,b,t); H(t) — within the limit;
• N = 4 needs a three-controlled phase flip — outside the limit;
• N = 5 needs a four-controlled phase flip — outside the limit.

Contract 0.2 does not relax the language limit to close this. Instead source imports exactly:

use package.algorithms.grover_primitives@0.2;

The immutable package exports the concrete fixed-width circuits mcz2, mcz3, mcz4, mcz5, diffusion2, diffusion3, diffusion4, and diffusion5. The mcz<N> and diffusion<N> names used in generic source are a standard-library facade, not registry identifiers. During monomorphization a closed, contract-versioned specialization table maps each N in {2,3,4,5} to the matching concrete export. Any other N fails with NM-ORACLE-004. This is deterministic symbol selection, not compiler gate synthesis, and it requires no generic-circuit extension to NMStdLibraryEntry.

§8 already permits checked circuit calls inside an oracle body, so a user's phase_oracle and the generic Grover carrier call the same verified concrete circuit. Synthesis lives in immutable package source whose correctness is fixtured once.

The decomposition must be ancilla-free, using an explicitly frozen parity phase construction over native P, CP, and CNOT gates. N = 2 uses the native CP(PI) form; wider specializations compute subset parities with CNOT, apply the required signed single-qubit P angle, and uncompute the parity. For every concrete export, package source and fixtures freeze the ordered gate sequence, all P/CP angles, the maximum gate count and depth, and the ideal full matrix including global phase. Referring only to a recursive construction is not a reproducible package specification. An ancilla-based v-chain is rejected for two independent reasons: §8 forbids allocation inside an oracle, and at N = 5 a v-chain needs two ancilla qubits, putting the program at seven qubits and past the statevector ceiling.

Note that this affects user oracle bodies, not only the diffusion operator. Marking a specific basis state at N = 4 or N = 5 requires the same multi-controlled phase flip, so without the corresponding concrete mcz4 or mcz5 export a caller cannot write a conforming PhaseOracle<4> or PhaseOracle<5>.

Without these packages the turnkey range for generic Grover is N <= 3.

7. Core types

7.1 XorOracle<N, M>

XorOracle<N, M> is a closed, statically named operation over an N-qubit input register and a disjoint M-qubit output register, implementing

|x> |y>  ->  |x> |y XOR f(x)>

for some f: {0,1}^N -> {0,1}^M.

Required properties:

• the input register is returned unchanged;
• the output register is XORed with a function of the input only;
• input and output registers are disjoint (NM-ORACLE-006);
• no measurement, reset, noise, allocation, or runtime control.

7.2 PhaseOracle<N>

In contract 0.2, PhaseOracle<N> is a marking oracle: an operation over N qubits that is diagonal in the computational basis with entries in {+1, -1}, implementing

|x>  ->  (-1)^g(x) |x>

for some g: {0,1}^N -> {0,1}.

U^2 = I follows from the diagonal {+1,-1} condition and is not an independent requirement; implementations may assert it as a cheap sanity check.

The general unit-modulus diagonal operation is deliberately not defined here. Its only current consumer would be Quantum Phase Estimation, which is out of scope (§23.2). PhaseOracle<N> permanently means the {+1,-1} marking contract defined above; a future QPE RFC must introduce a separately named type such as DiagonalUnitary<N> rather than widening this type and silently changing existing source semantics.

7.3 Coercion from XorOracle<N, 1> to PhaseOracle<N>

Deferred out of contract 0.2. The design is specified in §23.5.

Revision 2 specified this as let mark = phase_kickback(f, aux). That form contradicted three rules of this RFC simultaneously:

• it bound an oracle value to a variable, which §6.4 forbids;
• it captured a runtime qubit, making it the closure construction that §4 lists as a non-goal;
• it exempted the composite from the "every PhaseOracle is Tier B" rule of §9.2 without justification.

The |-> precondition on aux was also asserted rather than established by any mechanism in the contract.

Contract 0.2 therefore defines no coercion in either direction. A marking oracle is written directly as a phase_oracle declaration (§6.1). Since Grover is bounded at N <= 5 and its oracles are hand-written at that size, the coercion buys little in this contract, and deferring it removes the contradiction rather than papering over it.

7.4 BitVec<N>

BitVec<N> is an immutable ordered measurement carrier. It supports:

• bits[i] with compile-time checked bounds;
• bits_to_int(bits);
• equality against a same-width literal;
• deterministic JSON/IR serialization;
• return through NM-RFC-0007 Result<T, Error>.

It does not support mutation or unbounded concatenation in 0.2.

7.5 Const generic expressions

The first proposal permits only checked integer expressions built from:

• literals;
• declared const generic names;
• + and -;
• multiplication or division by a positive integer literal;
• closed ranges derived from those expressions.

Expressions must evaluate to finite non-negative safe integers before AST lowering. Runtime classical values cannot determine a register width. No square-root, floor, logarithm, or other intrinsic is added by this RFC.

8. Oracle effect and ownership rules

An oracle is accepted only when all reachable operations are bounded and belong to the whitelist below. Because §4 forbids measurement, reset, noise, and runtime control, unitarity of the body is a syntactic consequence rather than a semantic proof obligation; NM-ORACLE-002 is a whitelist check and should not be over-engineered into an effect system.

Allowed:

• supported unitary gates;
• checked circuit/oracle calls;
• compile-time for;
• compile-time if over const values, when introduced separately;
• adjoint, ctrl within the arity limit of §11.2, and positive integer pow;
• barriers, if the carrier records them as non-semantic scheduling metadata.

Rejected:

• measure, syndrome, sample, or expect;
• reset;
• @noise or mitigation;
• train, gradient, dataset encoding with data-dependent normalization;
• runtime if, match, or until;
• allocation inside the oracle;
• aliasing the same physical qubit into two distinct operands;
• leaving a declared clean ancilla dirty.

Register slices are views, not copies. The call:

combine(q[0..2], q[2..4]);

fails when the callee requires disjoint ownership because q[2] overlaps.

9. Verification model

Satisfying §8 makes a body well-formed. It does not establish that the body implements the convention its type declares. That is the job of this section.

Verification is selected by oracle class, not by N.

9.1 Tier A — structural verification (exact, N-independent)

Tier A applies to an XorOracle<N, M> whose body uses no ancilla and satisfies all of:

1. every gate is drawn from {X, CNOT, CCNOT};
2. every gate target lies in the output register;
3. every gate control lies in the input register.

Under these conditions the declared form of §7.1 holds by construction: each gate XORs one monomial of the input into one output bit, and no operation ever touches the input register. The proof is compositional and requires no simulation.

Properties of Tier A:

• cost is O(gate count);
• arithmetic is integer/GF(2) only, with no floating point anywhere;
• it is N-independent, so it applies at N = 99 exactly as at N = 3;
• it covers CCNOT bodies, which are non-Clifford and therefore outside any stabilizer method.

Tier A is a sufficient condition, not a complete one. A valid XorOracle written in a shape outside rules 1–3 is not accepted by Tier A. The compiler records NM-ORACLE-013 as a non-fatal fallback warning and attempts Tier B. If the total width exceeds the Tier B ceiling, NM-ORACLE-016 is the fatal diagnostic and carries the recorded fallback reason. This is fail-closed without incorrectly rejecting a body that bounded exhaustive verification can prove.

Discrete artifact. Tier A emits the canonical algebraic normal form (ANF) for every output bit after all checked circuit calls have been expanded. Each monomial is a sorted tuple of unique input indices; the empty tuple is the degree-zero constant. Duplicate monomials cancel modulo two, remaining monomials are lexicographically sorted, and output lists follow register order. The canonicalization is normative: a pair of identical CCNOT contributions must cancel and cannot leave a false nonlinear marker. For CNOT-only bodies the artifact reduces to the GF(2) matrix row, which for Bernstein–Vazirani is exactly the secret string s. The artifact is exact and feeds the oracle identity of §16.

Stabilizer tableau extraction is not normative. For the CNOT-only linear subclass, conjugating Pauli generators through the tableau extracts the same GF(2) map exactly and without a reference circuit. That is a legitimate and useful golden-test aid — it lets a test assert "this oracle implements s = 1011" — and implementations may use it as a cross-check. It cannot serve as the normative contract check, because it does not apply to CCNOT bodies.

9.2 Tier B — exhaustive numeric verification (bounded)

Tier B applies to every oracle that is not accepted by Tier A, and to every PhaseOracle<N>.

The monomorphized concrete circuit of total width n is evaluated over all 2^n computational basis inputs to construct the 2^n x 2^n matrix, which is then checked against the declared convention.

Tier B requires n <= NM_ORACLE_VERIFICATION_MAX_WIDTH = 5, giving at most a 32 x 32 matrix. An oracle that requires Tier B at greater width is rejected with NM-ORACLE-016.

Checks, with tau from §9.4:

Here ‖A‖∞ is the maximum absolute row sum and ‖A‖₂ is the induced spectral norm. Defining both norms is part of the contract; implementations cannot substitute an entrywise maximum while retaining the same tolerance. The leakage operator check covers the entire clean-ancilla input subspace, including superpositions, rather than only testing its computational-basis columns independently.

The XorOracle row compares the complex value, not the magnitude. A magnitude-only comparison would accept |x>|y> -> -|x>|y XOR f(x)> and every other phase-carrying variant of the permutation. That is not the semantics declared in §7.1, and the sign becomes physically observable as soon as the oracle appears under ctrl (§11.3). XorOracle is granted no global phase freedom.

Discrete artifact. After the tolerance check passes, the result is snapped to a discrete value — the truth table f for XorOracle, the sign vector in {+1,-1}^(2^N) for PhaseOracle — and that discrete value, not the floating-point matrix, is what is stored, hashed, and compared in fixtures.

9.3 Why PhaseOracle is always Tier B

A gate-wise structural rule cannot establish diagonality for phase oracles. The gate set contains no CCZ, so a doubly-controlled phase flip is written as H(t); CCNOT(a, b, t); H(t), and marking a specific basis state requires X-conjugation around it. Neither H nor X is diagonal, so the body is not gate-wise diagonal even though the composed unitary is.

This costs nothing in practice: PhaseOracle<N> is capped at N <= 5 by the statevector execution limit regardless (§5), which is exactly the Tier B verification ceiling.

9.4 Frozen tolerance and floating-point honesty

NM_ORACLE_VERIFICATION_TOLERANCE = 1e-10, frozen by this contract and versioned with it.

The contract does not claim exact mathematical equality for any floating-point comparison. All Tier B statements are tolerance statements.

Reproducibility caveat: gate matrices for Rx, Ry, Rz, P, and U are built from Math.cos and Math.sin, which IEEE-754 does not require to be correctly rounded and which may therefore differ in the last bits across platforms and engines. A frozen tolerance and byte-identical golden fixtures cannot both be assumed for such bodies. This contract resolves it by requiring that the stored artifact be the discrete value of §9.2, not the matrix. Tolerance absorbs the platform difference; the discrete artifact is then exactly reproducible and safely hashable.

No IEEE-754 matrix path may assert bit-level determinism, including paths that contain 1/sqrt(2) or nontrivial phase roots. An implementation may introduce a separately versioned symbolic algebraic-number carrier and prove exact equality inside that carrier; absent such a carrier, every Tier B matrix statement is tolerance-based. This RFC neither defines nor requires symbolic arithmetic.

9.5 Verification limits are not execution limits

These are independent and must never be conflated in code, diagnostics, or documentation:

• Verification tier answers "may this body carry this type?" It is chosen by oracle class (§9.1, §9.2).
• Execution limit answers "which backend can run this concrete circuit, and up to what width?" It is the existing backend gate-support and qubit-ceiling check (§12).

A Tier A CCNOT-bearing XorOracle<40,1> is a well-typed, fully verified oracle that no current backend can execute. That combination is legal, must produce a verification pass and an execution diagnostic, and must not be reported as a type error.

9.6 Algorithm preconditions

Oracle type conformance is necessary but not sufficient. XorOracle<N,M> guarantees the shape |x>|y> -> |x>|y XOR f(x)> for some f. Individual algorithms require more of f. Those requirements are algorithm preconditions, evaluated at the call site during monomorphization against the oracle's discrete artifact (§9.1, §9.2). They are not oracle contract checks and do not introduce new oracle types.

Two preconditions are normative in contract 0.2.

Affine — Bernstein–Vazirani. BV recovers s only when f(x) = s·x XOR c. A surviving degree-two-or-greater monomial in canonical ANF makes f nonlinear; the mere presence of CCNOT syntax does not, because equal contributions can cancel modulo two. BV's interference then produces a measurement distribution with no defined meaning, and it fails silently rather than loudly.

• Tier A: the artifact is a per-output-bit monomial list, so f is affine iff every monomial has degree <= 1. Exact, O(monomials), N-independent.
• Tier B: read the truth table and check that its algebraic normal form has degree <= 1.
• Violation: NM-ORACLE-018.

Constant-or-balanced — Deutsch–Jozsa. DJ is a promise problem; for an f that is neither constant nor balanced the output carries no specified algorithmic meaning.

• If f is affine, the promise is decidable directly from the artifact at any N, with no enumeration: s = 0 gives a constant f, and s != 0 gives an exactly balanced f.
• If f is nonlinear and its total concrete width is at most NM_ORACLE_VERIFICATION_MAX_WIDTH, the call-site checker materializes the bounded truth table solely to count its Hamming weight. A Tier A oracle stays Tier A; algorithm-precondition evaluation never changes its verification tier.
• Above that call-site exhaustive ceiling, contract 0.2 intentionally does not add a separate large-N nonlinear balance solver. This is a bounded contract choice, not a claim that every sparse ANF subclass has the same complexity as an unrestricted Boolean function.
• Violation: NM-ORACLE-019. A nonlinear f whose promise is outside the contract's bounded decision procedure: NM-ORACLE-020.

Preconditions are declared on the algorithm, recorded in the monomorphization record and the QASM 3 sidecar, and reported at the call site, naming both the algorithm and the oracle. A precondition failure is never reported as an oracle contract failure; the oracle may be perfectly valid for a different algorithm.

10. Ancilla contract

Ancilla remains explicit and caller-supplied:

xor_oracle compare(
  x: QReg<4>,
  out: QReg<1>,
  scratch: CleanAncilla<2>
) {
  // scratch must return to |00>
}

CleanAncilla<K> means:

• the caller supplies K qubits known to be in |0...0>;
• the oracle may use them;
• the restoration postcondition is verified numerically under Tier B, per §9.2, over the entire clean-ancilla input subspace. Any ancilla-using oracle is therefore Tier B and bounded by NM_ORACLE_VERIFICATION_MAX_WIDTH, counting ancilla in the total width;
• failure to establish the postcondition rejects the declaration (NM-ORACLE-007).

Syntactic compute/uncompute pairing may be used as an early diagnostic to give a better error message before the numeric check runs. It is explicitly not normative: proving uncompute statically is undecidable in general, and the numeric check is both exact within tolerance and cheap at this width.

The compiler never inserts a guessed uncompute sequence.

11. Modifiers

11.1 Adjoint

adjoint oracle_name(q);
inverse oracle_name(q);
inv @ oracle_name(q);

All three spellings normalize to one IR modifier. The existing inverse circuit_name(...) source spelling remains compatibility syntax and must retain byte-identical behavior for stable 0.1 programs.

Implementation requirement. The historical adjoint implementation used regular-expression source-text expansion in lib/nm/parser-source-preprocessing.ts and could not carry ctrl, pow, or generics. The experimental implementation migrates stable adjoint/inverse and generic modifiers to the NMQuantumModifier node of §13 while preserving the concrete expansion and byte-identical behavior required for stable 0.1 programs. There is one shared inversion path; generic lowering additionally retains the modifier node and provenance metadata.

11.2 Controlled application

ctrl(q[0]) @ U(q[1]);
ctrl(q[0..1]) @ oracle_name(q[2..5]);

Contract 0.2 limits controlled application to at most two controls in total, matching the native arity of CCNOT and CSWAP. A request for three or more controls is rejected with NM-ORACLE-017. No multi-controlled synthesis is performed, because the ancilla-based v-chain construction would require allocating qubits inside the oracle, which §8 forbids. Multi-controlled synthesis is deferred to a separate RFC (§23.3).

Controls must be written explicitly as qubit references. Revision 1 allowed a bare control count (ctrl(2) @ Z(q[2])); that spelling is withdrawn because it does not say which qubits control.

ctrl(controls) @ oracle_name(...) is accepted only when every gate in the oracle body has a controlled counterpart in the supported gate set. The set contains no CRx, no controlled U, no controlled RXX/RYY/RZZ, no controlled iSWAP, and no three-controlled X. Any body reaching outside that closure fails with NM-ORACLE-008. Tooling and documentation must describe this as "controlled application over a named subset", never as general ctrl support.

The compiler rejects control/target overlap (NM-ORACLE-005).

11.3 Global phase under control

GPhase is a supported gate and is stabilizer-native. Under control, a global phase becomes a relative phase:

ctrl(c) @ GPhase(theta)  ==  P(theta) on c

Consequences, all normative:

• for any oracle that may appear under ctrl, equivalence must be checked including global phase, not up to global phase;
• adjoint must negate the GPhase angle;
• §21 carries a dedicated fixture for a GPhase-bearing body under ctrl.

Revision 1's acceptance criterion "equivalent up to global phase" was unsound for controlled application and is corrected in §21.

11.4 Positive integer power

pow(4) @ phase_oracle_name(q);

Contract 0.2 expands a positive compile-time integer power. Zero, negative, fractional, and runtime powers fail closed. Expansion is bounded by a total expanded gate-count budget checked before expansion begins, not only by the value of the exponent (NM-ORACLE-009). A later RFC may define fractional gate powers; this RFC does not.

12. Monomorphization and limits

Generic declarations do not reach the runtime. Before execution/export the compiler:

1. resolves the exact package/module declaration and any closed standard-library facade to its concrete export;
2. infers or validates every const argument;
3. substitutes register widths and integer expressions;
4. expands compile-time loops and modifiers;
5. validates qubit ownership and oracle effects (§8);
6. runs the verification tier selected for each oracle (§9) and then the algorithm preconditions of §9.6 at each call site;
7. checks the existing parser/compiler/runtime resource budgets;
8. emits concrete source-mapped IR.

The active target remains authoritative:

• statevector programs remain subject to the statevector qubit limit;
• eligible Clifford programs may use the bounded stabilizer backend;
• non-native target gates must lower completely or fail;
• package, IR, source, statement, depth, and expansion budgets continue to apply.

Per §9.5, a program may pass step 6 and fail step 7. The generic type system does not imply that every N is executable on any backend.

13. AST and IR carrier

The parser adds independently versioned nodes:

type NMOracleKind = "xor" | "phase";

type NMOracleDeclaration = {
  kind: "oracle-declaration";
  oracleKind: NMOracleKind;
  name: string;
  constParameters: NMConstGenericParameter[];
  parameters: NMOracleParameter[];
  body: NMStatement[];
  sourceRange: NMSourceRange;
};

type NMAlgorithmDeclaration = {
  kind: "algorithm-declaration";
  name: string;
  constParameters: NMConstGenericParameter[];
  parameters: NMAlgorithmParameter[];
  resultType?: NMTypeReference;
  body: NMStatement[];
  sourceRange: NMSourceRange;
};

type NMQuantumModifier = {
  kind: "quantum-modifier";
  modifier: "controlled" | "adjoint" | "power";
  controls?: NMQubitRef[];
  power?: number;
  operation: NMUnitaryCall;
};

type NMOracleVerification = {
  tier: "structural" | "exhaustive";
  artifact: NMOracleDiscreteArtifact;
  tolerance?: number;
};

The executable IR contains only concrete calls and operations. The QASM 3 sidecar preserves the original generic declaration identity, concrete arguments, oracle discrete artifact and hash, verification tier, and expansion/source-map table. A closed standard-library facade also records the exact package identity, requested facade plus const arguments, and selected concrete export; replay never reruns selection against a newer table.

Unknown fields or future contract versions fail closed.

14. Diagnostics

Every diagnostic carries the declaration location, call location when applicable, concrete generic arguments, and one actionable recovery hint. NM-ORACLE-013 is a warning, not a rejection; it must name the offending gate when applicable and identify the first source-ordered cause: ancilla use, the gate set, a target outside the output register, or a control outside the input register. NM-ORACLE-016 must report the computed total width, the ceiling, and the recorded NM-ORACLE-013 fallback reason. NM-ORACLE-018 must name the offending canonical higher-degree monomial. NM-ORACLE-018/019/020 are reported at the call site and must state that the oracle itself is valid and may be used with a different algorithm.

15. Tooling behavior

CLI

Experimental source requires:

nm check main.nm --experimental-generic-oracles
nm run main.nm --experimental-generic-oracles
nm export main.nm --to qasm3 --experimental-generic-oracles

JSON output records the effective flag, concrete instantiations, oracle identities, verification tier per oracle, and expansion budgets.

Language Server and VS Code

Clients negotiate:

{
  "initializationOptions": {
    "nm": {
      "experimental": {
        "genericOracles": true
      }
    }
  }
}

Required editor behavior:

• completion for oracle/algorithm symbols and const parameters;
• hover showing concrete/inferred widths, verification tier, and the executable range for the concrete instantiation;
• go-to-definition through workspace/package imports;
• references and rename respecting public/private visibility;
• source-mapped diagnostics at both declaration and call;
• semantic tokens for xor_oracle, phase_oracle, algorithm, const generics, and modifiers.

Playground and Worker

The session toggle is off by default. Worker requests carry the effective feature bit and return the concrete expansion summary and verification tier. A cancelled expansion or run cannot overwrite a newer editor result.

16. Package and reproducibility policy

• Generic packages use exact versions under NM-RFC-0002.
• Closed generic standard-library facades are resolved before runtime through contract-versioned specialization tables. Registry and lockfile identities always use concrete NM-RFC-0002 package identifiers; angle-bracket generic syntax never appears inside a package identifier.
• Lockfiles record the package version and canonical source integrity.
• Oracle identity includes: canonical module and declaration name, oracle kind, source/package version, concrete widths after monomorphization, ordered compile-time parameters, verification tier, and the hash of the discrete artifact of §9.1/§9.2.
• Two oracle values with different identities are not silently interchangeable in reproducibility artifacts.
• Experiment records store concrete generic arguments and oracle artifact hashes.
• Workspace snapshots preserve original generic source plus the compiler contract version.
• A changed oracle body with the same package identity is an integrity error.
• Public package publication still requires the existing license, signature, moderation, and immutable-version policies.

17. Export policy

OpenQASM 3

Strict export receives only the concrete expanded circuit. N/M-only generic and oracle identity lives in the versioned sidecar. If expansion contains an operation outside the frozen strict carrier and target lowering cannot remove it, export fails.

Qiskit, Cirq, and PennyLane

Framework exporters may emit named concrete helper functions, but must not claim that the target framework preserved the N/M type/verification result. The export provenance records:

• original N/M declaration and oracle kind;
• concrete width;
• verification tier and discrete artifact hash;
• modifier expansion;
• unsupported or comment-only semantics.

18. Security and resource controls

• Parse and expansion byte limits run before allocation-heavy work.
• Generic instantiation count is bounded per program.
• Expansion detects direct and indirect recursion.
• pow gate-count growth is checked before expansion (§11.4).
• Tier B allocates at most 2^NM_ORACLE_VERIFICATION_MAX_WIDTH squared complex entries, bounded by construction; the ceiling is checked before allocation.
• Source maps and diagnostics have bounded counts and message sizes.
• Package resolution performs no network access from the parser/runtime.
• Oracle hashes are integrity identifiers, not secrecy mechanisms.
• User source and marked-state choices must not be placed in telemetry without the existing privacy/consent contract.

19. Migration and compatibility

Stable N/M 0.1 source parses identically when the feature is disabled. New keywords are rejected with NM-ORACLE-001 rather than partially interpreted. There is no automatic rewrite from the fixed Algorithm Pack entries to generic algorithms.

Future readers must either:

• support the exact 0.2.0-experimental AST/IR carrier; or
• provide an explicit lossless migration with permanent fixtures.

Silent best-effort migration is forbidden.

20. Staged implementation

1. Adjoint modifier migration: replace the source-text adjoint expansion with the NMQuantumModifier AST node (§11.1). No generics yet.
2. Parser-only experimental: xor_oracle/phase_oracle/algorithm declarations, const generics, feature negotiation, syntax diagnostics; no execution.
3. Concrete monomorphizer: deterministic call expansion, specialization selection, and source maps. No generic operation reaches verification or runtime.
4. Tier A structural verifier: dataflow rules, canonical ANF artifact, NM-ORACLE-013 fallback fixtures.
5. Tier B exhaustive verifier: matrix construction from the monomorphized concrete circuit, frozen tolerance, discrete artifact snapping, and NM-ORACLE-014/015/016 fixtures.
6. Algorithm precondition checker: affine and constant-or-balanced checks over the discrete artifact, with NM-ORACLE-018/019/020 fixtures (§9.6).
7. Generic Deutsch–Jozsa and Bernstein–Vazirani over XorOracle<N,1>, including the large-N Clifford stabilizer path.
8. ctrl within the two-control limit, plus the GPhase rule and fixtures.
9. package.algorithms.grover_primitives@0.2 with concrete mcz2 through mcz5 and diffusion2 through diffusion5, plus the frozen facade specialization table; ancilla-free over P/CP/CNOT, with explicit source sequences, angle/gate/depth budgets, and equivalence fixtures against the ideal matrices (§6.5).
10. Generic Grover over PhaseOracle<N>, N <= 5, with the ready range stated in every user-facing surface.
11. Compiler/export parity: lowering, QASM 3 sidecar, Qiskit/Cirq/PennyLane provenance.
12. Tooling parity: CLI, Worker, Playground, LSP, VS Code, MCP, and docs.
13. Preview evaluation: cross-platform matrix, packed artifacts, hostile inputs, fuzzing, performance ratchets, and named review.

Stage 9 is a hard prerequisite of stage 10, not an optimization. Without it a caller can write neither diffusion<4> nor a conforming PhaseOracle<4>, and the generic Grover package would ship with a ready range of N <= 3 while its type signature suggested N <= 5.

Deutsch–Jozsa and Bernstein–Vazirani are sequenced before Grover deliberately. The complete algorithms use only X, CNOT, and H; their oracle bodies use X/CNOT, are fully Clifford, run on the stabilizer backend at large N, and are verified by Tier A without any floating-point comparison. Grover requires Tier B, an (N-1)-controlled Z that this contract does not synthesize, and caps at N <= 5. Sequencing the higher-risk and narrower-range algorithm first would be a mistake.

21. Acceptance criteria

The capability cannot move from experimental to preview until:

• every syntax/semantic diagnostic has positive and negative fixtures, including all of NM-ORACLE-013 through NM-ORACLE-020;
• old 0.1 AST/runtime golden fixtures remain byte-identical;
• direct Core, Worker, CLI, LSP, VS Code, and Playground results agree;
• Tier A verification is exercised at small and large N on the same oracle family, and its discrete artifact matches the tableau-extracted GF(2) map for the CNOT-only subclass;
• canonical Tier A ANF fixtures prove that duplicate monomials cancel modulo two and that a duplicated CCNOT contribution does not trigger NM-ORACLE-018;
• Tier B verification produces the same discrete artifact on every platform in the support matrix, with the frozen tolerance documented and no claim of bit-level matrix equality;
• a permutation carrying a -1 phase — |x>|y> -> -|x>|y XOR f(x)> — is rejected as an XorOracle by Tier B, proving the check is on the complex value and not the magnitude (§9.2);
• a CCNOT-bearing oracle that is a valid XorOracle is accepted by §9.1 and simultaneously rejected at a Bernstein–Vazirani call site by NM-ORACLE-018, and an f that is neither constant nor balanced is rejected at a Deutsch–Jozsa call site by NM-ORACLE-019;
• an affine oracle's DJ promise is decided from the artifact with no enumeration at an N far beyond the Tier B ceiling (§9.6);
• a nonlinear Tier A oracle inside the call-site exhaustive ceiling has its DJ promise evaluated without changing verification tier, while the equivalent large-width call fails with NM-ORACLE-020;
• every concrete export of package.algorithms.grover_primitives@0.2 matches its ideal matrix within the frozen tolerance for N in {2,3,4,5}, including global phase, matches its frozen gate/depth budget, uses no ancilla, and keeps the total program width within the statevector ceiling;
• generic Grover is demonstrated end-to-end at N = 4 and N = 5 using those packages, or the published ready range is corrected to N <= 3;
• generic and manually expanded circuits agree for the bounded reference set, including global phase for every oracle usable under ctrl;
• a GPhase-bearing body under ctrl has a dedicated fixture proving the phase becomes relative (§11.3);
• control/target aliasing, three-control requests, and dirty ancilla cases fail closed;
• an oracle that verifies but cannot execute on any backend produces a verification pass plus an execution diagnostic, never a type error (§9.5);
• recursive or explosive expansion is rejected before excessive allocation;
• strict QASM 3 external-parser conformance passes for expanded supported programs;
• package lock, snapshot, experiment, and sidecar readers preserve oracle identity, verification tier, and concrete arguments;
• current-candidate Windows/Linux and Node matrix evidence is complete;
• documentation distinguishes local simulator evidence from hardware evidence, and states the executable range next to every generic example.

22. Relationship to Algorithm Pack 0.2 and 0.3

The Algorithm Pack 0.2 and 0.3 entries remain valid, fixed, versioned teaching circuits. This RFC does not retroactively label them generic.

The fixed entries give users executable value now; the proposed type system prevents future generic APIs from being simulated with copied, unchecked syntax.

23. Deferred work

23.1 Simon's algorithm

Deferred. There are three independent blockers, and the record must not reduce them to one:

1. Width. XorOracle<N,N> needs 2N qubits. Against the statevector ceiling of 5 this gives N <= 2, which is degenerate. The Pack 0.3 entry ships a fixed mask with a compressed single output qubit for exactly this reason.
2. Repeated sampling. Simon requires O(N) independent shots. The result is not a single circuit; it is a circuit plus a classical loop over shots.
3. GF(2) linear solver. Recovering the hidden string requires solving a linear system over GF(2) in the standard library, plus handling the rank-deficient case.

Blockers 2 and 3 are language and standard-library problems well outside the oracle contract. Removing only the width ceiling does not unblock Simon.

23.2 Quantum Phase Estimation

Deferred, and removed from contract 0.2 entirely.

Naive expansion of pow(2^k) @ U grows exponentially in k in gate count and will be rejected by the §11.4 budget. The algorithmic point of QPE is that controlled U^(2^k) is constructed directly for structured U, not by repetition, so a pow-expansion QPE delivers no algorithmic benefit while guaranteeing a budget violation. The width is also bounded by P + N <= 5.

A future QPE RFC must specify direct construction of controlled powers and a separately named general unit-modulus diagonal type, as required by §7.2.

23.3 Multi-controlled synthesis

Deferred to a separate RFC. Synthesizing an (N-1)-controlled Z requires either a v-chain with allocated ancilla — forbidden by §8 — or relative-phase Toffoli ladders whose correctness argument is not part of this contract.

What is deferred is general ctrl(k) synthesis in the compiler for arbitrary k and arbitrary target operations. The bounded cases this contract actually needs are closed instead by the fixtured standard library circuits of §6.5, and ctrl remains bounded at two controls as a language modifier (§11.2).

23.4 Statevector representation

Delivered by NM-016 outside this RFC and explicitly not a dependency in either direction (§5). The runtime now uses split Float64Array real/imaginary lanes with an exact 2^n * 16-byte state payload while preserving public complex snapshots. The five-qubit product ceiling remains unchanged; increasing it still requires a separate measured product decision.

23.5 XOR-to-phase coercion

Deferred from §7.3. When reintroduced it must be a static, named adapter declaration — not a value-producing expression, and not a compiler intrinsic recognized at an argument position:

phase_oracle from_xor<const N: Int>(
  q: QReg<N>,
  f: XorOracle<N, 1>,
  aux: MinusAncilla<1>
) {
  f(q, aux);
}

Requirements for the contract that reintroduces it:

• the adapter is a declaration carrying an identity under §16, resolved and hashed like any other oracle. Nothing is bound to a variable and no runtime qubit is captured, so §4 and §6.4 are both satisfied;
• MinusAncilla<1> is a typed state carrier parallel to CleanAncilla<K>. The reintroducing contract must define a unique legal preparation/constructor and linear ownership or typestate rules that preserve its |-> state, or else label the precondition as an explicit, unverifiable caller assertion. Tier B can verify only the adapter's restoration behavior assuming an ideal |-> input; it cannot establish the actual runtime input state. The contract must not present that numeric check as proof of the caller precondition;
• the composite is Tier B like every other PhaseOracle, with no exemption. Its total width is N + 1, so it is bounded by NM_ORACLE_VERIFICATION_MAX_WIDTH.

This makes the construction consistent with §4, §6.4, §9.2, and §10, at the cost of restricting it to widths Tier B can verify. That restriction is the honest outcome: the revision 2 form appeared to escape the ceiling only because it skipped the verification that would have imposed it.