Is there a physically universal cellular automaton or Hamiltonian?

Dominik JanzingarXiv 2010 · OpenReview

TL;DR

This paper introduces the concept of "physical universality" for cellular automata (CAs) and Hamiltonians, defining it as the ability of a system's autonomous evolution to implement any transformation on a region, given appropriate initialization of its environment. The authors explore the implications of this concept for understanding the fundamental limits of control, computation, and thermodynamics, proposing new avenues for defining physical priors and complexity.

What Problem Does This Paper Address?

The paper tackles a fundamental question in physics and computation: can we consistently model physical systems and their control mechanisms within a unified framework? Current approaches often rely on an external "controller" or "measurement apparatus" that is treated differently from the system itself. This leads to an infinite hierarchy of controllers (who controls the controller?) and a fuzzy boundary between the system and its environment. The authors aim to define a notion of universality where the controller is an integral part of the physical system, allowing for a consistent shift of the system-environment boundary. This is crucial for understanding the thermodynamic costs associated with control and computation, especially the challenges of isolating systems and the reversibility of processes.

Methods

The core of the paper is the formalization of "physical universality" for classical cellular automata (CAs). This is achieved through a series of definitions:

  • Conditional State Preparation: The ability to prepare a specific state in a region by initializing its complement.
  • Unconditional State Preparation: A stronger version where the initialization of the complement is independent of the initial state of the region.
  • Universal Implementation of Bijections: The ability to implement any bijective transformation on a region by initializing its complement. This is presented as the primary definition of physical universality for CAs.

The paper then extends these concepts to quantum CAs and physically universal Hamiltonians, adapting the definitions to the quantum realm. It also explores connections to ergodic theory, defining concepts like measure-preserving dynamical systems (MDS) and ergodicity, and uses these to prove theorems about state preparation in ergodic CAs. Furthermore, the authors introduce novel definitions for "free energy of configurations," "free energy for preparation," and "energy requirements for computation," linking them to thermodynamic costs. Finally, they propose a "physical prior" and "physical complexity" that differ from traditional Kolmogorov complexity by incorporating the cost of environmental initialization and system isolation.

Datasets

Not discussed in the paper. The paper focuses on theoretical frameworks and definitions rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Shifting the System-Environment Boundary: The concept of physical universality allows for a consistent and flexible definition of what constitutes a "system" and its "environment," mirroring the Heisenberg cut in quantum mechanics. This is a significant conceptual shift from traditional control paradigms.
  • Thermodynamic Cost of Control: Physically universal CAs provide a natural framework to study the thermodynamic costs associated with implementing control operations. This includes the energy required for state preparation and the challenges of isolating systems from their environment.
  • Physical Prior and Complexity: The proposed "physical prior" and "physical complexity" offer a more realistic model of probability and complexity by accounting for the physical constraints of initialization and environmental interaction, moving beyond purely algorithmic descriptions.
  • Infinite Hierarchies Avoided: By treating the controller as part of the universal system, the paper circumvents the problem of infinite hierarchies of controllers and meta-controllers.
  • Ergodicity and State Preparation: The paper demonstrates that ergodicity in CAs is a necessary but not sufficient condition for physical universality, highlighting that even simple ergodic systems might not possess the required control capabilities.

Key Results

  • The paper formally defines "physical universality" for classical cellular automata and outlines its quantum and Hamiltonian counterparts.
  • It proves that ergodic CAs allow for conditional state preparation.
  • Theorems are presented showing that certain configurations are unstable and that no configuration can last forever in a physically universal CA.
  • The paper introduces definitions for free energy and energy requirements for computation and state preparation within the CA framework.
  • A "physical prior" is proposed, which is invariant under certain physical symmetries and accounts for environmental initialization costs, differing from Solomonoff's prior.
  • A "physical complexity" measure is defined, which aims to capture the cost of implementing processes, not just description length.
  • The paper formulates three open questions regarding the existence of physically universal CAs and quantum CAs, and the thermodynamic cost of cycles.

Limitations and Future Work

  • Existence of Physically Universal CAs/Hamiltonians: The paper poses the fundamental question of whether physically universal CAs and quantum CAs actually exist. While the definitions are provided, their existence is not proven.
  • Thermodynamic Cost of Cycles: The paper suggests that the cost of implementing repeated cycles grows linearly with the number of cycles, but acknowledges this is speculative and calls for further investigation into the thermodynamic cost of cycles.
  • Physical Prior and Complexity: The authors note that their proposed physical prior depends on time and that a time-independent version would be desirable. They also acknowledge that the full implications and properties of their physical complexity measure require further exploration.
  • Quantum Universality: The paper outlines the definition for quantum state preparation but leaves open the question of whether physically universal quantum CAs exist.
  • "More Physical" Priors: The authors suggest that a field-theoretic model could lead to a prior invariant under the full Lorentz group, indicating a direction for future research.
  • "Death State" for CAs: The paper notes that computationally universal CAs might have a "death state" that could prevent entropy influx, a feature not present in physically universal CAs, suggesting a difference in their modeling capabilities.

Summary updated

Abstract

It is known that both quantum and classical cellular automata (CA) exist that are computationally universal in the sense that they can simulate, after appropriate initialization, any quantum or classical computation, respectively. Here we introduce a different notion of universality: a CA is called physically universal if every transformation on any finite region can be (approximately) implemented by the autonomous time evolution of the system after the complement of the region has been initialized in an appropriate way. We pose the question of whether physically universal CAs exist. Such CAs would provide a model of the world where the boundary between a physical system and its controller can be consistently shifted, in analogy to the Heisenberg cut for the quantum measurement problem. We propose to study the thermodynamic cost of computation and control within such a model because implementing a cyclic process on a microsystem may require a non-cyclic process for its controller, whereas implementing a cyclic process on system and controller may require the implementation of a non-cyclic process on a "meta"-controller, and so on. Physically universal CAs avoid this infinite hierarchy of controllers and the cost of implementing cycles on a subsystem can be described by mixing properties of the CA dynamics. We define a physical prior on the CA configurations by applying the dynamics to an initial state where half of the CA is in the maximum entropy state and half of it is in the all-zero state (thus reflecting the fact that life requires non-equilibrium states like the boundary between a hold and a cold reservoir). As opposed to Solomonoff's prior, our prior does not only account for the Kolmogorov complexity but also for the cost of isolating the system during the state preparation if the preparation process is not robust.
BibTeX
@misc{janzing2010is,
  author = {Dominik Janzing},
  title = {{Is there a physically universal cellular automaton or Hamiltonian?}},
  year = {2010},
  eprint = {1009.1720},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1009.1720},
}

Loading related content...

Figure