{"id":"bab94bc6-a7c0-4567-b671-3a29a8b5a37a","arxiv_id":"2608.13169","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A witness framework certifies when a unitary cannot be realized by a prescribed quantum circuit architecture, with SDP and LP relaxations and analytical Clifford bounds.","lead":"This paper introduces mathematical checks that prove when a target quantum operation cannot be built from a prescribed circuit layout, based on comparing quantum state overlaps. These checks give lower bounds on circuit resources and can benchmark whether a device goes beyond a simple architecture.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Clifford LP upper bounds rest on an unproven graph-basis diagonalisation step; the all-architectures Toffoli checks are also unreported.","rationale":"The reader's verdict of CONDITIONAL is appropriate. The central framework is a standard fidelity-maximisation problem with SDP/LP relaxations, and the reported numerical values are consistent with known Toffoli lower bounds. The main defect is evidential rather than clearly mathematical: the graph-basis diagonalisation lemma is the key step that turns the SDP into a tractable LP, yet it is not proved in the text, and no code or data accompanies the numerical certificate claims. Because the central assertion is that these are rigorous certificates, the missing proof and missing reproducibility checks are load-bearing. I found no clear internal contradiction beyond this gap, and the WLOG step is plausible, so the appropriate recommendation is to keep the paper conditional and require either a full proof of the diagonalisation step or release of verification code, rather than to reject.","tokens_in":18983,"tokens_out":31923,"duration_ms":306470,"concrete_test":"For the four Clifford rows of Table I and the Toffoli 3-gate architectures, solve the full SDP Eq. (4) with a high-precision SDP solver and compare its optimum with the LP value obtained from Eq. (C14). If LP_value > SDP_value + 1e-6 for any instance, the diagonalisation WLOG is false and the reported upper bounds are invalid. As a second, independent check, symbolically verify that the twirling map Φ(ρ) = (1/|S|)∑_{s∈S} sρs† preserves each constraint Tr_{B_O^k}ρ = Tr_{B_IO^k}ρ ⊗ 1_{B_I^k}/4 for all k, using the commutation of tensor-product Pauli operators with partial traces.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing point is the WLOG diagonalisation in Appendix C2. The LP of Eq. (C14) is obtained from the SDP of Eq. (4) only after asserting that the feasible τ can be replaced by its diagonal part in the graph-state basis, preserving positivity, normalisation, PPT, and the partial-trace constraints Tr_{B_O^k}τ = Tr_{B_IO^k}τ ⊗ 1_{B_I^k}/4 for all k. This is asserted in a single sentence with a citation to a depolarisation procedure, but the appendix does not prove that the stabilizer twirl preserves those specific partial-trace identities under the partial traces used here. If this WLOG step fails, the LP optimum is not guaranteed to upper bound α_Γ(U), and every Clifford witness in Tables I and II, the five-gate example, and the Toffoli depth bounds would be unsupported. The paper also provides no code, no data, and no enumeration of the 'all 12 possible architectures' used for the Toffoli depth-4 claim, so the exhaustive check cannot be independently reproduced. The step is plausible and may be correct, but it is the least-secure link in the certificate chain.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a framework for certifying that a target unitary cannot be implemented within a prescribed quantum circuit architecture. The central quantity is α_Γ(U), the maximum fidelity between the Choi state of the target unitary and the Choi states of circuits compatible with architecture Γ. Since the exact optimization is nonconvex, the authors relax it to a semidefinite program (Eq. (4)) and, for Clifford target unitaries, to a linear program (Eq. (C14)) via graph-state depolarization. They also give an analytical Bell-pair-counting method for staircase architectures (Appendix D). Numerical results for two-, three-, and five-gate examples yield upper bounds below 1, and the Toffoli gate is claimed to require circuit depth at least 3 and then at least 4 based on exhaustive checks over all two- and three-gate architectures. The witness operator in Eq. (2) converts a bound α_Γ(U)<1 into a linear functional that is nonnegative on all Γ-compatible unitaries and negative on the target unitary.","tokens_in":19146,"tokens_out":12715,"duration_ms":120893,"significance":"If the central reduction is proved, the framework would be a useful contribution: it provides quantitative incompatibility certificates, connects circuit-architecture questions to separability theory and convex relaxations, and the Clifford LP simplification is a genuine practical advance. The analytical Bell-pair-counting arguments in Appendix D are clean and give parameter-free bounds that scale to arbitrarily many gates. The agreement with the known five-gate Toffoli lower bound is also encouraging. At present, however, the advertised rigor is not fully delivered because the graph-diagonal WLOG step is unproved, the exhaustive Toffoli checks are unreported, and the numerical solver outputs are not accompanied by certificates.","major_comments":[{"comment":"The WLOG reduction to graph-diagonal operators is the load-bearing step for all Clifford results, but it is asserted rather than proved. The text states that the depolarisation procedure of Ref. [30] removes off-diagonal components while preserving the overlap with the graph state and the relevant positivity, normalisation, PPT and trace-preserving constraints. This is not immediate: the constraints in Eq. (C9) involve partial traces over specific subsystems B^O_k and partial transposes across the partitions B^IO_1|...|B^IO_m, whereas a stabilizer twirl acts globally on the full Hilbert space. One must prove that the twirl commutes with these subsystem operations, or otherwise exhibit a feasible graph-diagonal replacement for every feasible τ. Without such a proof, the LP in Eq. (C14) is not established as an upper bound on α_Γ(U), and the Clifford witnesses in Tables I and II, the five-gate example, and the Toffoli depth claims are unsupported. Please provide a complete proof of this reduction or replace it by a relaxation whose validity is proven.","section":"Appendix C2, Eqs. (C9)-(C14)"},{"comment":"The claimed lower bounds on the Toffoli circuit depth rest on exhaustive checks that are not reported. The text states that 'we obtained for all the six possible circuit architectures made of 2 two-qubit gates the same upper bound' and that 'Checking analogously the incompatibility of the Toffoli gate with all the 12 possible circuit architectures...' yields depth at least 4, but no list of the architectures, no per-architecture upper bounds, no solver settings, and no code are given. These exhaustive statements are central advertised conclusions and must be independently reproducible. Please include the full enumeration data or a script that reproduces the checks and reports the certified upper bound for each architecture.","section":"Examples I and II, Toffoli depth claims"},{"comment":"The numerical values are presented as rigorous upper bounds, but no certification is provided. The tables report approximate values such as ≃0.6366, ≤0.6798, and ≃0.857 obtained from LP/SDP/see-saw computations, without solver tolerances, dual certificates, or reproducible code. A floating-point optimum is not a mathematical certificate: for the witness construction one needs a guaranteed upper bound strictly below 1, and the see-saw tightness claims are likewise heuristic. Please provide either exact rational or interval-arithmetic-verified bounds, or make available code with fixed tolerances that yields certified values; the term 'rigorous certificate' should be reserved for data that actually certify the bound.","section":"Tables I, II and the five-gate example"}],"minor_comments":[{"comment":"The abstract claims that the LP enables 'more efficient numerical certification for circuits containing on the order of seven two-qubit gates', but the largest reported numerical LP example involves five gates; please add a seven-gate example or adjust the wording.","section":"Abstract"},{"comment":"The expression 'Tr[I_Γ]^2 diag(U†_LC τ U_LC) = ...' appears garbled; the normalisation factor Tr[I_Γ]^2 should be placed and defined explicitly.","section":"Eq. (C10)"},{"comment":"The identity operator 1 in the witness definition is not defined; it should be the identity on H_{i1i2i3 o1o2o3} (or the corresponding full space in the general case).","section":"Eq. (2)"},{"comment":"The caption of Table I does not specify the composition convention for the gates A1 and A2; please state explicitly whether U = A2∘A1 or A1∘A2.","section":"Table I"},{"comment":"The sentence 'We thus retrieve the upper bound obtained in Appendix D1 for the case n=3' applies to the SWAP-SWAP example; the distinction from the general Clifford case should be made explicit to avoid overgeneralisation.","section":"Appendix D2, Eq. (D7)"}],"recommendation":"major_revision","confidential_remarks":"The central risk is the unproved graph-diagonal WLOG reduction in Appendix C2. If the authors can supply a full proof and make the numerical certifications reproducible, the paper would be a solid contribution. I have no concerns about novelty or circularity; the analytical derivation is self-contained and the reference list is appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Core idea is worth engaging: architecture witnesses from Choi fidelity, an SDP for general unitaries, an LP reduction for Clifford targets, and an analytical Bell-pair count that gives a closed-form bound for staircase architectures of any length. The paper does something real: it turns \\\"can this unitary fit in this circuit shape?\\\" into a convex relaxation, and the relaxation is not vacuous\\u2014it reproduces known Toffoli bounds and even gives a clean analytical result for arbitrary-size staircases. Appendix D is the most solid part; the Bell-pair counting argument is clear and self-contained.\n\nThe main soft spot is exactly where the stress-test puts it. Appendix C2 asserts, with one sentence and a citation, that you can depolarise tau to graph-diagonal form while preserving positivity, normalisation, PPT, and the partial-trace constraints. That is load-bearing for every Clifford LP result in Tables I and II and for the five-gate example. It may well be true\\u2014graph-state stabilizer twirls often preserve such structures\\u2014but the text does not prove it, and the constraints being preserved are exactly the ones sensitive to partial traces across the gate bipartitions. This needs a real proof, or at least a detailed argument. It is an incomplete proof rather than a demonstrated error.\n\nSecond soft spot: the \\\"all 12 possible architectures\\\" and \\\"all six\\\" Toffoli checks are stated but not shown. No table, no enumeration, no code. The five-gate example likewise reports a single LP value with a see-saw tightness check. For a paper whose selling point is rigorous certificates, numerical solver output at 1e-4 precision is not a rigorous certificate. The LP is rational; exact or verified bounds should be feasible. No code or data is provided, which makes the exhaustive checks impossible to reproduce.\n\nThe paper's own claims are slightly stronger than what is demonstrated. The conclusion says \\\"rigorous proofs of incompatibility,\\\" but the certificate chain currently has an unproven lemma and unverified numerics. That is an honest mismatch, not an attempt to conceal; the appendices are transparent about many caveats. The citation pattern is fine: [30] is the natural source for the depolarisation step, and [32] is the correct benchmark.\n\nMy verdict: this should go to peer review. The framework is new, the analytical result is solid, and the gaps are addressable. I would ask for a full proof of the WLOG diagonalisation, a reproducible artifact or exact LP certificates, and a table of the architecture-by-architecture Toffoli values. With those in place, the paper would be quite strong.","headline":"A genuinely new witness framework with a clean analytical core, but the Clifford LP rests on an unproven diagonalisation step and the numerical certificates need reproducible support before the strongest claims hold.","tokens_in":19694,"tokens_out":2901,"would_cite":true,"duration_ms":28080,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":["03.67.-a","03.67.Lx","03.67.Mn"],"model":"deepseek-v4-flash","headline":"The paper claims that compatibility of a unitary with a circuit architecture can be certified by a fidelity optimization: when the relaxed optimum is below one, a witness operator proves the architecture cannot realize the target.","keywords":["quantum circuit architecture","architecture witnesses","Choi state fidelity","Clifford unitaries","stabiliser formalism","linear program relaxation","semidefinite program","Toffoli gate depth"],"falsifier":"Run a high-precision numerical search over feasible circuits for one of the reported examples, such as the five-gate Clifford pair or the Toffoli two-gate bounds; the paper's see-saw checks reach the claimed bounds up to $10^{-5}$ or $10^{-6}$, so any feasible circuit found with fidelity above the claimed upper bound beyond that tolerance would refute the method, while reaching it closely supports the claim.","tokens_in":18736,"feed_emoji":"⚛️","tokens_out":15099,"duration_ms":120073,"temperature":0.7,"pith_summary":"This paper introduces a way to prove that a given quantum unitary cannot be implemented within a prescribed circuit architecture, such as a fixed ordering of two-qubit gates on a chip. The method defines a fidelity between the target unitary and the best circuit of the allowed architecture, then relaxes the optimization: when the relaxed upper bound is below one, a constructed witness operator certifies incompatibility. For Clifford targets the semidefinite relaxation becomes a linear program, and for staircase architectures the authors derive analytical bounds by counting Bell pairs. These certificates give quantitative lower bounds on gate count and circuit depth, and they give experiments a threshold: seeing a fidelity above it certifies that the implemented device went beyond the tested architecture.","feed_headline":"Witnesses certify when a circuit layout can't build a unitary","feed_subtitle":"A fidelity value below one gives a rigorous no-go certificate and, for the Toffoli gate, depth bounds of 3 and 4.","key_machinery":"The central object is the optimised Choi-state fidelity $\\alpha_\\Gamma(U)$, the maximum overlap between the Choi vector of the target unitary and the Choi vector of circuits built from the allowed gates, normalised so that value $1$ means the target is realisable. Because the exact maximisation is non-convex, the machinery is a two-stage relaxation: a semidefinite program over a positive operator $\\tau$ with PPT and CPTP-marginal constraints for general targets, and a linear program for Clifford targets obtained by writing the Choi state as a graph state and restricting, without loss of generality, to operators diagonal in the graph-state basis. The analytical variant counts the number of Bell pairs that cross the cut between the last gate and the rest of the circuit; each such pair contributes a factor at most $1/2$, yielding bounds such as $1/4$ for SWAP staircases of arbitrary length.","core_discovery":"The central claim is that $\\alpha_\\Gamma(U)$, the maximum fidelity between the Choi state of $U$ and the Choi states of circuits compatible with architecture $\\Gamma$, can be bounded from above by a convex relaxation, and whenever that upper bound is strictly below $1$ the operator $W=\\alpha_\\Gamma(U)\\mathbb{1}-\\tfrac18|U\\rangle\\rangle\\langle\\langle U|$ is a valid circuit-architecture witness. For arbitrary targets the relaxation is a semidefinite program over a positive operator $\\tau$ with PPT and CPTP-marginal constraints. For Clifford targets, the stabiliser formalism identifies the relevant Choi state with a graph state, and a depolarisation step lets the authors restrict to graph-diagonal $\\tau$, reducing the SDP to a linear program. The paper proves, among other examples, that the Toffoli gate is incompatible with every three-qubit architecture made of two two-qubit gates (depth at least $3$) and with every one made of three such gates (depth at least $4$), and that a five-gate Clifford circuit is incompatible with the mirrored five-gate architecture at tight fidelity $0.5$. The analytical Bell-pair technique is demonstrated for staircase architectures with no-signalling relations between inputs and outputs, and the authors leave the generalization to arbitrary architectures as work in progress.","pith_inferences":["If the graph-diagonal reduction survives further scrutiny, the linear-program route should scale to Clifford circuits well past seven two-qubit gates, making architecture certificates practical for compiled Clifford subcircuits in error-correction pipelines; the paper demonstrates only the smaller cases.","The Bell-pair-counting picture suggests a resource interpretation: a target fails an architecture because the architecture cannot supply enough Bell-pair-generating steps across a time cut; extending this to general architectures would require adding trace-preserving constraints that the current analytical method drops.","Because the general semidefinite relaxation only enforces the PPT condition, tighter separability hierarchies should produce stronger witness thresholds for non-Clifford targets; the paper notes this possibility but does not test it."],"forward_implications":["The Toffoli gate cannot be implemented with two two-qubit gates on three qubits, so its circuit depth is at least 3, and it cannot be implemented with three such gates either, so the depth is at least 4.","For a Clifford target unitary, the linear-program formulation certifies architecture incompatibility for circuits with on the order of seven two-qubit gates, far beyond the reach of the general semidefinite relaxation.","An experimental measurement of the fidelity between the target and the implemented channel that exceeds the witness threshold is a quantitative certificate that the implemented channel goes beyond the tested architecture.","Architecture incompatibility becomes a separability problem, so two architectures that allow the same input-output signalling can still be distinguished, as shown by the three-gate and five-gate examples."],"supporting_citations":[{"why":"Supplies the witness template: a separating operator with positive expectation on all compatible states and negative expectation on the target.","marker":"[16]"},{"why":"Defines the quantum circuit architecture and link product used to compose gate Choi states into a whole-circuit Choi vector.","marker":"[21]"},{"why":"Supplies the graph-state and stabiliser formalism used to represent Clifford Choi states.","marker":"[29]"},{"why":"Supplies the depolarisation-to-graph-diagonal argument that turns the Clifford semidefinite relaxation into a linear program.","marker":"[30]"},{"why":"Supplies the reduction of stabiliser states to Bell pairs and local terms used in the analytical Bell-pair-counting bounds.","marker":"[31]"},{"why":"Establishes that five two-qubit gates are necessary for the Toffoli gate, the external benchmark with which the paper's depth bounds of at least 3 and at least 4 agree.","marker":"[32]"}],"fun_headline_variants":["Circuit architecture witnesses turn fidelity into no-go proofs","SDP certifies quantum circuits that cannot be built","Toffoli depth bounds from a new circuit witness framework","Linear programming yields rigorous absence proofs for Clifford circuits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise, made in the paper's Appendix C2, is that for Clifford targets an optimisation variable can be restricted to its diagonal part in a basis built from the target's graph state without changing the optimum; if that reduction failed, the linear-program upper bounds would cease to be valid upper bounds.","fun_headline_variants_meta":{"raw":{"variants":["Circuit architecture witnesses turn fidelity into no-go proofs","SDP certifies quantum circuits that cannot be built","Toffoli depth bounds from a new circuit witness framework","Linear programming yields rigorous absence proofs for Clifford circuits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000281,"raw_usage":{"total_tokens":1702,"prompt_tokens":1022,"completion_tokens":680,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":638,"completion_tokens_details":{"reasoning_tokens":618}},"tokens_in":638,"tokens_out":680,"duration_ms":6754,"temperature":1.0,"reasoning_tokens":618,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:13:26.210330+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a high-precision numerical search over feasible circuits for one of the reported examples, such as the five-gate Clifford pair or the Toffoli two-gate bounds; the paper's see-saw checks reach the claimed bounds up to $10^{-5}$ or $10^{-6}$, so any feasible circuit found with fidelity above the claimed upper bound beyond that tolerance would refute the method, while reaching it closely supports the claim.","supporting_citations":[{"cited_title":"Five Two-Qubit Gates Are Necessary for Implementing Toffoli Gate","cited_arxiv_id":"1301.3372","evidence_quote":"Establishes that five two-qubit gates are necessary for the Toffoli gate, the external benchmark with which the paper's depth bounds of at least 3 and at least 4 agree."}],"review_version":1}