{"id":"771effa7-ddc6-49a6-b2a2-5e373008d702","arxiv_id":"2610.06768","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Optimal matchgate-Clifford circuit synthesis is solvable in O(n²) time on path and complete connectivity graphs but becomes NP-complete on arbitrary tree connectivity.","lead":"This paper proves that finding the shortest circuit for a matchgate-Clifford operation has sharply different difficulty by hardware connectivity: fast quadratic-time optimal compilers exist for line and fully-connected layouts, while the problem becomes NP-hard on arbitrary tree layouts.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek/deepseek-v4-flash","headline":"No significant objection identified: the reader's load-bearing step, Lemma 7 (braid orientations exist for any swap sequence in the tree reduction), survives scrutiny and the central claims appear sound.","rationale":"The reader identified Lemma 7 as the most load-bearing assumption, and structurally it is: the NP-completeness claim collapses if the sign-placement lemma fails. After working through the proof, I find the lemma correct. The two claims — (i) ∏ s*_j over any π-invariant component C equals sgn(π_C), and (ii) any even-parity sign vector on a connected swap-multigraph component is realizable by orientation flips — both check out; the F2 parity argument is sound, and the polynomial-time construction is just linear-system solving. I also verified the companion potential lemma (Lemma 1) for Theorem 1; the exactly-±1 change of Φ follows from the cut-dynamics argument and the inversion-count calculation for exchanging values a and a+1 at non-adjacent positions. Consequently no load-bearing concern lands against the central claims (Theorems 1, 3, 4, 5). The reader's two supporting reasons for CONDITIONAL remain valid as stated and are acknowledged by the authors: the benchmark's constant-factor improvements are tied to the non-uniform random-walk ensemble disclosed in Appendix B (the abstract's phrasing is loose), and Theorem 2's μ(π) exact computation is left open, so the two-qubit-optimal word is non-constructive while the factor-2 approximation is constructive. These are presentation and completeness notes, not refutations, and the paper discloses both. My read therefore does not move the verdict; it stays CONDITIONAL for the same reasons the reader gave. The concrete verification proposed (small-case exhaustive equality check) would settle the reduction's soundness independently and is worth running, but I expect it to pass.","tokens_in":34585,"tokens_out":23600,"duration_ms":155881,"concrete_test":"Enumerate all unlabeled trees T on at most 8 vertices, all permutations π ∈ S_8, form w*(π), and compute ℓ_T^swap(π) by exhaustive BFS over token configurations and ℓ_T^braid(w*(π)) by exhaustive BFS over signed-permutation states on T; verify ℓ_T^braid(w*(π)) = ℓ_T^swap(π) for every instance. A single counterexample refutes the reduction; if equality holds on all small instances, Lemma 7's structural premise is confirmed exactly where a flaw would be forced to appear.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The structural hinge is the NP-hardness reduction's sign-placement lemma (Lemma 7, Appendix E): for any swap sequence S on a tree realizing π, orientations ε_i exist so the braid product equals w*(π), and they are efficiently found. The equality ℓ_T(w*(π)) = ℓ_T(π) (projection gives ≥, Lemma 7 gives ≤) is what makes the reduction answer-preserving, so both Theorem 4 and Theorem 5 ride on it. I checked the proof's two claims. First, on any π-invariant component C of the swap multigraph H(S), the product of the assigned signs of w*(π) equals sgn(π_C): each cycle contributes sgn(C_i), so ∏_{j∈C} s*_j = ∏_{cycles in C} sgn(C_i) = sgn(π_C); likewise ∏_{j∈C} s_j(w∘) = (-1)^{(#braids involving tokens of C)} = sgn(π_C), since each braid toggles both tokens it swaps and contributes exactly one negative entry, and tokens of one component never exchange with tokens of another. Hence δ* has even weight on every component. Second, any even-weight vector on a connected component lies in the F2-span of edge vectors (path-telescoping of e_u+e_v), so the orientations exist and the linear system is solvable in polynomial time. Both steps hold. I also spot-checked Lemma 1 (the potential bound behind Theorem 1): exchanging values a and a+1 at possibly non-adjacent positions changes inv by exactly ±1 (each intermediate position contributes equally before and after), and new cuts appear only at a, so ΔΦ ∈ {±1}. The remaining flagged items are presentation/completeness notes rather than correctness defects: the ×2.57/×2.28 benchmark factors are scoped to the non-uniform random-walk ensemble of Appendix B (sentence b418), which the abstract understates but the body discloses, and Theorem 2's μ(π) exact computation is left open (b151, b505) — an acknowledged, non-constructive step inside a secondary theorem, not part of the path/complete/tree complexity separation itself. I could not identify a load-bearing error.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek/deepseek-v4-flash","summary":"This paper studies exact optimal synthesis in the matchgate-Clifford group, formulated as the shortest-word problem in the group of unit-determinant signed permutations B_{2n}∩SO(2n) acting on 2n Majorana modes, with generators given by Majorana braids along the edges of a specified connectivity graph. The main results are: (i) on a path, the optimal gate count equals the potential Φ(w) = inv(π) + 2ν(w), with a constructive O(n²)-time compiler (Theorem 1); (ii) the minimum number of two-qubit gates on a path is μ(π) + 2ν_even(w), with μ(π) sandwiched between F(π) and 2F(π), and a single word achieving both the minimum total count and the minimum two-qubit count (Theorem 2); (iii) on a complete graph, ℓ_all(w) = 2n − κ(π) + d₋(w), again in O(n²) (Theorem 3); (iv) on arbitrary trees, the decision versions of gate-optimal and depth-optimal synthesis are NP-complete (Theorems 4–5), by reduction from token swapping on trees via an explicit sign-placement lemma, with the result extended to general connected graphs (Corollary 1). A benchmark on chains up to n = 80 reports constant-factor gate-count improvements over Qiskit and pytket.","tokens_in":34946,"tokens_out":16997,"duration_ms":104264,"significance":"The paper delivers a clean complexity separation: exact optimal matchgate-Clifford synthesis is polynomial-time with exact closed-form word lengths for path and complete connectivities, yet NP-complete on trees. The proofs combine potential-method lower bounds with matching constructive upper bounds and are unusually detailed; the NP-hardness reduction is answer-preserving through Lemma 7, whose two key steps (sign-defect vectors of even weight on every π-invariant component of the swap multigraph, and the F2-span realizability of such vectors) I verified. The closed forms also give exact diameters of the relevant Cayley graphs. The benchmark code and data are publicly available, which supports reproducibility of the empirical claims. I found no load-bearing errors: Lemma 1 (the potential change ±1, with new cut points only at position a) and Lemma 7 (orientation placement for arbitrary swap sequences) both hold as stated.","major_comments":[],"minor_comments":[{"comment":"The formula #₂(w) = μ(π) + 2ν_even(w) is exact, but the main term μ(π) is not known to be efficiently computable, a point the authors acknowledge immediately after the theorem ('The exact evaluation of the routing term μ(π) and how to construct a word that achieves it remains open'). Since the paper's headline is O(n²) solvability, I recommend carrying a one-line caveat into the theorem statement itself so readers do not read Theorem 2 as an efficiently computable closed form.","section":"§3.1.2, Theorem 2","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The multiplicative ratios (2.57, 2.28, etc.) are computed from unweighted linear fits over means of 10, 10, 8, 8, 6, and 5 targets per size; with only 5 targets at n = 80, the 'constant factor' claim should be reported explicitly as a fit ratio, ideally with per-size ratios and confidence intervals. It would also help to state in the caption or main text that Qiskit and pytket do not exploit the signed-permutation structure, so part of the observed gap is structural rather than algorithmic.","section":"§3.1.1 and Fig. 3","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"Reference [35] (Miltzow et al., on token swapping approximation) is cited to support 'well-known sorting algorithms for permutation matrices'; that reference does not appear to contain such an algorithm, and a standard sorting or inversion-distance reference would fit better.","section":"§3.1, Introduction","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"Reference [21] lists the author as 'A. Acuaviva, A. Acuaviva, and P. Acuaviva', which appears to be a transcription error; please correct the author list.","section":"References","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"Minor typo: 'in the grap' should read 'in the graph'.","section":"Appendix C, Lemma 5","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The number of sampled targets per circuit size appears only in Appendix B; a brief note in the caption would help readers interpret the error bars and the fit-based ratios directly from the figure.","section":"Appendix B / Fig. 3 caption","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"Because the reduction must construct the sign configuration w*(π) from the permutation alone, without prior knowledge of an optimal routing (a point the authors correctly emphasize), a small worked example of Lemma 7 on a short tree would substantially clarify the argument for readers.","section":"§3.3","authors_acknowledge":null,"authors_acknowledge_p":null}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is technically strong and, in my reading, correct: I verified the two load-bearing steps (Lemma 1's potential bound for the path case and Lemma 7's sign-placement for the tree reduction) and found no gaps. The recommendation is driven by presentation issues only. Two points for the editor: (1) the AI-assistance disclosure states that ChatGPT 5.6 and Claude were used 'to prove the main results'; the authors assert independent verification, and the proofs are checkable in detail, but please confirm this satisfies the journal's policy on AI use. (2) The paper leans on a cluster of recent group-internal references (e.g., Refs. [24], [29], [72], [74], [77]), but the load-bearing external citation (Aichholzer et al. on token swapping on trees) is published and appropriately used; I do not see a citation-pattern problem."},"author_rebuttal":null,"desk_editor":{"model":"deepseek/deepseek-v4-flash","letter":"The headline result is a genuine first: closed-form word lengths for optimal matchgate-Clifford synthesis under Majorana-braid generators on a path (ℓ_R = inv(π) + 2ν(w)) and all-to-all connectivity (ℓ_all = 2n − κ(π) + d_(w)), each realized by an O(n²) optimal compiler, plus NP-completeness of the decision version on arbitrary trees via a reduction from token swapping. Matchgate synthesis complexity was open in [24], and the path/complete-versus-tree separation is new. Standard Coxeter length functions for types B and D use different generators and miss the sign-correction term, so these formulas are not derivative.\n\nThe proofs are honest potential-method arguments with matching lower and upper bounds, no fitted parameters. Lemma 1, the step that each generator changes Φ by ±1, is the delicate part and it holds: the analysis of when a cut appears or disappears at position a, ruling out the ±3 jump, is correct. The NP-hardness reduction leans on Lemma 7, the sign-placement lemma — for any swap sequence on a tree realizing π, you can orient braids to realize the signed permutation w*(π). I checked the parity argument on each π-invariant component and the F₂-span argument (path-telescoping of e_u + e_v); both go through, so the equality ℓ_T(w*(π)) = ℓ_T(π) that carries the reduction stands.\n\nTwo soft spots, both minor and both acknowledged in the text. First, the ×2.57 and ×2.28 benchmark factors are scoped to the non-uniform random-walk ensemble of Appendix B; the body states this explicitly, but the abstract reads as general. The abstract should carry the ensemble qualifier. Second, Theorem 2's two-qubit-optimal formula #2(w) = μ(π) + 2ν_even(w) is not yet fully constructive because computing μ(π) is left open; the factor-2 approximation is the constructive part, and the authors say so. That is a completeness note on a secondary theorem, not a flaw in the main separation. I found no load-bearing error. The paper also discloses AI assistance and states independent verification of all arguments, which matches the detail level of the proofs.\n\nThis is for people working on fermionic simulation, matchgate compilation, classical shadows, and signed-permutation combinatorics; the compiler itself is practically useful. It deserves a serious referee.","headline":"A solid complexity separation for matchgate-Clifford synthesis: poly-time optimal compilers on path and all-to-all connectivity, NP-completeness on trees, with two minor presentation caveats in the benchmark claims and the two-qubit formula.","tokens_in":35688,"tokens_out":2308,"would_cite":true,"duration_ms":17236,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"pith_extraction":{"msc":["68Q17","81P68","20F55","05A05"],"pacs":["03.67.Lx"],"model":"deepseek/deepseek-v4-flash","headline":"Optimal synthesis of matchgate-Clifford circuits is easy on a line or all-to-all graph, but deciding it is NP-complete on arbitrary trees.","keywords":["matchgate-Clifford group","optimal unitary synthesis","Majorana braids","signed permutation group","token swapping","NP-completeness","fermionic linear optics","Cayley graph word length"],"falsifier":"Enumerate all permutations and all shortest swap routings on small trees (up to six or eight vertices) and check that the sign-placement lemma always holds: for each shortest routing, an orientation realizing the per-cycle signed permutation must exist and be found in polynomial time, and a single counterexample falsifies the NP-hardness reduction. Separately, on path and complete graphs with small $n$ ($2n \\le 10$ modes), compute the true shortest braid distance by breadth-first search on the Cayley graph and compare against the closed forms $\\mathrm{inv}(\\pi) + 2\\nu(w)$ and $2n - \\kappa(\\pi) + d_-(w)$; any mismatch would falsify Theorems 1 and 3.","tokens_in":35965,"feed_emoji":"🌲","tokens_out":8182,"duration_ms":41340,"temperature":0.7,"pith_summary":"Matchgate-Clifford unitaries are a standard class of classically simulable quantum circuits, and their adjoint action on Majorana operators is exactly the group of unit-determinant signed permutations of $2n$ modes. This paper asks how many Majorana-braid gates are needed to realize a given such unitary, and shows the answer depends on which edges of the connectivity graph the braids may use. On a path and on the complete graph, the optimal word length has a closed-form expression and an optimal compiler runs in $O(n^2)$ time. On an arbitrary tree, the decision version of optimal synthesis is NP-complete, in both gate count and depth. The path-graph compiler beats Qiskit and Tket by constant factors on chains of up to 80 qubits.","feed_headline":"Matchgate-Clifford synthesis easy on a line, NP-hard on trees","feed_subtitle":"Optimal compilers run in quadratic time on lines and all-to-all graphs; tree connectivity makes the decision problem NP-complete.","key_machinery":"The argument runs on the isomorphism between the adjoint action of the matchgate-Clifford group and the group $B_{2n} \\cap SO(2n)$ of unit-determinant signed permutation matrices of the $2n$ Majorana modes. Two potentials carry the positive results: on the path, $\\Phi(w) = \\mathrm{inv}(\\pi) + 2\\nu(w)$, where $\\nu(w)$ counts the negative defects, cuts $c$ where the leading $c\\times c$ minor has determinant $-1$, and the proof uses the connectedness of the inversion graph of a cut-free permutation to flip signs at no extra gate cost; on the complete graph, $\\Phi_{\\mathrm{all}}(w) = 2n - \\kappa(\\pi) + d_-(w)$, with $d_-$ counting defective cycles. For the NP-hardness, the load-bearing object is a sign-placement lemma that assigns signs to cycles of the underlying permutation, negative on the smallest element of each even-length cycle, so that any swap routing on the tree can be oriented, in polynomial time, to realize that signed permutation without knowing the optimal routing.","core_discovery":"The paper's central claim is that optimal exact synthesis in the matchgate-Clifford group, from the generating set of Majorana braids, has a complexity that depends sharply on the connectivity graph. On an open path, the optimal word length is $\\ell_R(w) = \\mathrm{inv}(\\pi) + 2\\nu(w)$, the inversion number of the underlying permutation plus twice the number of negative defects, and a matching circuit is output in $O(n^2)$ time. On the complete graph, the optimal length is $\\ell_{\\mathrm{all}}(w) = 2n - \\kappa(\\pi) + d_-(w)$, where $\\kappa$ counts the cycles of the permutation and $d_-$ counts the defective cycles, again constructible in $O(n^2)$ time. On an arbitrary tree, the decision version of gate-optimal and depth-optimal synthesis is NP-complete, via a reduction from token swapping on trees; the reduction is made to work by a lemma that places signs per cycle, negative on the smallest element of each even-length cycle, so that any routing of the underlying permutation can be oriented to realize the required signed permutation without knowing an optimal routing. A corollary extends NP-completeness to arbitrary connected graphs, and the closed-form path compiler yields constant-factor gate-count improvements over two production compilers in benchmarks on chains of up to 80 qubits.","pith_inferences":["Because the closed-form word lengths coincide with the Cayley-graph distances of the braid generating set, the results give exact diameters of those Cayley graphs, $2n$ on the all-to-all graph, which could be reused for sampling or benchmarking fermionic circuits.","The per-cycle sign placement used for the tree reduction may transfer to other signed-permutation groups where token-swapping hardness is known, potentially marking other braid-like gate sets as NP-hard to synthesize.","The NP-completeness on trees is a worst-case statement; typical instances may still admit practical heuristics, and the paper's own benchmark notes the sampled ensemble is not uniform on the group, so the reported constant-factor improvements describe typical random-walk targets rather than worst cases.","Since the two-qubit-optimal routing cost $\\mu(\\pi)$ remains open even with a factor-2 approximation, a natural next target is an exact polynomial algorithm for $\\mu(\\pi)$ or a hardness proof for it."],"forward_implications":["Every matchgate-Clifford unitary can be synthesized with at most $2n$ all-to-all braids, and this bound is tight; on the path the exact optimal word length is $\\mathrm{inv}(\\pi) + 2\\nu(w)$, with an explicit quadratic-time compiler.","On trees, and hence on general connected graphs, no polynomial-time algorithm for gate-optimal or depth-optimal synthesis exists unless P = NP.","On the path there is a single word that is simultaneously optimal in total gate count and in two-qubit gate count, with the two-qubit cost equal to $\\mu(\\pi) + 2\\nu_{\\mathrm{even}}(w)$; only a factor-2 approximation to $\\mu(\\pi)$ is known, and its exact computation is left open.","Benchmarks on chains of up to 80 qubits show the optimal path compiler reduces total gate counts by constant factors (up to about 2.6x) relative to Qiskit and Tket, and similar reductions in two-qubit gate count."],"supporting_citations":[{"why":"Supplies the NP-completeness of token swapping on trees, the problem from which gate-optimal and depth-optimal synthesis are reduced.","marker":"[43]"},{"why":"Provides the Coxeter-group machinery, inversion counts for adjacent transpositions and the Coxeter deletion property, used in the potential proofs and the $\\mu(\\pi)$ bounds.","marker":"[81]"},{"why":"Defines the matchgate-Clifford group and the Majorana braid generators whose signed-transposition action the paper synthesizes.","marker":"[26]"},{"why":"Establishes the $\\mathrm{SO}(2n)$ adjoint representation of matchgate unitaries that lets the synthesis work with signed permutations instead of exponential-size unitary matrices.","marker":"[62]"},{"why":"Supplies the max-flow machinery used to compute the pairing number $\\xi(\\pi)$ in the factor-2 approximation to the two-qubit-optimal routing cost.","marker":"[88]"},{"why":"Qiskit transpiler used as a benchmark baseline for the path-graph compiler.","marker":"[36, 37]"},{"why":"Tket transpiler used as the other general-purpose benchmark baseline.","marker":"[38]"},{"why":"The Givens-elimination compiler used in fermionic shadow settings, one of the four comparison methods in the benchmarks.","marker":"[68]"}],"fun_headline_variants":["Matchgate-Clifford synthesis: O(n²) on paths, NP-hard on trees","Quadratic-time optimal synthesis on paths; trees turn NP-complete","Path braid synthesis easy, tree braid synthesis hard","Optimal matchgate-Clifford compilers: paths fast, trees intractable","Gate-optimal braid circuits: path solved, tree NP-complete"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The load-bearing premise for the NP-hardness is Lemma 7, which asserts that for any swap sequence on a tree realizing a given permutation, the braid orientations can be chosen in polynomial time to realize the specific signed permutation whose signs are negative on the smallest element of each even-length cycle.","fun_headline_variants_meta":{"raw":{"variants":["Matchgate-Clifford synthesis: O(n²) on paths, NP-hard on trees","Quadratic-time optimal synthesis on paths; trees turn NP-complete","Path braid synthesis easy, tree braid synthesis hard","Optimal matchgate-Clifford compilers: paths fast, trees intractable","Gate-optimal braid circuits: path solved, tree NP-complete"]},"model":"deepseek/deepseek-v4-flash","effort":"low","cost_usd":0.000182,"raw_usage":{"cost":0.000182,"is_byok":false,"cost_details":{"upstream_inference_cost":0.000182,"upstream_inference_prompt_cost":0.00015064,"upstream_inference_completions_cost":3.136e-05},"total_tokens":1188,"prompt_tokens":1076,"completion_tokens":112,"prompt_tokens_details":{"audio_tokens":0,"video_tokens":0,"cached_tokens":0,"cache_write_tokens":0},"completion_tokens_details":{"audio_tokens":0,"image_tokens":0,"reasoning_tokens":26}},"tokens_in":1076,"tokens_out":112,"cost_source":"openrouter_usage","duration_ms":1804,"image_pages":[],"temperature":1.0,"billed_attempts":1,"reasoning_tokens":26,"transport_provider":"openrouter","cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-10-06T06:40:38.692144+00:00","model_set":{"reader":"deepseek/deepseek-v4-flash"},"falsifier":"Enumerate all permutations and all shortest swap routings on small trees (up to six or eight vertices) and check that the sign-placement lemma always holds: for each shortest routing, an orientation realizing the per-cycle signed permutation must exist and be found in polynomial time, and a single counterexample falsifies the NP-hardness reduction. Separately, on path and complete graphs with small $n$ ($2n \\le 10$ modes), compute the true shortest braid distance by breadth-first search on the Cayley graph and compare against the closed forms $\\mathrm{inv}(\\pi) + 2\\nu(w)$ and $2n - \\kappa(\\pi) + d_-(w)$; any mismatch would falsify Theorems 1 and 3.","supporting_citations":[{"cited_title":"Hardness of token swapping on trees","cited_arxiv_id":null,"evidence_quote":"Supplies the NP-completeness of token swapping on trees, the problem from which gate-optimal and depth-optimal synthesis are reduced."},{"cited_title":"Bjorner and F","cited_arxiv_id":null,"evidence_quote":"Provides the Coxeter-group machinery, inversion counts for adjacent transpositions and the Coxeter deletion property, used in the potential proofs and the $\\mu(\\pi)$ bounds."},{"cited_title":"Universal quantum computation with ideal clifford gates and noisy ancillas","cited_arxiv_id":null,"evidence_quote":"Defines the matchgate-Clifford group and the Majorana braid generators whose signed-transposition action the paper synthesizes."},{"cited_title":"Matchgates and classical simulation of quantum circuits","cited_arxiv_id":null,"evidence_quote":"Establishes the $\\mathrm{SO}(2n)$ adjoint representation of matchgate unitaries that lets the synthesis work with signed permutations instead of exponential-size unitary matrices."},{"cited_title":"Schrijver,Combinatorial optimization: polyhedra and efficiency, Vol","cited_arxiv_id":null,"evidence_quote":"Supplies the max-flow machinery used to compute the pairing number $\\xi(\\pi)$ in the factor-2 approximation to the two-qubit-optimal routing cost."},{"cited_title":"T|ket>: a retargetable compiler for NISQ devices","cited_arxiv_id":null,"evidence_quote":"Tket transpiler used as the other general-purpose benchmark baseline."},{"cited_title":"Fermionic Partial Tomography via Classical Shadows","cited_arxiv_id":null,"evidence_quote":"The Givens-elimination compiler used in fermionic shadow settings, one of the four comparison methods in the benchmarks."}],"review_version":1}