⚛️ quantum physics

Quantum Counting in the Rydberg Blockade

The authors propose and experimentally demonstrate a native quantum algorithm on neutral-atom quantum computers that utilizes Rydberg blockade dynamics to generate superpositions of solutions for planar 2SAT problems, enabling efficient approximate counting of solution counts through sampling.

Original authors: Joseph Gibson, Victor Drouin-Touchette, Stefanos Kourtis

Published 2026-10-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Joseph Gibson, Victor Drouin-Touchette, Stefanos Kourtis

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Counting is one of the most fundamental tasks in human thought, yet for computers, it can be a nightmare. While a machine can easily find a single solution to a complex puzzle, such as arranging a schedule or routing a network, figuring out exactly how many different solutions exist is a vastly harder problem. This difficulty sits at the heart of many challenges in artificial intelligence, network reliability, and the physics of materials. For decades, scientists have known that counting these possibilities is often so difficult that no efficient method exists for the hardest cases. Instead of giving up, researchers have turned to approximation, seeking to estimate the total number of solutions rather than finding the exact figure. This is where the promise of quantum computing enters the story, offering a new way to explore these vast landscapes of possibilities, not by calculating them one by one, but by letting the laws of physics do the heavy lifting.

A team of researchers at the Institut quantique in Sherbrooke, Quebec, has now demonstrated a practical way to perform this kind of approximate counting on a specific type of quantum computer built from neutral atoms. Their work focuses on a class of problems known as 2-satisfiability, which involves determining how many ways a set of logical rules can be satisfied. The researchers developed an algorithm that maps these logical rules directly onto a physical grid of atoms. In this setup, the atoms act as the variables in the puzzle, and their physical interactions enforce the rules. When the atoms are excited by a laser, they enter a special state where they cannot be too close to one another in their excited form, a phenomenon known as the Rydberg blockade. This physical constraint naturally prevents the system from settling into invalid configurations, effectively filtering out the wrong answers and leaving only the valid solutions.

The core of the new method involves a process of rapid change, or a "quench," where the system is suddenly driven from a simple starting state into a complex web of possibilities. If the system is allowed to evolve for a specific amount of time, it settles into a superposition that contains all the valid solutions at once. The researchers then measure the atoms to see which solution appears. By repeating this process many times, they can gather a collection of samples. The brilliance of the approach lies in how these samples are used: the algorithm identifies which variable appears most often in a specific state, fixes that variable to that state, and then repeats the process on the smaller, remaining problem. This step-by-step reduction allows the computer to estimate the total number of solutions by multiplying together the probabilities observed at each step.

To test their idea, the team first ran extensive simulations on a computer to see how the algorithm would behave in idealized conditions. They found that for simple one-dimensional chains of atoms, the method produced highly accurate estimates of the solution count. When they moved to more complex two-dimensional triangular grids, the results remained strong, though a slight bias emerged. This bias was caused by the fact that the physical interactions between atoms extend slightly further than just their immediate neighbors, which subtly favors certain types of solutions over others. Crucially, the simulations showed that the underlying sampling mechanism (RydSamp) achieves nearly uniform sampling for instances with up to 10,000 variables, a scale an order of magnitude larger than what is typically accessible to classical solvers today. While the full counting algorithm was tested on smaller instances in the simulations, this uniformity suggests the method is robust enough to handle much larger problems.

The true test came when the researchers implemented their algorithm on a real quantum processor, the Orion Alpha, located at a facility in Sherbrooke. This machine uses a grid of 81 atoms arranged in a triangular pattern to represent a specific counting problem. Because the commercial hardware lacks the ability to individually address every single atom with perfect precision, the team had to adapt their method. Instead of running the full, multi-step reduction process entirely on the quantum chip, they used a hybrid approach. They let the quantum computer handle the most difficult part of the problem—the sampling of solutions on a specific cut of the grid—and then used a classical computer to finish the calculation. Even with this simplified setup and the limitations of current hardware, the experiment was a success. The quantum processor generated estimates that were remarkably close to the exact count in one specific path, falling within a factor of 1.01, while another path yielded an estimate within a factor of 5.

The results suggest that this native approach to counting on neutral-atom quantum computers is a viable path forward. While the current hardware is not yet perfect, and the method relies on a mix of quantum sampling and classical calculation, the experiment proved that a machine with 81 atoms could tackle a problem that is difficult for standard computers to solve efficiently. The researchers noted that as these machines grow larger and the control over individual atoms improves, the method could become a powerful tool for solving some of the most intractable counting problems in science. For now, the work stands as a clear demonstration that quantum devices can do more than just find a single answer; they can begin to count the vast number of ways a system can exist, opening a new window into the complexity of the physical world.

Technical Summary: Quantum Counting in the Rydberg Blockade

Problem Statement
Counting the number of solutions to combinatorial problems, such as Boolean satisfiability (SAT), is a fundamental task in artificial intelligence, network reliability, and statistical physics. However, exact counting for hard instances belongs to the complexity class #P, which is believed to be intractable for classical computers. While approximate counting via sampling is a viable alternative, it requires the ability to sample solutions almost uniformly. Classical sampling-based methods often struggle to achieve this uniformity efficiently. Furthermore, existing quantum approaches, such as those based on Grover iterations, require circuit depths that grow exponentially with the number of variables, rendering them inaccessible to current noisy intermediate-scale quantum (NISQ) processors.

