Answers are grounded in this paper and cite their sources.
Proposed quantum algorithm estimates solution count for 2SAT using rydberg blockade, suggesting applicability to #P-complete problems.
We propose a quantum algorithm for approximately counting the number of solutions to planar 2-satisfiability (2SAT) formulas natively on neutral atom quantum computers. Our algorithm maps Boolean variables to atomic registers arranged in space according to a given formula, so that 2SAT constraints are enforced via the Rydberg blockade between neighboring atoms. A quench under Rydberg dynamics of an initial computational basis state produces a superposition of all solutions after a sufficiently long evolution. For almost uniform superpositions, a polynomial number of measurements is enough to estimate the solution count up to any constant multiplicative factor via sampling based counting. We demonstrate numerically that this protocol leads to almost uniform solution sampling in 1D and 2D grids and that it produces accurate counts for 2SAT instances on punctured grids, suggesting its general applicability as a heuristic for #P-complete problems.
No takes yet. Share an insight, caveat, or question.
Gibson et al. (2025) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: