Pith. sign in

REVIEW 4 major objections 4 minor 1 cited by

Graph Gaussian boson sampling is classically simulable in polynomial time

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review

2026-08-03 21:07 UTC pith:HH3KMWLG

load-bearing objection Settles the open question for graphical GBS distributions with an elegant, correct reduction; the load-bearing log-concavity step is true but under-supported. the 4 major comments →

arxiv 2511.16558 v2 pith:HH3KMWLG submitted 2025-11-20 quant-ph cs.DS

Simulating Gaussian boson sampling on graphs in polynomial time

Konrad Anand , Zongchen Chen , Mary Cryan , Graham Freifeld , Leslie Ann Goldberg , Heng Guo , Xinyuan Zhang This is my paper
classification quant-ph cs.DS MSC 81P6868Q1205C7068W20 PACS 03.67.Lx
keywords Gaussian boson samplinggraph matchingsperfect matchingsclassical simulationMarkov chain Monte Carlopermanent approximationboson samplingcomputational complexity
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

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.

Core claim

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

What carries the argument

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.

Load-bearing premise

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.

What would settle it

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.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • 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.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

4 major / 4 minor

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.

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 (4)
  1. [Section 4, Lemma 4.2, Eq. (11)] 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.
  2. [Section 4, after Lemma 4.2 (weighted log-concavity)] 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.
  3. [Section 4, Theorem 1.1 proof (TV amplification)] 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.
  4. [Theorem 1.1 statement and proof (running-time dependence on c)] 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.
minor comments (4)
  1. [Section 3, Eq. (7)] 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.
  2. [Section 4, proof of Theorem 1.1] 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.
  3. [Theorem 1.1 vs. Proposition 2.1] 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.
  4. [Section 4, notation] Haf(S) for an odd-cardinality set S is implicitly treated as 0; this convention should be stated explicitly before Lemma 4.2.

Circularity Check

0 steps flagged

No significant circularity: the derivation reduces to external algorithmic results and an explicit Cartesian-product identity; the sole unproved step is a missing proof/citation, not a circular assumption.

full rationale

The derivation is not circular. Theorem 1.1 samples μ_GBS,G(S) ∝ c^{2|S|} PM(S)^2. The reduction is explicit and external: Lemma 4.1 proves that the induced distribution of a weighted perfect matching of G□K2 is exactly μ_GBS,G, so the target is not assumed in the construction. Sampling is then delegated to the Jerrum–Sinclair algorithm (Proposition 2.1), and the rejection sampling step is justified by Lemma 4.2 (Z_{n-1} < 2n^2 Z_n, proved by AM-GM and Equation (10)) together with equation (12), which gives a constant rejection probability. Theorem 1.3 similarly reduces to the permanent/hafnian identities and to the Jerrum–Sinclair–Vigoda algorithm, with no fitted parameters and no target distribution assumed. There are no load-bearing self-citations: references to [ZZW+25], [OFJQ24], and [BDR+18] are background, and no uniqueness theorem or ansatz is imported from the authors' prior work. The one genuinely unsupported step is the assertion after Lemma 4.2 that 'the log concavity still holds for weighted matchings'—this is an omitted proof/citation (it is true via Heilmann–Lieb real-rootedness and Newton's inequalities), but it is not equivalent to the paper's target and is not a fitted or self-citational input. Minor correctness concerns, such as the c-versus-c^2 factor in the stated running time and the exact ε bookkeeping in the total variation analysis, are separate from circularity. Overall, the main claim has independent mathematical content and is not forced by definition or by self-citation.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

The central claim rests on external sampling theorems (JS89, JSV04/BSVV08), the cited GBS-to-hafnian identity, and an unproved weighted log-concavity assertion. No free parameters are fitted and no new entities are postulated.

axioms (5)
  • standard math Jerrum–Sinclair algorithm samples from the weighted matching distribution in polynomial time (Proposition 2.1)
    External theorem [JS89, JS96]; used to sample from μ_matching,λ' on G□K2.
  • standard math Jerrum–Sinclair–Vigoda algorithm samples weighted perfect matchings in bipartite graphs in polynomial time (Proposition 2.3)
    External theorem [JSV04, BSVV08]; used for Theorem 1.3.
  • domain assumption Weighted matching counts Z_k are log-concave for arbitrary nonnegative edge weights
    Asserted without proof or citation after Lemma 4.2; needed to extend Z'_{n-1}<Z'_n/2 to all k and get a constant rejection probability. Follows from real-rootedness of weighted matching polynomials, but the paper does not cite this.
  • domain assumption GBS graph distribution equals μ_GBS,G(S) ∝ c^{2|S|} Haf(A_S)^2 (Equation 9)
    Cited from [BDR+18]; defines the target distribution.
  • standard math Hafnian of an adjacency matrix counts perfect matchings
    Used throughout Lemma 4.1 and Lemma 4.2.

pith-pipeline@v1.3.0-alltime-deepseek · 9732 in / 30677 out tokens · 254192 ms · 2026-08-03T21:07:51.539921+00:00 · methodology

0 comments
read the original abstract

We show that a distribution related to Gaussian Boson Sampling (GBS) on graphs can be sampled classically in polynomial time. Graphical applications of GBS typically sample from this distribution, and thus quantum algorithms do not provide exponential speedup for these applications. We also show that another distribution related to Boson sampling can be sampled classically in polynomial time.

Figures

Figures reproduced from arXiv: 2511.16558 by Graham Freifeld, Heng Guo, Konrad Anand, Leslie Ann Goldberg, Mary Cryan, Xinyuan Zhang, Zongchen Chen.

Figure 1
Figure 1. Figure 1: On the left we have our graph G with vertex sets from left to right: L1, R1, R2, L2. The corresponding matrix A is a 2 × 3 matrix with all 1 entries, and k = 2 in this example. On the right, a perfect matching M selected from G is highlighted. Here S1(M) = {u (1) 1,1 , u (1) 2,1 } and z = {1, 1}. Proof. Given the matrix A, we will construct a bipartite graph G and weights λ such that its distribution µPM,λ… view at source ↗
Figure 2
Figure 2. Figure 2: On the left we have our original graph G, while on the right we have G □ K2 [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: On the left, we have a perfect matching M in G □ K2, with M ∩ E highlighted in red in the top copy, M ∩ E′ blue in the bottom copy, and M ∩ E0 black. On the right, we have our underlying graph G with the set SM and the corresponding edges chosen by M (in either or both copies) highlighted. Lemma 4.1. The induced distribution of SM is exactly µGBS,G(S). Proof. For M ∼ µPM,λ, as it is a perfect matching of G… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Gaussian Boson Sampling for Asset Clustering in Statistical Arbitrage Portfolios

    quant-ph 2026-07 conditional novelty 6.0

    GBS-based clustering (GBS Roots and adapted GBS Boost) produced higher StatArb portfolio returns than classical Spectral/SPONGE clustering in simulated S&P 500 backtests, with the advantage shrinking outside high-vola...

Reference graph

Works this paper leans on

20 extracted references · cited by 1 Pith paper

  1. [1]

    The computational complexity of linear optics

    Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. Theory Comput. , 9:143--252, 2013

    2013

  2. [2]

    Juan Miguel Arrazola and Thomas R. Bromley. Using G aussian boson sampling to find dense subgraphs. Phys. Rev. Lett. , 121:030503, 2018

    2018

  3. [3]

    Gaussian boson sampling for perfect matchings of arbitrary graphs

    Kamil Br\'adler, Pierre-Luc Dallaire-Demers , Patrick Rebentrost, Daiqin Su, and Christian Weedbrook. Gaussian boson sampling for perfect matchings of arbitrary graphs. Phys. Rev. A , 98:032310, 2018

    2018

  4. [4]

    Graph isomorphism and G aussian boson sampling

    Kamil Br\'adler, Shmuel Friedland, Josh Izaac, Nathan Killoran, and Daiqin Su. Graph isomorphism and G aussian boson sampling. Spec. Matrices , 9(1):166--196, 2021

    2021

  5. [5]

    Vazirani, and Eric Vigoda

    Ivona Bez \' a kov \' a , Daniel S tefankovi c , Vijay V. Vazirani, and Eric Vigoda. Accelerating simulated annealing for the permanent and combinatorial counting problems. SIAM J. Comput. , 37(5):1429--1454, 2008

    2008

  6. [6]

    The classical complexity of boson sampling

    Peter Clifford and Rapha \" e l Clifford. The classical complexity of boson sampling. In SODA , pages 146--155. SIAM , 2018

    2018

  7. [7]

    Faster classical boson sampling

    Peter Clifford and Rapha \" e l Clifford. Faster classical boson sampling. Phys. Scr. , 99(6):065121, 2024

    2024

  8. [8]

    Performance of gaussian B oson sampling on planted bipartite clique detection

    Yu-Zhen Janice Chen, Laurent Massouli\'e, and Don Towsley. Performance of gaussian B oson sampling on planted bipartite clique detection. arXiv , page 2510.12774, 2025

    arXiv 2025

  9. [9]

    Solving graph problems using G aussian boson sampling

    Yu-Hao Deng, Si-Qiu Gong, Yi-Chao Gu, Zhi-Jiong Zhang, Hua-Liang Liu, Hao Su, Hao-Yang Tang, Jia-Min Xu, Meng-Hao Jia, Ming-Cheng Chen, Han-Sen Zhong, Hui Wang, Jiarong Yan, Yi Hu, Jia Huang, Wei-Jun Zhang, Hao Li, Xiao Jiang, Lixing You, Zhen Wang, Li Li, Nai-Le Liu, Chao-Yang Lu, and Jian-Wei Pan. Solving graph problems using G aussian boson sampling. P...

    2023

  10. [10]

    Hamilton, Regina Kruse, Linda Sansoni, Sonja Barkhofen, Christine Silberhorn, and Igor Jex

    Craig S. Hamilton, Regina Kruse, Linda Sansoni, Sonja Barkhofen, Christine Silberhorn, and Igor Jex. G aussian boson sampling. Phys. Rev. Lett. , 119:170501, 2017

    2017

  11. [11]

    Approximating the permanent

    Mark Jerrum and Alistair Sinclair. Approximating the permanent. SIAM J. Comput. , 18(6):1149--1178, 1989

    1989

  12. [12]

    The M arkov chain M onte C arlo method: an approach to approximate counting and integration

    Mark Jerrum and Alistair Sinclair. The M arkov chain M onte C arlo method: an approach to approximate counting and integration. In Dorit S. Hochbaum, editor, Approximation Algorithms for NP-Hard Problems , page 482–520. PWS Publishing Co., 1996

    1996

  13. [13]

    A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries

    Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM , 51(4):671--697, 2004

    2004

  14. [14]

    Hamilton, Linda Sansoni, Sonja Barkhofen, Christine Silberhorn, and Igor Jex

    Regina Kruse, Craig S. Hamilton, Linda Sansoni, Sonja Barkhofen, Christine Silberhorn, and Igor Jex. Detailed study of G aussian boson sampling. Phys. Rev. A , 100:032326, 2019

    2019

  15. [15]

    Inapproximability of positive semidefinite permanents and quantum state tomography

    Alexander Meiburg. Inapproximability of positive semidefinite permanents and quantum state tomography. Algorithmica , 85(12):3828--3854, 2023

    2023

  16. [16]

    Madsen, Fabian Laudenbach, Mohsen Falamarzi

    Lars S. Madsen, Fabian Laudenbach, Mohsen Falamarzi. Askarani, Fabien Rortais, Trevor Vincent, Jacob F. F. Bulmer, Filippo M. Miatto, Leonhard Neuhaus, Lukas G. Helt, Matthew J. Collins, Adriana E. Lita, Thomas Gerrits, Sae Woo Nam, Varun D. Vaidya, Matteo Menotti, Ish Dhand, Zachary Vernon, Nicol\'as Quesada, and Jonathan Lavoie. Quantum computational ad...

    2022

  17. [17]

    Quantum-inspired classical algorithm for graph problems by G aussian boson sampling

    Changhun Oh, Bill Fefferman, Liang Jiang, and Nicol\'as Quesada. Quantum-inspired classical algorithm for graph problems by G aussian boson sampling. PRX Quantum , 5:020341, 2024

    2024

  18. [18]

    Aghaee Rad, T

    H. Aghaee Rad, T. Ainsworth, R. N. Alexander, B. Altieri, M. F. Askarani, R. Baby, L. Banchi, B. Q. Baragiola, J. E. Bourassa, R. S. Chadwick, I. Charania, H. Chen, M. J. Collins, P. Contu, N. D’Arcy, G. Dauphinais, R. De Prins, D. Deschenes, I. Di Luch, S. Duque, P. Edke, S. E. Fayer, S. Ferracin, H. Ferretti, J. Gefaell, S. Glancy, C. González-Arciniega...

    2025

  19. [19]

    Quantum computational advantage using photons

    Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, Peng Hu, Xiao-Yan Yang, Wei-Jun Zhang, Hao Li, Yuxuan Li, Xiao Jiang, Lin Gan, Guangwen Yang, Lixing You, Zhen Wang, Li Li, Nai-Le Liu, Chao-Yang Lu, and Jian-Wei Pan. Quantum computational advantage using photons. Science , 370(6523):1460...

    2020

  20. [20]

    Efficient classical sampling from G aussian boson sampling distributions on unweighted graphs

    Yexin Zhang, Shuo Zhou, Xinzhao Wang, Ziruo Wang, Ziyi Yang, Rui Yang, Yecheng Xue, and Tongyang Li. Efficient classical sampling from G aussian boson sampling distributions on unweighted graphs. Nat. Commun. , 16:9335, 2025

    2025

This paper was first reviewed by deepseek-v4-flash on August 3, 2026.