From quantum cellular automata to quantum lattice gases
arXiv:quant-ph/9604003 · doi:10.1007/BF02199356
Abstract
A natural architecture for nanoscale quantum computation is that of a quantum cellular automaton. Motivated by this observation, in this paper we begin an investigation of exactly unitary cellular automata. After proving that there can be no nontrivial, homogeneous, local, unitary, scalar cellular automaton in one dimension, we weaken the homogeneity condition and show that there are nontrivial, exactly unitary, partitioning cellular automata. We find a one parameter family of evolution rules which are best interpreted as those for a one particle quantum automaton. This model is naturally reformulated as a two component cellular automaton which we demonstrate to limit to the Dirac equation. We describe two generalizations of this automaton, the second of which, to multiple interacting particles, is the correct definition of a quantum lattice gas.
22 pages, plain TeX, 9 PostScript figures included with epsf.tex (ignore the under/overfull \vbox error messages); minor typographical corrections and journal reference added
References in corpus (2)
Cited by in corpus (327)
- Quantum random walks - an introductory overview
- Environment-Assisted Quantum Walks in Photosynthetic Energy Transfer
- Quantum walks: a comprehensive review
- Exponential algorithmic speedup by quantum walk
- Quantum algorithms for quantum chemistry and quantum materials science
- On the relationship between continuous- and discrete-time quantum walk
- Quantum Algorithms for Fermionic Simulations
- Continuous-Time Quantum Walks: Models for Coherent Transport on Complex Networks
- A Survey on Quantum Channel Capacities
- Search via Quantum Walk
- Controlling discrete quantum walks: coins and intitial states
- Low Depth Quantum Simulation of Electronic Structure
- Decoherence in quantum walks - a review
- Quantum Walks driven by many coins
- The quantum to classical transition for random walks
- Adiabatic Quantum Simulation of Quantum Chemistry
- One-Dimensional Three-State Quantum Walk
- Connecting the discrete and continuous-time quantum walks
- Localization of Two-Dimensional Quantum Walks
- Quantum random walks with decoherent coins
- A review of Quantum Cellular Automata
- Limit Theorem for Continuous-Time Quantum Walk on the Line
- Noisy intermediate-scale quantum computers
- Quantum Walks on a Random Environment
- Asymptotic evolution of quantum walks with random coin
- Using Quantum Computers for Quantum Simulation
- Quantum stochastic walks: A generalization of classical random walks and quantum walks
- Simulating Ising Spin Glasses on a Quantum Computer
- Topological phases and delocalization of quantum walks in random environments
- Google in a Quantum Network
- Relativistic quantum walks
- Relationship Between Quantum Walk and Relativistic Quantum Mechanics
- Thermodynamic uncertainty relation for general open quantum systems
- Polynomial-Time Simulation of Pairing Models on a Quantum Computer
- Quantum Simulation of Quantum Field Theory in the Light-Front Formulation
- Derivation of the Dirac Equation from Principles of Information Processing
- Quantum mechanics of lattice gas automata. I. One particle plane waves and potentials
- Limit distributions of two-dimensional quantum walks
- Quantum walks based on an interferometric analogy
- Grover Search with Lackadaisical Quantum Walks
- Quantum Walks in artificial electric and gravitational Fields
- Quantum Field as a quantum cellular automaton: the Dirac free evolution in one dimension
- Recurrence properties of unbiased coined quantum walks on infinite -dimensional lattices
- Quantum Walk with a time-dependent coin
- The Staggered Quantum Walk Model
- One- and two-dimensional quantum walks in arrays of optical traps
- Optical Cavity Implementations of the Quantum Walk
- One dimensional quantum walk with unitary noise
- The Dirac equation as a quantum walk: higher dimensions, observational convergence
- Quantum walks with random phase shifts
- Quantum Walks as simulators of neutrino oscillations in vacuum and matter
- Fast non-destructive parallel readout of neutral atom registers in optical potentials
- Quantum Random Walks do not need a Coin Toss
- Disordered quantum walk-induced localization of a Bose-Einstein condensate
- On the digraph of a unitary matrix
- Two-component Dirac-like Hamiltonian for generating quantum walk on one-, two- and three-dimensional lattices
- Nonlinear optical Galton board
- Quantum random walks with history dependence
- Free Dirac evolution as a quantum random walk
- Entanglement Dynamics in 1D Quantum Cellular Automata
- Discrete-time quantum walks: continuous limit and symmetries
- Quantum phase transition using quantum walks in an optical lattice
- Quantum Walks and discrete Gauge Theories
- Almost uniform sampling via quantum walks
- Quantum walks and non-Abelian discrete gauge theory
- Perfect state transfer by means of discrete-time quantum walk search algorithms on highly symmetric graphs
- Three routes to the exact asymptotics for the one-dimensional quantum walk
- Simulating Hadronic Physics on NISQ devices using Basis Light-Front Quantization
- Analysis of Absorbing Times of Quantum Walks
- Staggered Quantum Walks on Graphs
- Weak Limit of the 3-State Quantum Walk on the Line
- Local Unitary Quantum Cellular Automata
- Faster Search by Lackadaisical Quantum Walk
- The Random Walk in Generalized Quantum Theory
- Inhomogeneous Quantum Walks
- Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphs
- Simulating Anderson localization via a quantum walk on a one-dimensional lattice of superconducting qubits
- Quantum walks and Dirac cellular automata on a programmable trapped-ion quantum computer
- Quantumness of noisy quantum walks: a comparison between measurement-induced disturbance and quantum discord
- Discrete Lorentz covariance for Quantum Walks and Quantum Cellular Automata
- Distribution of chirality in the quantum walk: Markov process and entanglement
- Quantum lattice gases and their invariants
- A quantum cellular automaton for one-dimensional QED
- The Dirac equation as a quantum walk over the honeycomb and triangular lattices
- Foundation of Quantum Optimal Transport and Applications
- Limit distributions of three-state quantum walks: the role of coin eigenstates
- Parrondo's game using a discrete-time quantum walk
- Discrete-time quantum walk with feed-forward quantum coin
- Wigner formula of rotation matrices and quantum walks
- Theory of Quantum Games and Quantum Economic Behavior
- Quantum percolation and transition point of a directed discrete-time quantum walk
- Quantumness in decoherent quantum walk using measurement-induced disturbance
- Universal quantum computing using single-particle discrete-time quantum walk
- Electromagnetic lattice gauge invariance in two-dimensional discrete-time quantum walks
- Quantum Lattice Boltzmann is a quantum walk
- Random Time-Dependent Quantum Walks
- Propagating Quantum Walks: the origin of interference structures
- Dirac Quantum Cellular Automaton from Split-step Quantum Walk
- Quantum Cellular Automaton Theory of Light
- Coined Quantum Walks on Weighted Graphs
- Tailoring discrete quantum walk dynamics via extended initial conditions: Towards homogeneous probability distributions
- Directional correlations in quantum walks with two particles
- The Thirring quantum cellular automaton
- Quantum walks and gravitational waves
- Quantum walks with an anisotropic coin I: spectral theory
- Discrete Spacetime and Relativistic Quantum Particles
- Quantum Walk Search on the Complete Bipartite Graph
- Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
- Quantum cellular automata and free quantum field theory
- Quantum walk coherences on a dynamical percolation graph
- Emergence of Randomness and Arrow of Time in Quantum Walks
- Symmetry-noise interplay in quantum walk on an n-cycle
- Spatial entanglement using a quantum walk on a many-body system
- The Dirac Quantum Cellular Automaton in one dimension: Zitterbewegung and scattering from potential
- Spatial Search by Continuous-Time Quantum Walk with Multiple Marked Vertices
- Absorption problems for quantum walks in one dimension
- Localized quantum walks as secured quantum memory
- Relativistic effects in quantum walks: Klein's paradox and Zitterbewegung
- Simulating Dirac Hamiltonian in Curved Space-time by Split-step Quantum Walk
- Quantum Search with Multiple Walk Steps per Oracle Query
- Investigation of Continuous-Time Quantum Walk Via Modules of Bose-Mesner and Terwilliger Algebras
- Non-equilibrium absorbing state phase transitions in discrete-time quantum dynamics
- Dynamics and energy spectra of aperiodic discrete-time quantum walks
- On the Quantum Computational Complexity of the Ising Spin Glass Partition Function and of Knot Invariants
- Recurrences in three-state quantum walks on a plane
- Lattice-gas simulations of dynamical geometry in one dimension
- Equivalence of Szegedy's and Coined Quantum Walks
- Discrete-time quantum walk algorithm for ranking nodes on a network
- Quantum walks and quantum search on graphene lattices
- Quantum walks and orbital states of a Weyl particle
- Enhanced non-Markovian behavior in quantum walks with Markovian disorder
- The Grover search as a naturally occurring phenomenon
- Full-revivals in 2-D Quantum Walks
- Quantum mechanics of lattice gas automata. II. Boundary conditions and other inhomogeneities
- One-Dimensional Coinless Quantum Walks
- Equivalence between discrete quantum walk models in arbitrary topologies
- Special Relativity in a Discrete Quantum Universe
- Bounds on the dynamics of periodic quantum walks and emergence of the gapless and gapped Dirac equation
- When is a Quantum Cellular Automaton (QCA) a Quantum Lattice Gas Automaton (QLGA)?
- Quantum Query Complexity of Subgraph Containment with Constant-sized Certificates
- Optical implementability of the two-dimensional Quantum Walk
- Quantum Walks, Weyl equation and the Lorentz group
- Attractor-repeller pair of topological zero-modes in a nonlinear quantum walk
- Efficient and scalable quantum walk algorithms via the quantum Fourier transform
- Generalized eigenfunctions and scattering matrices for position-dependent quantum walks
- Electric quantum walks in two dimensions
- Pólya number of continuous-time quantum walks
- Relation between Random Walks and Quantum Walks
- Scattering model for quantum random walk on the hypercube
- Doubly-Special Relativity from Quantum Cellular Automata
- Quantum walks: decoherence and coin-flipping games
- Type-II Quantum Algorithms
- Decoupled Quantum Walks, models of the Klein-Gordon and wave equations
- Search by Lackadaisical Quantum Walk with Nonhomogeneous Weights
- Multi-bit quantum random number generator from a single qubit quantum walk
- Quantum walks in weak electric fields and Bloch oscillations
- Quantum walks with a one-dimensional coin
- Solutions of a two-particle interacting quantum walk
- Localization in Quantum Walks on a Honeycomb Network
- Simulating causal collapse models
- Pseudo Memory Effects, Majorization and Entropy in Quantum Random Walks
- Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk
- Discrete spacetime, quantum walks and relativistic wave equations
- Quantum cellular automata and quantum field theory in two spatial dimensions
- From curved spacetime to spacetime-dependent local unitaries over the honeycomb and triangular Quantum Walks
- Weyl, Dirac and Maxwell Quantum Cellular Automata: analitical solutions and phenomenological predictions of the Quantum Cellular Automata Theory of Free Fields
- Localization of the Grover walks on spidernets and free Meixner laws
- Connection Between Continuous and Discrete Time Quantum Walks on d-Dimensional Lattices; Extensions to General Graphs
- Free quantum field theory from quantum cellular automata: derivation of Weyl, Dirac and Maxwell quantum cellular automata
- Continuous Limit of Discrete Quantum Walks
- Discrete time quantum walks on percolation graphs
- Robust Quantum Walk Search Without Knowing the Number of Marked Vertices
- Analysis of Coined Quantum Walks with Renormalization
- Path-integral solution of the one-dimensional Dirac quantum cellular automaton
- N-dimensional alternate coined quantum walks from a dispersion relation perspective
- Multiple transitions between normal and hyperballistic diffusion in quantum walks with time-dependent jumps
- Simulation of Quantum Walks and Fast Mixing with Classical Processes
- Maximal entanglement from quantum random walks
- Continuous limits of linear and nonlinear quantum walks
- Asymptotic properties of the Dirac quantum cellular automaton
- Classical-like behavior in quantum walks with inhomogeneous, time-dependent coin operators
- Unitary Equivalence of Quantum Walks
- Continuous-time quantum walks on planar lattices and the role of the magnetic field
- Fractional recurrence in discrete-time quantum walk
- Dirac quantum walks on triangular and honeycomb lattices
- Discrete Feynman propagator for the Weyl quantum walk in 2+1 dimensions
- Quantum walk on distinguishable non-interacting many-particles and indistinguishable two-particle
- Quaternionic Madelung Transformation and Non-Abelian Fluid Dynamics
- Action Principles for Quantum Automata and Lorentz Invariance of Discrete Time Quantum Walks
- Quantum direct communication protocols using discrete-time quantum walk
- Discrete-time quantum walks on one-dimensional lattices
- Open Quantum Random Walks and Quantum Markov chains on Trees I: Phase transitions
- Quantum Walk with Jumps
- Detection of discrete spacetime by matter interferometry
- Exceptional Quantum Walk Search on the Cycle
- Quantum Walk Search on Kronecker Graphs
- Discrete-time quantum walks as fermions of lattice gauge theory
- Strongly trapped two-dimensional quantum walks
- Stationary States in Quantum Walk Search
- Accelerated quantum walk, two-particle entanglement generation and localization
- Quantum Walks and Reversible Cellular Automata
- Percolated quantum walks with a general shift operator: From trapping to transport
- Limit Theorems For Quantum Walks Associated with Hadamard Matrices
- Renormalization and Scaling in Quantum Walks
- Convergence of quantum random walks with decoherence
- Quantum field theory from a quantum cellular automaton in one spatial dimension and a no-go theorem in higher dimensions
- Edge states in a two-dimensional quantum walk with disorder
- Strategies for quantum-optimized construction of interpolating operators in classical simulations of lattice quantum field theories
- Fermionic and bosonic quantum field theories from quantum cellular automata in three spatial dimensions
- Dirac equation with ultraviolet cutoff and quantum walk
- Quantum walks, deformed relativity, and Hopf algebra symmetries
- Quantum circuits for the realization of equivalent forms of one-dimensional discrete-time quantum walks on near-term quantum hardware
- Decoherence on a two-dimensional quantum walk using four- and two-state particle
- Framework for discrete-time quantum walks and a symmetric walk on a binary tree
- Efficient Quantum Lattice Gas Automata
- Full Characterization of Oscillatory Localization of Quantum Walks
- Entanglement generation in spatially separated systems using quantum walk
- Oscillatory Localization of Quantum Walks Analyzed by Classical Electric Circuits
- Massless Dirac Equation from Fibonacci Discrete-Time Quantum Walk
- Scattering and perturbation theory for discrete-time dynamics
- Quantum search with interacting Bose-Einstein condensates
- Multi-qubit quantum computing using discrete-time quantum walks on closed graphs
- Evanescence in Coined Quantum Walks
- Quantum Walk on the Line through Potential Barriers
- Driven Discrete Time Quantum Walks
- Entanglement dynamics and phase transitions of the Floquet cluster spin chain
- Percolation assisted excitation transport in discrete-time quantum walks
- Quantum Optical Random Walk: Quantization Rules and Quantum Simulation of Asymptotics
- From gauge transformations to topology computation in quantum lattice gas automata
- Improved Upper Bounds for the Hitting Times of Quantum Walks
- Understanding and controlling N-dimensional quantum walks via dispersion relations. Application to the 2D and 3D Grover walks: Diabolical points and more
- The Lackadaisical Quantum Walker is NOT Lazy at all
- Quantum cellular automata without particles
- A Constructive Approach to Topological Invariants for One-dimensional Strictly Local Operators
- Probability distributions for Markov chains based quantum walks
- Inhibition of spreading in quantum random walks due to quenched Poisson-distributed disorder
- Quantum percolation in quasicrystals using continuous-time quantum walk
- Generic quantum walk using a coin-embedded shift operator
- Proposal of a quantum version of active particles via a nonunitary quantum walk
- Quantum walk based state transfer algorithms on the complete M-partite graph
- Quantum walker as a probe for its coin parameter
- Tree Search and Quantum Computation
- Unveiling and exemplifying the unitary equivalence of discrete time quantum walk models
- Zeno subspace in quantum-walk dynamics
- Green function approach for scattering quantum walks
- Asymptotics of Quantum Random Walk Driven by Optical Cavity
- Noise-enhanced quantum transport on a closed loop using quantum walks
- Correlated Markov Quantum Walks
- Mixing and Decoherence in Continuous-time quantum walks on long-range interacting cycles
- Multi-Dimensional Quantum Walks: a Playground of Dirac and Schrödinger Particles
- Complete classification of trapping coins for quantum walks on the 2D square lattice
- Quantum walk, entanglement and thermodynamic laws
- Ramsauer effect in one-dimensional quantum walk with multiple defects
- Bounds for mixing time of quantum walks on finite graphs
- Simple derivation of the Weyl and Dirac quantum cellular automata
- Statistical Properties of a Quantum Cellular Automaton
- Symmetry Protected Topological Phases and Majorana Mode in One-dimensional Quantum Walk with Boundary
- Tunable Aharonov-Bohm-like cages for quantum walks
- Nonlinear flip-flop quantum walks through potential barriers
- Quantization and Asymptotic Behaviour of Quantum Random Walk on Integers
- Grover Walks on a Line with Absorbing Boundaries
- Discrete time Dirac quantum walk in 3+1 dimensions
- Parrondo's paradox in quantum walks with inhomogeneous coins
- Quantum walk on a graph of spins: magnetism and entanglement
- Bandit Algorithm Driven by a Classical Random Walk and a Quantum Walk
- Quantum walks in polycyclic aromatic hydrocarbons
- Limit theorems and localization of three state quantum walks on a line defined by generalized Grover coins
- Quantum Walk Search through Potential Barriers
- Bounds on the Speedup in Quantum signalling
- Dynamical Triangulation Induced by Quantum Walk
- Robust Diabatic Quantum Search by Landau-Zener-Stückelberg Oscillations
- Doubling the Success of Quantum Walk Search Using Internal-State Measurements
- Spectral Properties of Quantum Walks on Rooted Binary Trees
- History Dependent Quantum Random Walks as Quantum Lattice Gas Automata
- Resonant quantum kicked rotor with two internal levels
- An algorithm to factorize quantum walks into shift and coin operations
- Quantum walk state transfer on a hypercube
- Scalar fermionic cellular automata on finite Cayley graphs
- Conditional limit measure of one-dimensional quantum walk with absorbing sink
- Suitable bases for quantum walks with Wigner coins
- Quantum Electrodynamics from Quantum Cellular Automata, and the Tension Between Symmetry, Locality and Positive Energy
- Phase transition of an open quantum walk
- Which number system is "best" for describing empirical reality?
- Discrete-Time Quantum Walks on Oriented Graphs
- Periodicity and Growth in a Lattice Gas with Dynamical Geometry
- Superdiffusivity of quantum walks: A Feynman sum-over-paths description
- Search by Lackadaisical Quantum Walk with Symmetry Breaking
- Borromean states in discrete-time quantum walks
- Ladder Operator Block-Encoding
- Logarithmic expansion of many-body wave packets in random potentials
- A massless interacting Fermionic Cellular Automaton exhibiting bound states
- Algebraic and geometric structures inside the Birkhoff polytope
- Symmetries of the Dirac quantum walk and emergence of the de Sitter group
- Two-particle coined-quantum walk with long-range interaction
- Continuous-time quantum walk on integer lattices and homogeneous trees
- Gravitationally induced entanglement dynamics between two quantum walkers
- Nonclassical oscillations in pre- and post-selected quantum walks
- Correlation effects in a discrete quantum random walk
- Clifford algebra from quantum automata and unitary Wilson fermions
- Analytical solutions for quantum walks on 1D chain with different shift operators
- Survival probability of the Grover walk on the ladder graph
- Polarization-path-frequency entanglement using interferometry and frequency shifters
- Monitored Recurrence of a One-parameter Family of Three-state Quantum Walks
- Quantum vs Classical Birth and Death Processes; Exactly Solvable Examples
- Entangled quantum cellular automata, physical complexity, and Goldilocks rules
- Adaptive Lattice Gas Algorithm: Classical and Quantum implementations
- Interference-induced localization in quantum random walk on clean cyclic graph
- Renormalization of Discrete-Time Quantum Walks with non-Grover Coins
- Localization and Fractality in Inhomogeneous Quantum Walks with Self-Duality
- Attractors and asymptotic dynamics of open discrete-time quantum walks on cycles
- Two-dimensional quantum central limit theorem by quantum walks
- Exciton propagation via quantum walks based on non-Hermitian coin flip operations
- Persistence of unvisited sites in quantum walks on a line
- Simulating Non Commutative Geometry with Quantum Walks
- Complementarity in quantum walks
- Experiments with Schrödinger Cellular Automata
- A limit theorem for a splitting distribution of a quantum walk
- Search and state transfer between hubs by quantum walks
- Recurrence in discrete-time quantum stochastic walks
- Two-particle Hadamard walk on dynamically percolated line and circle
- A simple model of quantum walk with a gap in distribution
- Designing non-equilibrium states of quantum matter through stochastic resetting
- On Quantum Semipermeable Barriers: Investigating Maxwell's Demon Toolbox
- Fully Quantum Lattice Gas Automata Building Blocks for Computational Basis State Encodings
- Reduced dynamics in quasi-Hermitian systems
- Quantum walks under superposition of causal order
- Characterization of anomalous diffusion in one-dimensional quantum walks