{"id":"67450c16-1160-403a-94bb-fed003b80aba","arxiv_id":"2412.17742","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The authors introduce a blocked loop Hafnian and finite-difference sieve that compute coarse-grained photon-number distributions of Gaussian states in exponential, not combinatorial, time.","lead":"This paper gives a faster way to compute photon-counting probabilities for noisy and partially distinguishable quantum light experiments, replacing a combinatorial explosion of terms with an exponential-time algorithm. The method enables exact validation checks for Gaussian boson sampling and for preparing non-Gaussian states such as GKP qubits at scales that were previously impractical.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The heralded-state density-matrix results depend on the arbitrary-matrix loop Hafnian master theorem, whose proof is only cited externally [70]; a gap there would undercut Sec. VII and the state-preparation applications.","rationale":"The reader's conditional verdict already identifies the arbitrary-matrix master theorem as the weakest link. My stress-test agrees: the paper's own text (Sec. VII A) admits that the master theorem for general A,γ was an assumption in a previous draft and is now delegated to Ref. [70]. This dependency matters for the heralded-state density matrices and the state-preparation benchmarks, which are part of the paper's stated contributions. I considered whether the central coarse-grained-distribution claim for Gaussian states has a separate flaw: the finite-difference sieve evaluates the generating function at nodes far from the physical region, but because the master theorem is a formal power series identity in z around 0, the Gaussian-state case can be extended by analytic continuation; the authors do not state this, so the written proof has a gap but not an irreparable one. Thus the concrete risk is concentrated in the external proof and the sketched permutation construction. The independent verification I propose (random non-Gaussian A,γ, exact expansion to N=6) would settle whether [70] is sound. If it passes, the conditional acceptance is appropriate; if it fails, Sec. VII and the GKP/Fock simulations would need revision, possibly leaving only the Gaussian coarse-grained results. Hence the reader's CONDITIONAL verdict remains unchanged.","tokens_in":50475,"tokens_out":15730,"duration_ms":149138,"concrete_test":"Verify the arbitrary-matrix loop Hafnian master theorem directly: for M=3, choose a random complex symmetric 6×6 matrix A and random 6-vector γ that do not satisfy the Gaussian constraint, expand the RHS of Eq. (24) as a power series in z to order N=6, and compare every coefficient c_{n1,n2,n3} with lhaf(A_{n⊕n},γ_{n⊕n})/(n1!n2!n3!) using exact rational arithmetic (e.g., with SymPy). A single mismatch refutes the theorem; full agreement confirms [70]. Additionally, for M=4 and random n,m, verify Eq. (87) numerically for a Gaussian A to test the permutation construction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Sec. VII computes off-diagonal elements ⟨v|ϱ_G|u⟩ of heralded non-Gaussian states by rewriting lhaf(A_{n⊕m},γ_{n⊕m}) as lhaf(A'_{t⊕t},γ'_{t⊕t}) with A',γ' not corresponding to valid Gaussian states. The subsequent finite-difference formula (89) invokes the loop Hafnian master theorem (24) for arbitrary symmetric A and vector γ. The authors state explicitly that this was an assumption in a previous draft and that a proof was later supplied by Tarasov [70]. This external proof is load-bearing not only for the off-diagonal formulas (92), (102), (103) and the GKP/Fock-state simulations, but also for the un-restricted finite-difference sieve used at arbitrary evaluation nodes in Sec. VI, since the derivation in Sec. III only justifies the master theorem for z near the physical region unless analytic continuation is supplied (the paper does not give that argument). The permutation construction of A',γ' (Eqs. 72-86) is also only sketched. If [70] contained a gap, the state-preparation applications in Sec. VIII would be unsupported, while the total-photon-number and coarse-grained distribution results for Gaussian states might still be recoverable.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops classical algorithms for computing coarse-grained photon-number distributions, photon-number moments and cumulants, and heralded density-matrix elements for Gaussian states affected by loss, spectral impurity, and partial distinguishability. The central technical ingredients are a loop-Hafnian master theorem derived from the normalization of Gaussian Fock probabilities (Eq. (24)), an O(N M^3 + N^2 log N) algorithm for the auxiliary polynomial coefficient f_N (Appendix A), a finite-difference sieve for coefficient extraction (Sec. V), and a blocked loop-Hafnian formula for coarse-grained probabilities (Eqs. (58)-(59)). These tools are then applied to off-diagonal density-matrix elements of heralded non-Gaussian states, using an extension of the master theorem to arbitrary symmetric matrices and loop vectors that is cited to the external preprint [70]. The numerical section validates the methods against analytic total-photon-number distributions and phase-space Monte Carlo, including a configuration of the Borealis experiment.","tokens_in":50726,"tokens_out":21318,"duration_ms":206009,"significance":"The Gaussian-state results are potentially significant: they replace a combinatorial sum over detection patterns with a product of (b_l+1) evaluations of a polynomial-coefficient routine, and the paper gives a careful derivation of the coefficient algorithm together with numerical validation against analytic formulas and independent Monte Carlo methods. The strengths include the self-contained derivation of the master theorem from the normalization of Gaussian Fock probabilities, the detailed proof and complexity analysis of the f-function algorithm in Appendix A, the reproducible numerical demonstrations, and the public code release. The heralded-state and GKP/Fock-state-preparation claims, however, are conditional on the arbitrary-matrix generalization of the loop-Hafnian master theorem, which is not proved in the manuscript and is delegated to an external preprint; the state-preparation applications in Sec. VIII should be read with that caveat.","major_comments":[{"comment":"Equation (40) drops the vacuum factor Pr(0|A,gamma) that is present in Eqs. (30) and (33). As written, the right-hand side equals f_N(A_Y,gamma_Y), not Pr(N_Y=N,N_Z=0|A,gamma), since q_N(A,gamma,0)=1 and the coefficient f_N is not a probability. The numerical implementations in Sec. VIII presumably include the correct normalization, but the displayed formula is inconsistent with the derivation and should be corrected.","section":"Sec. IV, Eq. (40)"},{"comment":"The off-diagonal density-matrix formulas depend on the loop-Hafnian master theorem for arbitrary symmetric matrices A' and vectors gamma', as the authors explicitly acknowledge in the paragraph preceding Eq. (89). The proof of this arbitrary-matrix extension is only cited to the external preprint [70] and is not reproduced or verified in the manuscript. Since Eqs. (92), (102), (103) and the GKP/Fock simulations in Sec. VIII all rely on this theorem, the state-preparation claims are not self-contained. The authors should either include a proof or state the precise theorem from [70] and confirm that it applies to the complex symmetric matrices A' with the arbitrary fill entries constructed in Sec. VII A.","section":"Sec. VII A, Eqs. (72)-(86) and (89)"},{"comment":"The construction of the permutation matrix P and the extended matrices A', gamma' is only illustrated for a single 4x4 example and then asserted for the general case. Because this construction is load-bearing for every density-matrix element formula in Sec. VII, a complete constructive proof with explicit indexing for general n and m, including the odd-T padding by the block (1), is needed. The current treatment leaves too much to inspection, especially the claimed ability to fill arbitrary entries of A' while preserving the identity in Eqs. (72) and (73).","section":"Sec. VII A, Eqs. (72)-(86)"},{"comment":"The finite-difference sieve evaluates f_N(A,gamma,w) at arbitrary nodes w_j = v_j + m(u_j-v_j), while the derivation of the master theorem in Sec. III is phrased for valid Gaussian states and does not explicitly supply the analytic-continuation or formal-power-series argument needed to justify those evaluations for arbitrary complex nodes. If the arbitrary-matrix theorem of [70] is invoked for this purpose, that dependence should be stated clearly in Secs. V and VI as well as in Sec. VII; otherwise a short argument showing that Eq. (24) holds as a formal power series identity in z near z=0 should be added.","section":"Sec. V and Sec. VI, finite-difference sieve"}],"minor_comments":[{"comment":"The quantity F_Fock = sqrt(<n|rho|n>) is called a fidelity, but for a pure target state |n> the standard fidelity is <n|rho|n>; the displayed quantity is the square-root fidelity. This terminology should be clarified, and the same comment applies to F_GKP.","section":"Sec. VIII, Eqs. (108) and (110)"},{"comment":"The kth finite-difference operator is defined for k >= 1, but Eq. (48) and later formulas use D^{(0)}_{z_i} when some n_i = 0. The k=0 case should be defined explicitly as the identity operator (or, equivalently, as evaluation at an arbitrary point), since the displayed formula in Eq. (44) gives P(v_j) rather than the identity.","section":"Sec. V, Eq. (44)"},{"comment":"The phase-space Monte Carlo runtimes are reported as single values without error bars or repeated-run statistics, despite the fact that the phase-space estimates themselves carry sampling uncertainty. Reporting the variance over runs or a statistical uncertainty on the runtime would make the comparison more informative.","section":"Sec. VIII, Figs. 5 and 8"},{"comment":"Reference [70] is an arXiv preprint; the manuscript should give the version or date and, if available, a journal reference, since the arbitrary-matrix master theorem is a load-bearing external result.","section":"References, [70]"},{"comment":"The text says that for cumulants one uses only the j=1 term of the expansion in Eq. (38), but the notation \tilde q_N is introduced without explaining that this is a different generating function, not simply a truncation of q_N. A sentence clarifying the distinction would prevent confusion.","section":"Sec. VI C, Eq. (68)"}],"recommendation":"major_revision","confidential_remarks":"The main Gaussian-state coarse-grained results appear sound and well validated, and the typo in Eq. (40) is easy to fix. The more serious issue is the dependence of the heralded-state results on the externally cited arbitrary-matrix master theorem [70] and on an only-sketched matrix construction in Sec. VII A. The editor may wish to verify that [70] is correct and that its hypotheses cover the matrices A' and gamma' used here; if so, a revision that states this dependency precisely and supplies the missing construction will likely be sufficient."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know: this is a real algorithmic advance, not a repackaging. The loop Hafnian master theorem (Eq. 24) is a genuine generalization of the older Hafnian master theorem, and the blocked loop Hafnian with the finite-difference sieve (Eq. 58) genuinely replaces a combinatorial sum over bin assignments with an exponential number of evaluations of a faster function. The complexity reduction they claim—from O(N 2^{2N} prod binom(...)) to O((N M^3 + N^2 log N) prod (b_l+1))—is the main event, and the derivation is careful. I read Sec. III and Appendix A; the master theorem follows from normalization of Fock probabilities, and the f-function algorithm is proved, not just stated. The numerical checks against analytic theory and phase-space Monte Carlo are credible, and they shipped code and data. That counts for a lot.\n\nThe soft spots are in proportion. The off-diagonal density-matrix results in Sec. VII depend on the loop Hafnian master theorem holding for arbitrary symmetric matrices, not just valid Gaussian states. The authors are upfront that a previous draft treated this as an assumption and that Tarasov supplied a proof [70]. That proof is load-bearing for the GKP and Fock-state simulations; if it were wrong, those applications would be unsupported. I haven't verified [70] myself, so this is a genuine caveat, but it is not a flaw in the paper's own derivation—they flagged it. The permutation construction of A' and gamma' is sketched rather than fully proved, which is a minor gap. The speculative near-optimality claim in the conclusion is just that—speculative—and should not be presented as a result. The stress-test note worries about analytic continuation for the finite-difference sieve at arbitrary nodes. I don't think that's a real gap: Eq. (24) is an identity of formal power series in z, so it extends beyond the physical region automatically. The only genuine dependency is the arbitrary-matrix version, which they have outsourced.\n\nWho is this for? Quantum optics theorists who care about realistic GBS validation and non-Gaussian state preparation with loss and spectral impurity. It deserves a serious referee, and I'd be willing to review a revision. The core results stand; the authors should be asked to either include the arbitrary-matrix proof or make the dependency on [70] even more explicit in the main text.","headline":"A solid algorithmic advance for coarse-grained photon-number statistics of Gaussian states; the core results hold up, and only the off-diagonal density-matrix section leans on an external proof.","tokens_in":51242,"tokens_out":1669,"would_cite":true,"duration_ms":17684,"reading_group":"yes","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 coarse-grained photon-number distributions of Gaussian states—including lossy, spectrally impure, and partially distinguishable systems—can be computed in exponential, rather than combinatorial, time via a blocked…","keywords":["Gaussian states","photon-number statistics","loop Hafnian","coarse-grained distributions","Gaussian boson sampling","finite-difference sieve","heralded non-Gaussian states","spectral impurity"],"falsifier":"For a small system, say a two-mode squeezed state with two internal spectral modes under loss, compute every density-matrix element of the heralded state up to $n_{\\mathrm{cutoff}}=5$ using the finite-difference formula, Eq. (103), and compare with the brute-force combinatorial blocked loop Hafnian, Eq. (54); any disagreement beyond numerical tolerance would falsify the speedup and the density-matrix formulas. Alternatively, test the master theorem itself by picking a random symmetric $4\\times4$ matrix $A$ and vector $\\gamma$ that do not come from a Gaussian state and evaluating both sides of Eq. (24) at several points $z$; a mismatch would invalidate Section VII while leaving the Gaussian-state probability results intact.","tokens_in":50285,"feed_emoji":"🧮","tokens_out":10608,"duration_ms":92405,"temperature":0.7,"pith_summary":"The paper asks how to compute photon-number statistics for realistic quantum-optical circuits, where loss, spectral impurity, and partial distinguishability turn pure states into mixed Gaussian states and detectors see only coarse-grained bins of photons. The authors prove that coarse-grained photon-number distributions, together with photon-number moments and cumulants and the density-matrix elements of heralded non-Gaussian states, can be computed in $O((N M^3 + N^2 \\log N) \\prod_l (b_l+1))$ time instead of the combinatorial $O(N 2^{2N} \\prod_l \\binom{|\\Lambda_l|+b_l-1}{b_l})$ time of summing over every compatible detection pattern. The engine is a loop-Hafnian master theorem that packages the photon-number generating function into a closed exponential, followed by a finite-difference sieve that extracts individual binned probabilities. If correct, the results make exact validation of Gaussian and Fock boson samplers practical at scales that previously needed Monte Carlo estimation, and they speed up noisy state-preparation simulations such as approximate GKP-state generation under loss and spectral impurity by about three orders of magnitude. The weakest spot is a master-theorem extension needed for off-diagonal density-matrix elements, which the paper flags as previously assumed and now supported by a cited proof.","feed_headline":"Coarse-grained photon counts lose their combinatorial explosion","feed_subtitle":"Blocked-loop-Hafnian methods speed up GKP-state and GBS validation by up to three orders of magnitude.","key_machinery":"The load-bearing object is the blocked loop Hafnian, a coarse-grained version of the loop Hafnian—a graph invariant that counts single-pair matchings with loops and encodes photon-number statistics of Gaussian states. The key identity is the loop-Hafnian master theorem, which sums the weighted loop Hafnians of all photon patterns into one closed rational-exponential function $q(A,\\gamma,z)$. The paper then applies a finite-difference sieve: for a polynomial $f_N(A,\\gamma,w)$ of degree $N$ in $L$ block variables, the repeated divided-difference operator $D_{w_j}^{(b_j)}$ returns exactly the coefficient belonging to the binned pattern $b$, so $\\mathrm{lhaf}_{\\Lambda}(A,\\gamma,b) = \\prod_{j=1}^{L} D_{w_j}^{(b_j)} f_N(A,\\gamma,w)$. The function $f_N$ is assembled from power traces $\\mathrm{tr}([XA]^k)$ and displacement terms $\\gamma^T[XA]^{k-1}X\\gamma$, giving the $O(N M^3 + N^2 \\log N)$ per-evaluation cost that replaces the expensive direct sum over loop Hafnians.","core_discovery":"The central discovery is a closed-form generating identity, the loop-Hafnian master theorem, and its use to define the blocked loop Hafnian. For a Gaussian state with adjacency matrix $A$ and loop vector $\\gamma$, the theorem states that $\\sum_{n} \\mathrm{lhaf}(A_{n\\oplus n},\\gamma_{n\\oplus n}) \\prod_i z_i^{n_i}/n_i! = \\exp(\\tfrac12 \\gamma^T[I-D(z)XA]^{-1}D(z)X\\gamma)/\\sqrt{\\det[I-D(z)XA]}$. Grouping detectors into blocks $\\Lambda_l$ and replacing $z_i$ by one common variable $w_j$ inside each block turns this sum into a generating function in the block variables; applying finite-difference operators $D^{(b_j)}_{w_j}$ to the function $f_N(A,\\gamma,w)$ isolates the probability of the coarse-grained pattern $b$. The paper proves that the time complexity drops from the combinatorial number of compatible patterns to $O((N M^3 + N^2 \\log N) \\prod_j (b_j+1))$, and it uses the same machinery for internal-mode (spectrally impure) Gaussian states, for coarse-grained moments and cumulants, and for off-diagonal elements of states heralded by fine- or coarse-grained measurements.","pith_inferences":["Editorial inference: the authors do not explore automatic differentiation in this paper, but since $f_N(A,\\gamma,w)$ is built from matrix powers and traces, the finite-difference sieve should be differentiable; this would turn the exact probability formulas into gradients for inverse design of noisy photonic circuits.","Editorial inference: because the cost scales with the product $(b_l+1)$, the method is most favorable when coarse-graining is strong; a natural extension is to threshold detectors, where each block has $b_l \\in \\{0,1\\}$, possibly combined with the fully distinguishable internal-mode simplifications in appendix D for further polynomial speedups.","Editorial inference: the same blocked-loop-Hafnian formalism could be applied to other bosonic problems with naturally coarse-grained final states, such as vibronic spectra or Franck-Condon factors, where loop Hafnians already appear and where binning over final vibrational states is common."],"forward_implications":["Exact validation of Gaussian boson samplers becomes cheaper: the paper computes the total photon-number distribution of the 216-mode Borealis configuration in about one second, roughly fifteen times faster than phase-space sampling with $2.4\\times 10^6$ samples, and with no sampling error.","Noisy state preparation can be simulated at new scales: the density matrix of an approximate GKP state up to Fock cutoff 26, under loss and two spectral modes, is computed about three orders of magnitude faster with the finite-difference sieve than with the combinatorial blocked loop Hafnian.","Coarse-grained photon-number moments and cumulants inherit the speedup, so genuine correlations of Gaussian photonic states can be extracted without expanding sums over combinations of modes.","Fock-state inputs through lossy linear circuits also reduce to blocked loop Hafnians, improving on permanent-based sums and enabling exact binned distributions for Fock boson sampling validation."],"supporting_citations":[{"why":"This reference supplies the Fock-basis expression for Gaussian photon-number probabilities in terms of the loop Hafnian, which the master theorem generalizes.","marker":"[24]"},{"why":"This reference provides the off-diagonal density-matrix-element formula and the realistic heralded-state framework that Section VII extends.","marker":"[52]"},{"why":"This reference defines the loop Hafnian and the $O(N M^3 + N^2 \\log N)$ algorithm for the $f_N$ function that the sieve calls.","marker":"[53]"},{"why":"This reference establishes the Hafnian master theorem for unlooped Hafnians, the special case this paper extends to loop vectors.","marker":"[56]"},{"why":"This reference introduces the finite-difference sieve used to extract polynomial coefficients and hence binned probabilities.","marker":"[60]"},{"why":"This reference gives an alternative finite-difference algorithm for the loop Hafnian that the paper relates to its blocked version.","marker":"[64]"},{"why":"This reference supplies the proof that the loop-Hafnian master theorem holds for arbitrary symmetric matrices and vectors, the assumption behind the off-diagonal element formulas.","marker":"[70]"},{"why":"This reference provides the phase-space simulation method used as the numerical baseline for total photon-number distributions.","marker":"[50]"},{"why":"This reference supplies the Borealis experimental configuration and public data used for the 216-mode total photon-number validation.","marker":"[43]"},{"why":"This reference gives the earlier total-photon-number result that the paper's formula generalizes and agrees with in the relevant case.","marker":"[44]"}],"fun_headline_variants":["Loop-Hafnian trick tames photon-counting explosion","Coarse-grained photon stats now computable in polynomial time","New algorithm speeds up quantum circuit validation","Blocked loop Hafnians cut exponential cost of photon counting","Exact photon-count simulation without the combinatorial blow-up"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The computation of off-diagonal density-matrix elements of heralded non-Gaussian states assumes the loop-Hafnian master theorem holds for arbitrary symmetric matrices and vectors, not only for matrices that describe physical Gaussian states; the paper states that an earlier version treated this as an assumption and that a cited proof now supports it.","fun_headline_variants_meta":{"raw":{"variants":["Loop-Hafnian trick tames photon-counting explosion","Coarse-grained photon stats now computable in polynomial time","New algorithm speeds up quantum circuit validation","Blocked loop Hafnians cut exponential cost of photon counting","Exact photon-count simulation without the combinatorial blow-up"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000616,"raw_usage":{"total_tokens":2921,"prompt_tokens":1064,"completion_tokens":1857,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":680,"completion_tokens_details":{"reasoning_tokens":1780}},"tokens_in":680,"tokens_out":1857,"duration_ms":14304,"temperature":1.0,"reasoning_tokens":1780,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T05:13:30.089550+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a small system, say a two-mode squeezed state with two internal spectral modes under loss, compute every density-matrix element of the heralded state up to $n_{\\mathrm{cutoff}}=5$ using the finite-difference formula, Eq. (103), and compare with the brute-force combinatorial blocked loop Hafnian, Eq. (54); any disagreement beyond numerical tolerance would falsify the speedup and the density-matrix formulas. Alternatively, test the master theorem itself by picking a random symmetric $4\\times4$ matrix $A$ and vector $\\gamma$ that do not come from a Gaussian state and evaluating both sides of Eq. (24) at several points $z$; a mismatch would invalidate Section VII while leaving the Gaussian-state probability results intact.","supporting_citations":[{"cited_title":"Mart ´ ınez-Cifuentes, H","cited_arxiv_id":null,"evidence_quote":"This reference provides the off-diagonal density-matrix-element formula and the realistic heralded-state framework that Section VII extends."},{"cited_title":"Quesada, L","cited_arxiv_id":null,"evidence_quote":"This reference defines the loop Hafnian and the $O(N M^3 + N^2 \\log N)$ algorithm for the $f_N$ function that the sieve calls."},{"cited_title":"Pozrikidis, An introduction to grids, graphs, and net- works (Oxford University Press, USA, 2014)","cited_arxiv_id":null,"evidence_quote":"This reference establishes the Hafnian master theorem for unlooped Hafnians, the special case this paper extends to loop vectors."},{"cited_title":"Shchesnovich, On the classical complexity of sam- pling from quantum interference of indistinguishable bosons, International Journal of Quantum Information 18, 2050044 (2020)","cited_arxiv_id":null,"evidence_quote":"This reference gives an alternative finite-difference algorithm for the loop Hafnian that the paper relates to its blocked version."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"This reference supplies the proof that the loop-Hafnian master theorem holds for arbitrary symmetric matrices and vectors, the assumption behind the off-diagonal element formulas."},{"cited_title":"Mart ´ ınez-Cifuentes, K","cited_arxiv_id":null,"evidence_quote":"This reference provides the phase-space simulation method used as the numerical baseline for total photon-number distributions."}],"review_version":1}