Exact finite checks and a schedule explorer

for t, s in product((0, 1), repeat=2): branch_vectors = [] for raw, _ in early: # Remaining order: physical 3, physical 4, physical 5. branch = select_coordinates(raw, 0: t, 1: s, (2, 3, 4)) branch, late_h = apply_circuit( branch, (("SD", 0), ("H", 0)) ) need(late_h == 1, "late H count changed") # Apply Z^(1-s), then X^(1-t). # This equals the manuscript's product up to branch phase. if 1 - s: branch = apply_gate(branch, ("Z", 0)) if 1 - t: branch = apply_gate(branch, ("X", 0)) branch_vectors.append(branch)

c0 = select_coordinates(branch_vectors[0], 0: 0, (1, 2)) c1 = select_coordinates(branch_vectors[1], 0: 1, (1, 2)) w0 = select_coordinates(branch_vectors[0], 0: 1, (1, 2)) w1 = select_coordinates(branch_vectors[1], 0: 0, (1, 2)) need(all(x == ZERO for x in w0 + w1), "streaming branch has wrong logical output") need(c0 == c1, "streaming branch loses coherence")

# True branch vector is raw / (4 * sqrt(2)**3). # Squared denominator is 16 * 8 = 128. need(inner(c0, c0) == (32, 0), "streaming branch probability is not 1/4")

def check_npt_symbolic_certificate(): # Ordered as output 0, input-reference 1,2,3. S1 = (2, "XZXZ") S3 = (2, "ZYZY") S2 = (0, "YXYX") need(multiply_paulis(S1, S3) == S2, "Choi stabilizer product is wrong") need(multiply_paulis(S3, S1) == S2, "Choi stabilizers do not commute") need(S1[1][1] == "Z" and S2[1][1] == "X" and S3[1][1] == "Y", "partial-transpose signs changed") # PT on input-reference position 1 changes only S3's sign. numerator = 1 + (-1) + (-1) * (+1) - (+1) need(numerator == -2, "negative eigenvalue certificate failed") # Eigenvalue = -2/16 = -1/8.

@dataclass(frozen=True) class Module: name: str inputs: frozenset outputs: frozenset depends: frozenset peak: int

def optimize_schedule(arrivals, modules, batch=False): """Exact frontier optimization in this finite module class.""" arrivals = tuple(arrivals) modules = tuple(modules) names = tuple(m.name for m in modules) need(len(names) == len(set(names)), "duplicate module name") by_name = m.name: m for m in modules need(all(m.peak >= max(len(m.inputs), len(m.outputs)) for m in modules), "invalid module peak")

def frontier(k, done): live = set(arrivals[:k]) produced = set() consumed = set() for name in done: m = by_name[name] produced |= set(m.outputs) consumed |= set(m.inputs) return frozenset((live | produced) - consumed)

@lru_cache(None) def solve(k, done): done = frozenset(done) live = frontier(k, done) if k == len(arrivals) and len(done) == len(modules): return len(live), ()