arXiv CSopen access

BPBO: Blindness-Preserving Brickwork Optimization by Certified Region Resynthesis

BPBO: Blindness-Preserving Brickwork Optimization by Certified Region Resynthesis Youngkyung Lee,1, ∗ Juyoung Kim,1, † and Doyoung Chung1, ‡

arXiv:2606.29962v1 [quant-ph] 29 Jun 2026

1

Cryptography Engineering Laboratory, Electronics and Telecommunications Research Institute, Daejeon, South Korea (Dated: June 29, 2026) Universal blind quantum computation (UBQC) hides a client’s computation by using a computation-independent BFK09 brickwork graph and encoding the computation in measurement angles, which limits the use of graph-changing optimizations. We study blindness-preserving brickwork optimization (BPBO): certified local resynthesis of BFK09-compatible brickwork patterns below the blinding layer. BPBO detects one-, two-, and three-wire regions; for each candidate region it either proves a semantic floor or supplies an executable witness, and it accepts a replacement only after its branch-frame, output-frame, and blinding behavior have been checked. The optimized outputs remain standard brickwork patterns and are evaluated with a logical qubit-recycled UBQC execution stack that runs arbitrary-length patterns using n × 2 active logical qubits. The layer evidence includes a one-wire H-count floor, a two-wire CNOT-cost floor, a three-wire parityledger floor, a clean three-cell CCZ witness whose optimality claim is scoped to the CNOT+T phase-gadget family, and an endpoint-target three-cell CCX/Toffoli application witness; the fixed middle-target CCX case is retained as a four-cell fallback. The security statement is a compatibility result: BPBO preserves UBQC blindness at the declared optimized dimensions and remains compatible with inherited verification guarantees under explicit test-round conditions, without introducing a new trap-soundness theorem. On Bell/CX, Grover-2, endpoint-Toffoli, and Grover-3 evaluation cases, BPBO demonstrates certified local reductions; in the largest case, Grover-3, the materialized pattern is reduced from 3 × 725 to 3 × 98 while preserving the expected marked-state statistics up to sampling noise.

I.

INTRODUCTION

A client who delegates a quantum computation to an untrusted server would like the server to learn nothing about that computation—a goal predating the protocols that achieve it [1]. Universal blind quantum computation (UBQC) achieves this with a structural commitment: client and server execute a measurementbased computation [2] on a brickwork graph fixed independently of the computation, so that all computational content resides in a stream of one-time-padded measurement angles [3]; trap-based extensions make the delegation verifiable at practical overhead [4, 5], and verifiable blind delegation has reached hardware demonstration [6, 7]. The same commitment blocks most direct pattern optimizations. Many standard routes to a smaller pattern—standardization [8], Pauliflow preprocessing [9], and flow-preserving or graph-level rewriting [10–12]—reorganize the command structure or change the graph/graph-like representation, while the BFK09 leakage model requires the server-facing graph rule to remain computation-independent. Circuit-level optimization [13] survives, but only upstream of the lowering, where it cannot touch the redundancy the lowering itself introduces. In this model, the public topology rule constrains optimization, while the declared dimensions remain permitted leakage. Pattern size is therefore an optimizable resource only when every rewrite stays

∗ [email protected] † [email protected] ‡ [email protected]

strictly below the blinding layer, and provably so. The strategy is therefore two-part. Because savings from computation-dependent server-facing graph changes are outside the admitted leakage surface unless hidden by padding or a separate leakage argument, BPBO keeps each admitted pattern inside the standard public brickwork family, declares the optimized dimensions, and makes pattern size the certified object: a local shortening is admitted only with a floor certificate or executable witness whose semantics, frame behavior, and blinding compatibility are checked. Because even an optimized blind pattern may remain long (Grover-3 lowers to 3×725 before optimization), a separate qubit-recycled runner executes the resulting standard brickwork pattern column by column with n × 2 active logical qubits. The optimization side certifies what can be shortened without changing the server-facing topology rule; the execution side makes the remaining long blind pattern runnable. We study blindness-preserving brickwork optimization (BPBO), an arity-stratified certified region-resynthesis method for the standard BFK09 brickwork family at declared dimensions (Fig. 1). BPBO operates below the blinding layer. It detects local one-, two-, and threewire regions and produces two distinct forms of evidence: floor certificates, which support lower-bound claims, and executable witnesses, which can be materialized only after semantic, branch-frame, output-frame, and blindingcompatibility checks. The accepted output is still a standard BFK09 brickwork pattern. A separate logical qubitrecycled execution stack then runs the resulting pattern at constant logical active width, using the two-column window naturally induced by column-ordered brickwork measurements.

2 The name is meant literally. Blindness-preserving means that the accepted executable rewrite changes only the declared pattern dimensions and the hidden angle stream, not the public graph family or the UBQC transcript interfaces. Brickwork fixes the domain to BFK09-compatible patterns. Optimization means local, certificate-gated shortening, not an unconstrained circuit compiler. Operationally, BPBO treats brickwork cells as resource suppliers and target regions as requirement ledgers, then applies one certify–construct– admit discipline across arities. The L1 layer handles one-wire regions through H-count certificates and onebrick witnesses; L2 handles two-wire entangling regions through CNOT-cost certificates and registered two-wire witnesses; L3 handles three-wire CCZ/CCX-class regions through parity-ledger certificates and explicit application witnesses. A floor certificate is kept separate from an executable replacement: the method may prove a lower bound even when the submitted artifact runtime has no admitted materialization for that region. The primary contribution is BPBO as a protocol-safe optimization contract, supported by execution and evidence components. • Blindness-preserving brickwork optimization. We formalize BPBO as a certificate-gated local optimizer for BFK09-compatible brickwork patterns, with a common certify–construct–admit rule for L1 one-wire, L2 two-wire, and L3 three-wire regions (Secs. IV–VII). • Qubit-recycled execution. We evaluate optimized brickwork patterns with a logical execution stack that uses n × 2 active logical qubits, preserves the UBQC transcript interfaces under the admission conditions, and admits a dynamic-circuit lowering with mid-circuit measurement and reset [14] (Sec. III). • Protocol admission and evidence. We prove branchframe closure, a conditional UBQC-blindness compatibility theorem at the declared optimized leakage, and compatibility with inherited trap-based verification under explicit admission conditions; the implementation is checked on layer-representative cases, with Grover-3 used as an integrated application rather than as a broad compiler-performance benchmark (Secs. VI and VIII). The representative reductions are chosen to cover the layers rather than to serve as an empirical optimality study. One-wire SYNTH1Q realizes an admitted onebrick subset of the H-count floor; Bell/CX and Grover-2 exercise the two-wire layer; endpoint-target CCX/Toffoli exercises an L3 application witness; and Grover-3 combines four admitted L3 applications into a full UBQC run. The benchmark corpus is implementation-facing, CCZ optimality is scoped to the CNOT+T phase-gadget family, and verification compatibility is inherited from

the underlying protocol under the stated admission conditions. Together, these cases exercise the L1, L2, L3, and integrated-composition admission paths claimed by the submitted artifact. The rest of the paper fixes the UBQC notation and leakage model (Sec. II), describes recycled brickwork execution (Sec. III), defines BPBO and its layer certificates (Secs. IV and V), states the admission and compatibility conditions (Sec. VI), explains the implementation pipeline (Sec. VII), reports results (Sec. VIII), and then discusses related work, scope, and reproducibility.

II.

BACKGROUND AND SECURITY MODEL A.

Brickwork UBQC

In the one-way model [2], computation proceeds by single-qubit measurements on an entangled resource state, with corrections propagated by the measurement calculus [8]. UBQC [3] fixes the resource to the brickwork state Gn×m : nm qubits in |+⟩, arranged on n horizontal wires and m columns, joined by CZ edges along each wire and by vertical rungs whose positions follow a fixed period-8 stagger. The graph depends only on the declared dimensions, not on the computation. The client prepares each qubit as |+θ ⟩ with θ drawn uniformly from the BFK angle alphabet A = {kπ/4 : k = 0, . . . , 7}. The server entangles according to Gn×m . For each qubit in column order, the client announces δ = ϕ′ + θ + rπ, where ϕ′ is the flow-adapted computation angle and r is a fresh uniform bit that flips the reported outcome’s interpretation.√ Measurement M δ projects onto |±δ ⟩ = (|0⟩ ± eiδ |1⟩)/ 2. Pauli byproducts are tracked as a classical output frame rather than corrected by the server.

B.

Server View and Leakage

The server-visible protocol view consists of the declared dimensions, the standard brickwork graph and column order, the received-qubit ensemble, the δ stream, the server’s measurement record, and the classical interaction generated during execution. Blindness in the sense of [3] states that, conditioned on the declared dimensions (n, m), this view is independent of the underlying computation. BPBO changes only the accepted brickwork length. For an input circuit C, the leakage surface after optimization is L(C) = (n, m′ ),

3 BPBO: certified local resynthesis circuit (client)

semantic fold

region decompose

floors / witnesses

admit (Thms. 4, 5, Lem. 2)

measure, reset, reuse not yet prepared measured

pattern 3 × m′ test rounds interleave recycled-window (traps, C1–C4) execution (n×2 active)

UBQC blinding δ = ϕ′ + θ + rπ

graph: standard brickwork(n, m′ ) — computation-independent

active: n × 2 = 6

(a)

(b)

FIG. 1. Blindness-preserving brickwork optimization (BPBO) and qubit-recycled execution workflow. (a) BPBO lowers a client-side basis stream to fixed BFK09 brickwork regions, certifies candidate local replacements by floors or witnesses, and admits only replacements whose frames and leakage remain protocol-compatible. The materialized output is again a standard brickwork pattern at the leaked dimensions (n, m′ ), with all computational content in measurement angles. (b) Recycledwindow execution: column-ordered measurement and nearest-column entanglement let two live columns suffice—measured qubits are reset and their indices reused—so a three-wire pattern of any length runs with six active qubits (Sec. III).

where m′ is the admitted optimized length. Thus the optimized dimensions are intentional leakage: Theorem 5 is conditioned on (n, m′ ) rather than on the unoptimized length. A client that must hide the optimized size can pad or bucket the pattern back to a canonical length, outside the optimizer; the bucket policy must be fixed independently of the hidden computation within the intended privacy class and may trade away some or all reported savings. Optimizer logs, selected-region metadata, witness identifiers, timing records, retry traces, and artifact handles are not server-visible protocol messages unless an implementation explicitly sends them.

C.

Security Claim Scope

The client is restricted to offline preparation of random single-qubit states |+θ ⟩ and classical computation; it holds no quantum memory. The server has unrestricted quantum capability and is arbitrarily malicious: no computational assumption is made, and it may deviate from the protocol at will. Communication consists of a oneway quantum channel from client to server during preparation and a two-way classical channel during execution. Within this model, the security role of BPBO is compatibility with the base UBQC leakage model. The admitted optimized pattern is executed at its declared dimensions (n, m′ ), and Sec. VI states the conditions under which the resulting view remains blind at that leakage surface. Verification guarantees are inherited from the underlying trap-based protocol [4, 5] when the optimized pattern satisfies the compatibility conditions specified in Sec. VI; BPBO does not introduce a new trap-soundness theorem. Qubit recycling is an execution schedule for the standard brickwork pattern after materialization; it does not alter the prepare-and-send client model or make allocation metadata part of the server-visible computation beyond the declared dimensions. Equally explicit are the non-claims: (i) no new

verification-soundness theorem is proved—soundness is inherited, never re-derived; (ii) no composable-security analysis is attempted—claims live in the standalone model of [3]; (iii) the empirical evidence of Sec. VIII is simulation-level, not a hardware demonstration; and (iv) pattern dimensions remain leaked by definition, so size hiding requires padding or bucketing that may forgo some optimization savings. These boundaries are revisited where each is load-bearing (Secs. VI and X).

III.

QUBIT-RECYCLED EXECUTION OF BRICKWORK PATTERNS

Prior circuit-based UBQC/MBQC simulation demonstrated the feasibility of small blind computations, including a two-qubit Grover instance, on gate-model platforms [15]. This section takes that execution viewpoint as its starting point but separates it from the optimizer: BPBO shortens admitted standard brickwork patterns, while the runner executes and tests those patterns through a two-column active window. A brickwork pattern of n rows and m columns has nm qubits; the raw Grover-3 lowering already needs 3×725 = 2175, far beyond full statevector simulation. The runner’s enabling observation is structural: all entanglers are mutually commuting CZs, horizontal edges connect only adjacent columns, and measurements are columnordered—so a qubit’s life is short. The streaming-window runner keeps only two columns alive: before measuring column c, it prepares column c+1 (fresh |+⟩ qubits, the column’s vertical rungs, and the horizontal edges into it), measures column c destructively, removes those qubits from the state, and reuses their indices. Peak active qubits are n × 2—six for every three-wire pattern in this paper, and eight in a four-wire smoke test included in the artifact package—independent of m; memory falls from 2nm amplitudes to 22n , and time is linear in m (Table I). Exactness. Just-in-time preparation is equivalent to

4 TABLE I. Hardware-facing resource accounting for representative accepted geometries. Measurements/resets count logical midcircuit measurement events and reset opportunities; a backend may omit the final physical reset. Column cycles are adaptive measurement/feed-forward rounds, equal to columns minus one because the output column is not measured.

