{"id":"9b3eda61-f287-4381-a1ab-a5bd416b7b73","arxiv_id":"2511.16558","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The GBS graph distribution c^{2|S|} PM(S)^2 is classically sampleable in polynomial time for all graphs.","lead":"A team shows that the probability distribution used in graph-based Gaussian boson sampling can be produced by a classical algorithm in polynomial time, for any graph. This removes the exponential-speedup argument for a family of proposed quantum-advantage applications.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Weighted log-concavity is the unproved linchpin, but it is true via Heilmann–Lieb; the gap is a missing citation/proof, not a false step.","rationale":"The paper's central reduction—projecting weighted perfect matchings of G□K2 to S and invoking Jerrum–Sinclair—is elegant and, apart from the flagged gap, correct. Lemma 4.2's AM-GM bound is valid, and the scaling by 4n^2 correctly makes the near-perfect/perfect ratio < 1/2. The only genuinely load-bearing unproved premise is the weighted log-concavity of Z_k, exactly as the reader identified. It is used to propagate the ratio bound from size n down to all sizes, giving constant acceptance probability. If it failed, the rejection algorithm's expected time could be exponential and Theorem 1.1 would fail. The paper neither proves nor cites this nontrivial fact. That said, the fact is a known consequence of Heilmann–Lieb real-rootedness of the weighted matching polynomial, so the correct verdict is conditional rather than reject: the authors need to supply the citation/proof, but the underlying claim is sound. The other issues noted by the reader—the c/c^2 notation and the rejection-sampling TV constant—are presentation/constant-factor problems that do not affect the polynomial-time nature of the result. Therefore the reader's CONDITIONAL verdict is appropriate, with no change.","tokens_in":10100,"tokens_out":26274,"duration_ms":240059,"concrete_test":"Settle the weighted log-concavity claim directly: (i) provide a rigorous citation/proof that the edge-weighted matching polynomial has only real roots for all nonnegative weights (Heilmann–Lieb), then verify that this implies Z_k^2 ≥ Z_{k-1}Z_{k+1}; or (ii) exhaustively test all graphs with n≤8 and random positive integer edge weights, computing Z_k by dynamic programming and checking log-concavity for every k. If any counterexample appears, Theorem 1.1 collapses; if none appears, as expected, the concern reduces to a missing reference and the verdict is unchanged. Separately, recompute the rejection-sampling total-variation bound with ε' = ε/8 to confirm the stated ε guarantee.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The decisive step is the unproved assertion after Lemma 4.2: 'It can be verified that the log concavity still holds for weighted matchings.' This is used to convert the near-perfect/perfect bound Z'_{n-1}<Z'_n/2 into Z'_{k-1}≤Z'_k/2 for every k, hence Z'≤2Z'_n, a constant rejection probability in the Jerrum–Sinclair chain. If this log-concavity failed, rejection sampling could take exponential time and Theorem 1.1 would collapse. The text supplies no proof or citation for this claim. However, the assertion is in fact correct: for nonnegative edge weights, the weighted matching polynomial sum_k (-1)^k Z_k x^{n-2k} is real-rooted by the Heilmann–Lieb theorem, and a real-rooted polynomial with roots x_i yields a polynomial in y=x^2 with nonnegative roots, whose coefficient sequence Z_k is log-concave by Newton's inequalities. Thus the concern is a missing-support gap, not a false premise. Secondary issues—the edge weight written as c^2 while the running time contains c, and the rejection-sampling TV analysis seemingly needing ε/8 rather than ε/2—are absorbed by the O(·) notation and do not threaten the polynomial-time conclusion.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims two polynomial-time classical sampling results. Theorem 1.1 asserts that, for any graph G and positive c, ε, there is an algorithm sampling ε-close in total variation distance to the graphical Gaussian-boson-sampling distribution μ_GBS,G(S) ∝ c^{2|S|} PM(S)^2 in time O(c m n^4 log^2(nc/ε)). The proof reduces this to sampling weighted perfect matchings from the Cartesian product G □ K2 (Lemma 4.1), runs the Jerrum–Sinclair Markov chain, and argues via Lemma 4.2 and a log-concavity claim that the rejection probability is constant. Theorem 1.3 gives a similar polynomial-time sampler for the boson sampling distribution when the input matrix is non-negative, using a reduction to Jerrum–Sinclair–Vigoda perfect-matching sampling. If correct, the first result removes the density restriction in ZZW+25 and implies no exponential quantum speedup for graphical GBS sampling applications.","tokens_in":10375,"tokens_out":36641,"duration_ms":361148,"significance":"The potential contribution is substantial: a simple, parameter-free polynomial-time classical sampler for the distribution underlying most GBS graph applications would resolve an open question and directly undercut the exponential-advantage narrative for those tasks. The reduction in Lemma 4.1 is exact and elegant, and the use of the Jerrum–Sinclair chain is natural. The second result is a useful warm-up. However, the current manuscript does not yet establish the main theorem: the proof of Lemma 4.2 contains a missing combinatorial case, the weighted log-concavity step is unproved, and the rejection-sampling TV-accuracy argument uses the wrong constant. These issues are repairable, but they are load-bearing.","major_comments":[{"comment":"The displayed identity for Z_{n-1} omits near-perfect matchings whose two unmatched vertices are the two copies of the same vertex of G. The missing contribution is ∑_{a∈V}∑_{S⊆V\\{a}} c^{2|S|} Haf(S)^2. This class is essential: for edgeless G with n=3, c=1, Z_2=3 but the right-hand side of (11) is 0; for a single-edge G with c=2, Eq. (11) gives 16 while the true Z_1 is 10. Since Lemma 4.2 is what makes the Jerrum–Sinclair rejection probability constant, the proof must be corrected, e.g. by splitting the second sum into the a≠b and a=b cases and adding the missing term.","section":"Section 4, Lemma 4.2, Eq. (11)"},{"comment":"The sentence 'It can be verified that the log concavity still holds for weighted matchings' is the bridge from Z'_{n-1} < Z'_n/2 to the bound Z' ≤ 2Z'_n in (12), but no proof or citation is given. Proposition 2.2 is stated for unweighted counts, and the injection proof for the unweighted case does not by itself give the weighted inequality Z_{k-1}Z_{k+1} ≤ Z_k^2. I believe the assertion is true via Heilmann–Lieb real-rootedness of the weighted matching polynomial plus Newton's inequalities, but the manuscript must supply the argument or a precise reference.","section":"Section 4, after Lemma 4.2 (weighted log-concavity)"},{"comment":"The proof invokes Proposition 2.1 with ε' = min{1/4, ε/2} and then rejects until a perfect matching is found. Conditioning on the perfect-matching event P amplifies the total variation error by a constant factor on the order of 1/μ(P), so ε' = ε/2 does not generally guarantee a final ε-close output. The proof should set ε' = ε/C for a sufficiently large universal constant C (e.g. ε/8) or include an explicit conditioning lemma. The running time is unchanged up to constants.","section":"Section 4, Theorem 1.1 proof (TV amplification)"},{"comment":"With the weights in Section 4 (λ_e = c^2 for edges of G and its copy, λ_e = 1 for the Cartesian edges), the maximum weight seen by the Jerrum–Sinclair chain is O(n^2 c^2), not O(n^2). Proposition 2.1 therefore gives O(c^2 m n^4 log^2(nc/ε)) up to log factors, not the stated O(c m n^4 log^2(nc/ε)). The statement should use c^2, or the proof of the running time should be revised.","section":"Theorem 1.1 statement and proof (running-time dependence on c)"}],"minor_comments":[{"comment":"There is a duplicated expression 'ν(z)∝k^{-n}ν(z)' in the display; the proportionality/normalization argument should be written cleanly, including the role of k^{-n} in the normalization.","section":"Section 3, Eq. (7)"},{"comment":"The phrase 'after at most O(log(1/ε)) rejections' is misleading: since each sample is a perfect matching with probability at least 1/2 − ε' ≥ 1/4, the expected number of restarts is O(1). If a high-probability bound is intended, it should be stated.","section":"Section 4, proof of Theorem 1.1"},{"comment":"Theorem 1.1 states log^2(nc/ε) while the cited running time in Proposition 2.1 has a single log factor. The exponent should be reconciled with the cited source and the derivation.","section":"Theorem 1.1 vs. Proposition 2.1"},{"comment":"Haf(S) for an odd-cardinality set S is implicitly treated as 0; this convention should be stated explicitly before Lemma 4.2.","section":"Section 4, notation"}],"recommendation":"major_revision","confidential_remarks":"The paper is potentially important, and the issues I found are repairable within the same framework. I would encourage the authors to fix the decomposition in Lemma 4.2, supply the weighted log-concavity reference/proof, and correct the TV-accuracy and running-time statements before resubmission. I saw no concerns about attribution or novelty disclosure."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main result is real. For any graph G and c>0, the paper gives a classical polynomial-time sampler for the GBS-on-graphs distribution μ_GBS,G(S) ∝ c^{2|S|} PM(S)^2. That removes the dense-graph restriction of ZZW+25 and goes beyond OFJQ24, which samples a distribution proportional to PM(S) rather than PM(S)^2. The reduction is neat: sample a weighted perfect matching from the Cartesian product G□K2 and project. Lemma 4.1 is exact, and the AM-GM bound in Lemma 4.2 checks out. The companion nonnegative-matrix boson sampling result in Theorem 1.3 is also new and uses a clean bipartite construction with JSV sampling. This is a genuine advance, not a reframing.\n\nThe soft spots are mostly in presentation and support. The most important is the unproved claim after Lemma 4.2 that weighted matching counts are log-concave. That assertion is load-bearing: it turns the near-perfect/perfect ratio bound into a constant rejection probability for the Jerrum–Sinclair chain. The paper gives no proof or citation, and the reader flagged this as a possible gap. I checked: the claim is true for nonnegative edge weights via the Heilmann–Lieb real-rootedness of the matching polynomial and Newton's inequalities. So the result stands, but the authors need to add a proof sketch or citation. This is a missing-support issue, not a false step.\n\nThere are also two smaller presentation issues. The edge weight is set to λ_e = c^2 in some places and c in the proofs; that inconsistency is harmless but should be disciplined. More substantively, the TV error analysis in the rejection-sampling argument looks off by a constant—the paper seems to use ε/2 where something like ε/4 or ε/8 is needed. The running time is O(·), so the polynomial bound is not threatened, but the constants need a careful pass.\n\nThe paper does not oversell. Remark 1.2 correctly states the consequence: no exponential quantum speedup for applications based on sampling from this distribution. The authors are also honest that general boson sampling with complex matrices remains untouched and that the permanent-approximation route is hard.\n\nFor a quantum advantage audience and for people working on matchings and counting, this is a useful, correct result that deserves serious refereeing. I would send it to review, and I'd expect acceptance after the log-concavity support and the constant issues are fixed.","headline":"Settles the open question for graphical GBS distributions with an elegant, correct reduction; the load-bearing log-concavity step is true but under-supported.","tokens_in":10915,"tokens_out":1305,"would_cite":true,"duration_ms":14817,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","68Q12","05C70","68W20"],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"Graph Gaussian boson sampling is classically simulable in polynomial time","keywords":["Gaussian boson sampling","graph matchings","perfect matchings","classical simulation","Markov chain Monte Carlo","permanent approximation","boson sampling","computational complexity"],"falsifier":"Compute the weighted matching counts Z_k for a family of graphs G□K2 with weights c^2 on original edges and check the inequalities Z_{k−1}Z_{k+1} ≤ Z_k^2 for all k; a single violation for some graph and c would refute the log-concavity step and thereby the polynomial-time guarantee. Equivalently, run the rejection sampler on a graph where the ratio Z'_{n−1}/Z'_n exceeds 1/2 and observe the acceptance probability decaying; a counterexample would be a concrete graph where the near-perfect-to-perfect ratio bound fails.","tokens_in":9964,"feed_emoji":"🎲","tokens_out":7342,"duration_ms":71115,"temperature":0.7,"pith_summary":"Gaussian boson sampling on graphs assigns to each vertex subset S a probability proportional to c^{2|S|} times the squared number of perfect matchings in the induced subgraph G[S]. This paper claims that this distribution can be sampled classically in polynomial time for every graph, with runtime O(c m n^4 log^2(nc/ε)) to reach ε total-variation accuracy. The proof works by realizing the distribution as the projection of a weighted perfect-matching distribution on the Cartesian product G□K2, which can be sampled with a standard Markov chain whose rejection rate is polynomially controlled. A second result achieves polynomial-time classical sampling for boson sampling when the input matrix is non-negative. If right, these results rule out exponential quantum speedup for GBS-based graph algorithms.","feed_headline":"Classical sampling of graph GBS runs in polynomial time","feed_subtitle":"A projection from perfect matchings lets a classical Markov chain reproduce the GBS graph distribution to any accuracy.","key_machinery":"The load-bearing object is the Cartesian product G□K2: two copies of G joined by matching edges v–v′, with weight c^2 on the original edges and weight 1 on the cross edges. A perfect matching M in this graph projects to the set S of vertices in the first copy that are covered by original edges, and the induced probability of S is proportional to c^{2|S|} PM(S)^2. The matching-sampling Markov chain on G□K2 must run in polynomial time; the ratio bound on near-perfect to perfect matchings (Lemma 4.2) and the claimed log-concavity of weighted matching counts together guarantee a constant acceptance probability for rejection sampling to a perfect matching.","core_discovery":"The central claim is Theorem 1.1: for any graph G and any positive c, the distribution μ_GBS,G(S) ∝ c^{2|S|} PM(S)^2 admits a classical sampler that is ε-close in total variation in time O(c m n^4 log^2(nc/ε)). The discovery is that this distribution is exactly the image of a weighted perfect-matching distribution on the Cartesian product G□K2 under the map recording which vertices of the first copy are matched by original edges. This turns GBS into a matching-sampling problem solvable in polynomial time by a known Markov chain, once the near-perfect/perfect matching ratio is polynomially bounded; the paper bounds it by 2n^2 and uses asserted log-concavity of weighted matching counts to exte","pith_inferences":["Editorial: The one-step verification of weighted log-concavity is the point most worth scrutinizing. A counterexample to Z_{k−1}Z_{k+1} ≤ Z_k² for some G□K2 weight assignment would invalidate the rejection-sampling argument and the polynomial-time claim.","Editorial: The result implies that near-term GBS experiments targeting graph problems must demonstrate advantage outside μ_GBS,G—for instance through lossy detection, threshold sampling, or non-graph-encoded squeezing—since the graph-encoded distribution is now classically simulable.","Editorial: The same perfect-matching reduction suggests a route to more general classical simulators: any matrix family for which permanents of principal submatrices can be approximated in polynomial time would inherit a polynomial-time sampler for the corresponding boson-sampling variant.","Editorial: The runtime O(c m n⁴ log²(nc/ε)) is polynomial but has degree 4 in n and degree 6 for dense graphs; practical simulation at large n may still be challenging, so the result is about asymptotic complexity rather than immediate desktop feasibility."],"forward_implications":["For every unweighted graph G and constant c>0, the graph GBS distribution μ_GBS,G is classically sampleable in O(c m n^4 log^2(nc/ε)) time to ε TV error; this removes the exponential quantum speedup for applications based on this distribution.","The construction extends to weighted graphs: if G has non-negative edge weights, setting the matching weights accordingly yields a polynomial-time sampler for the weighted analogue c^{2|S|} Haf(A_S)^2.","The same perfect-matching gadget, with a bipartite graph built from the rows and columns of the matrix, gives a polynomial-time classical sampler for the boson sampling distribution whenever the input matrix is non-negative.","For the general boson sampling problem, the paper's reduction shows that efficient classical sampling hinges on efficiently approximating |Perm(A_z)|; when such approximations are unavailable, the gadget does not yield a polynomial-time algorithm.","Because the runtime is polylogarithmic in 1/ε, high-accuracy samples cost only polylogarithmic extra time."],"fun_headline_variants":["Polynomial-time classical sampler for graph GBS","Graph GBS loses quantum speedup: classical sampling works","Classical Markov chain simulates graph GBS efficiently","No exponential quantum speedup for graph GBS","Polynomial-time classical simulation of graph GBS"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The argument relies on the unproved assertion that the weighted matching-count sequence Z_k (for the Cartesian product graph with weights c^2 and 1) is log-concave; if that log-concavity fails, the constant rejection-probability bound collapses and the sampling may take exponential time.","fun_headline_variants_meta":{"raw":{"variants":["Polynomial-time classical sampler for graph GBS","Graph GBS loses quantum speedup: classical sampling works","Classical Markov chain simulates graph GBS efficiently","No exponential quantum speedup for graph GBS","Polynomial-time classical simulation of graph GBS"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000453,"raw_usage":{"total_tokens":2042,"prompt_tokens":595,"completion_tokens":1447,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":339,"completion_tokens_details":{"reasoning_tokens":1373}},"tokens_in":339,"tokens_out":1447,"duration_ms":12091,"temperature":1.0,"reasoning_tokens":1373,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T21:07:51.539921+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the weighted matching counts Z_k for a family of graphs G□K2 with weights c^2 on original edges and check the inequalities Z_{k−1}Z_{k+1} ≤ Z_k^2 for all k; a single violation for some graph and c would refute the log-concavity step and thereby the polynomial-time guarantee. Equivalently, run the rejection sampler on a graph where the ratio Z'_{n−1}/Z'_n exceeds 1/2 and observe the acceptance probability decaying; a counterexample would be a concrete graph where the near-perfect-to-perfect ratio bound fails.","supporting_citations":[],"review_version":1}