{"id":"b1165bb8-f205-45cd-a600-62b3715f40fd","arxiv_id":"2506.19298","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"A neutral-atom quantum computer can approximately count solutions to planar 2-SAT formulas by quenching Rydberg atoms and sampling the resulting states, as demonstrated numerically on grids.","lead":"This paper proposes a quantum algorithm that uses the Rydberg blockade between neutral atoms to sample solutions of planar 2-SAT formulas, then counts solutions by sampling-based estimation. It could turn near-term neutral-atom quantum computers into heuristic solvers for hard counting problems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Fixed-time quench uniformity is the load-bearing assumption; the paper's own Thouless-time estimate suggests it fails for larger n, and the FF Markov chain mixing time is never bounded.","rationale":"The reader's weakest assumption — near-uniformity of the Rydberg quench sampling distribution at the chosen fixed evolution times — is exactly the load-bearing point. The paper is honest that it lacks theoretical guarantees, and its numerical evidence is limited to n ≤ 24. The SM's Thouless-time scaling is an internal tension: if tTh grows exponentially in n, then a fixed tmax cannot yield the global near-uniformity required by the JVV theorem, and the claimed O(poly(n)) operation count has no basis. My proposed spectral-gap test would settle whether the FF Markov chain mixes in polynomially many steps, and it is feasible with the same exact-diagonalization tools already used in the paper. This does not move the verdict: the paper is a clearly labeled heuristic with promising small-system numerics, so CONDITIONAL remains appropriate. I find no additional independent flaw beyond the reader's identified assumption, and no reason to escalate to REJECT or downgrade to UNVERDICTED.","tokens_in":12190,"tokens_out":11413,"duration_ms":133086,"concrete_test":"Build the practical-FF transition matrix M_{s,x} = (1/Δt)∫_{tmin}^{tmax} |⟨x|e^{-iH_PXP t}|s⟩|^2 dt exactly for 1D chains with n = 12, 16, 20, 24 (solution spaces of Fibonacci size) and compute its spectral gap. Extrapolate gap(n); if it closes as e^{-cn}, the number of FF steps needed for nη = O(1) is exponential, directly invalidating the O(poly(n)) sampling claim at the chosen fixed times. If gap(n) closes polynomially, the uniformity assumption is supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The polynomial operation count of RydCount depends on JVV's condition nη = O(1) holding at every self-reduction step. The paper fixes tmin = 10 Ω^-1 and tmax = 10^3 Ω^-1 and assumes the practical FF output distribution is close enough to uniform. This is the least secure premise. The SM's own Thouless-time estimate tTh ∝ D^{2/3}/Γ ~ e^{2cn/3}/√n means that for n ≳ 30 the chosen tmax lies below the equilibration time; a constant-time quench of a large system is not scrambled over the exponentially large solution space. The FI protocol already shows nη growing with n (Fig. 1), and the FF protocol's improvement is only demonstrated for small chains with non-monotonic η (Fig. 7). Moreover, no uniformity data is given for the induced subproblems produced by variable fixing (Algorithm 1 steps 13-14), even though JVV requires a fresh near-uniform sampler for each such subproblem. Since the paper explicitly states 'we do not have theoretical guarantees of uniformity at these timescales', the O(poly(n)) complexity claim is conditional on an unverified and, by the SM's own scaling, questionable assumption.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes RydCount, a hybrid quantum-classical algorithm for approximate counting of satisfying assignments of planar 2SAT instances on neutral-atom quantum computers. Boolean variables are mapped to atoms arranged in a blockade graph, and the PXP/Rydberg Hamiltonian is used to quench an initial computational basis state into a superposition over solution states. The algorithm then applies the Jerrum-Valiant-Vazirani self-reduction framework, estimating variable marginals from measurements, fixing the most likely variable to 1, reducing the register, and accumulating an estimate of the count. Numerical simulations for 1D chains, 2D grids, and punctured grids show that a feed-forward variant can produce near-uniform sampling and count estimates within a few percent for the small system sizes considered. The authors present the protocol as a practical near-term heuristic rather than a proven quantum speedup, and they explicitly state that no theoretical guarantees of uniformity at the chosen timescales are available.","tokens_in":12310,"tokens_out":5573,"duration_ms":57759,"significance":"If the uniformity assumption were substantiated, RydCount would be a significant proposal: it offers a counting heuristic that requires no variational parameter optimization, is implementable with global pulses on current analog neutral-atom devices, and inherits a degree of noise resilience because sampled solutions can be verified classically. The numerical benchmarks are a useful first step, and the paper is commendably explicit about the heuristic nature of the central uniformity assumption. However, the main complexity claim, O(poly(n)) operations for constant-factor counting, rests on the unproven and, by the paper's own Thouless-time estimate, questionable condition that nη=O(1) holds at fixed evolution times for all system sizes and for every induced subproblem generated by the self-reduction. The evidence presented does not yet establish that condition.","major_comments":[{"comment":"The central condition nη=O(1) (Eq. 5) is asserted for the fixed time window tmin=10Ω^-1, tmax=10^3Ω^-1 without a proof or scaling analysis. The SM's own estimate tTh ∝ D^{2/3}/Γ ≈ e^{2cn/3}/√n (with Γ∼n) grows exponentially with n, so for larger n the chosen tmax is below the estimated equilibration time. Since the manuscript states \"we do not have theoretical guarantees of uniformity at these timescales,\" the abstract's claim that the algorithm \"requires O(poly(n)) operations\" is not supported by the presented evidence.","section":"Main text, uniform-sampling subsection"},{"comment":"The FI protocol's nη grows roughly linearly with n, so it does not meet the JVV condition. The FF protocol's improvement is demonstrated only for small chains and grids (n up to about 24), and Fig. 7 shows that η is non-monotonic in the number of FF steps and fluctuates across runs. Crucially, no uniformity data are given for the induced subproblems created by fixing variables (Algorithm 1 steps 13-14), although JVV requires near-uniform sampling from each conditional distribution. The end-to-end counts in Figs. 2-3 do not close this gap, because the count estimator can be accurate for the tested sizes even when the per-step bias is not controlled.","section":"Figs. 1, 6, 7 and Algorithm 1"},{"comment":"The estimate κ is updated by division by the empirical probability p_c that variable c is 1. Any per-step sampling bias enters the estimator multiplicatively and propagates through up to n self-reduction steps. The manuscript does not bound the final multiplicative error in terms of the per-step total variation distance η, nor does it analyze the compounding of errors; the insets of Figs. 2-3 report relative errors for a few sizes but not a scaling law. Without such an analysis, the polynomial-sample claim for constant-factor approximation is not established.","section":"Algorithm 1, step 15"},{"comment":"The practical FF protocol is not a memoryless Markov chain in the sense of Eqs. (8)-(9): after each step the next input is a single sampled bitstring, so the evolution of the distribution depends on the entire history of sampled states. The SM notes that η is not monotonically decreasing in k and that scarred states act as attractors, reducing the process to FI behavior. No mixing-time bound or stationary-distribution analysis is provided, and the empirical convergence in Fig. 7 is for one small chain (n=18). Thus the claim that FF converges to uniform sampling is heuristic only.","section":"SM, feed-forward protocol"}],"minor_comments":[{"comment":"The phrase \"O(poly(n)) operations\" is imprecise; specifying the scaling of the sample count and evolution-time window, or explicitly labeling the statement as a heuristic conjecture, would align the abstract with the evidence in the main text.","section":"Abstract"},{"comment":"The footnote discards trand values closer than the Heisenberg time tH, but tH is never defined, and this rejection changes the effective time distribution U(tmin,tmax) used in Eq. (6); the authors should clarify how the reported η estimates account for this rejection.","section":"Footnote [51]"},{"comment":"The caption uses \"punched grids\" while the main text refers to \"punctured grids\"; the terminology should be made consistent.","section":"Fig. 3 caption"},{"comment":"The statement that \"all but an O(1) subset of initial states\" exhibit unexpectedly long thermalization times is unclear: it should specify whether the exceptional set has size O(1) in n or is a measure-zero subset with respect to a particular ensemble.","section":"Main text, initial-state discussion"},{"comment":"The scaling Γ∼n is attributed to Ref. [49], an arXiv preprint from the same group; providing a derivation or an additional independent citation would make the Thouless-time estimate easier to assess.","section":"SM, Thouless-time estimate"}],"recommendation":"major_revision","confidential_remarks":"The paper is honest about its limitations, and the numerical work is a reasonable first exploration, but the central complexity claim is currently stronger than the evidence. A revision that reframes the contribution as a heuristic with explicit scaling caveats, adds uniformity data for the induced subproblems produced by self-reduction, and provides a quantitative error-propagation analysis would make the paper suitable for publication. I do not see a clear internal contradiction that would require rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real new algorithm — RydCount — and the numerical work behind it is careful and mostly convincing for small systems. The paper is worth treating as a serious heuristic proposal. But don't let the O(poly(n)) phrasing fool you: the whole thing hinges on near-uniform sampling after fixed-time quenches, and the evidence for that at scale is thin and, if anything, points the other way.\n\nWhat's genuinely new: mapping planar 2SAT to Rydberg blockade graphs is known, but the RydCount self-reduction loop with feed-forward (FF) initial-state updates, and the numerical demonstration that the practical FF protocol brings nη down to O(1) on 1D chains and 2D grids, is not in the earlier literature. The paper also deserves credit for being candid. It states plainly that there are no theoretical guarantees of uniformity at the chosen timescales, and it shows the biased FI data rather than hiding it.\n\nWhere it's soft: the load-bearing premise is that a quench of duration between 10 and 10^3 Ω^-1 produces a distribution with nη=O(1) for every instance size, and stays that way on every induced subproblem created by variable fixing. The evidence is numerical, on chains and grids up to roughly n=24. The SM's own Thouless-time estimate, tTh ∝ D^{2/3}/Γ ~ e^{2cn/3}/√n, implies that for n beyond 30 the max evolution time is below the equilibration time. The FI protocol already shows nη growing with n; the practical FF is better but shown only for small chains with non-monotonic η. No uniformity data is given for the subproblems inside the self-reduction loop. So the O(poly(n)) statement is conditional, and the condition is not just unproven — the paper's own scaling suggests it may fail.\n\nThe tmin/tmax values are picked empirically from the same numerical experiments, which is a minor circularity, not a fatal one. Instance diversity is limited to grid-like graphs; that's fine for a first paper but worth noting.\n\nBottom line: this is a serious heuristic proposal for a practical near-term quantum counting device, and a well-executed numerical study. It is not a proof of polynomial-time counting. If I were refereeing, I'd ask for a scaling study of η on self-reduced subproblems and a more careful statement that the runtime claim is conditional. I'd send it to peer review.","headline":"RydCount is a fresh, honestly-presented heuristic for approximate #2SAT counting on neutral atoms, but its polynomial-time claim leans on an unproven fixed-time uniformity assumption that the paper's own Thouless analysis makes look doubtful at scale.","tokens_in":12962,"tokens_out":2510,"would_cite":true,"duration_ms":24120,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that a Rydberg-blockade quench samples planar 2SAT solutions nearly uniformly, turning approximate counting into a polynomial number of measurements.","keywords":["quantum counting","Rydberg blockade","planar 2SAT","sampling-based counting","neutral-atom quantum computing","PXP model","self-reduction","approximate counting"],"falsifier":"Simulate or run RydSamp on a 1D chain or 2D grid of, say, 40 or more atoms and compute $n\\eta$ at $t_{\\mathrm{min}} = 10\\,\\Omega^{-1}$ and $t_{\\mathrm{max}} = 10^3\\,\\Omega^{-1}$. If $n\\eta$ grows without bound with $n$, or if the RydCount estimate deviates beyond the promised constant factor as $n_{\\mathrm{samp}}$ scales polynomially, the central claim fails.","tokens_in":11880,"feed_emoji":"⚛️","tokens_out":6366,"duration_ms":55282,"temperature":0.7,"pith_summary":"The paper proposes a practical quantum algorithm, RydCount, for approximately counting solutions to planar 2-satisfiability (2SAT) formulas on neutral-atom quantum computers. The central claim is that a quantum quench under Rydberg blockade dynamics, starting from a computational basis state and measured at a random time, produces an almost uniform sample of satisfying assignments, and that this near-uniformity is enough to feed the classical sampling-based counting scheme of Jerrum, Valiant, and Vazirani. If the claim holds, approximate counts within a constant multiplicative factor follow from polynomially many measurements, sidestepping the variational optimization of other near-term proposals. The paper supports the claim with numerical simulations on 1D chains and 2D punctured grids with up to about two dozen atoms, and shows that a feed-forward variant mitigates a bias toward low-Hamming-weight states.","feed_headline":"Rydberg quench counts 2SAT solutions with polynomial samples","feed_subtitle":"Random-time Rydberg quenches sample 2SAT solutions near-uniformly, giving constant-factor counts in polynomial time.","key_machinery":"The central mechanism is the Rydberg blockade: when atoms are placed so that edges of a planar graph fall within the blockade radius, the constraint $(\\neg x_i \\lor \\neg x_j)$ for each edge is enforced by the PXP Hamiltonian's restriction to the blockade subspace. RydCount then runs a random-time quench of this Hamiltonian, measures in the computational basis, and feeds the measured bitstring back as the next initial state (feed-forward protocol) to suppress bias toward low-Hamming-weight states. The classic self-reduction of SAT turns the near-uniform samples into a product-of-likelihoods estimate of the count, requiring $O(n^4)$ samples in the worst case.","core_discovery":"On the paper's own terms, the discovery is that the Rydberg blockade provides a native, hardware-aligned encoding of monotone 2SAT in which every low-energy state of the PXP Hamiltonian is a satisfying assignment, and that a random-time quench of a simple product state explores this solution space nearly uniformly. The uniformity condition $n\\eta = O(1)$ is met in numerical studies for the feed-forward protocol, and RydCount then estimates the solution count by repeatedly sampling, fixing the most likely variable, reducing the atom register, and multiplying the observed likelihoods. The paper explicitly does not claim a proven speedup; it claims a polynomial-operation heuristic whose validity is robust to noise because sampled assignments can be checked in linear time.","pith_inferences":["If the near-uniform sampling claim holds beyond the simulated sizes, the same blockade encoding could be applied to other constraint satisfaction problems whose solutions are independent sets of unit-disk graphs, such as counting maximum independent sets, with the same sampling-to-counting reduction.","The paper's own Thouless-time estimate ($t_{\\mathrm{Th}} \\propto e^{2cn/3}/\\sqrt{n}$) suggests that a fixed quench window may become too short to reach near-uniformity on large systems; testing $n\\eta$ on systems with $n \\gtrsim 30$ atoms would reveal whether the heuristic's range is system-size-limited.","The feed-forward protocol effectively defines a quantum Markov chain over solution states; proving a mixing-time bound for that chain would upgrade the heuristic into a certified approximation algorithm, but the paper does not attempt this.","A direct experiment on a Rydberg array could measure the output distribution of a quench and compare it with the uniform distribution over independent sets, giving an immediate hardware check of the uniformity assumption."],"forward_implications":["For the 2D punctured-grid instances tested, RydCount returns solution counts within roughly 10% error using a polynomially scaling number of samples, and the error decreases with system size.","Because the protocol needs no variational parameter optimization, it avoids the convergence problems common to near-term hybrid quantum-classical counting algorithms.","The basic fixed-input version requires only global pulse control and is implementable on existing analog neutral-atom devices, while the feed-forward version requires selective addressability.","The validity of each sampled assignment can be verified in linear time, so hardware noise degrades the efficiency but not the correctness of the checks.","If combined with known constructions for embedding arbitrary Boolean functions in 2D atomic registers, the same sampling mechanism would give a heuristic for any #P counting problem."],"supporting_citations":[{"why":"Supplies the sampling-based counting reduction (JVV) that turns almost uniform samples into a constant-factor count via self-reduction.","marker":"[16]"},{"why":"Introduced the PXP model as the blockade limit of Rydberg dynamics, the effective Hamiltonian the paper evolves.","marker":"[34]"},{"why":"Extends the PXP model to Rydberg gases, supporting the blockade mapping used for 2SAT encodings.","marker":"[35]"},{"why":"Shows #P-completeness of planar 3-regular bipartite monotone 2SAT, motivating the planar 2SAT target.","marker":"[40]"},{"why":"Identifies scarred states and atypical survival probabilities that cause the fixed-input bias the feed-forward protocol mitigates.","marker":"[45]"},{"why":"Provides the Thouless-time scaling argument used to set $t_{\\mathrm{min}}$ and to discuss equilibration of the quench.","marker":"[50]"},{"why":"Shows that arbitrary Boolean functions can be represented in 2D atomic registers, extending RydCount to any #P function.","marker":"[30]"}],"fun_headline_variants":["Rydberg blockade maps 2SAT to neutral atom counting","Quantum counting of 2SAT via Rydberg quench","Approximate 2SAT counting with Rydberg sampling","Rydberg dynamics sample 2SAT solutions near uniformly","Rydberg quench yields near-uniform 2SAT solution samples"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole protocol rests on the assumption that at the fixed quench times used (between 10 and 1000 inverse Rabi frequencies), the measured distribution stays close enough to uniform, with $n\\eta$ of order one, for every problem size, even though no theoretical guarantee is given and the evidence is limited to small numerical systems.","fun_headline_variants_meta":{"raw":{"variants":["Rydberg blockade maps 2SAT to neutral atom counting","Quantum counting of 2SAT via Rydberg quench","Approximate 2SAT counting with Rydberg sampling","Rydberg dynamics sample 2SAT solutions near uniformly","Rydberg quench yields near-uniform 2SAT solution samples"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000463,"raw_usage":{"total_tokens":2261,"prompt_tokens":835,"completion_tokens":1426,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":451,"completion_tokens_details":{"reasoning_tokens":1341}},"tokens_in":451,"tokens_out":1426,"duration_ms":10987,"temperature":1.0,"reasoning_tokens":1341,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T18:33:43.009578+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate or run RydSamp on a 1D chain or 2D grid of, say, 40 or more atoms and compute $n\\eta$ at $t_{\\mathrm{min}} = 10\\,\\Omega^{-1}$ and $t_{\\mathrm{max}} = 10^3\\,\\Omega^{-1}$. If $n\\eta$ grows without bound with $n$, or if the RydCount estimate deviates beyond the promised constant factor as $n_{\\mathrm{samp}}$ scales polynomially, the central claim fails.","supporting_citations":[{"cited_title":"Functional completeness of planar Rydberg blockade structures","cited_arxiv_id":"2301.01508","evidence_quote":"Shows that arbitrary Boolean functions can be represented in 2D atomic registers, extending RydCount to any #P function."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the sampling-based counting reduction (JVV) that turns almost uniform samples into a constant-factor count via self-reduction."},{"cited_title":"Lesanovsky, Phys","cited_arxiv_id":null,"evidence_quote":"Introduced the PXP model as the blockade limit of Rydberg dynamics, the effective Hamiltonian the paper evolves."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Extends the PXP model to Rydberg gases, supporting the blockade mapping used for 2SAT encodings."},{"cited_title":"Xia and W","cited_arxiv_id":null,"evidence_quote":"Shows #P-completeness of planar 3-regular bipartite monotone 2SAT, motivating the planar 2SAT target."}],"review_version":2}