# BMCTE v2 System Specification

## Core Execution Model (Single Path)

There is only one pipeline:

U (N×N unitary)
 ↓
sample S ~ μ_U
 ↓
M = U_S (p×p submatrix)
 ↓
A = Ryser(M)
 ↓
w = |A|²
 ↓
accumulate histogram

No branching on p. No distinguishable approximation mode.

## GPU Architecture

**Kernel A — Sampling (O(Np))**
- categorical sampling per column
- vectorized CDF tables
- warp-parallel RNG streams

**Kernel B — Gather**
- construct p×p matrix in registers
- coalesced memory reads from U
- shared-memory staging optional

**Kernel C — Ryser Permanent**

Bitmask subset expansion:
- iterate over 2^p subsets
- compute column sums
- multiply row products

Cost: O(p·2^p)

**Kernel D — Reduction**
- atomic histogram accumulation
- or block-level reduction trees

## Fused Kernel (Final Form)

```
for k in 1..K:
    S = sample(U)
    M = gather(U, S)
    A = ryser(M)
    histogram += |A|^2
return normalize(histogram)
```

## Compiler IR (BMCTE-IR v2)

SAMPLE(U) → S
GATHER(U, S) → M
RYSER(M) → A
WEIGHT(A) → w
REDUCE() → output

## Optimization Rules

1. Fuse sampling + gather into single kernel
2. Keep M fully register-resident (p ≤ 8 ideal)
3. Inline Ryser loop (no function calls)
4. Batch Monte Carlo samples per dispatch
5. Avoid memory round trips entirely

## Distributed Execution

Each worker:

P̂_i = Σ_{k∈batch} w_k

Final aggregation:

P̂ = Σ_i P̂_i

No synchronization during sampling phase.

## Complexity Class

BMCTE: O(K(Np + p·2^p))