case Bell/CX Grover-2 clean CCZ patch endpoint CCX Grover-3 raw reference Grover-3 optimized n=4 smoke

geometry full amplitudes active meas./reset cycles 2×5 2×29 3×25 3×33 3×725 3×98 4×24

whole-graph preparation: a measurement on qubit q commutes with every future CZ not acting on q; every CZ acting on q is applied before q is measured (window ≥ 2 guarantees this for nearest-column edges); and the adaptive corrections depend only on classical outcomes, not on when future qubits were prepared. This equivalence is machine-checked at path-graph, elementary-cell, and long three-wire scales; the detailed replay thresholds and branch-count artifacts are reported with the implementation and reproducibility data. The point here is structural: recycling changes allocation time, not the brickwork measurement pattern. Adaptive corrections. Measurement angles adapt by the standard MBQC rule with dependencies generated east-flow on the brickwork—the brickwork’s causal flow [16] is strictly column-ordered, which is also why a two-column window is the canonical streaming unit rather than a tuned cache size; every branch of the H/T /CNOT elementary cells reproduces the zero branch modulo an output Pauli frame. The runner uses the same byproduct-frame algebra later used by BPBO admission, so the runner and admission checks share a single classical tracking convention [8]. From simulation to dynamic circuits, and the UBQC interfaces. The window runner lowers to a logical dynamic-circuit schedule with n × window active qubits, mid-circuit measurement and reset, and the adaptive corrections as classical conditionals—the same measureearly-and-reuse principle established for circuit-model compilation by qubit-reuse techniques [14]; the brickwork’s column structure makes the two-column reuse schedule canonical for this logical dependency structure rather than a search problem. One column cycle is: prepare the recycled next-column qubits in their blinded |+θ ⟩ states; apply the fixed vertical-rung CZ layer and the horizontal inter-column CZ layer; measure the retiring column in the client-provided adaptive bases; report outcomes and update the branch frame/output decoder; reset the retired column indices for reuse. Thus a pattern of m columns has m−1 adaptive cycles and time Tpattern ≈ (m − 1) τcol + Tout ,

210 258 275 299 22175 2294 296

4 4 6 6 6 6 8

8 56 72 96 2172 291 —

4 28 24 32 724 97 23

where τcol is the backend-specific prepare/CZ/measure/feed-forward/reset latency. We report this as a logical schedule and do not claim a backend hardware trace. Statistical validation and equivalence gates are reported with the implementation and results sections. The UBQC transcript interfaces are preserved: blinded angle streams, client/server transcript separation, and input/output one-time-pad decoding—recycling changes when logical qubits exist, not the server-visible data associated with each qubit.

IV.

BPBO METHOD CONTRACT

BPBO (blindness-preserving brickwork optimization) is a certifying local optimizer for fixed BFK09 brickwork patterns. Its generality is an input-domain statement: BPBO can analyze an arbitrary BFK09-compatible pattern or basis stream. It is not a claim of global optimality, complete synthesis, or an executable replacement for every certified floor. The contract is: Input: a fixed BFK09 brickwork pattern, or a basis stream that materializes to one. Output: either the original pattern, or a shorter standard BFK09 pattern P ′ plus an execution-plan certificate. Guarantee: if BPBO outputs P ′ , then each admitted replacement is semantically equivalent to the original region up to tracked frames, remains within the BFK09 angle alphabet, executes with the declared leakage surface (n, m′ ), and has passed branch-frame, output-frame, and materialized-saving checks. Non-guarantee: BPBO does not claim a global optimum, a complete witness compiler, or executable replacements for all floor-certified regions.

A.

Resource and Requirement View

BPBO rests on two changes of viewpoint. A brickwork cell is not “a gate slot” but a resource supplier : each wire’s chain through one cell supplies exactly two effective Hadamards (the chain factors as Rz H Rz H Rz —this single-wire restriction is the n=1 cell

5 of RBFK (1, k); larger macro-cells scale these supplies with their columns), the vertical rungs supply entangling capacity, and every measured column supplies a free phase from A. Dually, a target unitary is not “a circuit” but a requirement ledger : how many Hadamards, how much entangling capacity, and—per Lemma 3—which parity forms must receive odd phase deposits. Optimization is then a matching problem between supply and requirements, and it can be certified at both ends—by a single principle on the lower side (Theorem 1), and by an explicit angle-table witness on the upper.

B.

Common Certify–Construct–Admit Rule

Every accepted rewrite follows the same local rule: 1. parse the input into a BFK09-compatible stream and detect a candidate region; 2. canonicalize the region semantics modulo gauges and Pauli frames; 3. compute the region certificate or floor; 4. construct or retrieve a BFK09-realizable witness; 5. verify zero-branch semantic equivalence; 6. check branch-frame closure, output-frame admissibility, and positive materialized saving;

without being selected for execution. Surviving cells are handled later by materialization and scheduling; they are not a fourth resynthesis arity. The optimized payload is always the materialized BFK09 pattern, not the preview log that discovered it.

V.

BPBO LAYER CERTIFICATES AND WITNESSES

The previous section defined BPBO as a local certify– construct–admit method. This section supplies the certificates and witnesses used by that method: the reachable-family notation, the common lower-bound theorem, its one-, two-, and three-wire instantiations, and the L3 primitive and application witnesses that connect the floor certificates to evaluated regions. The claims in this section climb a fixed ladder. A semantic target is a zero-branch unitary modulo the stated gauge and output-frame conventions; a floor certificate is a lower bound in a stated realization class; a schedule hint is a feasible assignment in an over-approximating menu; an explicit witness is an angle table realizing the target modulo frame; and a runtime-admitted witness additionally passes the branch-frame, output-frame, and materialized-saving gates of Sec. VI. Exact cell complexity is claimed only where a scoped lower bound and an explicit witness meet in the same realization class.

7. materialize the optimized standard BFK09 pattern, emit its execution plan, and validate the accepted pattern. A.

A floor certificate is a lower-bound statement, not an executable replacement. Admission is a separate runtime gate. The status ladder is Detected→Canonicalized→Floor→Witness →Admitted→Materialized→Validated.

C.

Certified Resynthesis Layers

BPBO applies this discipline at three resynthesis arities. The layer names are not new primitive gates; they are the public organization of the optimizer’s certified region families. Layer Scope Floor L1 L2 L3

Gate

1-wire H-count ⌈h/2⌉ R2/R9/R10 2-wire CNOT-cost ⌈c/2⌉ E1-T/R12/R11/L2 3-wire parity ledger CCZ/CCX

This table is also a scope statement. The floors are mathematical lower bounds on region classes; the runtime executes only the admitted subsets for which a BFK09 witness, branch-frame behavior, output-frame handling, and a positive materialized saving have all been checked. Thus a region may be floor-certified or synthesis-available

Reachable Families

Let RBFK (n, k) denote the unitaries realizable by k consecutive clean cells on n wires modulo the permitted boundary gauge and a single-qubit Pauli output frame, at the zero-branch level (runtime admission is Sec. VI). For L1/L2 a clean cell is the corresponding one- or two-wire brickwork unit. For L3, the counted unit is the clean three-wire macro-cell defined in Sec. V D; the reported floor battery uses the same start convention as the registered witness artifacts. Its Clifford quotient is closed and fast: modulo Pauli frames, Clifford reachability uses the binary symplectic/tableau representation of Clifford action [17, 18], reducing to Sp(2n, F2 ), of order 6, 720, and 1 451 520 for n = 1, 2, 3. The implementation also keeps signed Clifford tableaus, with 24, 11 520, and 92 897 280 representatives at these arities. For the fixed local arities used here, membership and composition are tablebacked operations (the layer is exhaustively enumerated for n ≤ 2 and checked against sampled n = 3 consistency tests). The non-Clifford certificate families below use the deposit ledger—the phase-polynomial representation of CNOT+T and phase-gadget circuits [13, 19], transplanted to a setting where supply is a fixed cell menu rather than freely placed gates (Sec. IX).

6 B.

The Supply–Demand Floor

All formal BPBO floor certificates used below fit one bookkeeping template. Definition 1 (requirement map; supply filtration). Fix an arity n and a realization class F , including its cell or macro-cell unit, zero-branch convention, boundary gauges, and output-frame quotient. A requirement map assigns to each target class [U ]F a demand D(U ) in a partially ordered set, constant on the allowed gauge–Pauli orbit. A supply filtration for F is a monotone family S(0) ⊆ S(1) ⊆ S(2) ⊆ · · · that over-approximates reachability: U ∈ RF (n, k) implies D(U ) ∈ S(k). Theorem 1 (Supply–Demand Floor). For any requirement map D and supply filtration S (Definition 1) overapproximating the class F , F kmin (U )

≥ floorD (U ) := min{ k ≥ 0 : D(U ) ∈ S(k) },

with the convention that the minimum is +∞ if the set is empty. The proof is one paragraph (App. A): a k-cell realization in F would place D(U ) in S(k) by overapproximation, with orbit-invariance discharging the realization’s gauge and frame dressing. Two structural consequences carry through every instantiation. First, the bound is relative to its class F : where S overapproximates all clean windows the floor is unconditional, and where it over-approximates the CNOT+T phase-gadget family the floor is family-scoped—each corollary below carries its scope explicitly. Second, overapproximation means floor-tightness is not promised: D(U ) ∈ S(k) does not produce an angle-level witness at k, and the executability ladder of Sec. VII tracks this distinction operationally; the endpoint/middle CCX layout gap in Sec. VIII exhibits it live. L1 certificate. Corollary 1 (Hadamard grading, n = 1). Within the one-wire clean-cell model and fixed boundary/frame convention, let D(U ) = h(U ) be the minimal Hadamard count over A-decompositions. With S(0) = {h = 0} and S(k) = {h ≤ 2k} for k ≥ 1 (each cell’s wire chain supplies exactly two Hadamards), the floor is ⌈h(U )/2⌉. At n = 1 the filtration is exact—RBFK (1, k) = {U : h(U ) ≤ 2k}—so the floor is the one-wire clean-cell cost. The cell is Hadamard-limited, not T -limited: A phases ride in the available angle slots (proof sketch in App. A; exact cyclotomic enumeration confirms the small-k filtration used by the artifact). This inverts the resource intuition inherited from T -count-centric circuit optimization. Operationally, this is the L1 one-wire certified resynthesis layer. The production implementation uses deterministic H; H 7→ I cancellation, direct one-wire template replacement, and the runtime-admitted one-brick family displayed as SYNTH1Q. Only replacements with exact

semantic equivalence, branch-frame admission where required, output-frame admissibility, and positive materialized saving enter the materialized UBQC pattern; the theorem above is broader than the current executable subset. L2 certificate. Corollary 2 (Entangling grading, n = 2). With D(U ) = c(U ), the local-equivalence CNOT cost identified from Makhlin invariants [20] and entangling-gate lower bounds [21], and S(0) = {c = 0}, S(k) = {c ≤ 2k} for k ≥ 1 (two rungs per cell), ⌈c(U )/2⌉ is an entanglingcell floor. Equality is certified only for the named finite classes used below: the Clifford pre-contexts and the finite {I, T, T † } CNOT-context neighborhoods (exhaustive verification; App. A). Operationally, this is the L2 two-wire certified resynthesis layer. The runtime attempts only registered L2 candidates: T-context (E1-T), synthesized-context (R12-E-pre), Clifford-context (R11), and short-region reduction (L2-Reduce). Candidates are materialized only after exact zero-branch semantics, branch-frame closure or an equivalent witness, output-frame discharge, and positive materialized saving pass. Thus the claim is not that every two-wire unitary is executed at ⌈c/2⌉, nor that local one-wire work has zero cost; it is that the entangling-capacity lower bound is general within the stated cell model, and floor-tight rewrites are supplied for the finite registered classes.

C.

L3 Certificate: The Three-Wire Floor Algorithm

At n = 3 the same instantiation pattern yields not a formula but an algorithm. The target universe here is the clean three-wire CNOT+T phase-gadget family after canonicalization over per-wire Hadamard boundary gauges and Pauli output frames. The demand D(U ) is the resulting affine linear skeleton together with the nonconstant odd-support syndrome of Lemma 3. For k clean macro-cells, S(k) is the generous k-cell schedule menu: the alternating 2k two-rung blocks may realize any allowed GL(2, F2 ) action on their active wire pair, and odd deposits may be placed on parity forms carried by the wires under the stated start convention. Lemma 4 is the two-cell instance used for the CCZ no-go below; the floor algorithm uses the same menu for general k. Corollary 3 (Parity coverage, n = 3). With this demand and supply menu, floorD is a sound lower bound on clean-macro-cell cost within the stated phase-gadget family, computable by finite search. The production implementation certifies the floor, not necessarily an executable replacement, for an arbitrary in-scope target:

