Computational Phase Transition Signature in Gibbs Sampling
This addresses the challenge of verifying algorithmic phase transitions in emerging computational devices like quantum or stochastic annealers, which is incremental as it builds on known theoretical concepts.
The paper tackled the problem of observing computational phase transitions in physics-based processors, predicting and prescribing their physical observation in Gibbs' distributions through simulation, which could represent a milestone in physical computation theory.
Gibbs sampling is fundamental to a wide range of computer algorithms. Such algorithms are set to be replaced by physics based processors$-$be it quantum or stochastic annealing devices$-$which embed problem instances and evolve a physical system into an ensemble to recover a probability distribution. At a critical constraint to variable ratio, decision problems$-$such as propositional satisfiability$-$appear to statistically exhibit an abrupt transition in required computational resources. This so called, algorithmic or computational phase transition signature, has yet-to-be observed in contemporary physics based processors. We found that the computational phase transition admits a signature in Gibbs' distributions and hence we predict and prescribe the physical observation of this effect. We simulate such an experiment, that when realized experimentally, we believe would represent a milestone in the physical theory of computation.