Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Bulletin of the American Physical Society

Quantum cellular automata part II: Robust complexity under analog and digital evolution in 1- and 2-dimensions

Matthew Jones, Logan Edward Hillberry, Eric Jones, Mina Fasihi, Eliot Kapit, Lincoln D. Carr, P. Roushan, Jiang Zhang

Published Mar 16, 2021• 0 citations
OpenAlex

Related papers

Quantum cellular automata part I: Entanglement, physical complexity, and Goldilocks rules

Logan Edward Hillberry, M. Jones, David L. Vargas +6 more

Bulletin of the American Physical Society•Mar 16, 2021•0 citations

Nontrivial Quantum Cellular Automata in Higher Dimensions

Jeongwan Haah, Lukasz Fidkowski, Matthew B. Hastings

arXiv:1812.01625•Communications in Mathematical Physics•Nov 10, 2022•105 citations

Quantum Cellular Automata: Theory, Experimentation and Prospects

Massimo Macucci

IMPERIAL COLLEGE PRESS eBooks•Mar 1, 2006•34 citations

Quantum Cellular Automata, Black Hole Thermodynamics and the Laws of Quantum Complexity

Ruhi Shah, Jonathan Gorard

This paper introduces a new formalism for quantum cellular automata (QCAs), based on evolving tensor products of qubits using local unitary operators. It subsequently uses this formalism to analyze and validate several conjectures, stemming from a formal analogy between quantum computational complexity theory and classical thermodynamics, that have arisen recently in the context of black hole physics. In particular, the apparent resonance and thermalization effects present within such QCAs are investigated, and it is demonstrated that the expected exponential relationships between the quantum circuit complexity of the evolution operator, the classical entropy of the equilibrium QCA state, and the characteristic equilibration time of the QCA, all hold within this new model. Finally, a rigorous explanation for this empirical relationship is provided, as well as for the relationship with black hole thermodynamics, by drawing an explicit mathematical connection with the mean ergodic theorem, and the ergodicity of k-local quantum systems.

arXiv:1910.00578•Complex Systems•Dec 15, 2019•9 citations

Structures in quantum cellular automata

Gerhard Grössing, Anton Zeilinger

Physica B+C•Jul 1, 1988•31 citations

Nonlocal computation in quantum cellular automata

Siegfried Fussy, Gerhard Grössing, Herbert Schwabl +1 more

Quantum cellular automata (QCA) have been introduced [G. Gr\"ossing and A. Zeilinger, Complex Syst. 2, 197 (1988); 2, 611 (1988)] as n-dimensional arrays of discrete sites characterized by a complex number whose absolute square lies between 0 and 1 such that each site represents a quantum-mechanical probability amplitude. The evolutions of one-dimensional QCA with a local (i.e., nearest-neighbor) interaction and with periodic boundary conditions have been studied in some detail. In this paper we present a thorough mathematical analysis of one-dimensional QCA, and we particularly emphasize the effects of what we term nonlocal computation: because of the conservation of the total probability for each time step, information of the global array spread out over generally nonlocal distances must be conveyed for each time step to each local site via the normalization procedure. With the aid of a mathematical description of QCA evolution the following, previously observed phenomena can be explained: (i) the asymptotic appearance of plane-wave patterns after a characteristic transient phase, (ii) the dependence of the period of the patterns on the input parameters for both small and large values of the couplings between the sites, and (iii) the role of the initial values of the cells. Finally, the effects of nonlocal computation are made visible with the simulation of a ``double-slit-like'' experiment on a QCA grid.

Physical Review A•Nov 1, 1993•24 citations
This paper introduces a new formalism for quantum cellular automata (QCAs), based on evolving tensor products of qubits using local unitary operators. It subsequently uses this formalism to analyze and validate several conjectures, stemming from a formal analogy between quantum computational complexity theory and classical thermodynamics, that have arisen recently in the context of black hole physics. In particular, the apparent resonance and thermalization effects present within such QCAs are investigated, and it is demonstrated that the expected exponential relationships between the quantum circuit complexity of the evolution operator, the classical entropy of the equilibrium QCA state, and the characteristic equilibration time of the QCA, all hold within this new model. Finally, a rigorous explanation for this empirical relationship is provided, as well as for the relationship with black hole thermodynamics, by drawing an explicit mathematical connection with the mean ergodic theorem, and the ergodicity of k-local quantum systems.
Quantum cellular automata (QCA) have been introduced [G. Gr\"ossing and A. Zeilinger, Complex Syst. 2, 197 (1988); 2, 611 (1988)] as n-dimensional arrays of discrete sites characterized by a complex number whose absolute square lies between 0 and 1 such that each site represents a quantum-mechanical probability amplitude. The evolutions of one-dimensional QCA with a local (i.e., nearest-neighbor) interaction and with periodic boundary conditions have been studied in some detail. In this paper we present a thorough mathematical analysis of one-dimensional QCA, and we particularly emphasize the effects of what we term nonlocal computation: because of the conservation of the total probability for each time step, information of the global array spread out over generally nonlocal distances must be conveyed for each time step to each local site via the normalization procedure. With the aid of a mathematical description of QCA evolution the following, previously observed phenomena can be explained: (i) the asymptotic appearance of plane-wave patterns after a characteristic transient phase, (ii) the dependence of the period of the patterns on the input parameters for both small and large values of the couplings between the sites, and (iii) the role of the initial values of the cells. Finally, the effects of nonlocal computation are made visible with the simulation of a ``double-slit-like'' experiment on a QCA grid.