7 1. Canonicalize: search the 64 per-wire Hadamard boundary-gauge pairs for G U G′ in affinemonomial form (this automatically reduces Toffoli and the Hadamard-dressed Grover blocks to CCZ); report out-of-scope honestly if none exists. 2. Extract requirements, both Pauli-frame invariant: the linear skeleton (which input parity each output wire carries) and the nonconstant odd-support syndrome of Lemma 3. 3. Search the schedules: for k = 0, 1, 2, . . . , enumerate the generous k-cell menu for an assignment realizing the skeleton while exposing every parity in the syndrome. The first feasible k is the certified floor, and the feasible assignment is emitted as a synthesis hint rather than as an angle-level witness. The public artifact reports the positive-cost floor battery using the clean START=5 macro-cell convention up to its stated finite cap; cap failures are reported as unresolved, not as no-go theorems. Soundness is Theorem 1’s over-approximation direction: within the stated clean phase-gadget family and macro-cell convention, any physical gadget realization would appear in the generous menu, so infeasibility in that menu proves a lower bound for that family. On the FLOOR-3W battery {CNOT, CX01 CX21 , tc, CCZ, CCXmid , H ⊗3 CCZ}— where tc denotes the seven-gate CNOT + T Toffoli phase core—Corollary 3’s search returns floors (1, 1, 2, 3, 3, 3), matching the registered battery values. These are lower bounds until a target-specific witness achieves them; Sec. V D supplies that meeting point for the central CCZ witness and the registered application witnesses.

D.

L3 Case Study: Phase-Gadget CCZ Witnesses and Optimality

The three-wire BPBO layer uses parity-ledger certificates and registered witnesses for the evaluated CCZ/CCX-class regions. CCZ is the representative case because the registered Toffoli and Grover-3 application regions reduce to CCZ up to local layers. This case study gives the exact clean-macro-cell value for CCZ within the certified CNOT+T phase-gadget family [19] and an unconditional three-cell upper bound in the full brickwork model; it does not prove a family-free two-cell no-go.

1.

Setting

A macro-cell is a nine-column window of the threewire brickwork; its internal rung schedule is fixed by the window’s start column modulo 8, and the two clean phases (start ≡ 5, 7 mod 8) carry no boundary rung. A k-cell realization of a unitary U assigns angles from A to k consecutive clean macro-cells whose zero-branch map equals P U for some single-qubit Pauli tensor P (the

output frame; admitted witnesses pass the output-frame checks of Sec. VI). Within this case study, the certified scope is the phase-gadget family: realizations that factor as CNOT+T gadgets—monomial blocks at the rungs with diagonal phase deposits on the parity forms carried by the wires. The registered production witnesses reported here lie in this family; realizations outside it are addressed by adversarial search (Remark 1). Column counts use four conventions. A macro-cell window has nine local columns including its boundary; each macrocell contributes eight angle-carrying measured columns; connected patch columns merge shared boundaries, so three start-5 macro-cells form a 3 × 25 connected patch with 72 measured qubits; and period columns count the 24-column alignment period used when Grover blocks are concatenated.

2.

The requirement and the obstruction

By the parity-ledger analysis of Sec. V, every phasegadget realization of CCZ modulo a single-qubit Pauli frame must deposit odd (T-family) phases on all seven parity forms—the deposit syndrome is a representationindependent invariant (Lemma 3, App. A)—and in particular on the three x0 -containing parities x0 ⊕x1 , x0 ⊕x2 , and x0 ⊕x1 ⊕x2 , at moments when those forms are physically carried by a wire. Whether a window can schedule those deposits is a finite question about its fixed rung alternation, and for two cells the answer is negative: Theorem 2 (Phase-gadget two-cell no-go). Within the phase-gadget family, no clean two-macro-cell window (start ≡ 5 or 7 mod 8) realizes CCZ modulo a singlequbit Pauli output frame. The mechanism is geometric (Fig. 2): the wire x0 mixes only at (0, 1)-blocks, and a two-cell window alternates blocks too coarsely to expose the outer pair x0 ⊕x2 together with the remaining required parities and still return the wires to identity. The proof is a finite enumeration (64 and 3 · 63 · 3 assignments) over an overapproximated menu, which is what makes the bound sound (App. A). Remark 1 (Scope). Outside the gadget family— arbitrary-angle windows whose internal dressing does not factor as CNOT+T gadgets—the statement rests on adversarial search: approximately 1.8×105 randomized and structured two-cell candidate windows cap at frame fidelity 0.730 (start 5) and 0.854 (start 7) against CCZ. We state Theorem 2 as a bounded no-go and do not claim a family-free impossibility. Theorem 3 (Three-cell witness). There exist angles in A on three consecutive clean start-5 macro-cells whose composite equals (Y ⊗X⊗Z) · CCZ exactly. The witness (schedule (rotA, CXb)×3 : in each cell the (1, 2) block acts by local rotations and the (0, 1) block carries

8 the CNOT; full angle tables in App. B) is verified exactly: with all angles integer multiples of π/4, the composite cell map lies in Z[ζ8 ]8×8 , and its proportionality to (Y ⊗X⊗Z) · CCZ is a division-free cross-multiplication identity in cyclotomic integer arithmetic—no floating point enters the certificate. Independent floating-point reconstruction agrees (elementwise deviation below 10−15 ), and the witness was cross-verified by a second, independently implemented toolchain. The witness is itself a phase-gadget realization—CNOT+T blocks with boundary and diagonal deposits—in the same family as Theorem 2, so the lower and upper bounds meet within a single realization class. Corollary 4. Within the CNOT+T phase-gadget family, the clean-macro-cell complexity of CCZ on the threewire brickwork is exactly three (Theorems 2 and 3). For unrestricted-angle windows we prove the three-cell upper bound (the witness is unconditional) and report adversarial evidence against two cells (Remark 1); we do not claim a family-free lower bound.

3.

How the witness is constructed: two synthesis principles

The witness is not a lucky search result; it is produced by a reusable procedure built on two principles. Lemma 1 (Frame-chained synthesis). Let T1 , . . . , Tk be per-cell targets with Tk · · · T1 = U . Solve the cells sequentially against residue-adapted targets: cell j real† izes Pj Gj Tj Rj−1 exactly, where Pj is a single-qubit Pauli output frame, Rj−1 = (Uj−1 · · · U1 )(Tj−1 · · · T1 )† is the exact accumulated residue, Gj a per-wire Hadamard boundary gauge, and Gk trivial. Then Uk · · · U1 = P U with P the final cell’s Pauli frame, by construction. The gauge masks Gj are a search dimension: greedy choices can dead-end, and existence of a closing assignment is established per schedule. Chaining is the synthesis-time instance of the byproduct-adaptation rule proved in Sec. VI: each cell’s residue is absorbed into the next cell’s target exactly as runtime byproducts are absorbed into future measurement angles. Without it, individually perfect cells compose to fidelity cos(π/4) ≈ 0.707—the frames of earlier cells flip the phase deposits of later ones. The second principle is a scheduling rule: a cell’s trailing boundary always emits per-wire Hadamard gauge that the next cell absorbs, so a block whose linear action is iSWAP-class (a same-pair double-CNOT “rotation”) cannot occupy the final cell, whose outgoing gauge must be trivial. Re-running the schedule enumeration under this end-safe constraint yields four candidate schedules, all of which then solve at fidelity 1.0; the rule’s mechanism is established by a Makhlin-invariant scan [20] of the two-rung block family, and we use it as a verified design rule rather than a closed-form theorem.

two clean macro-cells

third cell

x0 B(0,1)

B(0,1)

B(0,1)

x1 B(1,2)

B(1,2)

B(1,2)

x2 x0 mixes only here: two slots ledger demand: odd deposits on x0 ⊕x1 , x0 ⊕x2 , x0 ⊕x1 ⊕x2 identity-returning schedules cover ≤ 2 of 3; the dashed cell adds the missing exposure

FIG. 2. L3 phase-gadget obstruction for two clean macrocells. A clean two-macro-cell window alternates two-rung blocks on wire pairs (1, 2) and (0, 1) in a fixed order set by the stagger phase. Tracking which parity forms each wire carries through the block sequence, the three x0 containing parities required by CCZ’s ledger can never all visit a wire while the schedule returns the wires to identity: every identity-returning assignment covers at most two of {x0 ⊕x1 , x0 ⊕x2 , x0 ⊕x1 ⊕x2 }. A third cell adds the missing exposure, and Theorem 3 provides the corresponding L3 witness.

The same machinery yields, beyond bare CCZ: the Grover block B = H ⊗3 CCZ as a three-cell witness (the diffusion Hadamard layer absorbed into the boundary gauge), and, by composing four chained blocks, a complete twelve-cell Grover-3 reference whose physical correctness is measured in Sec. VIII. Because each block spans 24 ≡ 0 (mod 8) columns, consecutive blocks preserve the stagger phase and concatenate with zero alignment padding. The endpoint-target CCX/Toffoli witness is the other runtime-facing L3 application: it closes at the three-cell floor for target wire x2 , while the fixed middletarget placement remains a registered four-cell fallback because the three-row brickwork geometry is not rowsymmetric. Sec. VIII and App. B separate these two application witnesses explicitly.

VI. ADMISSION, BLINDNESS, AND VERIFICATION COMPATIBILITY

A rewrite certified at the zero-branch level (Sec. V D) is not yet a protocol participant. Four gaps remain between a frame/gauge-correct unitary and an admissible pattern: measurement outcomes are random, the full output decoder must compose all Pauli-frame sources, the angles are subsequently blinded, and the protocol may interleave verification rounds. This section states the protocol-level admission conditions that close these gaps—promoting a witness from “correct” to “admissible in the running protocol” without introducing a new security model. Theorem 4 (Branch-frame closure). Consider a clean pattern of N measured columns with unblinded base angles αr,c ∈ A. The client applies the deterministic sign adaptation (−1)xr αr,c , while the tracker bits (xr , zr ) per wire evolve, per column, by (i) zr ⊕= sr,c for outcome sr,c , (ii) za ⊕= xb , zb ⊕= xa for each rung (a, b) in the column, and (iii) (xr , zr ) ← (zr , xr ) at the column hop. Then for every outcome string s, the branch map equals

9 Pbr (s) U0 up to global Q phase, where U0 is the zero-branch map and Pbr (s) = r X xr Z zr is the tracker’s final Pauli. Moreover Pbr (s) is client-computable from s and the public schedule, and all adapted base angles remain in A. Theorem 4 is stated so as to be its own implementation specification: the tracker’s update rules are the runtime’s classical feed-forward, and its final Pauli is the decoder’s relabeling mask. For a fixed branch s, the measurement projector is ⟨+(−1)xr αr,c +πsr,c |; the +πs term is branch semantics (the outcome-1 projector), not an online instruction. This is the standard MBQC feed-forward in an equivalent byproduct gauge: the usual (−1)x α + zπ convention folds the tracked z-shift into the transmitted angle, whereas we keep it in the classical frame. The two gauges produce identically distributed blinded transcripts and differ only by output frame bookkeeping. The same algebra serves twice—at compile time, the framechained synthesis of Lemma 1 absorbs the deterministic inter-cell residues into the angle tables; at run time, the identical rules absorb the measurement randomness. The implementation validates this branch closure as an artifact gate (Sec. VIII and App. C); those validation counts are evidence for the implementation, not an additional security theorem. The decoder must accordingly compose every output-frame term, Fout (s) = Fbr (s) ⊕ FUBQC,out ⊕ FBPBO,static . For computational-basis output, the X components of this Pauli frame relabel bit strings; the Z components are phase-frame data unless coherent output or non-Z readout is requested. Sec. VIII shows the histogram consequence of omitting a required term.

transmits the result, does the server see exactly a standard UBQC transcript at the declared dimensions? Theorem 5’s hypothesis is BPBO’s design discipline restated: materialization produces only the standard brickwork at the leaked dimensions, and selected-region data stay below the blinding layer. The server learns the declared optimized dimensions (n, m′ ); within a fixed leakage class, blindness is inherited from the base protocol after these admission conditions establish transcript equivalence. Optimizer logs, witness identifiers, noncanonical timing records, retry behavior, and artifact handles are not server-visible protocol messages unless a particular implementation sends them; they are outside the transcript modeled by Theorem 5. Lemma 2 (Round indistinguishability and verification compatibility). Interleave optimized computation rounds with test rounds (every qubit a dummy |z⟩, z uniform, or a trap |+θ ⟩, θ uniform), provided: (C1) test rounds are generated at the optimized dimensions (n, m′ ); (C2) trap/dummy positions are drawn, conditional on (n, m′ ), independently of the computation and of optimizer-internal metadata such as deposit ledgers, witness choices, and selected-region plans; (C3) both round types use the standard brickwork(n, m′ ), the same canonical column order, and any recycledwindow schedule as a deterministic function of (n, m′ ); and (C4) both round types are blinded by the same mechanism, so the base protocol’s preparation indistinguishability applies. Then the server’s pre-abort protocol transcript is distributed as in the base test-round protocol. Under C1–C4, BPBO outputs are compatible with the hypotheses of the underlying test-round verification theorem; soundness remains the cited base theorem.

Theorem 5 (Blindness at optimized leakage). Let an optimized pattern be produced by rewrites that encode no computation in the topology: once the (permitted-leakage) dimensions (n, m′ ) are fixed, the materialized graph is the standard brickwork(n, m′ ), angles are sent in the standard column order, any recycled-window schedule is a deterministic function of (n, m′ ), and no rewrite metadata is sent to the server. All remaining computation dependence lies in the measurement angles, whose adaptations are deterministic, client-computable, and A-valued. Under UBQC blinding (δ = ϕ′ +θ+rπ with fresh uniform θ, r per qubit), any two computations with the same admitted leakage (n, m′ ) induce the same server-visible protocolview distribution: materialized graph, received-qubit ensemble, transmitted angle sequence, and outcome interaction depend only on (n, m′ ). The only computationdependent quantity intentionally declared outside the angle one-time pad is the dimension m′ itself; size hiding requires a bucket policy fixed independently of the hidden computation.