Methodology: RydCount
The authors propose RydCount, a sampling-based approximate counting algorithm designed natively for neutral-atom quantum computers (NAQCs). The algorithm targets planar 2-satisfiability (2SAT) formulas.

Physical Encoding: The algorithm maps Boolean variables to atomic registers trapped in optical tweezers. The 2SAT constraints are enforced via the Rydberg blockade. Specifically, the system evolves under a Rydberg Hamiltonian where nearest-neighbor atoms in the Rydberg state are energetically prohibited from simultaneous excitation. This physical constraint naturally encodes the monotone 2SAT formula $\phi_G(x) = \bigwedge_{(i,j) \in E} (\neg x_i \lor \neg x_j)$ , where the low-energy subspace corresponds to the solution space of the formula.
Sampling Protocol: The core subroutine, RydSamp, involves preparing an initial computational basis state (typically $|0\rangle^{\otimes n}$ ), applying a "quench" via a static laser pulse for a random evolution time $t \in [t_{min}, t_{max}]$ , and measuring the resulting state in the computational basis.
Feed-Forward (FF) Mechanism: To improve sampling uniformity, the algorithm employs a feed-forward protocol. If a measured bitstring is a valid solution, it is fed back as the initial state for the next iteration. Theoretical analysis suggests that for generic initial states, the chaotic dynamics of the Rydberg Hamiltonian spread the state amplitude across the accessible Hilbert space, leading to an almost uniform distribution over the solution set after a sufficient number of FF steps ( $k$ ).
Self-Reduction Counting: The algorithm follows the Jerrum-Valiant-Vazirani (JVV) framework. It iteratively fixes variables to their maximum-likelihood state based on collected samples, reducing the problem size at each step. The final estimate is the product of the reciprocals of these observed probabilities.

Key Contributions and Results

Theoretical Feasibility: The authors demonstrate that the Rydberg blockade representation preserves the self-reducibility required for JVV counting. They show that while the Rydberg Hamiltonian does not produce a perfectly uniform distribution due to imperfect blockade and long-range interaction tails, it achieves "almost uniform" sampling ( $n\eta \lesssim 1$ ) for instances with up to $n \approx 10^4$ variables using a polynomial number of FF steps.
Classical Simulations:
- 1D and 2D Grids: Simulations on 1D chains and 2D triangular grids show that the estimated count converges to a value within a constant multiplicative factor of the exact count as the number of samples increases.
- Bias Analysis: The authors identify a systematic bias in 2D and punctured grids caused by next-nearest neighbor interactions, which penalize high Hamming weight states. This leads to an underestimation of the probability of variables being in state $|1\rangle$ , resulting in a systematic overestimation of the total count. Consequently, the algorithm acts as an effective upper bound on the exact count in these scenarios rather than a precise estimate within a multiplicative factor.
- Punctured Grids: For random "punctured" 2D grids (where sites are removed), the algorithm converges to within a factor of $1.1$ of the exact count for low hole densities. The authors note that classical solvers like GANAK exhibit exponential runtime scaling for these instances, suggesting the existence of classically hard #2SAT instances within this graph ensemble, though they do not claim RydCount is faster or superior in runtime.
Experimental Demonstration: The authors implemented a simplified, hybrid variant of RydCount on Pasqal's Orion Alpha NAQC. Due to hardware limitations (lack of selective atom addressability), they could not perform the full iterative self-reduction. Instead, they:
1. Used a single-step ( $k=1$ ) sampling from the ground state.
2. Pre-selected a graph separator to decompose the 81-variable problem into two smaller subproblems.
3. Solved the subproblems classically and combined them with the quantum-derived multiplicative factor from the separator.
4. Evaluated two decimation paths (fixing variables to 0 or 1) to establish upper and lower bounds.
Experimental Results: For an 81-variable planar grid instance, the raw hardware shots yielded estimates within a multiplicative factor of 5 (for the $x_c=1$ path) and 1.01 (for the $x_c=0$ path) of the exact count. Post-selecting only valid solution bitstrings improved the $x_c=0$ path to within a factor of $<1.25$ . The two paths successfully bounded the exact count.

Significance and Outlook
The paper claims that RydCount represents a viable near-term approach to approximate counting on NISQ devices. Its significance lies in:

Native Implementation: It utilizes the natural physics of NAQCs (Rydberg blockade) to enforce constraints, avoiding the deep circuits required by gate-based quantum algorithms.
Scalability: The protocol is shown to work for problem sizes ( $n=81$ ) that are challenging for current non-annealing quantum processors and approach the limits of state-of-the-art classical solvers for specific graph ensembles.
Future Potential: The authors note that while current clock rates are low (<10 Hz), future improvements to 100 Hz, combined with the ability to trap thousands of atoms and implement selective addressability (already demonstrated in academic labs), could position RydCount as a competitive alternative to classical methods for #P-hard problems. The use of atom chains to encode planar 3-regular bipartite graphs suggests the method could be extended to #P-complete instances.

The authors remain modest, acknowledging that the current experimental demonstration is a simplified hybrid variant and that systematic biases due to long-range interactions must be mitigated (e.g., via better blockade strength or addressability) to achieve precise estimates rather than just bounds.

More like this