On the absence of homogeneous scalar unitary cellular automata

Abstract Failure to find homogeneous scalar unitary cellular automata (CA) in one dimension led to consideration of only “approximately unitary” CA - which motivated our recent proof of a No-go Lemma in one dimension. In this note we extend the one dimensional result to prove the absence of nontrivial homogeneous scalar unitary CA on Euclidean lattices in any dimension.

• Publication year

  1996

• Venue

  Physics Letters A

• Publication date

  1996-04-12

• Fields of study

  Physics

• Identifiers
  DOI 10.1016/S0375-9601(96)00745-1arXiv quant-ph/9604011
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Computation theory of cellular automata

  1998cited by this paper
• Numerical solution of the Schrödinger equation using discrete kinetic theory.

  1996cited by this paper
• From quantum cellular automata to quantum lattice gases

  1996cited by this paper
• UNITARITY IN ONE DIMENSIONAL NONLINEAR QUANTUM CELLULAR AUTOMATA

  1996cited by this paper
• A decision procedure for well-formed linear quantum cellular automata

  1996cited by this paper
• A decision procedure for unitary linear quantum cellular automata

  1996cited by this paper
• Role of time in the sum-over-histories framework for gravity

  1994cited by this paper
• Lattice Boltzmann equation for quantum mechanics

  1993cited by this paper
• Cellular automata for quantum systems

  1993cited by this paper
• Nonlocal computation in quantum cellular automata.

  1993cited by this paper
• Weyl, Dirac, and Maxwell equations on a lattice as unitary cellular automata.

  1993cited by this paper
• Invertible cellular automata: a review

  1991cited by this paper
• From equilibrium spin models to probabilistic cellular automata

  1989cited by this paper
• Numerical Recipes: The Art of Scientific Computing

  1989cited by this paper
• A conservation law in quantum cellular automata

  1988cited by this paper
• Cellular automata and statistical mechanical models

  1987cited by this paper
• Feynman path integral for the Dirac equation

  1984cited by this paper
• Quantum Mechanics and Path Integrals

  1965cited by this paper

• Infinite reduction in absorbing time in quantum walks over classical ones

  2026cites this paper
• A hybrid quantum walk model unifying discrete and continuous quantum walks

  2025cites this paper
• Translation Groups for arbitrary Gauge Fields in Synthetic Crystals with real hopping amplitudes

  2025cites this paper
• Quantum Electrodynamics from Quantum Cellular Automata, and the Tension Between Symmetry, Locality, and Positive Energy

  2025cites this paper
• Lackadaisical discrete-time quantum walk on Johnson graph

  2024cites this paper
• Degenerate perturbation theory to quantum search

  2023cites this paper
• Bandit Algorithm Driven by a Classical Random Walk and a Quantum Walk

  2023cites this paper
• Fundamental Physics and Computation: The Computer-Theoretic Framework

  2022cites this paper
• Robust Quantum Walk Search

  2022cites this paper
• Fixed-point Quantum Walk Search

  2021cites this paper
• Implementing quantum gates using length-3 dynamic quantum walks

  2021cites this paper
• Robust quantum walk search without knowing the number of marked vertices

  2021cites this paper
• Search by lackadaisical quantum walk with symmetry breaking

  2021cites this paper
• Quantum cellular automata and quantum field theory in two spatial dimensions

  2020cites this paper
• Search on vertex-transitive graphs by lackadaisical quantum walk

  2020cites this paper
• Unstructured search by random and quantum walk

  2020cites this paper
• Quantum computation, Markov chains and combinatorial optimisation

  2020cites this paper
• Quantum field theory from a quantum cellular automaton in one spatial dimension and a no-go theorem in higher dimensions

  2020cites this paper
• On Quantum Extensions of Hydrodynamic Lattice Gas Automata

  2019cites this paper
• A review of Quantum Cellular Automata

  2019cites this paper
• Chirality from quantum walks without a quantum coin

  2019cites this paper
• Quantum walk search on Kronecker graphs

  2018cites this paper
• Quantum Walks on Quantum Cellular Automata Lattices: Towards a New Model for Quantum Computation

  2018cites this paper
• Inhibition of spreading in quantum random walks due to quenched Poisson-distributed disorder

  2018cites this paper
• Discrete-time quantum walks as fermions of lattice gauge theory

  2018cites this paper
• Discrete spacetime, quantum walks, and relativistic wave equations

  2018cites this paper
• Quantum walk search on the complete bipartite graph

  2018cites this paper
• Photonic quantum walks with four-dimensional coins

  2018cites this paper
• Building a quantum computer

  2017cites this paper
• Faster search by lackadaisical quantum walk

  2017cites this paper
• Insights from Quantum Information into Fundamental Physics

  2017cites this paper
• Oscillatory localization of quantum walks analyzed by classical electric circuits

  2016cites this paper
• Thermalization in Many-Particle Quantum Walks

  2016cites this paper
• Exceptional Configurations for Search by Szegedy's Quantum Walk

  2016cites this paper
• Exact simulation of coined quantum walks with the continuous-time model

  2016cites this paper