Lemma 2 extends the same factoring to verification, and its conditions are operational rather than technical: (C1) is met by generating test rounds at the optimized dimensions, (C3) is the materializer’s mechanically checked invariant, and (C4) is the base protocol’s own lemma. (C2) is the one genuinely new design constraint that optimization introduces: trap placement must not be correlated with the computation or with optimizer metadata—in particular, not with the deposit ledger, however tempting it is to guard the “loadbearing” angles—since any such correlation opens a leakage channel through test-round statistics. These are compatibility conditions, not a new trap-soundness theorem. Under C1–C4 the verified protocol can use the optimized geometry uniformly: every round, test or computation alike, shrinks by the same factor (quantified in Sec. VIII).

With branch frames closed, blindness reduces to a transcript question: after the client computes each outcomedependent adapted angle, applies fresh UBQC pads, and

Sections IV–VI define the BPBO contract, certificates, and admission rule. This section describes the submitted artifact implementation of that contract. Its

VII. IMPLEMENTATION AND ARTIFACT-GATED PIPELINE

10 semantic verifiers and admission predicates are shared across the supported L1/L2/L3 candidate certificates they inspect, while candidate generation is intentionally registry-seeded. Registration is only a source of candidates: a replacement is executed only after it passes the semantic, frame, pattern, cost, and plan gates below. Unsupported or non-admitted regions fall back to the unoptimized BFK09 materialization. Evidence vocabulary. We label evidence as analytic proof, exact cyclotomic certificate, numerical/tolerance reconstruction, sampled branch replay, runtime admission, or regression equivalence. Section VIII uses these labels rather than treating every artifact check as the same kind of evidence.

A.

Candidate Sources and Witness Registry

Production circuits enter the implementation as basis streams already lowered to {H, CX, T, T † , Paulis}. Since such streams do not necessarily retain gate-level markers for multi-qubit cores, the converter folds cores back semantically. A window folds only when its 8 × 8 unitary equals G X t Z z CCZ G′ exactly for per-wire Hadamard gauges G, G′ and a Pauli correction. The criterion is decomposition-agnostic: any correct CCZ/Toffoli expansion may fold, not only a memorized template. Each accepted fold carries a per-window equality assertion, and the converted stream must recompose to the input at fidelity 1.0. The witness registry is a candidate source and cache, not the definition of BPBO. It currently contains the clean CCZ three-cell witness (WIT-CCZ3), the H ⊗3 CCZ application witness (WIT-GROVER-BLOCK), the endpoint-target CCX/Toffoli three-cell application witness (WIT-CCX-TARGET2), the fixed middle-target four-cell fallback (WIT-CCX4), and the composite fourapplication Grover-3 pack (PACK-GROVER3). The last entry is not a new primitive witness; it is a registered composition with fixed output-frame decoding. Regions without an executable registered candidate can still be floor-certified and displayed as analysis results, but registry membership or preview status alone never executes a replacement.

B.

Production Materializers

The implementation has two materialization surfaces. L1 and L2 run as a cell-loop over the current operation stream: same-wire and adjacent two-wire regions are certified, candidate replacements are constructed by the registered families of Sec. IV C, and the local admission predicate accepts only frame-safe witnesses. L3 uses separate N3 candidates: semantic CCZ/CCX-class regions are detected in the basis stream, before local rewrites that would destroy the recoverable three-wire core, matched to registered three-wire witnesses or composite packs,

and selected only when the resulting BFK09 pattern is smaller than the current materialization. The materializer emits an execution plan rather than a mere pass log. The plan records ladder/admission status, stable handle, selected-for-execution flag, backend, frame injections, decoder metadata, baseline/executed geometry, materialized column spans, vertices, measured vertices, and the base-angle table over A under the deterministic schedule. Preview regions explain missed opportunities, but the accepted materialized pattern is the authoritative execution object.

C.

Validation Gates

Every submitted artifact payload is gated by checks tied to the contract above: semantic equality or a registered witness certificate; declared recomposition equality or tolerance; zero-branch semantics and branch-frame closure; runtime-safe output frames; a standard-brickwork base-angle pattern over A; positive materialized execution saving; and a plan whose execution plan.executed pattern matches the runtime /phase/pattern. The decoder composes the pershot branch byproduct, the UBQC output one-time pad, and any static BPBO output frame. Pattern-shape checks enforce Theorem 5’s hypotheses, while module batteries and witness re-verification connect the implementation to App. C. This is the implementation boundary used in Sec. VIII: submitted lowered input streams receive the supported local analysis and certification, but the submitted artifact optimizes execution only for the registry-seeded candidate family. Extending that family is a synthesis and materializer problem (Sec. X), not a change to the BPBO contract or to the inherited UBQC security model.

D.

Cost Model and Selection

We report four costs, because they answer different questions. The executed geometry is rows times columns; columns are the closest proxy for measurement depth and communication rounds, while vertices=rows×columns counts prepared qubits in the full-pattern view. Measured vertices exclude the output column and therefore count adaptive measurement steps. Operation cells count the compiler-level regions selected before materialization and explain why a pattern shrank; they are not the executed geometry. The qubit-recycling platform adds a separate runtime-space quantity, n × 2 active qubits, determined by the two-column execution window. Selection is therefore column-first. A candidate may reduce operation cells but still be rejected if its materialized pattern does not improve the executed BFK09 geometry; a no-regression fallback then keeps the current materialization. Conversely, the authoritative data shown to the client and in the certificate are the rows,

11 tor checks, and regression-equivalence evidence. A floor alone is not an executable-layout claim, and regression equivalence is engineering regression evidence rather than an independent semantic proof.

columns, vertices, measured vertices, and base angles of the accepted pattern itself. The base-angle table is client/certificate metadata used to generate blinded angles; optimizer tags, candidate identifiers, and preview regions are not part of the server-visible transcript. This is why the execution plan is checked against the pattern that actually runs: preview regions can explain an opportunity, but only the accepted materialization is evidence of an optimized UBQC execution.

VIII.

A.

Layer-Representative Results

The results are organized by the certified resynthesis layers of Sec. IV C, not by a single flagship circuit. Table II freezes the representative results used in this manuscript. The first row isolates the L1 witnessadmission claim; the next two exercise two-wire and mixed one-/two-wire machinery; the following two isolate the L3 primitive/application distinction; the last row uses Grover-3 as an integrated four-application case.

RESULTS

Evidence map. The tables distinguish floor targets, exact witnesses, runtime-admitted payloads, sampled simula-

TABLE II. Layer-representative optimization results. When geometry is reported, baseline and executed geometries are written as rows×columns; vertices are rows×columns. The authoritative executed geometry is the materialized BFK09 pattern, while operation-cell counts explain the selected region plan. The reference column may be a raw geometry, prior baseline, or floor target; the evidence column gives status and handle. Role

Example

Reference/baseline

Materialized/result

Evidence status and handle

L1 witness

one-wire SYNTH1Q

H-count floor ⌈h/2⌉

admitted one-brick BFK09 witness

L2 sanity

Bell/CX

2 × 13 (26 vertices)

2 × 5 (10 vertices)

L1/L2 mixed

Grover-2

2 × 125 (250 vertices)

2 × 29 (58 vertices)

L3 primitive

clean CCZ

phase-gadget target = 3 cells

floor

witness patch 3 × 25 (75 vertices, 72 measured)

L3 application

endpoint CCX/Toffoli

endpoint floor target = 3 cells

Integrated

Grover-3

3 × 725 (2175 vertices)

executable payload 3 × 33 (99 vertices, 96 measured) 3 × 98 (294 vertices, 291 measured), 12 cells

HCOUNT-1W exact reachability; SYNTH1Q branch-frame admission; executable subset only EQUIV-GATE regression equivalence; compact two-wire execution one-/two-wire certified resynthesis plus EQUIV-GATE materialization check WIT-CCZ3/BRANCH-CLOSURE; standalone CCZ is synthesis-available / previewsafe unless selected by a runtime materializer WIT-CCX-TARGET2 exact witness plus branch replay; core witness 3 × 25, frame Z ⊗ Z ⊗ I PACK-GROVER3/RUN-GROVER3 runtimeadmitted registered composite; STAT-GROVER3 ideal P (111) = 0.9453125

B.

Benchmark Coverage and Fallback Controls

The representative table above isolates the method’s layers. To answer the separate question of breadth, the artifact package freezes a benchmark/control matrix under handle BENCH-CORPUS. This matrix is deliberately scoped: it is a regression and evidence corpus for the implemented optimizer, not a statistical optimality claim over all Clifford+T inputs. It combines the ten-circuit EQUIV-GATE corpus with L3 controls that would otherwise be easy to overstate: standalone clean CCZ is a preview-safe primitive unless a runtime materializer selects it, endpoint-target CCX is runtime-admitted at three macrocells, and fixed middle-target CCX remains a four-cell fallback. TABLE III. Frozen benchmark and control coverage. Baseline/executed geometries are rows×columns when both are present. The random rows are seeded Clifford+T circuits from the EQUIV-GATE corpus; their role is implementation coverage, not a distributional performance claim. The corpus has fallback and preview controls, but not a broad no-op or admission-reject battery. Group

Cases

Baseline → executed

Positive controls

Bell/CX; Grover-2; Grover-3

Seeded random 2q

rand2q s1, rand2q s2

Seeded random 3q

rand3q s1, rand3q s2

Seeded random 4q

rand4q s1, rand4q s2

Endpoint CCX

target row 2

2×13 → 2×5; 2×125 → EQUIV-GATE PASS; 2×29; 3×725 → 3×98 PACK-GROVER3/RUN-GROVER3 PASS 2×93 → 2×45; 2×109 → EQUIV-GATE PASS 2×37 3×133 → 3×69; EQUIV-GATE PASS 3×117 → 3×45 4×109 → 4×61; EQUIV-GATE PASS 4×117 → 4×53 floor target 3 cells → WIT-CCX-TARGET2 PASS 3×33

Gate/control result

Scope Layer demos plus registered integrated stress test Two-wire corpus coverage Three-wire nonspecialized inputs Wider compiler path; no L3 optimality claim Runtime-admitted L3 application

12 floor target 3 cells → 3×25 patch target row 1 floor target 3 cells; known executable 4 cells three random branch-pattern trials 4×24 window; peak active window = 8

clean CCZ witness

Middle-target CCX n=4 platform smoke

The current package includes fallback and preview-safe controls, but not a broad admission-reject/no-op corpus. This limits empirical claims about rejection behavior on unstructured inputs. The correctness claim instead rests on the admission verifier and the materialized-pattern checks of Sec. VII; broader negative testing is a useful artifact extension and is listed as a limitation in Sec. X.

WIT-CCZ3/BRANCH-CLOSURE Synthesis-available / PASS preview-safe primitive WIT-CCX4 truth-table PASS Row-asymmetry fallback, not a silent replacement SMOKE-N4 PASS Platform-only smoke test; no optimization claim

2,175 brickwork vertices

Standalone CCZ

7.4× overall, 3.07× vs. baseline

2,000

903

1,000

294 0

C.

raw lowering two-wire certified 3 × 725 3 × 301

Integrated Application: Grover-3

We use three-qubit Grover search [22] (two iterations, marked state |111⟩) as a registered integrated stress test, not as a broad benchmark. The production runtime receives only the lowered basis stream {H, CX, T, T † , X} (95 gates). The converter folds four CCZ-class subsequences semantically (95 → 39 abstract gates), records four floor-3 cores and a fidelity-1.0 recomposition check, and gates execution on PACK-GROVER3. The runtimeadmitted materialization RUN-GROVER3 is

FIG. 3. Grover-3 materialization cost at the three stages of optimization: raw Clifford+T lowering onto the brickwork (geometry 3 × 725, i.e., 725 columns on three rows), the prior two-wire certificate optimizer (3 × 301), and the full pipeline of this work (3 × 98, RUN-GROVER3)—a 7.4× overall reduction. Each accepted pattern remains in the standard brickwork family at its declared optimized dimension; the leaked dimension (n, m′ ) is permitted leakage under Theorem 5.

3 × 98 = 294 vertices,

D.

Measured Output Statistics

We also check outcome-level behavior by measurement. The frozen STAT-GROVER3 run executes the optimized pattern under the computation-round recycled-window simulator with Born sampling, adaptive corrections, and the composed output decoder; over 4000 shots it yields P (|111⟩) = 0.9445

vs. ideal 0.9453

(0.2σ for the marked bin at binomial σ = 0.0036), with total-variation distance 0.0028 to the ideal eight-outcome

100 probability (log)

