Theory

We study the capabilities and limits of probabilistic computers and their relationship with quantum computers. We use statistical physics to understand how correlations, constraints, and representations affect computation, and how approximations change the result.

Probabilistic and quantum computation

Comparisons with quantum computers change as algorithms and hardware improve. Our work on pushing the boundary of quantum advantage develops stronger probabilistic methods for comparison with quantum annealing. The generalized Probabilistic Approximate Optimization Algorithm (PAOA) learns stochastic search dynamics and lets us compare probabilistic and quantum variational approaches to optimization.

Our generalized Ising work studies how probabilistic models can represent quantum interference. Signed or complex contributions can cancel, creating a sign problem that can require many samples to recover an accurate result. Neural quantum states (NQS) provide another connection: p-computers sample learned representations of quantum states. Our hardware demonstrations so far use models with nonnegative ground-state amplitudes.

Correlations and approximations

Cluster mean-field theory (CMFT) lets us study large interacting systems through smaller clusters. Interactions within each cluster are retained, while external interactions become approximate effective fields. Changing the partition lets interactions that crossed cluster boundaries act directly within a cluster. We examine how cluster size and update rules affect optimization quality and sampling accuracy.

An interaction graph is divided into clusters that fit individual devices, with boundary samples and mean fields exchanged between probabilistic and classical computers.
An interaction graph is divided into clusters that fit individual devices, with boundary samples and mean fields exchanged between probabilistic and classical computers.

Figure: Partitioning a large graph into locally evolving clusters. Zhang et al., Extreme-Scale Ising Machines with Cluster Mean-Field Theory, Fig. 1, CC BY 4.0. Full-resolution figure.

Constraints and continuous spins

Potts models represent choices with more than two states. Mean-field feedback can impose global constraints approximately while preserving sparse interactions. Heisenberg models extend our interest in probabilistic dynamics to continuous spin vectors with programmable interactions.

Physical foundations

Our earlier work on modular spin circuits connected spin transport and magnetization dynamics with transistor-level circuit simulation. It provides a foundation for understanding how physical devices implement computational models.

Recent Publications

Foundational Publications