Summary: We investigate dynamical many-body systems capable of universal computation, which leads to their properties being unpredictable unless the dynamics is simulated from the beginning to the end. Unpredictable behavior can be quantitatively assessed in terms of a data compression of the states occurring during the time evolution, which is closely related to their Kolmogorov complexity. We analyze a master equation embedding of classical cellular automata and demonstrate the existence of a phase transition between predictable and unpredictable behavior as a function of the random error introduced by the probabilistic character of the embedding. We then turn to have this dynamics competing with a second process inducing quantum fluctuations and dissipatively driving the system to a highly entangled steady state. Strikingly, for intermediate strength of the quantum fluctuations, we find that both unpredictability and quantum entanglement can coexist even in the long time limit. Finally, we show that the required many-body interactions for the cellular automaton embedding can be efficiently realized within a variational quantum simulator platform based on ultracold Rydberg atoms with high fidelity.
{© 2023 The Author(s). Published by IOP Publishing Ltd on behalf of the Institute of Physics and Deutsche Physikalische Gesellschaft}