versus 3 × 301 = 903 for the prior certificate-era optimizer and 3 × 725 = 2175 for the raw lowering (Fig. 3): a 3.07× reduction over the optimized baseline and 7.4× overall. In the dynamic-circuit schedule of Table I, this is 291 mid-circuit measurements/reset opportunities and 97 adaptive column cycles on six active qubits, versus 2172 measurements and 724 cycles for the raw streamed reference. The RUN-GROVER3 server probe (fold count, certification, runtime admission, and materialization) records 181.819 s, reported as 182 s; the separate full-stack harness records its own timing. The measured column count lies in the predicted 97–105 band: the twelvecell core is exact, the four blocks concatenate at 24 ≡ 0 (mod 8) columns each, and Pauli layers are represented in frame/decoder metadata rather than extra columns.

this work 3 × 98

measured (4000 shots) ideal

10−1

10−2

000

001

010

011

100

101

110

111

FIG. 4. Decoded output distribution of the optimized Grover3 pattern under the computation-round recycled-window simulator (STAT-GROVER3, 4000 Born-sampled shots, six active logical qubits), against the ideal two-iteration Grover distribution. The marked outcome |111⟩ is recovered at 0.9445 versus the ideal 0.9453 (0.2σ); total-variation distance 0.0028. Error bars are ±1σ binomial at 4000 shots; the vertical scale is logarithmic so the seven unmarked outcomes remain resolvable. Decoding applies the per-shot branch byproduct mask, the UBQC output X pad, and the static BPBO output frame; omitting a required term relabels the histogram.

distribution (Fig. 4). Every shot ran with six active logical qubits (Sec. III). The production runner, transfermatrix machinery, and an independently coded window sampler agree on the relevant reference checks, so the histogram is a consistency check for the admitted pattern and decoder, not an independent proof of blindness or verifiability.

13 E.

Inherited Test-Round Cost Profile

Under Lemma 2, inherited test-round verification can be run on the optimized geometry at reduced absolute cost: every round—test or computation—is a 3 × 98 pattern, so the ∼ 3× per-round saving multiplies through the protocol’s round overhead. On this geometry, the TRAP-REF harness uses uniform traps on one bipartite class at density 1/2, giving T ≈ 73 traps per round in expectation over the measured columns. Its analytic curve uses 1 − (1 − sin2 (ε/2))T and matches the frozen simulations across ε ∈ [0.05, 0.2]; a single-column Z-tamper model is detected with probability 0.63. Since execution is column-streamed, rejected rounds can abort when the first violation appears, saving 51–56% of the remaining columns conditional on rejection. Soundness amplification remains the base protocol’s theorem; these measurements show the cost profile on the optimized geometry.

F.

Endpoint Toffoli and the Layout Gap

The L3 application row of Table II isolates the Toffoli/CCX point that is easiest to misstate. The floor algorithm certifies floor(CCX) = 3, but floor certification and executable layout are separate questions. For the endpoint-target placement used by the production Toffoli path (controls on rows 0, 1, target on row 2), the registered WIT-CCX-TARGET2 witness closes at the floor: three macrocells, connected core 3×25 (3·8+1 columns), output frame Z ⊗Z ⊗I, exact cyclotomic zero-branch certification, and endpoint branch replay. The submitted executable payload then adds the standard eight-column runtime wrapper/boundary around that connected core, giving the displayed 3×33 pattern with 99 vertices and 96 measured vertices; this payload dimension is not claimed as a separate minimal-layout theorem. The fixed middle-target placement remains deliberately separate. The same floor value is three, but the known middle-target witness is the registered WIT-CCX4 four-cell fallback with frame X ⊗ Y ⊗ Y . This is not a contradiction and not a silent replacement policy: the BFK09 three-row geometry is not row-symmetric, so the endpoint-target application can absorb the boundary Hadamards at the floor while the fixed middle target currently uses the conservative four-cell path. In the paper’s main result table, therefore, endpoint-target CCX/Toffoli is the L3 application result; the middletarget witness is a scope and robustness item for the witness appendix. The relation to adjacent systems is summarized in Sec. IX.

G.

is gated by a reproducible regression-equivalence harness rather than by code inspection (handle EQUIV-GATE, App. C). On the frozen ten-circuit corpus—Bell, Grover-2, Grover-3, the legacy fixed-middle Toffoli row, and seeded random Clifford+T circuits on two to four wires—the gate compares declared fields against the preconsolidation runtime: (i) materialized pattern geometry, where the loop must do no worse and in fact reproduces every column count exactly, including Grover-3 at 98; (ii) the frozen expected-output fields under the same decoder convention; and (iii) per-family rewrite counters, pinning not just the result but the applied rewrite families. All three invariants hold on all ten circuits. This is regression evidence, not an independent semantic proof; the exact witnesses, branch replay, runtime admission, and sampled statistics above provide the claim-specific evidence. The current endpoint-target WIT-CCX-TARGET2 Toffoli path is validated by the separate L3 witness/materializer battery summarized in Table II; it is not conflated with the legacy middle-layout row.

Regression Equivalence of the Unified Loop

The unified orchestration of Sec. VII replaced the development-era fixed pass chain, and the replacement

IX.

RELATED WORK

Blind and verifiable quantum computation. UBQC originates with the brickwork protocol of Broadbent, Fitzsimons, and Kashefi [3], built on the one-way model [2] and the measurement calculus [8]—our byproduct trackers are instances of the latter’s signal-shifting algebra. Verifiability was added through trap-based protocols [4] and brought to practical overheads by test-round schemes [5] (see [23] for a survey); experimentally, blind delegation was first demonstrated photonically [24], and verifiable blind delegation has been demonstrated on a networked trapped-ion server with a photonic client [6] and in a multi-client Qline configuration [7]. In the BFK/prepare-and-send brickwork line, the public graph is computation-independent within the declared leakage surface. Overheads have been optimized at the protocol level—the quantum communication of blind computation has been upper- and lower-bounded, placing the brickwork protocol within a constant factor of optimal for single-qubit clients [25]—but that line bounds the protocol, uniformly; it does not provide a layer that certifies how small the fixed-brickwork pattern of a given computation may be. (A complementary line removes the quantum client entirely under computational assumptions [26]; the present work stays information-theoretic, in the prepare-and-send model where the brickwork constraint—and hence the size-optimization problem— arises.) BPBO contributes such a certifying optimization layer inside the constraint these protocols impose, with admission and compatibility arguments (Theorem 5 and Lemma 2) showing that admitted rewrites compose with inherited blindness and verification guarantees rather than re-deriving either. MBQC pattern optimization. Standardization [8], Pauli-flow preprocessing and circuit extraction [9],

14 flow-preserving rewrite systems for Pauli-measurement patterns [10], and graph-level optimizers such as Graphix [11, 16] optimize or reorganize MBQC representations by allowing changes to the command structure, open graph, or a closely related graph-like representation; ZX-based circuit simplification uses local complementation and pivoting in graph-like diagrams [12]. These methods are powerful when the graph or graphlike representation is an optimization variable; under the fixed BFK09 leakage model, computation-dependent graph changes are not directly admissible unless followed by padding or a security argument showing that the rewritten graph leaks no computation-dependent structure. BPBO is complementary: it keeps the output inside the standard brickwork family at declared optimized dimensions, changes hidden measurement-angle data and declared permitted length leakage, and certifies floors or executable witnesses over the reachable BFK family RBFK rather than over all graphs. Brickwork resource reduction. A line specific to UBQC lowers the cost of the brickwork realization itself: Chien, Van Meter, and Kuo [27] count the fault-tolerant brickwork layers of a circuit by tiling each gate of a Clifford+T decomposition into bricks, while a more recent thread reduces the qubit count by altering the resource state—substituting smaller cluster fragments for selected bricks [28], or replacing the fixed brickwork with nonfixed variants that cut the ancillae per gate [29]. These approaches optimize different resource axes: decomposeand-tile analyses the cost of standard brickwork realizations, while resource-state variants change the graph and therefore require their own leakage argument or padding discipline under a BFK-style interface. BPBO instead preserves the standard brickwork family at declared optimized dimensions and shortens admitted patterns by arity-stratified certified resynthesis; the logical qubit-recycled runner then executes the resulting standard brickwork pattern at constant logical active width. Circuit-model optimization and synthesis. In the circuit model, many resource measures are optimized under their own cost models, including exact and approximate Clifford+T synthesis [30, 31], T-count and T-depth optimization via phase polynomials over F2 -parities [13], and entangling-gate lower bounds for unitary synthe-

sis [21]. Our demand-side machinery adapts part of this reasoning to the blind setting: the parity ledger of Sec. V is a phase-polynomial and phase-gadget representation [13, 19], and the L1/L2/L3 floors are analogues of single-qubit, entangling-count, and three-wire cellcomplexity bounds. The L3 certificates borrow phasegadget language from this synthesis tradition, but the admitted objects are fixed-brickwork MBQC witnesses rather than circuit-level rewrites. The differences arise from the fixed-brickwork UBQC interface: supply is a fixed brickwork cell menu rather than freely placed gates, residues chain through Clifford frames across cells, and the output is a certificate that gates execution rather than a circuit-level rewrite. The two toolchains compose: circuit-level optimization applies upstream, before lowering, and BPBO compresses certifiable local slack left by the lowering on admitted regions. Qubit reuse. Measure-early-reset-and-reuse compilation is established for circuit-model hardware, where finding the reuse schedule is itself an optimization problem [14]. The runner of Sec. III is the brickwork counterpart: column ordering makes the two-column live window canonical for the logical brickwork dependency structure (Table I), and the same lowering yields logical dynamiccircuit schedules with n×window active qubits. Earlier circuit-based UBQC/MBQC simulation work studied small blind computations on gate-model platforms, including a two-qubit Grover instance [15]. Here that execution viewpoint is used as context; the present paper centers on BPBO-certified local reduction and qubitrecycled execution of optimized standard brickwork patterns. What distinguishes the runner from both lines is the coupling: constant-width logical execution preserves the UBQC transcript interfaces—blinding, byproduct decoding, and test-round compatibility under Sec. VI’s conditions—which Sec. VIII exercises through artifactvalidated simulation, statistics, and regression gates. Design-space summary. Table IV summarizes the combination addressed here. It is not a ranking of systems with different goals: BPBO is compared as a certifying optimizer for the standard brickwork family at declared optimized dimensions, while the qubit-recycled runner is compared as a logical execution stack for the optimized standard brickwork patterns. The non-affirmative entries identify scope differences, not deficits.

TABLE IV. Representative systems from the two nearest lines of work against the six properties addressed by BPBO and the qubit-recycled execution stack. This is a design-space summary, not a general-purpose ranking: the compared systems pursue orthogonal goals, and each non-affirmative entry names the reason, scoped to the cited version (Graphix as described in [11]; qubitreuse compilation as in [14]) and footnoted. The last row summarizes the combination addressed in this paper. graph-preserving optimization

size-floor certificates

blindness verification preservation compatibility

constant-width UBQC execution

Graphix [11] graph-changinga not targetedb out of scopec out of scopec no UBQC transcript stackd Qubit-reuse compilation [14] circuit-modele not targetedb out of scopec out of scopec no UBQC transcript stackd This work: BPBO + recycled execution Yes (Sec. IV) Yes (Sec. V) Yes (Thm. 5) Yes (Lem. 2) Yes (Sec. III)

artifact-validated optimized execution —d —d Yes (Sec. VIII)

a Optimizes by rewriting the open graph into local-Clifford decorated form—a graph change that is not directly admissible under fixed-topology blindness without padding or a separate leakage argument (Sec. IX). b Emits optimized artifacts, not lower-bound certificates on pattern size. c Blind or verified delegation is outside the system’s stated scope; no security claim is made or required there. d Neither system targets the UBQC transcript/admission stack (blinding, byproduct decoding, and test-round compatibility), which these axes require; qubit-reuse compilation targets circuit-model hardware. e Operates in the circuit model; the graph-preservation axis does not apply.

15 X.

SCOPE AND LIMITATIONS

Scoped optimality claims. Theorem 2 excludes twocell CCZ realizations within the CNOT+T phase-gadget family; the three-cell witness lies in the same family, so the clean-window cell complexity is exactly three within that family. The same witness gives an unconditional three-cell upper bound in the full brickwork model under the stated macro-cell convention. Outside the family we have adversarial evidence only—approximately 1.8 × 105 randomized searches over arbitrary-angle two-cell nets, with frame-aligned fidelity reaching at most 0.854—and a family-free two-cell no-go remains open. Thus every formal “exactly three” statement in Sec. V D carries the phase-gadget scope explicitly. General verification, registry-seeded synthesis. The verifier and admission predicates are schema-general for submitted local candidates, but candidate generation in the submitted artifact is registry-seeded. The L3 registry covers the clean CCZ witness, the H ⊗3 CCZ application witness, the endpoint-target CCX application witness, the fixed middle-target fallback, and the registered Grover-3 composition (Sec. VIII and App. B). The frame-chained synthesizer is a heuristic with a sound verifier, not a deterministic or complete witness compiler, so a local region without an admitted witness/materialization retains the unoptimized BFK09 lowering. Closing this gap—a synthesis-andmaterialization procedure with completeness guarantees over a specified RBFK (3, k) target class, frame convention, and admission contract—is a theory target, not a current claim. Scaling beyond three wires. The formal certificate language generalizes as stated: the supplier side is governed by the binary symplectic representation of Clifford/stabilizer operations [17, 18], and the demand side by a 2n −1-coordinate parity ledger, so a floor is definable once the target class, supply filtration, and frame quotient are specified. What grows is not only search cost but executable coverage: materializers, frame metadata, branch checks, and benchmarks must also scale. Complete all-target enumeration is used through n = 2; the n = 3 claims here are targeted floor batteries, schedule enumerations, and witness verifications for the registered CCZ/CCX-class families, not a catalog of every three-wire unitary. Wider targets will need structureexploiting search in place of enumeration; the floor algorithm’s cap-and-certify design supports scoped certificates, but no complete beyond-three-wire compiler or materializer coverage is delivered here. Benchmark and rejection coverage. The benchmark suite is a fixed regression and evidence corpus for the implemented optimizer, not a distributional performance study over Clifford+T inputs. The artifact includes fallback and preview-safe controls, but not a broad noop or admission-reject corpus covering malformed candidates, invalid frames, unsupported windows, invalid alphabets, or non-improving materializations. Conse-

