Speaker
Description
We introduce a novel framework that connects probabilistic cellular automata (PCA) with quantum cellular automata (QCA) to tackle graph optimization problems, focusing on the Maximum Independent Set (MIS) task. Starting from a new class of classical PCA rules acting locally on graphs with bounded degree, we show how to construct a corresponding QCA whose dissipative dynamics drives the system toward configurations close to the optimal solution. Remarkably, this quantum extension allows the automaton to explore the solution space more efficiently, approaching the optimal MIS with high probability in polynomial time. This approach highlights how QCA dynamics can serve as a unifying language bridging classical stochastic computation and quantum optimization.