• Exact simulation of coined quantum walks with the continuous-time model

  2016cites this paper
• Equivalence of Szegedy’s and coined quantum walks

  2016cites this paper
• Manipulation et propagation de photons intriqués en fréquence et étude des marches aléatoires en fréquence

  2016cites this paper
• Staggered Quantum Walks on Graphs

  2016cites this paper
• Stationary States in Quantum Walk Search

  2016cites this paper
• Exceptional quantum walk search on the cycle

  2016cites this paper
• Simulating continuous-time Hamiltonian dynamics by way of a discrete-time quantum walk

  2016cites this paper
• Doubling the success of quantum walk search using internal-state measurements

  2015cites this paper
• Grover search with lackadaisical quantum walks

  2015cites this paper
• Spatial search by continuous-time quantum walk with multiple marked vertices

  2015cites this paper
• Correcting for potential barriers in quantum walk search

  2015cites this paper
• Quantum search with multiple walk steps per oracle query

  2015cites this paper
• Quantum walk search through potential barriers

  2015cites this paper
• Frameworks for Quantum Algorithms

  2014cites this paper
• Discrete spacetime and relativistic quantum particles

  2013cites this paper
• Spatial search via non-linear quantum walk

  2013cites this paper
• Symmetries in discrete time quantum walks on Cayley graphs

  2012cites this paper
• When is a Quantum Cellular Automaton (QCA) a Quantum Lattice Gas Automaton (QLGA)

  2012cites this paper
• Periodicity and perfect state transfer in quantum walks on variants of cycles

  2012cites this paper
• Periodicity and perfect state transfer in quantum walks on three families of graphs

  2012cites this paper
• Reflections in Hilbert Space

  2012cites this paper
• Time evolution of continuous-time quantum walks on dynamical percolation graphs

  2012cites this paper
• Symmetries in discrete time quantum walks on Cayley graphs

  2012cites this paper
• Application of quantum walks on graph structures to quantum computing

  2011cites this paper
• Quantum Query Complexity of Subgraph Containment with Constant-sized Certificates

  2011cites this paper
• Google in a Quantum Network

  2011cites this paper
• Maximal entanglement from quantum random walks

  2011cites this paper
• Where to quantum walk

  2011cites this paper
• A quantum random walk model for the (1 + 2) dimensional Dirac equation

  2011cites this paper
• Full revivals in 2D quantum walks

  2010cites this paper
• Pólya number of the continuous-time quantum walks

  2010cites this paper
• Maximal entanglement from quantum random walks

  2010cites this paper
• Discrete-time quantum walks on one-dimensional lattices

  2010cites this paper
• Discrete Time Quantum Lattice Systems

  2009cites this paper
• Recurrence in coined quantum walks

  2009cites this paper
• Quantum Cellular Automata

  2008cites this paper
• On the Relationship Between Continuous- and Discrete-Time Quantum Walk

  2008cites this paper
• The Quantum Complexity of Markov Chain Monte Carlo

  2008cites this paper
• Recurrence properties of unbiased coined quantum walks on infinite d -dimensional lattices

  2008cites this paper
• Quantum Walk Based Search Algorithms

  2008cites this paper
• Quantum walks and ground state problems

  2007cites this paper
• A path integral formula with applications to quantum random walks in Zd

  2007cites this paper
• Local unitary quantum cellular automata

  2007cites this paper
• Quantum Cellular Automata: Theory and Applications

  2007cites this paper
• A random walk approach to quantum algorithms

  2006cites this paper
• Se p 20 06 A random walk approach to quantum algorithms

  2006cites this paper
• Exploring scalar quantum walks on Cayley graphs

  2006cites this paper
• From Dirac to Diffusion: Decoherence in Quantum Lattice Gases

  2005cites this paper
• Quantum walks on Cayley graphs

  2005cites this paper
• Marches quantiques généralisées pour l'algorithmique quantique

  2005influential citation
• An algebraic study of unitary one dimensional quantum cellular automata

  2005cites this paper
• Spatial search and the Dirac equation

  2004cites this paper
• Random walk in generalized quantum theory

  2004cites this paper
• Decoherence in Discrete Quantum Walks

  2003cites this paper
• Controlling discrete quantum walks: coins and initial states

  2003cites this paper
• Continuous time quantum algorithms

  2003cites this paper
• Quantum walks on general graphs

  2003cites this paper
• Quantum random walks: An introductory overview

  2003cites this paper
• Lattice Boltzmann and quantum lattice gas representations of one-dimensional magnetohydrodynamic turbulence

  2003cites this paper
• Quantum Cellular Automata from Lattice Field Theories

  2003cites this paper
• Ja n 20 03 Decoherence in Discrete Quantum Walks

  2003cites this paper
• Quaternionic Madelung Transformation and Non-Abelian Fluid Dynamics

  2002cites this paper
• Quantum walks in optical lattices

  2002cites this paper
• Quantum computation for physical modeling

  2002cites this paper
• An Example of the Difference Between Quantum and Classical Random Walks

  2001cites this paper