quently, the empirical claims are limited to the representative L1/L2/L3 cases, seeded regression circuits, and explicit L3 fallback checks of Sec. VIII; broader negative testing is future artifact work. Size leakage and padding. Pattern length is treated throughout as permitted leakage, matching the BFK09 model in which the server sees the graph dimensions. A client who must also hide optimized-size information can pad or bucket the optimized pattern to public standardbrickwork dimensions, trading away some or all of the resource the optimization recovered. Theorem 5 applies at whichever declared dimensions are chosen, provided the padded or bucketed pattern still satisfies the admission and transcript conditions; the choice belongs to the application policy, not to the BPBO methodology. Verification constraints and evidence level. Lemma 2’s condition C2 obliges trap and dummy positions to be drawn independently of the computation—conditioned only on the declared dimensions (n, m′ ) and, in particular, uncorrelated with deposit ledgers or other highimpact angle locations. A generator tuned to guard those locations falls outside the inherited-verification argument. Our verification evidence is simulation-level mechanism and cost evidence: detection and abort statistics (Sec. VIII) match the sin2 (ε/2) prediction for the stated perturbation model on the optimized recycled-window geometry, and no new soundness theorem is claimed beyond the inherited guarantees under Lemma 2’s conditions [4, 5]. Verifiable blind delegation has been demonstrated on hardware at small scale [6, 7]; what has not been demonstrated is BPBO-optimized standardbrickwork execution with the UBQC/recycled-execution stack, and the dynamic-circuit lowering [14] makes that a concrete experimental follow-up.

XI.

CONCLUSION

In prepare-and-send BFK09 brickwork, the public graph family and declared dimensions constrain optimization, but they do not eliminate it. BPBO shows that BFK09-compatible patterns can be shortened to declared optimized standard-brickwork dimensions by certified local resynthesis: regions are analyzed by arity, floors or witnesses are checked, and only protocol-admissible materializations are executed. The qubit-recycling runner is a separate logical execution stack that makes the resulting long blind patterns executable and testable at constant logical active width. The submitted artifact implementation is registry-seeded rather than complete, but it exercises a common certificate-and-admission discipline across representative L1 one-wire, L2 two-wire, and L3 three-wire cases, with Grover-3 as the integrated application. The next steps are a complete witness compiler for a specified target class, structure-exploiting search and executable coverage beyond three wires, broader noop/admission-reject benchmarks, and hardware execution of BPBO-optimized standard-brickwork patterns.

16 ACKNOWLEDGMENTS

This work was supported by Electronics and Telecommunications Research Institute (ETRI) grant funded by the Korean government [26ZS1320, Research on Quantum-Based New Cryptographic System for Ensuring Perfect Data Privacy].

DATA AVAILABILITY

The artifact package supporting the BPBO and qubitrecycled execution claims is available as ancillary material accompanying this arXiv submission and is described in App. C. The public record is defined by the ancillary directory anc/artifact package/, manifest.json, and SHA256SUMS.txt. The package contains frozen result data, registered witness tables, verification scripts, environment pins, and the code-only runtime used for the quick and full reproducibility checks. Usage and public-archive license status are recorded in the artifact’s USAGE AND LICENSE.txt; a DOI-bearing archive can be cited in later versions when available. The principal witness angle tables are printed in full in App. B, so the central CCZ, Grover-block, and CCX witness/layout claims can be checked independently of the packaged runtime; benchmark, statistical, resource-model, and fullstack equivalence claims are reproduced from the artifact package.

Appendix A: Proofs

Conventions. Throughout Appendix A, phases in parity ledgers are measured in π/4 units modulo 8, equality of implemented unitaries is modulo a global phase unless stated otherwise, and Rz (t) = diag(1, eit ). We √ use column-vector Q multiplication, |+t ⟩ = (|0⟩ + eit |1⟩)/ 2, and P (a, b) = r Xrar Zrbr in the printed wire order. A branch +πs is projector semantics for the observed outcome, not an extra server instruction.

1.

Parity-Ledger Necessity

For a π/4-valued diagonal 3-qubit phase function in the CNOT+T / phase-gadget P scope, write the phase over parity forms: φ(x) = π4 L cL χL (x) with cL ∈ Z8 , L ranging over the L seven nonempty subsets of {x0 , x1 , x2 } and χL (x) = i∈L xi . A gadget realization specifies its P deposits explicitly, so it comes with a representation φ = i ai χLi ; no uniqueness of the coefficients is claimed (indeed none holds mod 8: the parity-evaluation matrix has determinant ±32, and e.g. 4(χA + χB + χA⊕B ) ≡ 0 mod 8). What is invariant is the odd support:

Lemma 3 (Necessity: the odd-support syndrome). For a phase-gadget realization with deposit multiset 7 {(Li , aP i π/4)}, define the deposit syndrome o ∈ F2 by oL = i:Li =L ai mod 2. Then: (i) o is an invariant of the realized diagonal up to global phase: any two integer representations of phase functions equal mod 8 up to an additive constant differ, beyond the constant coordinate, by a kernel vector of the parity-evaluation matrix, and every such kernel vector is even—so the nonconstant odd-support syndrome is well defined on diagonals modulo global phase. (ii) CCZ has syndrome o = (1, . . . , 1): the expansion of πx0 x1 x2 over parities has coefficients (1, 1, 1, 7, 7, 7, 1), all odd. (iii) The syndrome is unchanged by single-qubit Pauli output frames on diagonal targets. Consequently every gadget realization of CCZ modulo a single-qubit Pauli frame deposits odd phase on all seven parities—in particular on the three x0 -containing forms. Proof. (i) The 8×8 parity-evaluation matrix M (columns: the constant and the seven χL ; rows: the points of {0, 1}3 ) has Smith normal form with invariant factors (1, 1, 1, 1, 2, 2, 2, 4); accordingly its kernel mod 8 has order 32, isomorphic to Z4 ×Z32 , and consists of even P vectors only. Two of its relations are transparent: 2 L χL ≡ 0 (every nonzero point lies in exactlyPfour of the seven parities) and, for each variable xi , 4 L∋xi χL ≡ 0 (every point lies in zero, two, or four of the four parities containing xi ); the full kernel is tabulated in the artifact (App. C) and is reproduced by exhaustive enumeration. A global phase shifts only the constant coordinate. Since every invariant factor divides 4, every kernel vector lies in 2Z88 ; hence representations of the same diagonal (mod global phase) agree mod 2 on the nonconstant coordinates, and o is well defined. P (ii) Diπ rect expansion (machine-verified): πx x x = 0 1 2 i xi − 4  P (x ⊕x ) + (x ⊕x ⊕x ) , i.e. c = (1, 1, 1, 7, 7, 7, 1). i j 0 1 2 i<j (iii) Write P = X a Z b . An X output frame is a readout translation x 7→ x ⊕ a, not a phase: writing the realization in monomial form X a D with D its diagonal factor, the frame equation X a D = X a Z b CCZ reduces to D = Z b CCZ. Translations send each parity to itself up to a sign and a constant (χL (x ⊕ a) = χL (x) ⊕ χL (a); in the integer lift, u ⊕ 1 = 1 − u = −u + 1 and u ⊕ 0 = u), so they preserve the nonconstant syndrome; admitting X frames therefore does not relax the odd-support requirement. P For the diagonal equation, Z b multiplies the phase by π i∈b xi , an even representation shift (4 per affected single-variable parity). (Machine closure over all 64 Pauli frames.)

2.

The Supply–Demand Floor (Theorem 1)

Proof. Let U admit a k-cell realization in the class F , i.e. U ∈ RF (n, k) up to the model’s gauge and Pauli-frame dressing. Orbit-invariance of D makes D(U ) well defined on the dressed target, and the over-approximation

17 property then places D(U ) ∈ S(k). By definition of floorD (U ), D(U ) ∈ / S(j) for all j < floorD (U ). Hence F no realization with fewer cells exists in F : kmin (U ) ≥ floorD (U ). If the minimum is empty, then no realizable U in the stated class can have that demand, because any realization would place it in some S(k). Soundness of each instantiation below therefore reduces to checking exactly two properties of its (D, S) pair—orbit-invariance of the demand and over-approximation of the supply—which is how the proofs are organized.

3.

Wire-Count Instantiations (Corollaries 1, 2)

Proof sketch (Corollary 1). Both directions are general in k. Supply (upper bound): one cell’s wire chain is Rz HRz HRz —exactly two Hadamards with free Aphases—so k concatenated cells realize, by construction, exactly the alternating words with at most 2k Hadamards (adjacent phases merge). Demand (achievability): any U with h(U ) ≤ 2k has a minimal-H normal form; if its Hadamard count falls short of the supplied 2k by an odd amount, the identity H = S H S H S pads the word without changing the realized unitary or exceeding the supply, and leftover slots absorb as identity cells. Hence RBFK (1, k) = {h ≤ 2k} for every k. The exhaustive enumeration in the cyclotomic ring Z[ζ16 ] (exact arithmetic, no floating point) through k = 3 is an independent confirmation of the equality at small k, not the source of generality. Artifacts in App. C. Proof sketch (Corollary 2). A two-wire cell carries two rungs, hence entangling capacity two: k cells realize CNOT-cost at most 2k, giving the floor ⌈c/2⌉ with c the Makhlin-invariant CNOT-cost [20]. Certification on the stated scope is by finite exhaustion: all Clifford pairs, and the bounded-T contexts as full-alphabet neighborhoods of the CNOT base cells, each verified to meet the floor by an explicit rewrite. Artifacts in App. C.

4.

Two-Cell Schedule Coverage and Theorem 2

Lemma 4 (Coverage). Model a clean two-macro-cell window generously: the two-rung blocks act on their wire pairs by any element of GL(2, F2 ) (including SWAP), and odd deposits may be placed on every parity form carried by a wire at a block boundary or inside a block’s two-form span; the net linear action must return to the identity. Exhaustively over all assignments (64 at start 5; 3 · 63 · 3 at start 7): the identity-returning assignments number 13 and 28, and the coverable subsets of {x0 ⊕x1 , x0 ⊕x2 , x1 ⊕x2 , x0 ⊕x1 ⊕x2 } are {3, 6}, {3, 5, 6}, {3, 6, 7} (start 5) and {6, 7}, {3, 6}, {3, 6, 7}, {3, 5, 6}, {5, 6, 7} (start 7), in the mask notation x0 =1, x1 =2, x2 =4. (Single-variable parities are carried by the input wires and are always coverable; the four nontrivial parities are the binding ones.)

In every case at most two of the three x0 -containing forms are covered. The schedules are fixed by the brickwork’s stagger: a clean window starting at column ≡ 5 (mod 8) carries vertical rungs at relative columns {1, 3} on wire pair (1, 2) and {5, 7} on (0, 1), so a two-cell window is four same-pair two-rung blocks (menu 64 ); a window starting at ≡ 7 carries rungs at {1}=(1, 2), {3, 5}=(0, 1), {7}=(1, 2), and the two-cell junction merges the adjacent (1, 2) rungs, giving the block sequence single–double– double–double–single (menu 3 · 63 · 3). The menu grants every two-rung block all of GL(2, F2 ) and every single rung {id, CX→ , CX← }: for the lower bound only the superset direction matters (physical reachability ⊆ menu), and the menu is not vacuously generous—CNOT actions are calibrated directly, and a Makhlin-invariant scan [20] of the two-rung block family confirms that even the iSWAP class is attainable. Proof. Finite machine enumeration over the assignments above (artifacts: the schedule-enumeration and per-form coverage scripts with their battery outputs; availability per App. C). Soundness of the bound: any physical phase-gadget realization induces an assignment in the model—a monomial block’s linear action lies in GL(2, F2 ), deposits occur only on carried forms (a subset of the allowed slots), and a diagonal-mod-Pauli target forces identity linear return (Lemma 3 (iii) absorbs translations). The menu only over-approximates, so failure in the model implies failure of every gadget realization. Proof of Theorem 2. By Lemma 3, a two-cell gadget realization of CCZ modulo a single-qubit Pauli frame must deposit odd phases on all three x0 -containing parities. By Lemma 4, no clean two-cell schedule covers all three. Contradiction.

5.

Verification Protocol of Theorem 3

