Speaker
Description
We study probabilistic cellular automata (PCA) and quantum cellular automata (QCA) as frameworks for solving the Maximum Independent Set (MIS) problem. We first introduce a synchronous PCA whose dynamics drives
the system toward the manifold of maximal independent sets. Numerical evidence shows that the MIS convergence
probability increases significantly as the activation probability p → 1, and we characterize how the steps required to
reach the absorbing state scale with system size and graph connectivity. Motivated by this behavior, we construct
a QCA combining a pure dissipative phase with a constraint-preserving unitary evolution that redistributes probability within this manifold. Tensor Network simulations reveal that repeated dissipative–unitary cycles concentrate
population on MIS configurations. We also provide an empirical estimate of how the convergence time scales with
graph size, suggesting that QCA dynamics can provide an efficient alternative to adiabatic and variational quantum
optimization methods based exclusively on local and translationally invariant rules.
| Sessions | Quantum Simulation |
|---|---|
| Invited | No |