Maximum Independent Set via Probabilistic and Quantum Cellular Automata

• URL: http://arxiv.org/abs/2512.06778v1
• Date: Sun, 07 Dec 2025 10:33:52 GMT
• Title: Maximum Independent Set via Probabilistic and Quantum Cellular Automata
• Authors: Federico Dell'Anna, Matteo Grotti, Vito Giardinelli,
• Abstract summary: We first introduce a synchronous PCA whose dynamics drives the system toward the manifold of maximal independent sets.<n>Motivated by this behavior, we construct a QCA combining a pure dissipative phase with a constraint-preserving unitary evolution.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 tends to 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.

Related papers

• SKANet: A Cognitive Dual-Stream Framework with Adaptive Modality Fusion for Robust Compound GNSS Interference Classification [47.20483076887704]
  Global Navigation Satellite Systems (GNSS) face growing threats from sophisticated jamming interference.<n>We propose a cognitive deep learning framework built upon a dual-stream architecture that integrates Time-Frequency Images (TFIs) and Power Spectral Density (PSD)<n>We show that SKANet achieves an overall accuracy of 96.99%, exhibiting superior robustness for compound jamming classification.
  arXiv  Detail & Related papers  (2026-01-19T07:42:45Z)
• Tractable Infinite-Horizon Stochastic Model Predictive Control for Quantum Filtering via Eigenstate Reduction [8.368020865178844]
  We propose a tractable Model Predictive Control framework for finite-dimensional quantum systems.<n>Online SMPC step requires only deterministic propagation of the filter and a terminal fidelity evaluation.<n>We establish equivalence and mean-square stability guarantees, and validate the approach on multi-level and Ising-type systems.
  arXiv  Detail & Related papers  (2025-11-08T08:25:48Z)
• Free Cumulants and Full Eigenstate Thermalization from Boundary Scrambling [0.0]
  We introduce a solvable many-body quantum model, which we term boundary scrambling, for which the full dynamics of higher-order OTOCs is analytically tractable.<n>We obtain exact expressions for (higher-order) correlations between matrix elements and show these to be stable away from the solvable point.<n>These results provide insight into the emergence of random-matrix behavior from structured Floquet dynamics and show how techniques from free probability can be applied in the construction of exactly-solvable many-body models.
  arXiv  Detail & Related papers  (2025-09-09T18:01:45Z)
• Free Probability in a Minimal Quantum Circuit Model [0.0]
  We study the dynamics of higher-order out-of-time-order correlators (OTOCs) in a minimal circuit model for quantum dynamics.<n>We prove the exponential decay of all higher-order OTOCs and fully characterize the relevant time scales.<n>This approach and the relevant influence matrix are expected to be applicable in more general settings.
  arXiv  Detail & Related papers  (2025-06-12T18:00:11Z)
• Scaling of Stochastic Normalizing Flows in $\mathrm{SU}(3)$ lattice gauge theory [44.99833362998488]
  Non-equilibrium Markov Chain Monte Carlo simulations provide a well-understood framework based on Jarzynski's equality to sample from a target probability distribution.<n>Out-of-equilibrium evolutions share the same framework of flow-based approaches and they can be naturally combined into a novel architecture called Normalizing Flows (SNFs)<n>We present the first implementation of SNFs for $mathrmSU(3)$ lattice gauge theory in 4 dimensions, defined by introducing gauge-equivariant layers between out-of-equilibrium Monte Carlo updates.
  arXiv  Detail & Related papers  (2024-11-29T19:01:05Z)
• Unbiasing time-dependent Variational Monte Carlo by projected quantum evolution [44.99833362998488]
  We analyze the accuracy and sample complexity of variational Monte Carlo approaches to simulate quantum systems classically. We prove that the most used scheme, the time-dependent Variational Monte Carlo (tVMC), is affected by a systematic statistical bias. We show that a different scheme based on the solution of an optimization problem at each time step is free from such problems.
  arXiv  Detail & Related papers  (2023-05-23T17:38:10Z)
• A self-consistent field approach for the variational quantum eigensolver: orbital optimization goes adaptive [52.77024349608834]
  We present a self consistent field approach (SCF) within the Adaptive Derivative-Assembled Problem-Assembled Ansatz Variational Eigensolver (ADAPTVQE) This framework is used for efficient quantum simulations of chemical systems on nearterm quantum computers.
  arXiv  Detail & Related papers  (2022-12-21T23:15:17Z)
• Formal Controller Synthesis for Markov Jump Linear Systems with Uncertain Dynamics [64.72260320446158]
  We propose a method for synthesising controllers for Markov jump linear systems. Our method is based on a finite-state abstraction that captures both the discrete (mode-jumping) and continuous (stochastic linear) behaviour of the MJLS. We apply our method to multiple realistic benchmark problems, in particular, a temperature control and an aerial vehicle delivery problem.
  arXiv  Detail & Related papers  (2022-12-01T17:36:30Z)
• Directed percolation in non-unitary quantum cellular automata [0.0]
  We construct a non-unitary Quantum Cellular Automaton that generalises the Domany-Kinzel cellular automaton. We study the resulting dynamical evolution using the numerical simulations using the tensor network iTEBD algorithm.
  arXiv  Detail & Related papers  (2021-05-04T10:10:16Z)
• Quantum Markov Chain Monte Carlo with Digital Dissipative Dynamics on Quantum Computers [52.77024349608834]
  We develop a digital quantum algorithm that simulates interaction with an environment using a small number of ancilla qubits. We evaluate the algorithm by simulating thermal states of the transverse Ising model.
  arXiv  Detail & Related papers  (2021-03-04T18:21:00Z)
• Towards quantum simulation of Sachdev-Ye-Kitaev model [5.931069258860319]
  We study a simplified version of the Sachdev-Ye-Kitaev (SYK) model with real interactions by exact diagonalization. A quantum phase transition from a chaotic state to an integrable state is observed by increasing the discrete separation.
  arXiv  Detail & Related papers  (2020-03-03T14:18:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.