Proof (verification). The witness is an explicit artifact: three 3 × 8 angle tables over A (App. B). Verification separates four layers. First, the floating transfermatrix contraction on the production geometry equals (Y ⊗X⊗Z) · CCZ after global-phase alignment with maximum elementwise deviation below 10−15 ; a brute-force state-summation rebuild agrees within 5 × 10−14 , and a separately coded toolchain reproduces the identity to unit fidelity. Second, every printed angle is in A, so the adapted branches of Theorem 4 remain in the BFK alphabet. Third, branch closure is a symbolic consequence of Theorem 4; the BRANCH-CLOSURE replay of all 72 single flips and 3000 random branches is implementation evidence, not an additional assumption in the proof. Fourth, the zero-branch identity is also certified without floating point: because all angles are integer multiples of π/4, the transfer-matrix path sum lies in Z[ζ8 ]8×8 , and proportionality to (Y ⊗X⊗Z)·CCZ is the division-free cross-

18 multiplication identity Uab Ti0 j0 = Tab Ui0 j0 over all 64 entries. The same EXACT-WIT method is applied handle-byhandle in App. B, including the Grover-block and both registered CCX witnesses.

6.

Proof of Lemma 1 (Frame-Chained Synthesis)

Proof. Define R0 = I and let cell j realize exactly † with Pj a Pauli tensor and Gj Uj = Pj Gj Tj Rj−1 a per-wire Hadamard gauge (Gk = I). By induction, Rj := (Uj · · · U1 )(Tj · · · T1 )† = Pj Gj : indeed Uj Rj−1 (Tj−1 · · · T1 ) = Pj Gj Tj (Tj−1 · · · T1 ). At j = k, Rk = Pk , i.e. Uk · · · U1 = Pk (Tk · · · T1 ). The residue normal form Rj = phase · Pauli · G was additionally verified mechanically on the production witnesses. The premise—that each adapted target is realizable at fidelity 1—depends on the gauge choices Gj ; greedy selection can dead-end (observed on a four-cell schedule), so the masks are searched, and existence of a closing assignment is established per schedule by exhibiting the witness. This is a zero-branch chaining lemma; nonzero branch behavior is handled separately by Theorem 4.

7.

Proof of Theorem 4 (Branch-Frame Closure)

The proof rests on four exact single- and two-qubit identities, each verified in isolation: (a) Rz (t) X = eit X Rz (−t), (b) CZ (X⊗I) = (X⊗Z) CZ, (c) |−t ⟩ = |+t+π ⟩, Rz (t+π) = Rz (t) Z, (d) HX = ZH, HZ = XH. Proof. In the pattern’s column gauge, column c applies a diagonal layer (the measurement phases and the rung CZs) followed by a hop Hadamard on every wire. Induct on columns with invariant Vc = phase · Πc Wc , where Wc is the zero-branch partial map at base angles and Πc the tracker Pauli. Pushing Πc through the adapted diagonal layer: on a wire with xr = 1, identity (a) converts the sign-flipped angle back to the base angle, and the branch flip +πs contributes Z s by (c)—the tracker’s outcome injection; the scalar in (a) is absorbed into the global phase factor. Z-components commute with the diagonal layer. Each rung spreads X-components onto the partner wire as Z by (b)—the tracker’s rung rule. The hop Hadamard exchanges X ↔ Z per wire by (d)—the tracker’s swap. Hence Vc+1 = phase · Πc+1 Wc+1 , and at c = N the claim follows. Pbr (s) depends only on s and the public schedule, so it is client-computable; the adaptation is a sign flip plus π-shifts, so angles stay in A. The induction proves all branches; sampled replay validates the implementation: BRANCH-CLOSURE checks the three-cell CCZ witness on all 72 single flips and 3000 random branches, while PACK-GROVER3 checks the twelve-cell composite on

its sampled branch replay. The endpoint Toffoli replay is a separate WIT-CCX-TARGET2 artifact.

8.

Proof of Theorem 5 (Blindness Preservation)

Proof. The server-visible protocol view has three components. Graph: the rewrites introduce no non-standard topology—after materialization the graph is the standard brickwork determined by (n, m′ ) alone. Angles: per qubit, δ = ϕ′ + θ + rπ with fresh uniform θ on the cyclic group A and uniform r; therefore δ is uniform and independent of ϕ′ —hence of the computation and of every other qubit (one-time-pad over Z8 ; the adapted ϕ′ remains in A by Theorem 4, so no out-of-alphabet value leaks structure). Received qubits and outcomes: the joint BFK state-angle message remains independent of ϕ′ , not merely its marginal state. Condition on a public value of δ and on the past transcript. For any adapted angle ϕ′ , the two compatible choices of r give antipodal preparations |+θ ⟩ and |+θ+π ⟩ with equal probability, whose average density is I/2; hence the conditional quantum message is independent of ϕ′ . Tensoring over independently blinded qubits and iterating through the adaptive transcript gives the usual BFK quantum-classical mixture. The outcome interaction is generated by the server’s measurements of this mixture at the public δ values. Every server-visible component’s distribution depends only on (n, m′ ), so the view does. The base protocol’s blindness theorem then applies at dimensions (n, m′ ); the component check is the reduction to the base malicious-server theorem, not a separate honest-server proof.

9.

Proof of Lemma 2 (Round Indistinguishability)

Proof. Compare the pre-abort view components across round types at fixed (n, m′ ), conditioning on the past transcript. Graph: identical by construction. Received qubits: computation rounds send |+θ ⟩, θ uniform (⇒ I/2 per qubit); test rounds send dummies |z⟩, z uniform (I/2) or traps |+θ ⟩ (I/2); preparations are independent, so ′ both joint ensembles equal (I/2)⊗nm , and trap/dummy positions carry no computation or optimizer-metadata dependence by assumption. Angles: both round types blind by δ = ϕ′ + θ + rπ, so the δ-sequence is i.i.d. uniform in both. Interaction: the server receives the same pre-abort quantum/classical transcript distribution as in the base protocol at (n, m′ ). Thus the base protocol’s verification theorem applies under its own hypotheses. No new soundness is claimed; the content is that optimization does not add distinguishable transcript structure under C1–C4.

19 Appendix B: Witness Data

The witness tables below use a common format. Each macro-cell is a nine-column start-5 window; the eight angle-carrying columns per wire are listed, and the ninth column is the window boundary with Q no free phase. Frames use the convention P (a, b) = r Xrar Zrbr in the printed wire order, up to global phase. The evidence ledger is handle-specific: object

handle

cells frame

WIT-CCZ3

3

(3, 5)

EXACT-WIT + floating rebuild

H ⊗3 CCZ

WIT-GROVER-BLOCK

3

(4, 6)

EXACT-WIT + floating rebuild

12

pack ledger checkpoint/frame/distribution validation

CCX0,1→2

WIT-CCX-TARGET2

3

(0, 3)

EXACT-WIT + endpoint branch replay

CCX0,2→1

WIT-CCX4

4

(7, 6)

EXACT-WIT + truth-table validation

Table V is the explicit angle assignment for Theorem 3. Its composite equals (Y ⊗X⊗Z)·CCZ—frame bits (a, b) = (3, 5)—with elementwise deviation below 10−15 after global-phase alignment, and exactly over Z[ζ8 ] by the cross-multiplication certificate of App. A. TABLE V. The three-cell CCZ witness: measurement angles in units of π/4 (entry k denotes kπ/4 ∈ A), per wire and per anglecarrying column of each nine-column start-5 macro-cell window. Handle: WIT-CCZ3. The composite equals (Y ⊗X⊗Z) · CCZ exactly (Theorem 3). relative measured column cell wire 0 1 2 3 4 5 6

7

1

2

3

cell wire 0 1 2 3 4 5 6

7

1

x0 x1 x2

0 2 2 0 0 0 0 1 0 2 0 0 0 2 1 6 6 2 2 1 0

3 3 0

2

x0 x1 x2

1 0 3 3 0 0 0 2 6 2 0 0 0 2 2 0 6 2 2 1 0

3 3 0

3

x0 x1 x2

2 0 0 0 2 2 0 0 2 2 4 0 0 2 2 0 2 2 0 0 0

0 0 0

evidence

CCZ

Grover-3 pack PACK-GROVER3

relative measured column

x0 x1 x2

0 2 2 0 0 0 0 1 0 2 0 0 0 2 1 6 6 2 2 1 0

3 3 0

x0 x1 x2

2 0 0 0 2 2 0 0 2 2 4 0 0 2 2 0 2 3 0 0 0

x0 x1 x2

0 0 0 0 2 2 2 2 2 2 2 2 0 0 2 0 2 0 2 0 0

Table VII prints the endpoint-target CCX witness used by the production Toffoli path in Sec. VIII: three cells, controls on x0 , x1 , target row x2 , and frame bits (a, b) = (0, 3), i.e. Z⊗Z⊗I. Its zero-branch map is exact-certified by EXACT-WIT; the independent floating reconstruction has maximum elementwise deviation 9.72 × 10−16 after global-phase alignment. The endpoint-specific branch replay passes all 72 single flips and 4000 random branches, observing all 64 possible output frames in that sampled replay. Runtime admission is the separate productionpath check summarized by WIT-CCX-TARGET2. TABLE VII. The endpoint-target three-cell CCX witness (WIT-CCX-TARGET2, controls x0 , x1 , target wire x2 ): measurement angles in units of π/4, same format as Table V; composite equals (Z⊗Z⊗I) · CCX0,1→2 exactly. relative measured column cell wire 0 1 2 3 4 5 6

7

1

0 3 0

x0 x1 x2

1 7 2 2 7 5 0 1 4 2 2 1 2 2 2 0 2 2 2 4 0

7 1 3

2

0 2 0

x0 x1 x2

1 0 3 3 0 0 0 2 6 2 0 0 0 2 2 0 6 2 2 1 0

3 3 0

3

x0 x1 x2

0 0 0 0 2 2 2 2 2 2 2 2 0 0 2 0 2 2 2 0 0

0 2 0

The registered witness family shares this format. Table VI prints the Grover block B = H ⊗3 CCZ (three cells, with the diffusion Hadamard layer absorbed into the boundary gauge; frame bits (a, b) = (4, 6), i.e. I⊗Z⊗Y up to global phase). This printed block is exact-certified as WIT-GROVER-BLOCK. The twelve-cell PACK-GROVER3 composite is a separate registered pack assembled from four chained blocks; its evidence is the stored checkpoint/frame ledger, expected distribution, sampled branch replay, and runtime admission (Sec. VII), not a new primitive exact-witness theorem. Artifact filenames are mapped in App. C. TABLE VI. The Grover-block witness B = H ⊗3 CCZ: measurement angles in units of π/4, same format and schedule class as Table V; composite equals (I⊗Z⊗Y ) · H ⊗3 CCZ (phase-preserving 24-column period; Sec. V D). Handle: WIT-GROVER-BLOCK.

Table VIII prints the fixed middle-target fallback witness WIT-CCX4: four cells, controls on x0 , x2 , target row x1 , and frame bits (a, b) = (7, 6), i.e. X⊗Y ⊗Y up to global phase. It is exact-certified by EXACT-WIT; the independent floating reconstruction has maximum elementwise deviation 9.16 × 10−16 after global-phase alignment. The searched three-cell closure failure is scoped to the end-safe schedule family used by the witness search, whereas the four-cell table is evidence for row-placement asymmetry and fallback realizability, not the selected production Toffoli path. TABLE VIII. The fixed middle-target four-cell CCX fallback witness (WIT-CCX4, controls x0 , x2 , target wire x1 ): measurement angles in units of π/4, same format as Table V; composite equals (X⊗Y ⊗Y ) · CCX0,2→1 exactly (Sec. VIII).

20 relative measured column cell wire 0 1 2 3 4 5 6

7

1

x0 x1 x2

3 0 5 6 2 3 0 0 1 2 2 2 2 2 3 2 2 1 4 2 0

2 3 0

2

x0 x1 x2

2 0 0 0 2 2 0 0 2 2 0 0 0 2 2 0 2 1 0 0 0

0 1 0

3

x0 x1 x2

2 2 0 6 2 3 0 2 2 2 2 0 2 2 2 4 6 0 4 2 6

3 0 0

4

x0 x1 x2

3 0 0 6 2 3 0 2 1 4 1 2 2 0 3 4 0 0 3 2 6

2 2 0

Appendix C: Reproducibility and Availability

TABLE IX. Implementation mapping for the public L1/L2/L3/R1 terminology used in the manuscript. Historical pass labels are audit labels; the theory is the arity-stratified certify–construct–admit calculus of Sec. VII.

Manuscript layer

Runtime/audit labels

Primary implementation files

L1 one-wire resynthesis

R2-HH, R9, R10/SYNTH1Q

local cancellation.py, template synthesis.py, angle resynthesis.py, single brick synthesis.py

L2 two-wire resynthesis

E1-T, R12-E-pre, R11, L2-Reduce

two wire t context synthesis.py, two wire region synthesis.py, two wire synthesis.py, l2 reduce.py

L3 three-wire application synthesis CCZ/CCX witnesses, N3 candidates l3 ccz witness.py, l3 toffoli core.py, n3 region decomposer.py, l3 grover3 runtime pack.py, payload builder.py R1 compact materialization

compact scheduling

loop.py and the final BFK09 pattern materializers

Equivalence gate

EQUIV-GATE

equivalence harness and frozen manifests

