{"id":"e51fa503-3191-45de-836b-a1f293d01629","arxiv_id":"2607.26154","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For Pauli measurement sets whose frustration graph is perfect and which have no active sign dependencies, reduced robustness of magic equals the maximum over anticommuting cliques of the summed absolute expectation values, bounded by the square root of the clique number.","lead":"This paper identifies exactly when a small set of Pauli measurements can efficiently certify nonstabilizerness ('magic') in a quantum state, and gives a closed-form formula for the certification power in terms of the anticommutation graph of the measurements. It offers a practical design principle for scalable magic detection in quantum devices.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the central Theorem 5 argument is internally sound; the main external dependency (Eq. 3) is checkable and likely correct.","rationale":"The reader's weakest assumption (Eq. 3) is indeed the most load-bearing external input: if it failed, Theorems 3 and 5 would collapse. But on inspection the V-representation is not a mysterious black box; it follows from the fact that a stabilizer state's support in M is a commuting set, that non-maximal supports are convex combinations of maximal-support vertices via averaging over sign extensions, and that every admissible sign pattern on a maximal independent set is realized by some stabilizer state. Thus the concern, while worth settling computationally, is not currently a demonstrated flaw. The proof of Theorem 5 itself is sound: the dual program is correctly reformulated as MWIS, the perfect-graph collapse Eq. (B10) is standard, the variance bound for anticommuting sets is correct, and the saturation argument using an involution with zero trace is valid. The numerical irreproducibility and the unaddressed complexity of checking 'no active dependencies' are legitimate practical shortcomings, but they do not undercut the central theoretical claim. Therefore the reader's CONDITIONAL verdict remains appropriate, with no adjustment.","tokens_in":17040,"tokens_out":38959,"duration_ms":374908,"concrete_test":"Independently verify Eq. (3) by brute force for small instances: for n=2,3 and a sample of random Pauli measurement sets M, enumerate all stabilizer states, project onto M, compute the convex hull of the projected expectation vectors, and compare its vertex set with {v_{S,f}: S in I_max(G_M), f in B_S}. If the vertex sets coincide for all tested M, the central dependency of Theorem 5 is confirmed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I find no load-bearing flaw in the central claim. The proof of Theorem 5 is internally consistent: Theorem 3 and Proposition 4 are valid given the V-representation Eq. (3), and the perfect-graph antiblocker identity (Lemma 8) is correctly applied. The one genuinely external dependency is Eq. (3), imported from Ref. [20]; it is not proved in the manuscript. However, it can be derived by elementary arguments: any projected stabilizer state has commuting support, and averaging over sign extensions to a maximal independent set expresses it as a convex combination of the listed vertices; conversely, each listed vertex is realized by a stabilizer state. So I do not see a live counterexample. The remaining concerns (missing code/data/error bars, open verification of the no-active-dependencies promise) bear on reproducibility and applicability, not on the truth of the theorem. They do not change the reader's conditional verdict.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the reduced stabilizer polytope STAB(M) obtained by projecting n-qubit stabilizer states onto a small set M of Pauli expectation values. It introduces a sign-relaxed polytope ^STAB(M), proves (Theorem 3) that the relaxation is exact iff M has no active dependencies, shows (Proposition 4) that the dual separation oracle for the relaxed robustness is a maximum-weight independent set problem on the frustration graph G_M, and derives (Theorem 5) a closed form RoM_M(ρ)=max(1, max_{Q clique} ∑_{P∈Q}|tr(Pρ)|) ≤ √cl(G_M) when G_M is perfect. It further proves the universal ceiling √(2n+1), attained by the Jordan-Wigner set, establishes Clifford covariance, and reports numerical detection rates for four measurement sets.","tokens_in":17290,"tokens_out":14790,"duration_ms":134059,"significance":"The central result, if correct, identifies a nontrivial family of measurement-limited magic witnesses that are evaluable in polynomial time with no fitting parameters: the closed form in Theorem 5 is a parameter-free consequence of LP duality and perfect-graph antiblocker duality. The no-active-dependencies condition is a crisp, checkable graph-theoretic criterion, and the bound √cl(G_M) gives a transparent trade-off between witness capacity and simultaneous measurability. The Appendix B proofs are careful and complete. I find no load-bearing flaw in the central derivation; the stress-test concern about Eq. (3) is a completeness issue rather than a correctness issue. The paper's main value is theoretical; the numerical figures are illustrative and would benefit from reproducibility details.","major_comments":[],"minor_comments":[{"comment":"The exact V-representation STAB(M)=conv{v_{S,f}: S∈I_max(G_M), f∈B_S} is imported from the unreviewed preprint Ref. [20], and Theorems 3 and 5 rest on it. I believe the representation is correct (commuting support plus sign-averaging over a maximal extension gives the convex hull), but the manuscript should include a self-contained derivation or explicitly state this as a lemma with proof, so the central claim is not conditional on an external source.","section":"Appendix A, Eq. (A1) [main text Eq. (3)]"},{"comment":"The assertions that STAB(K_{2n+1}) is a cross-polytope and that the JW set has a unique nontrivial dependency ∏γ_i∝1 are stated without proof. The latter is load-bearing for the no-active-dependencies check and deserves a one-line proof; the former is illustrative and can be labelled as such.","section":"Results, JW set paragraph and Proposition 9"},{"comment":"The detection rates are reported without error bars, confidence intervals, or information about independent seeds/randomness. No code or data repository is mentioned. Please provide these reproducibility details, or state clearly that the figures are schematic.","section":"Results, numerical paragraph and Fig. 2"},{"comment":"The polynomial-time claim for evaluating Eq. (11) invokes the ellipsoid method for MWIS on perfect graphs [30,31]. This is a theoretical polynomial-time result, not a practical algorithm. For the specific graphs used (complete graphs, incidence graphs of paths, chordal trees), much simpler combinatorial algorithms exist; the text should make this distinction explicit.","section":"Theorem 5, paragraph after Eq. (11)"},{"comment":"Minor typographical and clarity issues: 'addtion' in the JW-set paragraph; the phrase 'Euclidean ball' in the same paragraph is not derived and should carry a reference; the notation ^STAB(M)\\STAB(M) in Fig. 1 should be defined (it is clear from context but a formal definition would help).","section":"General presentation"}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is technically sound in my assessment; the stress-test concern about Eq. (3) does not land as a correctness flaw, but the paper's self-containedness would be improved by a proof of that V-representation. The numerical section is the weakest part and should be made reproducible before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: the central claim is sound and it is a real step forward. Theorems 3 and 5 give a clean, polynomial-time computable closed form for reduced robustness of magic whenever the measurement set has no active dependencies and the frustration graph is perfect. The proof chain is clear: sign relaxation is exact iff no active dependencies; the dual separation becomes MWIS; perfect graphs collapse the antiblocker to clique incidence; then the closed form follows from Cauchy-Schwarz and anticommutation. I checked the key steps and I do not see a load-bearing gap. The Clifford covariance observation is simple but useful for coverage.\n\nWhat is genuinely new: the sign-relaxed polytope and the exactness criterion, the MWIS dual, and the perfect-graph closed form with the sqrt(clique number) capacity bound. That is more than a repackaging of the reduced-polytope framework from Varela et al. and the MWIS energy-witness idea.\n\nSoft spots, in order of importance. First, the numerical section is not reproducible as reported. No code, no data, no error bars, no details on how the Clifford rotations were sampled or how the MWIS was solved at n=8. For a paper whose practical pitch is scalable certification, that is a real omission, but it does not affect the theorems. Second, the 'no active dependencies' condition is characterized but not efficiently verifiable as far as the paper shows; the authors leave that for future work, which is honest, but it means the class of measurement sets for which the closed form applies is not yet certified in practice. Third, minor gaps: the cross-polytope claim for K_{2n+1} and the chordal claim for the tree set are asserted without proof, and polynomial-time MWIS on perfect graphs is cited rather than implemented. The latter is standard, so I do not weight it much. Fourth, the paper leans on Eq. (3), the V-representation of the reduced stabilizer polytope from Ref. [20], without proving it. I believe it is correct — the argument sketched in the stress test works — but it is an external dependency and worth making explicit. Also, Appendix C honestly states that a graph-theoretic mixed-state resource criterion is still missing; the main results are about linear reduced RoM, not the full magic resource theory for mixed states.\n\nWho this is for: anyone working on magic certification with limited measurement sets, or on the geometry of stabilizer polytopes. It deserves a serious referee. I would send it to review with the request that the numerical section be brought up to a reproducible standard and the dependency verification question addressed, but the theory part is ready.","headline":"Solid paper: exact reduction of reduced-RoM to a maximum-weight clique problem on perfect frustration graphs; main theorems hold up, numerics need work.","tokens_in":17735,"tokens_out":2207,"would_cite":true,"duration_ms":21391,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that, when a set of measured Pauli operators has no active dependencies and a perfect frustration graph, the reduced robustness of magic equals the largest sum of absolute Pauli expectation values over a pairwise anticommu","keywords":["nonstabilizerness","magic","reduced robustness of magic","frustration graph","perfect graphs","maximum-weight clique","Pauli measurements","Clifford covariance"],"falsifier":"Take any Pauli measurement set M satisfying the theorem's hypotheses—no active dependencies and a perfect frustration graph—and any n-qubit state ρ; compute RoM_M(ρ) by solving the exact linear program over the reduced stabilizer polytope (enumerating its vertices via Eq. (3)) and compare it to max(1, max_Q Σ_{P∈Q}|tr(Pρ)|). If they differ for any such instance, or if the value exceeds √cl(G_M), the theorem is false. A smaller-scale check: for the single-qubit set M={X,Y,Z} (the complete graph on three nodes, perfect, no active dependencies), RoM_M(ρ) must equal max(1, |tr(Xρ)|+|tr(Yρ)|+|tr(Zρ","tokens_in":17002,"feed_emoji":"⚛️","tokens_out":12900,"duration_ms":97820,"temperature":0.7,"pith_summary":"To certify that a quantum state has 'magic'—the resource behind universal quantum computation—one normally needs full tomography and an optimization over exponentially many stabilizer states. Using a limited set of Pauli measurements promises efficiency, but the resulting reduced stabilizer polytope is hard to characterize. This paper shows the difficulty decomposes into two graph-theoretic obstructions: the frustration graph, which records which measured Paulis anticommute and hence which can be measured together, and the sign dependencies imposed by Pauli product relations. The authors prove that when no 'active dependency' forces a parity constraint inside a commuting set, those sign dependencies can be discarded exactly; if the frustration graph is also perfect, the reduced robustness of magic collapses to a closed-form sum over pairwise anticommuting cliques, bounded by the square root of the largest anticommuting set. This yields a polynomial-time magic witness, a capacity-versus-measurability tradeoff, and a graph-based design principle for scalable certification.","feed_headline":"One formula turns a few measurements into a quantum magic witness","feed_subtitle":"When the frustration graph is perfect and dependency-free, reduced magic equals a clique sum—making it polynomial-time.","key_machinery":"The load-bearing object is the frustration graph G_M: nodes are the measured Pauli operators, and edges join anticommuting pairs. Its independent sets are exactly the commuting contexts that can be measured in a single setting, and its cliques are pairwise anticommuting sets. The paper's technical move is to relax the reduced stabilizer polytope by retaining all sign patterns on every maximal independent set instead of only the parity-consistent ones; this sign-relaxed polytope is exact precisely when M has no active dependency (a minimal commuting subset whose Paulis multiply to ±1). In the dual of the relaxed monotone, feasibility becomes a maximum-weight independent set computation on G_M","core_discovery":"The central discovery is Theorem 5: for an n-qubit state ρ and a Pauli measurement set M with no active dependencies and a perfect frustration graph G_M, the reduced robustness of magic equals RoM_M(ρ) = max(1, max_Q Σ_{P∈Q} |tr(Pρ)|), where Q ranges over cliques of G_M, i.e., over pairwise anticommuting subsets of measured Pauli operators. This value is at most √cl(G_M), the square root of the maximum size of such a set. As a corollary, the reduced robustness—and hence a certificate of nonstabilizerness (a value exceeding 1)—is computable in polynomial time, since it reduces to a maximum-weight clique problem on a perfect graph. The bound is tight: it is attained by any state supported on t","pith_inferences":["Because the closed form needs only |tr(Pρ)| for P in a clique, an experimentalist could certify magic from a handful of Pauli expectation values without any tomography: measure each anticommuting clique (requiring at most cl(G_M) commuting settings by perfectness) and check whether any clique sum exceeds 1.","The dependency-free condition may be achievable by adding auxiliary Pauli operators to a measurement set, since adding operators can break active dependencies; if so, the exact formula could cover far more practical measurement sets than the four families constructed here.","The paper leaves the mixed-state quadratic profile as an algebraic identity, not a magic measure; a natural next step would be to find a stabilizer upper bound on the dephased purity, which would yield a graph-theoretic mixed-state magic criterion.","The weighted Lovász bound is proposed as a sound polynomial-time lower bound for imperfect graphs; one could test numerically which imperfect frustration graphs make this bound tight, potentially extending the closed form beyond perfect graphs."],"forward_implications":["Evaluating RoM_M(ρ) for any state becomes a maximum-weight clique problem with weights |tr(Pρ)|, solvable in polynomial time when M is dependency-free and G_M is perfect—no optimization over exponentially many stabilizer states.","The witness capacity of a measurement set is exactly √cl(G_M), so a larger capacity requires a larger pairwise-anticommuting set; since at most 2n+1 mutually anticommuting Paulis exist on n qubits, the universal ceiling is √(2n+1), attained by the Jordan–Wigner Majorana set.","The condition χ(G_M)=cl(G_M) for perfect graphs means all needed expectation values can be collected in at most cl(G_M) commuting measurement settings, so the closed form also reduces experimental overhead.","Clifford rotations of a solvable measurement set preserve both the closed form and the capacity while covering different Pauli directions, so rotating the measurement ensemble enlarges the set of states detected without raising the bound; numerics confirm higher detection rates for Haar-random and variational states.","The same graph-theoretic reference (independent-set supports of stabilizer states) underlies quadratic magic witnesses and stabilizer Rényi entropy, giving a unified perspective on magic diagnostics."],"fun_headline_variants":["Clique sums certify quantum magic in polynomial time","Graph structure makes magic detection polynomial-time","Magic witnessed by cliques: efficient certification","Frustration graph unlocks scalable magic detection","Reduced magic equals clique sum when graph is perfect"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The central claim rests on the exact vertex description of the reduced stabilizer polytope: every extreme point must be indexed by a maximal commuting set of measured Paulis together with an admissible sign pattern; if that description missed any extreme points, the sign relaxation would not be exact and the closed-form clique formula would fail.","fun_headline_variants_meta":{"raw":{"variants":["Clique sums certify quantum magic in polynomial time","Graph structure makes magic detection polynomial-time","Magic witnessed by cliques: efficient certification","Frustration graph unlocks scalable magic detection","Reduced magic equals clique sum when graph is perfect"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000136,"raw_usage":{"total_tokens":968,"prompt_tokens":711,"completion_tokens":257,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":455,"completion_tokens_details":{"reasoning_tokens":189}},"tokens_in":455,"tokens_out":257,"duration_ms":2834,"temperature":1.0,"reasoning_tokens":189,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T00:40:43.948043+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take any Pauli measurement set M satisfying the theorem's hypotheses—no active dependencies and a perfect frustration graph—and any n-qubit state ρ; compute RoM_M(ρ) by solving the exact linear program over the reduced stabilizer polytope (enumerating its vertices via Eq. (3)) and compare it to max(1, max_Q Σ_{P∈Q}|tr(Pρ)|). If they differ for any such instance, or if the value exceeds √cl(G_M), the theorem is false. A smaller-scale check: for the single-qubit set M={X,Y,Z} (the complete graph on three nodes, perfect, no active dependencies), RoM_M(ρ) must equal max(1, |tr(Xρ)|+|tr(Yρ)|+|tr(Zρ","supporting_citations":[],"review_version":1}