{"id":"7165d631-7094-4a0c-8cf8-d6205468cacb","arxiv_id":"2608.13543","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"New block-matrix algorithms synthesize distributed CNOT and Clifford circuits with provably near-minimal non-local gates, with an application to CSS code compilation.","lead":"This paper gives algorithms that rewrite quantum circuits for modular computers, using fewer expensive operations between distant qubit blocks, and proves the count is near the theoretical minimum. It matters for future fault-tolerant machines, where cross-module operations are the slow and error-prone bottleneck.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The central theorem (2n(k-1) non-local gates for BlockRowCol and DistRowCol, asymptotically optimal for k=o(n/log n)) survives scrutiny. I checked the decomposition of C(A,B) into one CNOT plus local Cliffords: the cited fact is standard and the emitted gates never have identity Pauli strings, so the proxy is exact. The block-Gaussian-elimination argument correctly bounds block row additions by 2k(k-1), each costing at most n/k rank-factorized gates. The lower bound's constant is affected by sign omissions but not its asymptotic exponent. The k=2 constant-factor optimality proof is careful about row-space dimensions. The only weaknesses I see are minor: Lemma 5.1's proof is sketchy but it supports only an optional subcircuit-detection heuristic, and the missing code snapshot/hash is a reproducibility issue, not a correctness issue. These do not change the conditional acceptance already given.","tokens_in":38302,"tokens_out":41796,"duration_ms":396640,"concrete_test":"Instrument the public implementation to count, on random CNOT parity matrices (n=64, k=8), the total number of generalized CNOT gates emitted by BlockRowCol and verify it never exceeds 2n(k-1); additionally, take a random emitted C(A,B), conjugate with the local Cliffords from §2.2, and confirm the result is exactly one non-local CNOT plus local gates.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I could not identify a load-bearing flaw in the central claim. The cost model in §2.2 is valid: any non-identity Pauli string can be conjugated to a single-qubit Z or X by local Cliffords, so C(A,B) is (U†⊗V†)CNOT(U⊗V) with exactly one non-local CNOT; the algorithms never emit C(A,B) with A or B identity, so the proxy is exact. The 2n(k-1) upper bound for BlockRowCol follows from at most 2k(k-1) block row additions (Lemma 3.4, rank ≤ n/k per addition), and the same count holds for DistRowCol if one sums the Steiner-tree edge bounds over the decreasing set of active partitions. The lower bound (Lemma 3.7) ignores ± signs on Pauli strings, which changes constants by a factor logarithmic in gate count, not asymptotics. Lemma 5.1 is used only for optional CNOT-subcircuit detection, not for Theorems 3.1/4.1.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper develops methods for minimizing non-local gates in distributed CNOT, Clifford, and Clifford+RZ circuits when qubits are partitioned into k blocks with arbitrary inter-block connectivity. The central construction is a representation in which non-local Clifford operations are written as generalized CNOT gates C(A,B), each costing one physical non-local CNOT. The main results are BlockRowCol for CNOT circuits and DistRowCol for Clifford circuits, both using at most 2n(k−1) generalized CNOT gates regardless of partition connectivity, with a counting lower bound showing asymptotic optimality when k=o(n/log n), and a constant-factor approximation for k=2. The paper also presents a Clifford+RZ resynthesis heuristic with generalized-CNOT folding, a DAG bin-packing method for finding Clifford/CNOT subcircuits, benchmarks against pytket-dqc, and applications to CSS codes, phantom codes, the bicycle architecture, and tree tensor networks.","tokens_in":38327,"tokens_out":33327,"duration_ms":371768,"significance":"Assuming the main theorems are correct, this is a substantial contribution to distributed quantum compilation: it replaces topology-dependent routing heuristics with a tableau/linear-algebra method whose non-local gate count depends only on n and k, rather than on the inter-block graph. The proofs are explicit and the pseudocode is complete enough to reimplement; the counting lower bounds are parameter-free, and the claims are accompanied by a public implementation and benchmarks. The paper is appropriately cautious about the Clifford+T regime, where it reports worse performance than existing tools. The main advertised asymptotic claim concerns k=o(n/log n), and for that regime the argument is convincing. The main weaknesses are an overreach in the 'any k' optimality theorem and an error in the tree tensor network application.","major_comments":[{"comment":"The claim that running Patel–Markov–Hayes (or Aaronson–Gottesman) and choosing the better result gives asymptotic optimality for any value of k is not supported for arbitrarily restricted partition connectivity. Those algorithms synthesize circuits in an all-to-all qubit model; when k is large and the partition graph is not complete, their output can contain CNOTs between non-adjacent partitions, which are not valid non-local gates in the stated architecture. As written, the theorem either needs an explicit all-to-all connectivity assumption for this sentence, or it needs a connectivity-respecting O(n^2/log n) synthesis algorithm. The k=O(n/log n) part of the theorem is unaffected.","section":"§3.4, Theorem 3.2 (and §4.3, Theorem 4.1)"},{"comment":"The cost model for tree tensor networks is inconsistent. With n=2^a leaves and the cited scaling 2^{2l}, a highest-level gate (l≈a) has cost polynomial in n, not 2^{n/2}; writing '2^{n/2}' for the cost and calling 2^{2l} 'super-exponential' does not follow. The recurrence and the claimed O(2^{n/2} n log n) bound therefore need to be redone. The qualitative comparison with Patel–Markov–Hayes may survive with different exponents, but the current asymptotic statement is not justified.","section":"§8.4"}],"minor_comments":[{"comment":"The count of possible generalized CNOT gates uses 4^{n/k} for each Pauli string, but P^±_{n/k} has 2·4^{n/k} elements; the constant in the lower-bound estimate should be adjusted. The asymptotic conclusion is unchanged.","section":"§3.4, Lemma 3.7"},{"comment":"The condition 'i_1 ≠ ±I_2' appears to be a typo for i_1 ≠ i_2.","section":"§2"},{"comment":"The phrase 'super-exponential in the level' misdescribes 2^{2l}, which is exponential in l.","section":"§8.4"},{"comment":"The statement that non-ZX-type gates provide no benefit for CNOT unitaries is phrased as an expectation based on [31]; please state explicitly that Theorem 3.3 is restricted to ZX-type circuits and that the broader optimality claim is conditional.","section":"§3.4, discussion before Theorem 3.3"}],"recommendation":"major_revision","confidential_remarks":"The central synthesis results are sound and the paper should be publishable after the overclaim in Theorems 3.2/4.1 is fixed and Section 8.4 is corrected. The 'any k' statement is the kind of claim that could mislead readers; I would ask the authors to either prove it with an architecture-aware algorithm or restrict the statement. No concerns about novelty or citation behavior."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The central claim in this paper holds up. BlockRowCol and DistRowCol use at most 2n(k-1) non-local gates for distributed CNOT and Clifford synthesis on any connected architecture, and the lower bound in Lemma 3.7, modulo a constant-factor slip, supports asymptotic optimality for k = o(n/log n). I'd engage with this seriously.\n\nWhat's actually new: the block-matrix reinterpretation of RowCol, the tableau-based DistRowCol, the k=2 constant-factor approximation theorem (Theorem 3.3), and the CSS-code application (Theorem 8.1). The upper-bound proofs are detailed enough to reimplement, and the pseudocode is complete. The cost model—one non-local CNOT per generalized CNOT—is valid, since any Pauli string can be conjugated to a single-qubit Z or X by local Cliffords, and the algorithms never emit identity strings. No fitted parameters, no circular reasoning. The benchmarks are honest, including the clear admission that the Clifford+T results are often worse than existing tools.\n\nSoft spots, in proportion: Lemma 3.7 undercounts Pauli string choices by dropping the ± signs in P^±, which has 2·4^(n/k) elements rather than 4^(n/k). That weakens the constant in the lower bound but not the asymptotics, so it's a minor fix. Lemma 5.1, the CNOT-subcircuit detection lemma, has a sketchy proof (the co-diagonalization step is hand-waved), but it's only used for optional peephole optimization, not for Theorems 3.1 and 4.1. The implementation is public but lacks a commit hash or data snapshot, which makes exact reproduction harder than it should be. Finally, the optimality statement is for worst-case inputs; for fixed k the constant factor is what it is.\n\nOverall this is a serious theory-and-implementation paper. The main theorems are well supported. I'd send it to peer review, and ask the author to fix the constant in Lemma 3.7, tighten Lemma 5.1, and pin the code version.","headline":"Solid distributed-CNOT/Clifford synthesis paper with a correct central theorem; the lower-bound constant needs a small fix but the asymptotics hold.","tokens_in":38992,"tokens_out":2142,"would_cite":true,"duration_ms":20109,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Block-matrix Gaussian elimination compiles distributed CNOT and Clifford circuits with at most 2n(k−1) non-local gates on any connected partition topology, and matches the lower bound when k grows slowly relative to n.","keywords":["distributed quantum computing","Clifford circuit synthesis","CNOT circuit synthesis","generalized CNOT gates","block matrix Gaussian elimination","Steiner tree routing","stabilizer tableau","CSS codes"],"falsifier":"Pick two partitions of size $n/k \\ge 2$, choose random Pauli strings $A$ and $B$, and synthesize the generalized CNOT gate $C(A,B)$ down to physical CNOTs using the local-Clifford construction of [15]; if any such gate requires more than one CNOT between the partitions, then the quantity being minimized is not the physical non-local gate count, and the paper's bounds and optimality theorems would be stated about the wrong quantity.","tokens_in":37966,"feed_emoji":"⚛️","tokens_out":13789,"duration_ms":131677,"temperature":0.7,"pith_summary":"This paper claims that distributing a quantum circuit over $k$ blocks need not cost many extra non-local operations: for $n$ qubits split into $k$ equal partitions, both CNOT circuits and full Clifford circuits can be resynthesized with at most $2n(k-1)$ non-local gates, for any connected graph between the partitions. When the number of partitions is small relative to the number of qubits ($k=o(n/\\log n)$), the paper proves this bound is asymptotically optimal, and for $k=2$ it gives a factor-2 approximation for every input circuit. The construction works by viewing the parity matrix (or stabilizer tableau) as a block matrix and performing Gaussian elimination on blocks, where each block operation is realized with generalized CNOT gates that cost one physical non-local CNOT each. A reader should care because non-local gates dominate time and error budgets in modular fault-tolerant quantum computers and block-code architectures, so a connectivity-independent formula for their minimum is a practical compilation target.","feed_headline":"Distributed CNOT synthesis cut to 2n(k−1) non-local gates","feed_subtitle":"Block matrix elimination matches the lower bound for CNOT and Clifford circuits on any connected partition topology.","key_machinery":"The load-bearing object is the generalized CNOT gate $C(A,B)=e^{i\\pi/4 (A\\wedge B)}$, a Clifford gate between two partitions whose Pauli strings $A$ and $B$ can be made to look like $Z$ and $X$ by local Cliffords, so each one costs exactly one physical non-local CNOT. The algorithm's workhorse is the block row addition on a parity matrix or tableau: a binary coefficient matrix $R$ describing which rows of one partition are added to rows of another. ZX-type generalized CNOT gates act as rank-one block row additions, and the rank factorization of $R$ turns any block row addition into $\\mathrm{rank}(R)$ such gates. Steiner trees route the elimination through the partition connectivity graph while the row-space lemmas maintain the required inclusions, and for Clifford circuits a symplectic analogue supplies the anticommuting Pauli strings needed to disentangle one partition at a time.","core_discovery":"The central discovery is that the hard part of distributed CNOT synthesis—eliminating the interaction between partitions—reduces to block Gaussian elimination on the parity matrix. Off-diagonal blocks are cleared by block row additions, and a ZX-type generalized CNOT gate performs exactly a rank-one block row addition, so any block row addition with coefficient matrix $R$ costs $\\mathrm{rank}(R)$ such gates. The resulting algorithms, BlockRowCol and its Clifford analogue DistRowCol working on stabilizer tableaux, use at most $2n(k-1)$ non-local gates on any connected inter-partition graph; the paper proves this as Theorems 3.1 and 4.1. A counting argument shows this is asymptotically optimal whenever $k=o(n/\\log n)$, and running the better of this method and standard linear-reversible synthesis is asymptotically optimal for every $k$. For $k=2$ the algorithm is within a factor of two of optimal on every input. The representation also extends to Clifford+RZ circuits by generalizing the Pauli exponential representation, and to CSS codes, where any logical CNOT circuit can be implemented with $O(k^2)$ inter-block transversal CNOTs and $O(nk)$ intra-block Pauli measurements.","pith_inferences":["Beyond the paper: because block row addition is a generic primitive on parity matrices and tableaux, other synthesis engines—SAT-based, template-based, or peephole optimizers—could likely be given the same block treatment rather than being restricted to Gaussian elimination.","Beyond the paper: the CSS-code translation suggests a compiler recipe for any code with a transversal gate: express block row additions in that inter-block primitive and pay a cost depending on the number of blocks rather than the number of qubits, which could generalize to codes with other transversal primitives.","Beyond the paper: the benchmarks' suggestion that Clifford+RZ resynthesis rarely beats the input circuit points to a testable hypothesis—for T-rich circuits the bottleneck is phase structure, not inter-block connectivity—which could be checked by fixing T-count and increasing block size while watching whether non-local gates per phase gate saturate."],"forward_implications":["For any connected graph between partitions, every CNOT circuit on $n$ qubits in $k$ blocks can be compiled to at most $2n(k-1)$ non-local gates, and when $k=o(n/\\log n)$ no asymptotically better worst-case bound is possible.","The same $2n(k-1)$ guarantee holds for full Clifford circuits through DistRowCol, independent of inter-partition connectivity.","For $k=2$, BlockRowCol is a factor-2 approximation of the optimal non-local gate count for every individual CNOT circuit, not just in the worst case.","In a CSS code with one ancilla per block, any logical CNOT circuit can be implemented with at most $6k(k-1)$ inter-block transversal CNOTs and $O(nk)$ intra-block Pauli measurements, regardless of inter-block connectivity.","For Clifford+RZ circuits with $r$ phase gates, the distribution procedure introduces at most $2(k-1)(r+n)$ generalized CNOT gates, and the representation plugs into phase-folding and T-count optimization."],"supporting_citations":[{"why":"This supplies the Pauli exponential representation of circuits that the paper generalizes to the distributed setting.","marker":"[8]"},{"why":"This supplies the stabilizer tableau formalism used by DistRowCol for Clifford synthesis.","marker":"[10]"},{"why":"This is the RowCol CNOT synthesis algorithm that BlockRowCol generalizes to block matrices.","marker":"[11]"},{"why":"This supplies the architecture-aware tableau disentangling method that DistRowCol adapts to partitions.","marker":"[12]"},{"why":"This supplies the local-Clifford construction showing each generalized CNOT gate needs a single non-local CNOT, which sets the paper's cost model.","marker":"[15]"},{"why":"This supplies the Steiner-tree technique for eliminating columns under restricted connectivity, which the paper reuses for partition-level connectivity.","marker":"[26]"},{"why":"This supplies the standard linear-reversible synthesis algorithm used as a baseline and in the combined asymptotically optimal strategy, and contributes the counting lower-bound style.","marker":"[27]"}],"fun_headline_variants":["Block Gaussian elimination cuts distributed CNOT synthesis to O(nk)","Optimal distributed CNOT synthesis via block matrix elimination","Distributed Clifford circuits cut to 2n(k−1) non-local gates","Asymptotically optimal synthesis for distributed CNOT and Clifford","Block elimination matches lower bound for distributed CNOT circuits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The cost model assumes every generalized CNOT gate $C(A,B)$ can be implemented with exactly one non-local CNOT plus local Clifford operations; if that implementation ever required a non-constant number of non-local CNOTs, the $2n(k-1)$ bounds, the CSS-code operation counts, and the asymptotic optimality claims would all need to be rescaled.","fun_headline_variants_meta":{"raw":{"variants":["Block Gaussian elimination cuts distributed CNOT synthesis to O(nk)","Optimal distributed CNOT synthesis via block matrix elimination","Distributed Clifford circuits cut to 2n(k−1) non-local gates","Asymptotically optimal synthesis for distributed CNOT and Clifford","Block elimination matches lower bound for distributed CNOT circuits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000714,"raw_usage":{"total_tokens":3224,"prompt_tokens":972,"completion_tokens":2252,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":588,"completion_tokens_details":{"reasoning_tokens":2177}},"tokens_in":588,"tokens_out":2252,"duration_ms":17233,"temperature":1.0,"reasoning_tokens":2177,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T04:36:42.012431+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Pick two partitions of size $n/k \\ge 2$, choose random Pauli strings $A$ and $B$, and synthesize the generalized CNOT gate $C(A,B)$ down to physical CNOTs using the local-Clifford construction of [15]; if any such gate requires more than one CNOT between the partitions, then the quantity being minimized is not the physical non-local gate count, and the paper's bounds and optimality theorems would be stated about the wrong quantity.","supporting_citations":[{"cited_title":"Picturing Quantum Software: An Introduction to the ZX-Calculus and Quantum Compilation","cited_arxiv_id":null,"evidence_quote":"This supplies the Pauli exponential representation of circuits that the paper generalizes to the distributed setting."},{"cited_title":"Improved simulation of stabilizer circuits","cited_arxiv_id":null,"evidence_quote":"This supplies the stabilizer tableau formalism used by DistRowCol for Clifford synthesis."},{"cited_title":"Optimization of cnot circuits on limited-connectivity architecture","cited_arxiv_id":null,"evidence_quote":"This is the RowCol CNOT synthesis algorithm that BlockRowCol generalizes to block matrices."}],"review_version":1}