{"id":"a1c530bb-4203-4a78-a044-55625d886309","arxiv_id":"1908.10070","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A classical sampling algorithm for Gaussian boson sampling decomposes Hafnians into smaller Hafnians and permanents, enabling simulation of 18-30 photons and lowering the estimated quantum-supremacy threshold.","lead":"Researchers propose a faster classical algorithm for simulating Gaussian boson sampling, a leading quantum-supremacy experiment candidate. It lets ordinary computers simulate 18 to 30 detected photons before becoming impractical, lowering the estimated size at which a quantum device could win.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Truncation at N=c n_most is not merely unquantified: for Fig. 7(b) parameters (m=36, r=0.2) n_most=0, so the stated Step 1 emits n=0 with probability 1, yet the figure reports nonzero photon counts; the omitted tail is about 52%.","rationale":"The reader's weakest assumption identified the truncation in Section 3.1, and that is indeed the load-bearing point for the claim that the algorithm samples the GBS output distribution. My pass sharpens the concern with a concrete parameter set from the paper itself: for m=36, r=0.2, n_most=0 and hence N=0, so the described first step can only sample n=0, while Fig. 7(b) shows photon counts. This is an internal inconsistency rather than just a missing error bound. The concern is fixable: one can sample the negative-binomial distribution exactly, or choose N by an explicit tail bound, or state that the practical benchmarks are for fixed-n conditional sampling. For that reason the result should remain conditional rather than rejected. I did not find a concrete error in the Hafnian decomposition or the complexity analysis, and the small-n numerical validation in Fig. 6 gives some support, so I would not move the verdict away from conditional on this pass.","tokens_in":19640,"tokens_out":20135,"duration_ms":206800,"concrete_test":"Implement Step 1 exactly as written for m=36, r=0.2: compute n_most = 2 floor((m/2 - 1) sinh^2 r), set N = 50 n_most, renormalize Eq. (14), and sample n from the truncated distribution. Record the frequency of n>0. If no positive n is ever produced while Fig. 7(b) shows photons, the published validation contradicts the described algorithm. In the same run, evaluate P_0, P_2, P_4 and sum_{n>N} P_n to confirm the tail is about 0.52; this settles whether the truncation error is negligible.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central sampling claim rests on Step 1 of §3.1, where the photon-number distribution is truncated at N = c n_most and renormalized with c=50. No total-variation bound is given, and the issue is sharper than a missing bound. For the paper's own validation run in Fig. 7(b), m=36 and r=0.2. The definition n_most = 2 floor((m/2 - 1) sinh^2 r) gives sinh^2(0.2) ≈ 0.0405, so (m/2-1) sinh^2 r ≈ 0.689, hence n_most = 0 and N = 0. After renormalization, the first step samples n=0 with probability 1, so no configuration with photons can be produced. Yet Fig. 7(b) reports nonzero frequencies for modes with photon number =1 and >1, and the caption says the first part of the sampling process was used. Direct evaluation of Eq. (14) at these parameters gives P_0 ≈ 0.484, P_2 ≈ 0.339, P_4 ≈ 0.126, so the omitted tail has probability about 0.52. The truncation is therefore not a negligible approximation in a parameter regime the authors themselves present. If the benchmarks are instead meant for fixed-n conditional sampling, that needs to be stated, because then the advertised full-GBS sampler and its O(m sinh^2 r + poly(n)2^{8n/3}) complexity do not describe the implemented procedure.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a two-step classical simulation algorithm for Gaussian boson sampling (GBS) with identical single-mode squeezed input states. In the first step, the total photon number n is sampled from the (truncated) negative-binomial distribution P_n; in the second step, a photon-mode assignment is sampled from the conditional distribution p_n(s) using a Hafnian-permanent decomposition of the marginal probabilities. The authors claim time complexity O(m sinh^2 r + poly(n)2^{8n/3}) with polynomial space and O(m sinh^2 r + poly(n)2^{5n/2}) with O(m2^n) space, and report numerical simulations of 18 photons on a laptop, 20 on a 256-core workstation, and an estimated 30 on Sunway TaihuLight. They interpret these numbers as evidence that the photon-number threshold for quantum computational supremacy with GBS is lower than for standard boson sampling.","tokens_in":20009,"tokens_out":7178,"duration_ms":72783,"significance":"If the algorithm is correct and the error analysis supports the practical benchmarks, this is a valuable contribution to the classical-simulation side of the quantum-supremacy debate: it gives explicit complexity exponents for GBS, provides an open-source implementation, and compares favorably with threshold-detector GBS simulations. The paper's strengths include the concrete parametric complexity derivations in Appendices C and D, the independent numerical consistency check for n=4 in Figure 6, and the de facto benchmark against brute-force sampling. However, the central claim about simulating the full GBS output distribution depends on an unquantified truncation step in Section 3.1 and on a theorem whose proof is only sketched; these points materially affect the 18/20/30-photon claims.","major_comments":[{"comment":"The truncation of the photon-number distribution is not a negligible approximation and, as stated, contradicts the paper's own numerical validation. For the parameters of Fig. 7(b), m=36 and r=0.2, we have n_most = 2 floor((m/2-1) sinh^2 r) = 2 floor(17 * 0.0405) = 0, so with N = 50 n_most the truncated support is {0}; after renormalization, Step 1 samples n=0 with probability 1, yet Fig. 7(b) reports nonzero frequencies for photon number =1 and >1. Direct evaluation of Eq. (14) gives P_0 ≈ 0.49, so the omitted tail has probability about 0.51. The manuscript must either provide a total-variation bound for the truncated sampler or explicitly restrict the claims to parameter regimes where the tail is controlled; if the benchmarks are for fixed-n conditional sampling, that needs to be stated, because then the advertised full-GBS sampler is not the implemented procedure.","section":"Section 3.1, Eq. (14), Fig. 7(b)"},{"comment":"The stated complexity O(m sinh^2 r + poly(n)2^{8n/3}) is a bound for the conditional second step at a fixed n. When Step 1 samples n from the truncated distribution, the support extends up to N = c n_most, and the second-step cost grows exponentially in the sampled n. The paper does not bound the total cost of the two-step sampler, nor the expected cost over P_n, nor the error incurred by the cutoff. Without such a bound, the advertised complexity does not describe the full GBS sampler in the form that produced the numerical benchmarks; the complexity claim should be restated as applying to conditional fixed-n sampling, with a separate analysis for the full sampler.","section":"Abstract and Section 3.5, algorithm complexity"},{"comment":"The correctness of the sampling algorithm rests on Theorem 1, but the proof in Appendix G is a sketch in which the counting argument for the factor F(k,mu,j1,j2) in Appendix H is asserted rather than fully derived, and no independent verification of the theorem is supplied for n>4. Figure 6 validates the full output distribution only for n=4 and m=16; Figure 7 checks only single-mode occupation frequencies, not the joint distribution. The runtime benchmarks for n=18 and n=20 therefore do not by themselves establish that the implemented sampler is drawing from the claimed distribution. A complete proof of Theorem 1, or a machine-checked verification, together with a distribution-level statistical test for a non-trivial n (for example n=8 or n=10), would be needed to support the practical claims.","section":"Section 3.4, Theorem 1; Appendix G; Figures 6 and 7"}],"minor_comments":[{"comment":"There are several typographical errors: 'constrcuted' in Section 2.3, 'complele' in Section 3.4.1, 'our our algorithm' in Section 3.5, 'Hafnain' in the title of Appendix F, and 'theorical' in the caption of Figure 6.","section":"Throughout"},{"comment":"The caption of Figure 6 mentions three curves (blue, green, yellow) but the text describes only two comparisons; please make the correspondence between panels and curves explicit.","section":"Section 3.5, Figure 6"},{"comment":"The notation ([k]\\s over mu) and the set-valued use of s are not defined before the pseudocode; a brief definition of the set notation used in Algorithm 2 would improve readability.","section":"Algorithm 2, line 10"},{"comment":"The phrase 'establish a lower bound for achieving quantum computational supremacy' is imprecise: the paper gives an upper bound on classical simulation cost, from which one infers a lower bound on the photon number needed for a quantum advantage claim. Rephrasing would avoid confusion.","section":"Abstract and Table 1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a serious algorithmic contribution and the conditional fixed-n sampling part may well be sound, but the paper's headline claim about simulating the full GBS distribution is not supported as written: the truncation step is inconsistent with one of the paper's own figures and no error bound is provided. I would ask the authors to clarify the fixed-n versus full-distribution distinction, supply the missing tail analysis, and strengthen the validation of Theorem 1 before reconsidering the paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The one new thing worth knowing: the paper gives a graphical summation rule that decomposes GBS marginal probabilities into sums of smaller Hafnians and permanents, yielding O(poly(n)2^{8n/3}) time for fixed-n conditional sampling (O(poly(n)2^{5n/2}) with exponential space). That is a real step beyond the threshold-detector algorithm and beyond brute force, and the derivation is plausible. They provide code, check against brute force for n=4, and show the runtime scaling up to n=18. The complexity exponents come from the math rather than fitted parameters, which is good.\n\nThe soft spot is load-bearing. Step 1 of their sampler truncates the photon-number distribution at N = c n_most and renormalizes, with no total-variation bound. That would be a minor gap if the tail were obviously small, but it is not. In their own Fig. 7(b), with m=36 and r=0.2, n_most = 2 floor(17 sinh^2(0.2)) = 0, so N=0. The renormalized Step 1 would then output n=0 with probability 1, yet the figure reports nonzero photon counts. Direct evaluation of Eq. (14) gives P_0 ≈ 0.49, so roughly half the probability mass is being discarded. Either the figure was produced by conditioning on n>0, which is not stated, or the full-distribution sampler as implemented differs from the one in the text. The advertised practical limits (18/20/30 photons) are therefore not established as benchmarks for sampling from the full GBS distribution. What is established is a faster conditional sampler for fixed n, which is still a meaningful contribution.\n\nOther concerns are minor: Theorem 1's proof is \"rather involved\" and not independently checked, and the Sunway estimate is an extrapolation with a known 4x discrepancy on the Kunlun server. Neither changes my read of the core fixed-n algorithm.\n\nWho benefits: anyone working on classical simulation of GBS or on benchmarks for photonic quantum advantage. The fixed-n decomposition technique is probably correct and will be useful. The full-distribution claim needs repair before the paper can be taken as a valid benchmark.\n\nRecommendation: send it to peer review. A good referee should demand a total-variation bound for the truncation (or an explicit conditioning on n), a fix of the Fig. 7(b) inconsistency, and a restatement of what the 18/20/30 numbers actually mean.","headline":"A genuinely faster fixed-n GBS sampler based on a new Hafnian/permanent decomposition, but the full-distribution sampler has an unquantified truncation that in one of the paper's own examples discards half the distribution.","tokens_in":20533,"tokens_out":3264,"would_cite":true,"duration_ms":34371,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68"],"pacs":[],"model":"deepseek-v4-flash","headline":"Classical simulation of Gaussian boson sampling reaches 30 photons by splitting Hafnians into smaller pieces.","keywords":["Gaussian boson sampling","classical simulation","Hafnian","permanent","quantum computational supremacy","squeezed states","negative binomial distribution","marginal sampling"],"falsifier":"Compute the exact tail probability $T=\\sum_{n>N}P_n$ for a claimed operating point (for instance $m=n^2$ with the squeezing parameters used in the 18- and 20-photon runs); if $T$ is larger than the statistical uncertainty of the benchmark, the empirical output distribution must differ measurably from exact GBS, settling the approximation question. A direct check would be to run the algorithm and brute-force sampling side by side at a feasible size, such as $n=6$ or $8$, and compare large sample sets with a chi-square statistic.","tokens_in":19441,"feed_emoji":"","tokens_out":13076,"duration_ms":111217,"temperature":0.7,"pith_summary":"This paper claims that Gaussian boson sampling—a proposed quantum-supremacy experiment in which squeezed light passes through a linear optical network and photons are counted—can be simulated classically much faster than by brute force. The algorithm samples the total photon number from its known negative-binomial distribution and then draws each photon's output mode one at a time, computing the needed marginal probabilities by splitting each large Hafnian into products of smaller Hafnians and permanents. The running time is $O(m\\sinh^2 r + \\mathrm{poly}(n)2^{8n/3})$ in polynomial space, improving to $O(m\\sinh^2 r + \\mathrm{poly}(n)2^{5n/2})$ with $O(m2^n)$ storage. Numerically the authors report 18 photons in about a day on a laptop, 20 photons on a 256-core workstation, and an estimated 30 photons on a modern supercomputer. If correct, the classical-simulation threshold for Gaussian boson sampling sits below the 30–50 photon range quoted for standard boson sampling, making GBS an easier target for demonstrating quantum computational supremacy.","feed_headline":"Classical algorithm samples 30-photon Gaussian boson output","feed_subtitle":"Photon-by-photon marginals bring 18-30 photon outputs within a day of computing, below standard boson sampling's 50.","key_machinery":"The load-bearing object is the Hafnian $\\mathrm{Haf}(V)$, a matrix function like the permanent but summing over perfect matchings, which enters through the GBS output probability $p(s)=\\frac{\\tanh^n r}{s_1!\\cdots s_m!\\cosh^m r}|\\mathrm{Haf}(W_s)|^2$. The paper views $W_x$ with entries $W(x_i,x_j)$ as the adjacency matrix of a complete graph with self-loops, so each matching is a collection of edges. The mechanism that carries the speedup is the summation-path rule: because $W=UU^T$ gives $\\sum_i W(i,j)W^*(i,j')=\\delta_{j,j'}$, a chain of unresolved internal modes in the expansion of $|\\mathrm{Haf}(W_x)|^2$ contracts to a single edge, and the remaining expression collapses into a sum of products of sub-Hafnians and permanents (Theorem 1). That decomposition lets each conditional marginal be evaluated in $O(\\mathrm{poly}(n)2^{8n/3})$ time, or $O(\\mathrm{poly}(n)2^{5n/2})$ time if intermediate sub-Hafnians are stored in $O(m2^n)$ memory.","core_discovery":"The paper's central claim is that, for GBS with the same squeezing parameter in every input mode, sampling an output configuration $s=(s_1,\\dots,s_m)$ does not require evaluating an $n\\times n$ Hafnian for every configuration. The output probability factors as $p(s)=P_n p_n(s)$, where $P_n$ has a closed negative-binomial form and the conditional distribution $p_n(s)$ is independent of the squeezing parameter. By moving to an ordered list $x=(x_1,\\dots,x_n)$ of photon positions, the authors express each conditional probability $q_n(x_k\\mid x_1,\\dots,x_{k-1})$ as a sum over pairs of perfect matchings. Using the unitarity of the interferometer matrix $W=UU^T$, internal summations over unresolved modes collapse to delta functions, and the sum reorganizes (Theorem 1) into a combination of Hafnians and permanents of submatrices, which lowers the exponent in the running time. The resulting sampling algorithm has the stated time and space bounds, simplifies to a 0-or-1 permanent in the collision-free regime, and is checked against brute-force sampling at small sizes before being extrapolated to 18, 20, and 30 photons.","pith_inferences":["The photon-number truncation at $N=c n_{\\mathrm{most}}$ is renormalized without a total-variation bound; if the tail above $N$ is non-negligible, the stated 18/20/30-photon numbers describe an approximate sampler rather than exact GBS simulation.","The same splitting technique is a general recipe for Hafnian-based marginal probabilities and should transfer to other GBS variants, such as scattershot boson sampling, threshold detection, or lossy networks, where the same unitarity contraction applies.","A tighter analysis of the truncated tail, or a faster Hafnian subroutine plugged into Theorem 1, could move the practical simulation limit in either direction, so the supremacy threshold is not a fixed physical constant."],"forward_implications":["A 30-photon Gaussian boson sampling experiment could be classically sampled in about a day on a large supercomputer, so a GBS supremacy demonstration would need more than 30 photons to beat the classical benchmark.","The exponential-space variant bounds the full photon-number-resolving simulation, including collision events, by $O(\\mathrm{poly}(n)2^{5n/2})$ time.","In the collision-free regime, where threshold detection is equivalent to photon counting, the reported limits improve on threshold-detector GBS simulation at the same sizes.","Because $p_n(s)$ is independent of the squeezing parameter, the second stage of the algorithm applies to a whole family of GBS settings, with only the photon-number selection depending on $r$."],"supporting_citations":[{"why":"Supplies the $O(n^3 2^{n/2})$ Hafnian algorithm used as the per-Hafnian cost in the complexity analysis and runtime estimates.","marker":"[5]"},{"why":"Supplies the sequential-conditional-sampling method that Step 3 adapts to Gaussian boson sampling.","marker":"[12]"},{"why":"Introduces the Gaussian boson sampling model with single-mode squeezed states that the algorithm simulates.","marker":"[17]"},{"why":"Provides the output-probability Hafnian formula, the negative-binomial photon-number distribution, and the most-probable-photon-number quantity used for truncation.","marker":"[20]"},{"why":"Provides the standard-boson-sampling simulation limits (30 photons on a laptop, 50 on a supercomputer) against which the paper compares GBS.","marker":"[23]"},{"why":"Provides the threshold-detector GBS simulation baseline that the paper's algorithm outperforms in the collision-free regime.","marker":"[26]"},{"why":"Provides a large-scale threshold-detector GBS simulation benchmark used in the comparison table.","marker":"[16]"}],"fun_headline_variants":["Classical algorithm simulates 30-photon Gaussian boson sampling","Simulation shortcut brings Gaussian boson sampling to laptops","Gaussian boson sampling: classical speedup to 30 photons","Classical method slashes Gaussian boson sampling simulation cost"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the photon-number distribution can be cut off at $N=c n_{\\mathrm{most}}$ and renormalized without changing the sampled distribution; if the tail above $N$ is not negligible in the regimes claimed, the algorithm samples from a distribution that is not the true GBS distribution.","fun_headline_variants_meta":{"raw":{"variants":["Classical algorithm simulates 30-photon Gaussian boson sampling","Simulation shortcut brings Gaussian boson sampling to laptops","Gaussian boson sampling: classical speedup to 30 photons","Classical method slashes Gaussian boson sampling simulation cost"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00049,"raw_usage":{"total_tokens":2421,"prompt_tokens":963,"completion_tokens":1458,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":579,"completion_tokens_details":{"reasoning_tokens":1388}},"tokens_in":579,"tokens_out":1458,"duration_ms":13883,"temperature":1.0,"reasoning_tokens":1388,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:54:32.676253+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the exact tail probability $T=\\sum_{n>N}P_n$ for a claimed operating point (for instance $m=n^2$ with the squeezing parameters used in the 18- and 20-photon runs); if $T$ is larger than the statistical uncertainty of the benchmark, the empirical output distribution must differ measurably from exact GBS, settling the approximation question. A direct check would be to run the algorithm and brute-force sampling side by side at a feasible size, such as $n=6$ or $8$, and compare large sample sets with a chi-square statistic.","supporting_citations":[{"cited_title":"The classical complexity of boson sampling","cited_arxiv_id":null,"evidence_quote":"Supplies the sequential-conditional-sampling method that Step 3 adapts to Gaussian boson sampling."},{"cited_title":"Hamilton, Regina Kruse, Linda Sansoni, Sonja Barkhofen, Christine Silber- horn, and Igor Jex","cited_arxiv_id":null,"evidence_quote":"Introduces the Gaussian boson sampling model with single-mode squeezed states that the algorithm simulates."},{"cited_title":"A detailed study of Gaussian Boson Sampling","cited_arxiv_id":"1801.07488","evidence_quote":"Provides the output-probability Hafnian formula, the negative-binomial photon-number distribution, and the most-probable-photon-number quantity used for truncation."},{"cited_title":"Classical boson sampling algorithms with superior performance to near-term experiments","cited_arxiv_id":null,"evidence_quote":"Provides the standard-boson-sampling simulation limits (30 photons on a laptop, 50 on a supercomputer) against which the paper compares GBS."},{"cited_title":"Gaussian boson sam- pling using threshold detectors","cited_arxiv_id":null,"evidence_quote":"Provides the threshold-detector GBS simulation baseline that the paper's algorithm outperforms in the collision-free regime."},{"cited_title":"Classical benchmarking of Gaussian Boson Sampling on the Titan supercomputer","cited_arxiv_id":"1810.00900","evidence_quote":"Provides a large-scale threshold-detector GBS simulation benchmark used in the comparison table."}],"review_version":1}