TABLE X. Claim-to-artifact map. The table reports stable manuscript-facing handles; the companion manifest maps each handle to the exact scripts, JSON outputs, hashes, and internal provenance identifiers in the submitted artifact package.

claim (anchor)

manuscript-facing artifact handle

exact cell/macro-cell maps (Secs. III–V)

CELLMAP-3W: transfer maps

n=1 reachability filtration (Cor. 1)

HCOUNT-1W: reachability filtration

two-wire finite-class CNOT-cost floor (Cor. 2)

L2-FLOOR: finite-class optimality certificate

odd-support syndrome, kernel mod 8 (Lem. 3)

LEDGER-KERNEL: Smith-form certificate

floor algorithm + battery (1, 1, 2, 3, 3, 3) (Secs. IV–V)

FLOOR-3W: floor battery

phase-gadget two-cell CCZ no-go (Thm. 2)

CCZ-NOGO-PG: phase-gadget no-go search

three-cell witness, frame decode (Thm. 3)

WIT-CCZ3: witness + reconstruction

Grover block and 12-cell pack (Sec. V D)

WIT-GROVER-BLOCK, PACK-GROVER3

endpoint Toffoli three-cell application (Sec. VIII)

WIT-CCX-TARGET2: exact witness + endpoint branch replay

branch closure, 72+3000 branches (Thm. 4)

BRANCH-CLOSURE: branch replay

four local identities; OTP fact (Thms. 4, 5)

LOCAL-ID: identity checks

decomposer/converter generality (Sec. VII)

PIPELINE-CHECK: converter/decomposer

server probe 3 × 98, 182 s (Sec. VIII)

RUN-GROVER3: server probe; full-stack harness separated

histogram statistics (Fig. 4)

STAT-GROVER3: measured distribution

test-round reference (Sec. VIII)

TRAP-REF: trap/abort reference

middle-target Toffoli fallback (App. B)

WIT-CCX4: registered four-cell witness

exact cyclotomic certificates for WIT-CCZ3/WIT-GROVER-BLOCK/WIT-CCX-TARGET2/WIT-CCX4 EXACT-WIT: integer identities constant window beyond three wires (Sec. III)

SMOKE-N4: n=4 window test

dynamic-circuit resource schedule (Table I)

HW-SCHEDULE: resource model

regression-equivalence gate, 10/10 (Sec. VIII)

EQUIV-GATE: legacy-vs-unified harness

benchmark/control coverage (Table III)

BENCH-CORPUS: frozen matrix

paper-audit support scripts (no wrapper claim)

PAPER-AUDIT: manuscript consistency support

21 Archive and integrity. The reported numerical results in the tables, figures, and evaluation claims mapped above trace to artifacts in the submitted artifact package anc/artifact package/. SHA256SUMS.txt fixes the individual files inside the package, and scripts/verify hashes.ps1 checks those file-level hashes. Public artifact record. The package is supplied as ancillary material with this arXiv submission. The artifact package, manifest.json, and SHA256SUMS.txt define the public record for the reproducibility bundle; usage and license status are stated in USAGE AND LICENSE.txt. A DOI-bearing archive can be cited in later versions when available. Printed and artifact-dependent checks. The paper remains independently checkable at its load-bearing witness points without the runtime package: the principal angle tables are printed in Tables V–VIII and, together with the brickwork semantics fixed in Secs. II and V D, suffice to reconstruct the central CCZ, Grover-block, and CCX witness identities on a standard MBQC simulator; all proofs appear in full in App. A. Sampled histograms, server timings, benchmark matrices, resource-model outputs, and full-stack regression checks are artifact-backed claims, with the Grover-3 distribution represented by STAT-GROVER3 and visualized in Fig. 4. Environment and entry points. The package separates docs/ (methodology notes), verification/ (self-contained scripts and their JSON outputs), witnesses/ (registered angle tables), results/ (frozen server-probe, benchmark, resource-model, and statistics artifacts), runtime v4/ (the code-only runtime used by the full checks), and scripts/ (reproducibility entry points). One environment pin is load-bearing for full runtime reproduction: the production basis-stream generation is pinned to Qiskit 1.3.3 [32]—later major versions emit a different Grover-3 stream, in which the final semantic fold does not arise—while the central witness and floor checks are SDK-free apart from NumPy. Table X maps claims to stable manuscript-facing artifact handles. The manifest.json file is the authoritative map from each handle to scripts, JSON outputs, hashes, and internal revision identifiers; the latter are engineering labels, not proof objects. The reproducibility entry points are scripts/run quick checks.ps1 for the SDK-free witness/floor checks and scripts/run full checks.ps1 for the same checks plus the EQUIV-GATE fast full-stack battery and L3 witness/materializer validation. The PAPER-AUDIT handle denotes support scripts and frozen outputs used for manuscript consistency; no single wrapper is claimed here.

Statements drafted on one track were audited on the other before being promoted to claims, and the manuscript-facing numerical and figure claims listed in App. C were then anchored to machine-checked artifacts. Mandatory acceptance assertions gate the runtime path, including per-window recomposition fidelity, registered

witness admission, frame-ledger checks, materializedwindow equality, and Grover-3 pack checkpoint checks. We also report the failures this methodology caught, because they clarify the claims that survived crosschecking. Four would-be over-claims were intercepted by cross-audit before any external statement: (i) an early version of the cell-count limit theorem counted cells against a relabeled sub-core and was re-proved with the corrected statement; (ii) the parity-ledger necessity argument originally asserted coefficient uniqueness mod 8— false, the parity-evaluation kernel has order 32—and was repaired into the odd-support syndrome invariant of Lemma 3 via the Smith-normal-form analysis; (iii) a results draft quoted a single binomial draw (≈ 83 traps) as the per-round trap count where the expectation (≈ 73) was meant; (iv) an enumeration claim overstated its scope (“fully enumerated” for n = 3) and was rescoped to exhaustive-for-n ≤ 2 with group-order-verified sampling at n = 3. These repairs are documented by the corresponding audit scripts or revision notes rather than silently absorbed. The same discipline produced the paper-audit support scripts of App. C, which check the manuscript-facing numerical statements and figure data covered by PAPER-AUDIT against artifacts.

[1] A. M. Childs, Secure assisted quantum computation, Quantum Information and Computation 5, 456 (2005), arXiv:quant-ph/0111046. [2] R. Raussendorf and H. J. Briegel, A one-way quantum

computer, Physical Review Letters 86, 5188 (2001). [3] A. Broadbent, J. Fitzsimons, and E. Kashefi, Universal blind quantum computation, in Proc. 50th Annual IEEE Symposium on Foundations of Computer Science

Appendix D: Independent Cross-Verification Methodology

The results in this paper were produced under a deliberate two-track discipline. Here “independent implementation” means independently coded from the candidategeneration or production-runtime path at the checked boundary, while sharing the declared mathematical conventions, witness file schema, and public artifact inputs. The independently checked boundaries are the theory-side transfer-matrix machinery, the production runtime materializers, the stored witness rebuilds, and the Grover-3 pack validation. evidence class

examples

meaning

exact arithmetic

EXACT-WIT, floor certificates

integer or finite-enumeration identity

witness maps, transfer matrices

machine-precision agreement after phase alignment

floating rebuild

JSON/checkpoint identity PACK-GROVER3, runtime admission stored semantic checkpoints and frame ledgers agree sampled replay/statistics

branch replay, histograms

implementation and empirical evidence within stated scope

22 (FOCS) (2009) pp. 517–526, arXiv:0807.4154. [4] J. F. Fitzsimons and E. Kashefi, Unconditionally verifiable blind quantum computation, Physical Review A 96, 012303 (2017), arXiv:1203.5217. [5] D. Leichtle, L. Music, E. Kashefi, and H. Ollivier, Verifying BQP computations on noisy devices with minimal overhead, PRX Quantum 2, 040302 (2021), arXiv:2109.04042. [6] P. Drmota, D. P. Nadlinger, D. Main, B. C. Nichol, E. M. Ainley, D. Leichtle, A. Mantri, E. Kashefi, R. Srinivas, G. Araneda, C. J. Ballance, and D. M. Lucas, Verifiable blind quantum computing with trapped ions and single photons, Physical Review Letters 132, 150604 (2024), arXiv:2305.02936. [7] B. Polacchi, D. Leichtle, G. Carvacho, G. Milani, N. Spagnolo, M. Kaplan, E. Kashefi, and F. Sciarrino, Experimental verifiable multiclient blind quantum computing on a Qline architecture, Physical Review Letters 134, 200603 (2025). [8] V. Danos, E. Kashefi, and P. Panangaden, The measurement calculus, Journal of the ACM 54, 8 (2007), arXiv:0704.1263. [9] W. Simmons, Relating measurement patterns to circuits via Pauli flow (2021), arXiv:2109.05654 [quant-ph]. [10] T. McElvanney and M. Backens, Complete flowpreserving rewrite rules for MBQC patterns with Pauli measurements (2022), arXiv:2205.02009 [quant-ph]. [11] S. Sunami and M. Fukushima, Graphix: optimizing and simulating measurement-based quantum computation on local-Clifford decorated graph (2022), arXiv:2212.11975. [12] R. Duncan, A. Kissinger, S. Perdrix, and J. van de Wetering, Graph-theoretic simplification of quantum circuits with the ZX-calculus, Quantum 4, 279 (2020), arXiv:1902.03178. [13] M. Amy, D. Maslov, and M. Mosca, Polynomial-time Tdepth optimization of Clifford+T circuits via matroid partitioning, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 33, 1476 (2014), arXiv:1303.2042. [14] M. DeCross, E. Chertkov, M. Kohagen, and M. FossFeig, Qubit-reuse compilation with mid-circuit measurement and reset, Physical Review X 13, 041057 (2023), arXiv:2210.08039. [15] Y. Lee and D. Chung, Simulation of two-qubit Grover algorithm in MBQC with universal blind quantum computation (2025), arXiv:2503.09099 [quant-ph]. [16] D. E. Browne, E. Kashefi, M. Mhalla, and S. Perdrix, Generalized flow and determinism in measurement-based quantum computation, New Journal of Physics 9, 250 (2007), arXiv:quant-ph/0702212. [17] S. Aaronson and D. Gottesman, Improved simulation of stabilizer circuits, Physical Review A 70, 052328 (2004), arXiv:quant-ph/0406196. [18] D. Gottesman, The Heisenberg representation of quantum computers (1998), arXiv:quant-ph/9807006.

[19] A. Cowtan, S. Dilkes, R. Duncan, W. Simmons, and S. Sivarajah, Phase gadget synthesis for shallow circuits, Electronic Proceedings in Theoretical Computer Science 318, 213 (2020), arXiv:1906.01734. [20] Y. Makhlin, Nonlocal properties of two-qubit gates and mixed states and optimization of quantum computations, Quantum Information Processing 1, 243 (2002), arXiv:quant-ph/0002045. [21] V. V. Shende, S. S. Bullock, and I. L. Markov, Synthesis of quantum-logic circuits, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 25, 1000 (2006), arXiv:quant-ph/0406176. [22] L. K. Grover, A fast quantum mechanical algorithm for database search, in Proc. 28th Annual ACM Symposium on Theory of Computing (STOC) (1996) pp. 212–219, arXiv:quant-ph/9605043. [23] A. Gheorghiu, T. Kapourniotis, and E. Kashefi, Verification of quantum computation: An overview of existing approaches, Theory of Computing Systems 63, 715 (2019). [24] S. Barz, E. Kashefi, A. Broadbent, J. F. Fitzsimons, A. Zeilinger, and P. Walther, Demonstration of blind quantum computing, Science 335, 303 (2012), arXiv:1110.1381. [25] A. Mantri, C. A. Pérez-Delgado, and J. F. Fitzsimons, Optimal blind quantum computation, Physical Review Letters 111, 230502 (2013), arXiv:1306.3677. [26] U. Mahadev, Classical verification of quantum computations, in Proc. 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (2018) pp. 259–267, arXiv:1804.01082. [27] C.-H. Chien, R. Van Meter, and S.-Y. Kuo, Fault-tolerant operations for universal blind quantum computation, ACM Journal on Emerging Technologies in Computing Systems 12, 9 (2015), arXiv:1306.3664. [28] Z. Yang, M.-Q. Bai, and Z. Mo, The brickwork state with fewer qubits in blind quantum computation, Quantum Information Processing 21, 125 (2022). [29] S. Ma, C. Zhu, X. Liu, H. Li, and S. Li, Universal blind quantum computation with improved brickwork states, Physical Review A 109, 012606 (2024). [30] V. Kliuchnikov, D. Maslov, and M. Mosca, Fast and efficient exact synthesis of single qubit unitaries generated by Clifford and T gates, Quantum Information and Computation 13, 607 (2013), arXiv:1206.5236. [31] N. J. Ross and P. Selinger, Optimal ancilla-free Clifford+T approximation of z-rotations, Quantum Information and Computation 16, 901 (2016), arXiv:1403.2975. [32] A. Javadi-Abhari, M. Treinish, K. Krsulich, C. J. Wood, J. Lishman, J. Gacon, S. Martiel, P. D. Nation, L. S. Bishop, A. W. Cross, B. R. Johnson, and J. M. Gambetta, Quantum computing with Qiskit (2024), arXiv:2405.08810 [quant-ph].