An overview of quantum cellular automata
---
paper_title: Mathematical Foundations of Quantum Mechanics I

paper_content:

We have already used average values of position and momentum of a particle and seen that we can get the average value of an observable F [represented by an operator function \( \hat F\left( {\hat x,\hat p} \right) \)] in a state ψ by ::: ::: $$ \left\langle {\hat F} \right\rangle \equiv \bar F = \int {\psi ^* \hat F\psi dV} , $$ ::: ::: (4.1) ::: ::: where \( \hat F \) is the operator which is somehow related to F. In a first approach we are now going to deal with operators from a more general point of view. After this we shall determine a class of operators which is very important in quantum mechanics.
---
paper_title: A Six States Minimal Time Solution to the Firing Squad Synchronization Problem

paper_content:

Abstract From Balzer's work (1967), we know that the firing squad synchronization problem has a minimal-time solution with eight states. We show that such a solution exists with only six states. Our method is somewhat different from all previous ones: the initial line is iteratively divided in two inequal parts so that each new right part can be treated as the homothetical image of a shorter initial line.
---
paper_title: Environment-induced decoherence and the transition from quantum to classical

paper_content:

We study dynamics of quantum open systems, paying special attention to these aspects of their evolution which are relevant to the transition from quantum to classical. We begin with a discussion of the conditional dynamics of simple systems. The resulting models are straightforward but suffice to illustrate basic physical ideas behind quantum measurements and decoherence. To discuss decoherence and environment-induced superselection (einselection) in a more general setting, we sketch perturbative as well as exact derivations of several master equations valid for various systems. Using these equations we study einselection employing the general strategy of the predictability sieve. Assumptions that are usually made in the discussion of decoherence are critically reexamined along with the “standard lore” to which they lead. Restoration of quantum-classical correspondence in systems that are classically chaotic is discussed. The dynamical second law - it is shown - can be traced to the same phenomena that allow for the restoration of the correspondence principle in decohering chaotic systems (where it is otherwise lost on a very short time-scale). Quantum error correction is discussed as an example of an anti-decoherence strategy. Implications of decoherence and einselection for the interpretation of quantum theory are briefly pointed out.
---
paper_title: Theory of cellular automata: a survey

paper_content:

This article surveys some theoretical aspects of cellular automata CA research. In particular, we discuss classical and new results on reversibility, conservation laws, limit sets, decidability questions, universality and topological dynamics of CA. The selection of topics is by no means comprehensive and reflects the research interests of the author. The main goal is to provide a tutorial of CA theory to researchers in other branches of natural computing, to give a compact collection of known results with references to their proofs, and to suggest some open problems.
---
paper_title: Simulating physics with computers

paper_content:

On the program it says this is a keynote speech--and I don't know what a keynote speech is. I do not intend in any way to suggest what should be in this meeting as a keynote of the subjects or anything like that. I have my own things to say and to talk about and there's no implication that anybody needs to talk about the same thing or anything like it. So what I want to talk about is what Mike Dertouzos suggested that nobody would talk about. I want to talk about the problem of simulating physics with computers and I mean that in a specific way which I am going to explain. The reason for doing this is something that I learned about from Ed Fredkin, and my entire interest in the subject has been inspired by him. It has to do with learning something about the possibilities of computers, and also something about possibilities in physics. If we suppose that we know all the physical laws perfectly, of course we don't have to pay any attention to computers. It's interesting anyway to entertain oneself with the idea that we've got something to learn about physical laws; and if I take a relaxed view here (after all I 'm here and not at home) I'll admit that we don't understand everything. The first question is, What kind of computer are we going to use to simulate physics? Computer theory has been developed to a point where it realizes that it doesn't make any difference; when you get to a universal computer, it doesn't matter how it's manufactured, how it's actually made. Therefore my question is, Can physics be simulated by a universal computer? I would like to have the elements of this computer locally interconnected, and therefore sort of think about cellular automata as an example (but I don't want to force it). But I do want something involved with the
---
paper_title: Partitioned quantum cellular automata are intrinsically universal

paper_content:

There have been several non-axiomatic approaches taken to define Quantum Cellular Automata (QCA). Partitioned QCA (PQCA) are the most canonical of these non-axiomatic definitions. In this work we show that any QCA can be put into the form of a PQCA. Our construction reconciles all the non-axiomatic definitions of QCA, showing that they can all simulate one another, and hence that they are all equivalent to the axiomatic definition. This is achieved by defining generalised n-dimensional intrinsic simulation, which brings the computer science based concepts of simulation and universality closer to theoretical physics. The result is not only an important simplification of the QCA model, it also plays a key role in the identification of a minimal n-dimensional intrinsically universal QCA.
---
paper_title: Quantum mechanical computers

paper_content:

The physical limitations, due to quantum mechanics, on the functioning of computers are analyzed.
---
paper_title: A review of Quantum Cellular Automata

paper_content:

Discretizing spacetime is often a natural step towards modelling physical systems. For quantum systems, if we also demand a strict bound on the speed of information propagation, we get quantum cellular automata (QCAs). These originally arose as an alternative paradigm for quantum computation, though more recently they have been proposed as models of periodically driven (Floquet) quantum systems, where the index theory for QCAs has allowed the classification of chiral phases of two-dimensional Floquet systems. QCAs have also been suggested as a natural discretization of quantum field theory, and some interesting examples of QCAs have been introduced where a quantum field theory is recovered in the continuum limit. This review discusses all of these applications, as well as some other interesting results on the structure of quantum cellular automata, including the matrix product unitary approach and higher dimensional classifications.
---
paper_title: Entanglement dynamics in one-dimensional quantum cellular automata

paper_content:

Several proposed schemes for the physical realization of a quantum computer consist of qubits arranged in a cellular array. In the quantum circuit model of quantum computation, an often complex series of two-qubit gate operations is required between arbitrarily distant pairs of lattice qubits. An alternative model of quantum computation based on quantum cellular automata (QCA) requires only homogeneous local interactions that can be implemented in parallel. This would be a huge simplification in an actual experiment. We find some minimal physical requirements for the construction of unitary QCA in a one-dimensional Ising spin chain and demonstrate optimal pulse sequences for information transport and entanglement distribution. We also introduce the theory of nonunitary QCA and show by example that nonunitary rules can generate environment assisted entanglement.
---
paper_title: Intrinsically universal n-dimensional quantum cellular automata

paper_content:

Several non-axiomatic approaches have been taken to define Quantum Cellular Automata (QCA); Partitioned QCA (PQCA) are the most canonical. Here we show any QCA can be put into PQCA form. Our construction reconciles the non-axiomatic definitions of QCA, showing that they can all simulate one another, thus they are all equivalent to the axiomatic definition. A simple n-dimensional QCA capable of simulating all others to arbitrary precision is described, where the initial configuration and the evolution of any QCA can be encoded within the initial configuration of the intrinsically universal QCA. Several steps then correspond to one step of the simulated QCA, achieved via a non-trivial reduction of the problem to universality in quantum circuits. Results are formalised by defining generalised n-dimensional intrinsic simulation, preserving topology in that each cell of the simulated QCA is encoded as a group of adjacent cells in the universal QCA. Implications are discussed.
---
paper_title: Partitioned quantum cellular automata are intrinsically universal

paper_content:

There have been several non-axiomatic approaches taken to define Quantum Cellular Automata (QCA). Partitioned QCA (PQCA) are the most canonical of these non-axiomatic definitions. In this work we show that any QCA can be put into the form of a PQCA. Our construction reconciles all the non-axiomatic definitions of QCA, showing that they can all simulate one another, and hence that they are all equivalent to the axiomatic definition. This is achieved by defining generalised n-dimensional intrinsic simulation, which brings the computer science based concepts of simulation and universality closer to theoretical physics. The result is not only an important simplification of the QCA model, it also plays a key role in the identification of a minimal n-dimensional intrinsically universal QCA.
---
paper_title: On the Computing Power of One-Way Cellular Arrays

paper_content:

There are two simple models of parallel language recognizer: one-way cellular array (OCA) and one-way iterative array (OIA). For inputs of length n, both arrays consist of n identical finite-state machines (cells). The communication between cells is one-way, from left to right. The difference in the two models is in the manner in which the input is applied. For the OCA, the input is applied to the cells in parallel. For the OIA, the input is applied serially to the leftmost processor. An input string is accepted if the rightmost cell eventually enters an accepting state. We show that OCA's accept exactly the same class of languages as OIA's. It is relatively easy to show that OIA's can simulate OCA's. The difficult part is the converse, i.e., that OCA's can simulate OIA's. This is rather surprising since in an OIA, every cell of the array has access to each symbol of the input string, whereas in an OCA, the i-th cell can only access the first i symbols of the input. This result when combined with known results concerning OIA's answers some open questions concerning the computational complexity of OCA's. We also prove some new results concerning linear-time OCA's and OIA's. For example, we show: (1) linear-time OCA's are equivalent to 2n-time OIA's (note that 2n-time is optimal for OIA's); (2) the concatenation of a linear-time OCA language with a real-time (i.e., n-time) OCA language is a linear-time OCA language; (3) every semilinear language is a linear-time OCA language.
---
paper_title: When is a Quantum Cellular Automaton (QCA) a Quantum Lattice Gas Automaton (QLGA)?

paper_content:

Quantum cellular automata (QCA) are models of quantum computation of particular interest from the point of view of quantum simulation. Quantum lattice gas automata (QLGA - equivalently partitioned quantum cellular automata) represent an interesting subclass of QCA. QLGA have been more deeply analyzed than QCA, whereas general QCA are likely to capture a wider range of quantum behavior. Discriminating between QLGA and QCA is therefore an important question. In spite of much prior work, classifying which QCA are QLGA has remained an open problem. In the present paper we establish necessary and sufficient conditions for unbounded, finite QCA (finitely many active cells in a quiescent background) to be QLGA. We define a local condition that classifies those QCA that are QLGA, and we show that there are QCA that are not QLGA. We use a number of tools from functional analysis of separable Hilbert spaces and representation theory of associative algebras that enable us to treat QCA on finite but unbounded configu...
---
paper_title: Quantum cellular automata without particles

paper_content:

Quantum cellular automata (QCA) constitute space and time homogeneous discrete models for quantum field theories (QFTs). Although QFTs are defined without reference to particles, computations are done in terms of Feynman diagrams, which are explicitly interpreted in terms of interacting particles. Similarly, the easiest QCA to construct are quantum lattice gas automata (QLGA). A natural question then is, which QCA are not QLGA? Here we construct a nontrivial example of such a QCA; it provides a simple model in $1+1$ dimensions with no particle interpretation at the scale where the QCA dynamics are homogeneous.
---
paper_title: Insights from Quantum Information into Fundamental Physics

paper_content:

This thesis is split into two parts, which are united in the sense that they involve applying ideas from quantum information to fundamental physics. The first part is focused on examining discrete-time models in quantum computation (discrete-time quantum walks and quantum cellular automata) as discretized models of relativistic systems. One of the results here is a theorem demonstrating that a large class of discrete-time quantum walks have relativistic dynamics in the continuum limit. Additionally, the problem of fermion doubling for these models is investigated, and it is seen that the problem can be circumvented in two dimensional space. This was already known for one dimensional systems. Another result involves taking the limits of causal free field theories in discrete spacetime to recover continuum field theories, something that is not straightforward because of the nontrivial nature of the vacuum in quantum field theory. Additionally, it is shown that general systems of fermions evolving causally in discrete spacetime can be represented by quantum cellular automata, which makes them efficiently simulable by quantum computers. A related result is that quantum cellular automata composed of fermions are equivalent to regular quantum cellular automata. In the second part of this thesis, the focus is on the foundations of statistical physics. The main result of this part is a general bound on the time it takes a quantum system to effectively reach equilibrium. The discussion also includes a practical definition of equilibration that takes our measurement capabilities into account. Finally, the nature of the equilibrium state is also discussed, with a focus on initial state independence, which relates to the important question of when the equilibrium state is a Gibbs state.
---
paper_title: On the circuit depth of structurally reversible cellular automata

paper_content:

We study the family of structurally reversible cellular automata that use the (generalized) Margolus neighborhoods. We show that every reversible cellular automaton (RCA) can be embedded into the standard two layer Margolus neighborhood defined by two overlapping square partitions of the cellular space and two one-to-one local rules. The embedding allows step-by-step simulations. Then we investigate how many layers of one-to-one local rules are required in exact representations of RCA. We show how in the d-dimensional cellular space any consecutive d + 2 layers can be combined into d + 1 layers. This proves that no more than d + 1 layers are necessary. We demonstrate that in the two-dimensional case d = 2 the number d + 1 is optimal by providing an example of an RCA with three layers of local rules that cannot be expressed in two layers.
---
paper_title: Index theory of one dimensional quantum walks and cellular automata

paper_content:

If a one-dimensional quantum lattice system is subject to one step of a reversible discrete-time dynamics, it is intuitive that as much “quantum information” as moves into any given block of cells from the left, has to exit that block to the right. For two types of such systems — namely quantum walks and cellular automata — we make this intuition precise by defining an index, a quantity that measures the “net flow of quantum information” through the system. The index supplies a complete characterization of two properties of the discrete dynamics. First, two systems S 1, S 2 can be “pieced together”, in the sense that there is a system S which acts like S 1 in one region and like S 2 in some other region, if and only if S 1 and S 2 have the same index. Second, the index labels connected components of such systems: equality of the index is necessary and sufficient for the existence of a continuous deformation of S 1 into S 2. In the case of quantum walks, the index is integer-valued, whereas for cellular automata, it takes values in the group of positive rationals. In both cases, the map \({S \mapsto {\rm ind} S}\) is a group homomorphism if composition of the discrete dynamics is taken as the group law of the quantum systems. Systems with trivial index are precisely those which can be realized by partitioned unitaries, and the prototypes of systems with non-trivial index are shifts.
---
paper_title: Nontrivial Quantum Cellular Automata in Higher Dimensions

paper_content:

We construct a three-dimensional quantum cellular automaton (QCA), an automorphism of the local operator algebra on a lattice of qubits, which disentangles the ground state of the Walker-Wang three fermion model. We show that if this QCA can be realized by a quantum circuit of constant depth, then there exists a two-dimensional commuting projector Hamiltonian which realizes the three fermion topological order which is widely believed not to be possible. We conjecture in accordance with this belief that this QCA is not a quantum circuit of constant depth, and we provide two further pieces of evidence to support the conjecture. We show that this QCA maps every local Pauli operator to a local Pauli operator, but is not a Clifford circuit of constant depth. Further, we show that if the three-dimensional QCA can be realized by a quantum circuit of constant depth, then there exists a two-dimensional QCA acting on fermionic degrees of freedom which cannot be realized by a quantum circuit of constant depth; i.e., we prove the existence of a nontrivial QCA in either three or two dimensions. The square of our three-dimensional QCA can be realized by a quantum circuit of constant depth, and this suggests the existence of a $\mathbb{Z}_2$ invariant of a QCA in higher dimensions, totally distinct from the classification by positive rationals (i.e., by one integer index for each prime) in one dimension. In an appendix, unrelated to the main body of this paper, we give a fermionic generalization of a result of Bravyi and Vyalyi on ground states of 2-local commuting Hamiltonians.
---
paper_title: Classification of Quantum Cellular Automata

paper_content:

There exists an index theory to classify strictly local quantum cellular automata in one dimension. We consider two classification questions. First, we study to what extent this index theory can be applied in higher dimensions via dimensional reduction, finding a classification by the first homology group of the manifold modulo torsion. Second, in two dimensions, we show that an extension of this index theory (including torsion) fully classifies quantum cellular automata, at least in the absence of fermionic degrees of freedom. This complete classification in one and two dimensions by index theory is not expected to extend to higher dimensions due to recent evidence of a nontrivial automaton in three dimensions. Finally, we discuss some group theoretical aspects of the classification of quantum cellular automata and consider these automata on higher dimensional real projective spaces.
---
paper_title: Applying causality principles to the axiomatization of probabilistic cellular automata

paper_content:

Cellular automata (CAs) consist of an bi-infinite array of identical cells, each of which may take one of a finite number of possible sstates. The entire array evolves in discrete time steps by iterating a global evolution G. Further, this global evolution G is required to be shift-invariant (it acts the same everywhere) and causal (information cannot be transmitted faster than some fixed number of cells per time step). At least in the classical [7], reversible [11] and quantum cases [1], these two top-down axiomatic conditions are sufficient to entail more bottom-up, operational descriptions of G. We investigate whether the same is true in the probabilistic case.
---
paper_title: Representation of reversible cellular automata with block permutations

paper_content:

We demonstrate the structural invertibility of all reversible one- and two-dimensional cellular automata. More precisely, we prove that every reversible two-dimensional cellular automaton can be expressed as a combination of four block permutations, and some shift-like mappings. Block permutations are very simple functions that uniformly divide configurations into rectangular regions of equal size and apply a fixed permutation on all regions.
---
paper_title: Clifford Quantum Cellular Automata: Trivial group in 2D and Witt group in 3D

paper_content:

We study locality preserving automorphisms of operator algebras on lattices (QCA), specializing in those that are translation invariant and map every prime $p$-dimensional Pauli matrix to a tensor product of Pauli matrices (Clifford). If $\mathfrak C(D,p)$ denotes the group of translation invariant Clifford QCAs modulo Clifford circuits and shifts on a uniform $D$-dimensional lattice of $p$-dimensional qudits, we prove that $\mathfrak C(D,p)$ has exponent 2 or 4 depending on the prime $p$, that $\mathfrak C(D=2,p) = 0$, and that $\mathfrak C(D = 3, p)$ contains the Witt group of the finite field $\mathbb F_p$. The nontrivial examples in $D=3$ are found by disentangling the ground state of a commuting Pauli Hamiltonian which is constructed by coupling layers of prime dimensional toric codes such that an exposed surface has an anomalous topological order that is not realizable by commuting Pauli Hamiltonians strictly in two dimensions. ::: In an appendix independent of the main body of the paper, we revisit a recent theorem of Freedman and Hastings that any two-dimensional QCA, which is not necessarily Clifford or translation invariant, is a constant depth quantum circuit followed by a shift. We give a more direct proof of the theorem without using any ancillas.
---
paper_title: A quantum cellular automaton for one-dimensional QED

paper_content:

We propose a discrete spacetime formulation of quantum electrodynamics in one dimension (a.k.a the Schwinger model) in terms of quantum cellular automata, i.e. translationally invariant circuits of local quantum gates. These have exact gauge covariance and a maximum speed of information propagation. In this picture, the interacting quantum field theory is defined as a “convergent” sequence of quantum cellular automata, parameterized by the spacetime lattice spacing—encompassing the notions of continuum limit and renormalization, and at the same time providing a quantum simulation algorithm for the dynamics.
---
paper_title: The Feynman problem and Fermionic entanglement: Fermionic theory versus qubit theory

paper_content:

The present paper is both a review on the Feynman problem, and an original research presentation on the relations between Fermionic theories and qubits theories, both regarded in the novel framework of operational probabilistic theories. The most relevant results about the Feynman problem of simulating Fermions with qubits are reviewed, and in the light of the new original results the problem is solved. The answer is twofold. On the computational side the two theories are equivalent, as shown by Bravyi and Kitaev (Ann. Phys. 298.1 (2002): 210-226). On the operational side the quantum theory of qubits and the quantum theory of Fermions are different, mostly in the notion of locality, with striking consequences on entanglement. Thus the emulation does not respect locality, as it was suspected by Feynman (Int. J. Theor. Phys. 21.6 (1982): 467-488).
---
paper_title: Matrix Product Unitaries: Structure, Symmetries, and Topological Invariants

paper_content:

Matrix Product Vectors form the appropriate framework to study and classify one-dimensional quantum systems. In this work, we develop the structure theory of Matrix Product Unitary operators (MPUs) which appear e.g. in the description of time evolutions of one-dimensional systems. We prove that all MPUs have a strict causal cone, making them Quantum Cellular Automata (QCAs), and derive a canonical form for MPUs which relates different MPU representations of the same unitary through a local gauge. We use this canonical form to prove an Index Theorem for MPUs which gives the precise conditions under which two MPUs are adiabatically connected, providing an alternative derivation to that of [Commun. Math. Phys. 310, 419 (2012), arXiv:0910.3675] for QCAs. We also discuss the effect of symmetries on the MPU classification. In particular, we characterize the tensors corresponding to MPU that are invariant under conjugation, time reversal, or transposition. In the first case, we give a full characterization of all equivalence classes. Finally, we give several examples of MPU possessing different symmetries.
---
paper_title: On the circuit depth of structurally reversible cellular automata

paper_content:

We study the family of structurally reversible cellular automata that use the (generalized) Margolus neighborhoods. We show that every reversible cellular automaton (RCA) can be embedded into the standard two layer Margolus neighborhood defined by two overlapping square partitions of the cellular space and two one-to-one local rules. The embedding allows step-by-step simulations. Then we investigate how many layers of one-to-one local rules are required in exact representations of RCA. We show how in the d-dimensional cellular space any consecutive d + 2 layers can be combined into d + 1 layers. This proves that no more than d + 1 layers are necessary. We demonstrate that in the two-dimensional case d = 2 the number d + 1 is optimal by providing an example of an RCA with three layers of local rules that cannot be expressed in two layers.
---
paper_title: Partitioned quantum cellular automata are intrinsically universal

paper_content:

There have been several non-axiomatic approaches taken to define Quantum Cellular Automata (QCA). Partitioned QCA (PQCA) are the most canonical of these non-axiomatic definitions. In this work we show that any QCA can be put into the form of a PQCA. Our construction reconciles all the non-axiomatic definitions of QCA, showing that they can all simulate one another, and hence that they are all equivalent to the axiomatic definition. This is achieved by defining generalised n-dimensional intrinsic simulation, which brings the computer science based concepts of simulation and universality closer to theoretical physics. The result is not only an important simplification of the QCA model, it also plays a key role in the identification of a minimal n-dimensional intrinsically universal QCA.
---
paper_title: On one-dimensional quantum cellular automata

paper_content:

Since Richard Feynman introduced the notion of quantum computation in 1982, various models of "quantum computers" have been proposed (R. Feynman, 1992). These models include quantum Turing machines and quantum circuits. We define another quantum computational model, one dimensional quantum cellular automata, and demonstrate that any quantum Turing machine can be efficiently simulated by a one dimensional quantum cellular automaton with constant slowdown. This can be accomplished by consideration of a restricted class of one dimensional quantum cellular automata called one dimensional partitioned quantum cellular automata. We also show that any one dimensional partitioned quantum cellular automaton can be simulated by a quantum Turing machine with linear slowdown, but the problem of efficiently simulating an arbitrary one dimensional quantum cellular automaton with a quantum Turing machine is left open. From this discussion, some interesting facts concerning these models are easily deduced.
---
paper_title: Generalized partitioned quantum cellular automata and quantization of classical CA

paper_content:

In this paper, in order to investigate natural transformations from discrete CA to QCA, we introduce a new formulation of finite cyclic QCA and generalized notion of partitioned QCA. According to the formulations, we demonstrate the condition of local transition functions, which induce a global transition of well-formed QCA. Following the results, extending a natural correspondence of classical cells and quantum cells to the correspondence of classical CA and QCA, we have the condition of classical CA such that CA generated by quantumization of its cells is well-formed QCA. Finally we report some results of computer simulations of quantumization of classical CA.
---
paper_title: Intrinsically universal one-dimensional quantum cellular automata in two flavours

paper_content:

We give a one-dimensional quantum cellular automaton (QCA) capable of simulating all others. By this we mean that the initial configuration and the local transition rule of any onedimensional QCA can be encoded within the initial configuration of the universal QCA. Several steps of the universal QCA will then correspond to one step of the simulated QCA. The simulation preserves the topology in the sense that each cell of the simulated QCA is encoded as a group of adjacent cells in the universal QCA. The encoding is linear and hence does not carry any of the cost of the computation. We do this in two flavours: a weak one which requires an infinite but periodic initial configuration and a strong one which needs only a finite initial configuration.
---
paper_title: Church's Thesis and Principles for Mechanisms

paper_content:

After a brief review of Church's thesis and Godel's objection to it, it is argued that Turing's analysis of computation by a human being does not apply directly to mechanical devices. A set-theoretic form of description for discrete deterministic machines is elaborated and four principles (or constraints) are enunciated, which, it is argued, any such machine must satisfy. The most important of these, called “the principle of local causality” rejects the possibility of instantaneous action at a distance. Although the principles are justified by an appeal to the geometry of space-time, the formulation is quite abstract, and can be applied to all kinds of automata and to algebraic systems. It is proved that if a device satisfies the principles then its successive states form a computable sequence. Counter-examples are constructed which show that if the principles be weakened in almost any way, then there will be devices which satisfy the weakened principles and which can calculate any number-theoretic function.
---
paper_title: More Really is Different

paper_content:

In 1972, P.W.Anderson suggested that `More is Different', meaning that complex physical systems may exhibit behavior that cannot be understood only in terms of the laws governing their microscopic constituents. We strengthen this claim by proving that many macroscopic observable properties of a simple class of physical systems (the infinite periodic Ising lattice) cannot in general be derived from a microscopic description. This provides evidence that emergent behavior occurs in such systems, and indicates that even if a `theory of everything' governing all microscopic interactions were discovered, the understanding of macroscopic order is likely to require additional insights.
---
paper_title: On one-dimensional quantum cellular automata

paper_content:

Since Richard Feynman introduced the notion of quantum computation in 1982, various models of "quantum computers" have been proposed (R. Feynman, 1992). These models include quantum Turing machines and quantum circuits. We define another quantum computational model, one dimensional quantum cellular automata, and demonstrate that any quantum Turing machine can be efficiently simulated by a one dimensional quantum cellular automaton with constant slowdown. This can be accomplished by consideration of a restricted class of one dimensional quantum cellular automata called one dimensional partitioned quantum cellular automata. We also show that any one dimensional partitioned quantum cellular automaton can be simulated by a quantum Turing machine with linear slowdown, but the problem of efficiently simulating an arbitrary one dimensional quantum cellular automaton with a quantum Turing machine is left open. From this discussion, some interesting facts concerning these models are easily deduced.
---
paper_title: Entanglement Generation of Clifford Quantum Cellular Automata

paper_content:

Clifford quantum cellular automata (CQCAs) are a special kind of quantum cellular automata (QCAs) that incorporate Clifford group operations for the time evolution. Despite being classically simulable, they can be used as basic building blocks for universal quantum computation. This is due to the connection to translation-invariant stabilizer states and their entanglement properties. We will give a self-contained introduction to CQCAs and investigate the generation of entanglement under CQCA action. Furthermore, we will discuss finite configurations and applications of CQCAs.
---
paper_title: Quantum walks and non-Abelian discrete gauge theory

paper_content:

A new family of discrete-time quantum walks (DTQWs) on the line with an exact discrete $U(N)$ gauge invariance is introduced. It is shown that the continuous limit of these DTQWs, when it exists, coincides with the dynamics of a Dirac fermion coupled to usual $U(N)$ gauge fields in $2D$ spacetime. A discrete generalization of the usual $U(N)$ curvature is also constructed. An alternate interpretation of these results in terms of superimposed $U(1)$ Maxwell fields and $SU(N)$ gauge fields is discussed in the Appendix. Numerical simulations are also presented, which explore the convergence of the DTQWs towards their continuous limit and which also compare the DTQWs with classical (i.e. non-quantum) motions in classical $SU(2)$ fields. The results presented in this article constitute a first step towards quantum simulations of generic Yang-Mills gauge theories through DTQWs.
---
paper_title: Quantum Walks With Neutral Atoms: Quantum Interference Effects of One and Two Particles

paper_content:

We report on the state of the art of quantum walk experiments with neutral atoms in state-dependent optical lattices. We demonstrate a novel state-dependent transport technique enabling the control of two spin-selective sublattices in a fully independent fashion. This transport technique allowed us to carry out a test of single-particle quantum interference based on the violation of the Leggett-Garg inequality and, more recently, to probe two-particle quantum interference effects with neutral atoms cooled into the motional ground state. These experiments lay the groundwork for the study of discrete-time quantum walks of strongly interacting, indistinguishable particles to demonstrate quantum cellular automata of neutral atoms.
---
paper_title: Supersonic quantum communication

paper_content:

When locally exciting a quantum lattice model, the excitation will propagate through the lattice. The effect is responsible for a wealth of non-equilibrium phenomena, and has been exploited to transmit quantum information through spin chains. It is a commonly expressed belief that for local Hamiltonians, any such propagation happens at a finite"speed of sound". Indeed, the Lieb-Robinson theorem states that in spin models, all effects caused by a perturbation are limited to a causal cone defined by a constant speed, up to exponentially small corrections. In this work we show that for translationally invariant bosonic models with nearest-neighbor interactions, this belief is incorrect: We prove that one can encounter excitations which accelerate under the natural dynamics of the lattice and allow for reliable transmission of information faster than any finite speed of sound. The effect is only limited by the model's range of validity (eventually by relativity). It also implies that in non-equilibrium dynamics of strongly correlated bosonic models far-away regions may become quickly entangled, suggesting that their simulation may be much harder than that of spin chains even in the low energy sector.
---
paper_title: Quantum-cellular-automata pseudorandom maps

paper_content:

Quantum computation based on quantum-cellular automata (QCA) can greatly reduce the control and precision necessary for experimental implementations of quantum information processing. A QCA system consists of a few species of qubits in which all qubits of a species evolve in parallel. We show that, in spite of its inherent constraints, a QCA system can be used to study complex quantum dynamics. To this aim, we demonstrate scalable operations on a QCA system that fulfill statistical criteria of randomness and explore which criteria of randomness can be fulfilled by operators from various QCA architectures. Other means of realizing random operators with only a few independent operators are also discussed.
---
paper_title: Decoupled Quantum Walks, models of the Klein-Gordon and wave equations

paper_content:

Decoupling a vectorial PDE consists in solving the system for each component, thereby obtaining scalar PDEs that prescribe the evolution of each component independently. We present a general approach to decoupling of Quantum Walks, again defined as a procedure to obtain an evolution law for each scalar component of the Quantum Walks, in such a way that it does not depend on the other components. In particular, the method is applied to show the relation between the Dirac (or Weyl) Quantum Walk in three space dimensions with (or without) mass term, and the Klein-Gordon (or wave) equation.
---
paper_title: Quantum State Transfer through Noisy Quantum Cellular Automata

paper_content:

We model the transport of an unknown quantum state on one dimensional qubit lattices by means of a quantum cellular automata evolution. We do this by first introducing a class of discrete noisy dynamics, in the first excitation sector, in which a wide group of classical stochastic dynamics is embedded within the more general formalism of quantum operations. We then extend the Hilbert space of the system to accommodate a global vacuum state, thus allowing for the transport of initial on-site coherences besides excitations, and determine the dynamical constraints that define the class of noisy quantum cellular automata in this subspace. We then study the transport performance through numerical simulations, showing that for some instances of the dynamics perfect quantum state transfer is attainable. Our approach provides one with a natural description of both unitary and open quantum evolutions, where the homogeneity and locality of interactions allow one to take into account several forms of quantum noise in a plausible scenario.
---
paper_title: Dirac Quantum Cellular Automaton from Split-step Quantum Walk

paper_content:

Simulations of one quantum system by an other has an implication in realization of quantum machine that can imitate any quantum system and solve problems that are not accessible to classical computers. One of the approach to engineer quantum simulations is to discretize the space-time degree of freedom in quantum dynamics and define the quantum cellular automata (QCA), a local unitary update rule on a lattice. Different models of QCA are constructed using set of conditions which are not unique and are not always in implementable configuration on any other system. Dirac Cellular Automata (DCA) is one such model constructed for Dirac Hamiltonian (DH) in free quantum field theory. Here, starting from a split-step discrete-time quantum walk (QW) which is uniquely defined for experimental implementation, we recover the DCA along with all the fine oscillations in position space and bridge the missing connection between DH-DCA-QW. We will present the contribution of the parameters resulting in the fine oscillations on the Zitterbewegung frequency and entanglement. The tuneability of the evolution parameters demonstrated in experimental implementation of QW will establish it as an efficient tool to design quantum simulator and approach quantum field theory from principles of quantum information theory.
---
paper_title: Ultracold quantum gases in optical lattices

paper_content:

Artificial crystals of light, consisting of hundreds of thousands of optical microtraps, are routinely created by interfering optical laser beams. These so-called optical lattices act as versatile potential landscapes to trap ultracold quantum gases of bosons and fermions. They form powerful model systems of quantum many-body systems in periodic potentials for probing nonlinear wave dynamics and strongly correlated quantum phases, building fundamental quantum gates or observing Fermi surfaces in periodic potentials. Optical lattices represent a fast-paced modern and interdisciplinary field of research.
---
paper_title: On the structure of Clifford quantum cellular automata

paper_content:

We study reversible quantum cellular automata with the restriction that these are also Clifford operations. This means that tensor products of Pauli operators (or discrete Weyl operators) are mapped to tensor products of Pauli operators. Therefore Clifford quantum cellular automata are induced by symplectic cellular automata in phase space. We characterize these symplectic cellular automata and find that all possible local rules must be, up to some global shift, reflection invariant with respect to the origin. In the one dimensional case we also find that every uniquely determined and translationally invariant stabilizer state can be prepared from a product state by a single Clifford cellular automaton timestep, thereby characterizing these class of stabilizer states, and we show that all 1D Clifford quantum cellular automata are generated by a few elementary operations. We also show that the correspondence between translationally invariant stabilizer states and translationally invariant Clifford operations holds for periodic boundary conditions.
---
paper_title: Propagation of quantum walks in electric fields.

paper_content:

We study one-dimensional quantum walks in a homogeneous electric field. The field is given by a phase which depends linearly on position and is applied after each step. The long time propagation properties of this system, such as revivals, ballistic expansion and Anderson localization, depend very sensitively on the value of the electric field $\Phi$, e.g., on whether $\Phi/(2\pi)$ is rational or irrational. We relate these properties to the continued fraction expansion of the field. When the field is given only with finite accuracy, the beginning of the expansion allows analogous conclusions about the behavior on finite time scales.
---
paper_title: Quantum Walks as simulators of neutrino oscillations in vacuum and matter

paper_content:

We analyze the simulation of Dirac neutrino oscillations using quantum walks, both in vacuum and in matter. We show that this simulation, in the continuum limit, reproduces a set of coupled Dirac equations that describe neutrino flavor oscillations, and we make use of this to establish a connection with neutrino phenomenology, thus allowing to fix the parameters of the simulation for a given neutrino experiment. We also analyze how matter effects for neutrino propagation can be simulated in the quantum walk. In this way, important features, such as the MSW effect, can be incorporated. Thus, the simulation of neutrino oscillations with the help of quantum walks might be useful to explore these effects in extreme conditions, such as the solar interior or supernovae, in a complementary way to existing experiments.
---
paper_title: Discrete-time quantum walks as fermions of lattice gauge theory

paper_content:

It is shown that discrete-time quantum walks can be used to digitize, i.e., to time discretize fermionic models of continuous-time lattice gauge theory. The resulting discrete-time dynamics is thus not only manifestly unitary, but also ultralocal, i.e. the particle's speed is upper bounded, as in standard relativistic quantum field theories. The lattice chiral symmetry of staggered fermions, which corresponds to a translational invariance, is lost after the requirement of ultralocality of the evolution; this fact is an instance of Meyer's 1996 no-go lemma stating that no non-trivial one-dimensional scalar quantum cellular automaton can be translationally invariant [1]. All results are presented in a single-particle framework and for a (1+1)-dimensional spacetime.
---
paper_title: Doubly-Special Relativity from Quantum Cellular Automata

paper_content:

It is shown how a doubly special relativity model can emerge from a quantum cellular automaton description of the evolution of countably many interacting quantum systems. We consider a one-dimensional automaton that spawns the Dirac evolution in the relativistic limit of small wave vectors and masses (in Planck units). The assumption of invariance of dispersion relations for boosted observers leads to a non-linear representation of the Lorentz group on the -space, with an additional invariant given by the wave vector . The space-time reconstructed from the -space is intrinsically quantum, and exhibits the phenomenon of relative locality.
---
paper_title: Molecular binding in interacting quantum walks

paper_content:

We show that the presence of an interaction in the quantum walk of two atoms leads to the formation of a stable compound, a molecular state. The wave function of the molecule decays exponentially in the relative position of the two atoms; hence it constitutes a true bound state. Furthermore, for a certain class of interactions, we develop an effective theory and find that the dynamics of the molecule is described by a quantum walk in its own right. We propose a setup for the experimental realization as well as sketch the possibility to observe quasi-particle effects in quantum many-body systems.
---
paper_title: Quantum walking in curved spacetime: $(3+1)$ dimensions, and beyond

paper_content:

A discrete-time Quantum Walk (QW) is essentially an operator driving the evolution of a single particle on the lattice, through local unitaries. Some QWs admit a continuum limit, leading to familiar PDEs (e.g. the Dirac equation). Recently it was discovered that prior grouping and encoding allows for more general continuum limit equations (e.g. the Dirac equation in $(1+1)$ curved spacetime). In this paper, we extend these results to arbitrary space dimension and internal degree of freedom. We recover an entire class of PDEs encompassing the massive Dirac equation in $(3+1)$ curved spacetime. This means that the metric field can be represented by a field of local unitaries over a lattice.
---
paper_title: Disordered Quantum Walks in one lattice dimension

paper_content:

We study a spin-12-particle moving on a one-dimensional lattice subject to disorder induced by a random, space-dependent quantum coin. The discrete time evolution is given by a family of random unitary quantum walk operators, where the shift operation is assumed to be deterministic. Each coin is an independent identically distributed random variable with values in the group of two-dimensional unitary matrices. We derive sufficient conditions on the probability distribution of the coins such that the system exhibits dynamical localization. Put differently, the tunneling probability between two lattice sites decays rapidly for almost all choices of random coins and after arbitrary many time steps with increasing distance. Our findings imply that this effect takes place if the coin is chosen at random from the Haar measure, or some measure continuous with respect to it, but also for a class of discrete probability measures which support consists of two coins, one of them being the Hadamard coin.
---
paper_title: Quantum Field as a quantum cellular automaton: the Dirac free evolution in one dimension

paper_content:

We present a quantum cellular automaton model in one space-dimension which has the Dirac equation as emergent. This model, a discrete-time and causal unitary evolution of a lattice of quantum systems, is derived from the assumptions of homogeneity, parity and time-reversal invariance. The comparison between the automaton and the Dirac evolutions is rigorously set as a discrimination problem between unitary channels. We derive an exact lower bound for the probability of error in the discrimination as an explicit function of the mass, the number and the momentum of the particles, and the duration of the evolution. Computing this bound with experimentally achievable values, we see that in that regime the QCA model cannot be discriminated from the usual Dirac evolution. Finally, we show that the evolution of one-particle states with narrow-band in momentum can be effi- ciently simulated by a dispersive differential equation for any regime. This analysis allows for a comparison with the dynamics of wave-packets as it is described by the usual Dirac equation. This paper is a first step in exploring the idea that quantum field theory could be grounded on a more fundamental quantum cellular automaton model and that physical dynamics could emerge from quantum information processing. In this framework, the discretization is a central ingredient and not only a tool for performing non-perturbative calculation as in lattice gauge theory. The automaton model, endowed with a precise notion of local observables and a full probabilistic interpretation, could lead to a coherent unification of an hypothetical discrete Planck scale with the usual Fermi scale of high-energy physics.
---
paper_title: Efficient Quantum Algorithms for Analyzing Large Sparse Electrical Networks

paper_content:

Analyzing large sparse electrical networks is a fundamental task in physics, electrical engineering and computer science. We propose two classes of quantum algorithms for this task. The first class is based on solving linear systems, and the second class is based on using quantum walks. These algorithms compute various electrical quantities, including voltages, currents, dissipated powers and effective resistances, in time $\operatorname{poly}(d, c, \operatorname{log}(N), 1/\lambda, 1/\epsilon)$, where $N$ is the number of vertices in the network, $d$ is the maximum unweighted degree of the vertices, $c$ is the ratio of largest to smallest edge resistance, $\lambda$ is the spectral gap of the normalized Laplacian of the network, and $\epsilon$ is the accuracy. Furthermore, we show that the polynomial dependence on $1/\lambda$ is necessary. This implies that our algorithms are optimal up to polynomial factors and cannot be significantly improved.
---
paper_title: From Dirac to Diffusion: Decoherence in Quantum Lattice Gases

paper_content:

We describe a model for the interaction of the internal (spin) degree of freedom of a quantum lattice-gas particle with an environmental bath. We impose the constraints that the particle-bath interaction be fixed, while the state of the bath is random, and that the effect of the particle-bath interaction be parity invariant. The condition of parity invariance defines a subgroup of the unitary group of actions on the spin degree of freedom and the bath. We derive a general constraint on the Lie algebra of the unitary group which defines this subgroup, and hence guarantees parity invariance of the particle-bath interaction. We show that generalizing the quantum lattice gas in this way produces a model having both classical and quantum discrete random walks as different limits. We present preliminary simulation results illustrating the intermediate behavior in the presence of weak quantum noise.
---
paper_title: Two-particle bosonic-fermionic quantum walk via 3D integrated photonics

paper_content:

Quantum walk represents one of the most promising resources for the simulation of physical quantum systems, and has also emerged as an alternative to the standard circuit model for quantum computing. Here we investigate how the particle statistics, either bosonic or fermionic, influences a two-particle discrete quantum walk. Such an experiment has been realized by exploiting polarization entanglement to simulate the bunching-antibunching feature of noninteracting bosons and fermions. To this scope a novel three-dimensional geometry for the waveguide circuit is introduced, which allows accurate polarization independent behavior, maintaining remarkable control on both phase and balancement.
---
paper_title: The Dirac equation as a quantum walk: higher dimensions, observational convergence

paper_content:

The Dirac equation can be modelled as a quantum walk (QW), whose main features are being: discrete in time and space (i.e. a unitary evolution of the wave-function of a particle on a lattice); homogeneous (i.e. translation-invariant and time-independent) and causal (i.e. information propagates at a bounded speed, in a strict sense). This link, which was proposed already by Succi and Benzi, Bialynicki-Birula and Meyer, is shown to hold for Bargmann–Wigner equations and symmetric hyperbolic systems in general. We then analytically prove the convergence of the solution of the QW to the solution of the Cauchy problem for the Dirac equation. We do so by adapting a powerful method from standard numerical analysis, which is of general interest to the field of quantum simulation. At the practical level, this result provides precise error bounds and convergence rates, thereby validating the QW as a quantum simulation scheme. At the theoretical level, it reinforces the status of this QW as a simple, discrete toy model of relativistic particles.
---
paper_title: Lattice Boltzmann equation for quantum mechanics

paper_content:

Abstract It is shown that the lattice Boltzman equation for hydrodynamics can be extended in such a way as to describe non-relativistic quantum mechanics.
---
paper_title: Globally controlled quantum wires for perfect qubit transport, mirroring, and computing.

paper_content:

We describe a new design for a q wire with perfect transmission using a uniformly coupled Ising spin chain subject to global pulses. In addition to allowing for the perfect transport of single qubits, the design also yields the perfect "mirroring" of multiply encoded qubits within the wire. We further utilize this global-pulse generated perfect mirror operation as a "clock cycle" to perform universal quantum computation on these multiply encoded qubits where the interior of the q wire serves as the quantum memory while the q-wire ends perform one- and two-qubit gates.
---
paper_title: Initial-state-dependent thermalization in open qubits

paper_content:

We study, from a thermodynamic perspective, the equilibrium states of a qubit interacting with an arbitrary environment of dimension N>>2. We show that even in presence of memory about the initial state, in some cases the qubit can be considered in a thermal state characterized by an entanglement Hamiltonian, which encodes the effects of the environment, and an initial-state- dependent entanglement temperature that measures the degree of entanglement generated between the system and its environment. Geometrical aspects of the thermal states are studied, and the results are confirmed for the concrete case of the Quantum Walk on the Line.
---
paper_title: Quantum Walks, Weyl equation and the Lorentz group

paper_content:

Quantum cellular automata and quantum walks provide a framework for the foundations of quantum field theory, since the equations of motion of free relativistic quantum fields can be derived as the small wave-vector limit of quantum automata and walks starting from very general principles. The intrinsic discreteness of this framework is reconciled with the continuous Lorentz symmetry by reformulating the notion of inertial reference frame in terms of the constants of motion of the quantum walk dynamics. In particular, among the symmetries of the quantum walk which recovers the Weyl equation--the so called Weyl walk--one finds a non linear realisation of the Poincar\'e group, which recovers the usual linear representation in the small wave-vector limit. In this paper we characterise the full symmetry group of the Weyl walk which is shown to be a non linear realization of a group which is the semidirect product of the Poincar\'e group and the group of dilations.
---
paper_title: From quantum cellular automata to quantum lattice gases

paper_content:

A natural architecture for nanoscale quantum computation is that of a quantum cellular automaton. Motivated by this observation, 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.
---
paper_title: Quantum Walks in artificial electric and gravitational Fields

paper_content:

The continuous limit of quantum walks (QWs) on the line is revisited through a recently developed method. In all cases but one, the limit coincides with the dynamics of a Dirac fermion coupled to an artificial electric and/or relativistic gravitational field. All results are carefully discussed and illustrated by numerical simulations.
---
paper_title: Action Principles for Quantum Automata and Lorentz Invariance of Discrete Time Quantum Walks

paper_content:

Abstract A discrete action principle for general quantum automata is proposed. This action principle is particularized to Discrete Time Quantum Walks (DTQWs) and then extended into an energy and momentum preserving, manifestly covariant formulation. Space–time coordinates are introduced as new variables of the action and their equations of motion enforce energy and momentum conservation. This guarantees that the proposed action can be used to build future, DTQW-based self-consistent models of spinors interacting with gauge fields. A discrete stress–energy tensor for the DTQW is also obtained. The manifest covariance of the formulation highlights the special role played by the grid reference frame in the DTQW dynamics. The main discussion is complemented by three appendices.
---
paper_title: Quantum walking in curved spacetime

paper_content:

A discrete-time Quantum Walk (QW) is essentially a unitary operator driving the evolution of a single particle on the lattice. Some QWs admit a continuum limit, leading to familiar PDEs (e.g. the Dirac equation). In this paper, we study the continuum limit of a wide class of QWs, and show that it leads to an entire class of PDEs, encompassing the Hamiltonian form of the massive Dirac equation in $(1+1)$ curved spacetime. Therefore a certain QW, which we make explicit, provides us with a unitary discrete toy model of a test particle in curved spacetime, in spite of the fixed background lattice. Mathematically we have introduced two novel ingredients for taking the continuum limit of a QW, but which apply to any quantum cellular automata: encoding and grouping.
---
paper_title: Relativistic effects and rigorous limits for discrete- and continuous-time quantum walks

paper_content:

The mathematical relationship between the discrete-time and continuous-time quantum walks and the one-dimensional Dirac equation is explored by studying a class of solutions for each, expressed in terms of the generalized, regular, and modified Bessel functions, respectively. Rigorous limits connecting these solutions are established. In addition, new analytical and numerical results are presented for quantum walks and the Dirac equation, including entanglement, relativistic localization and wave packet spreading, and normal and anomalous Zitterbewegung.
---
paper_title: Simulating Dirac Hamiltonian in Curved Space-time by Split-step Quantum Walk

paper_content:

Dirac particle represents a fundamental constituent of our nature. Simulation of Dirac particle dynamics by a controllable quantum system using quantum walks will allow us to investigate the non-classical nature of dynamics in its discrete form. In this work, starting from a modified version of one-spatial dimensional general inhomogeneous split-step discrete quantum walk we derive an effective Hamiltonian which mimics a single massive Dirac particle dynamics in curved (1 + 1) space-time dimension coupled to U(1) gauge potential—which is a forward step towards the simulation of the unification of electromagnetic and gravitational forces in lower dimension and at the single particle level. Implementation of this simulation scheme in simple qubit-system has been demonstrated. We show that the same Hamiltonian can represent (2 + 1) space-time dimensional Dirac particle dynamics when one of the spatial momenta remains fixed. We also discuss how we can include U(N) gauge potential in our scheme, in order to capture other fundamental force effects on the Dirac particle. The emergence of curvature in the two-particle split-step quantum walk has also been investigated while the particles are interacting through their entangled coin operation.
---
paper_title: Simulating physics with computers

paper_content:

On the program it says this is a keynote speech--and I don't know what a keynote speech is. I do not intend in any way to suggest what should be in this meeting as a keynote of the subjects or anything like that. I have my own things to say and to talk about and there's no implication that anybody needs to talk about the same thing or anything like it. So what I want to talk about is what Mike Dertouzos suggested that nobody would talk about. I want to talk about the problem of simulating physics with computers and I mean that in a specific way which I am going to explain. The reason for doing this is something that I learned about from Ed Fredkin, and my entire interest in the subject has been inspired by him. It has to do with learning something about the possibilities of computers, and also something about possibilities in physics. If we suppose that we know all the physical laws perfectly, of course we don't have to pay any attention to computers. It's interesting anyway to entertain oneself with the idea that we've got something to learn about physical laws; and if I take a relaxed view here (after all I 'm here and not at home) I'll admit that we don't understand everything. The first question is, What kind of computer are we going to use to simulate physics? Computer theory has been developed to a point where it realizes that it doesn't make any difference; when you get to a universal computer, it doesn't matter how it's manufactured, how it's actually made. Therefore my question is, Can physics be simulated by a universal computer? I would like to have the elements of this computer locally interconnected, and therefore sort of think about cellular automata as an example (but I don't want to force it). But I do want something involved with the
---
paper_title: Schemes for parallel quantum computation without local control of qubits, Phys

paper_content:

Typical quantum computing schemes require transformations (gates) to be targeted at specific elements (qubits). In many physical systems, direct targeting is difficult to achieve; an alternative is to encode local gates into globally applied transformations. Here we demonstrate the minimum physical requirements for such an approach: a one-dimensional array composed of two alternating ``types'' of two-state system. Each system need be sensitive only to the net state of its nearest neighbors, i.e. the number in state $``\ensuremath{\uparrow}''$ minus the number in $``\ensuremath{\downarrow}.''$ Additionally, we show that all such arrays can perform quite general parallel operations. A broad range of physical systems and interactions is suitable: we highlight two examples.
---
paper_title: Any AND-OR Formula of Size N can be Evaluated in time N^{1/2 + o(1)} on a Quantum Computer

paper_content:

For any AND-OR formula of size N, there exists a bounded-error N1/2+o(1)-time quantum algorithm, based on a discrete-time quantum walk, that evaluates this formula on a black-box input. Balanced, or "approximately balanced," formulas can be evaluated in O(radicN) queries, which is optimal. It follows that the (2-o(1))th power of the quantum query complexity is a lower bound on the formula size, almost solving in the positive an open problem posed by Laplante, Lee and Szegedy.
---
paper_title: Quantum Communication through Spin Chain Dynamics: an Introductory Overview

paper_content:

We present an introductory overview of the use of spin chains as quantum wires, which has recently developed into a topic of lively interest. The principal motivation is in connecting quantum registers without resorting to optics. A spin chain is a permanently coupled 1D system of spins. When one places a quantum state on one end of it, the state will be dynamically transmitted to the other end with some efficiency if the spins are coupled by an exchange interaction. No external modulations or measurements on the body of the chain, except perhaps at the very ends, is required for this purpose. For the simplest (uniformly coupled) chain and the simplest encoding (single qubit encoding), however, dispersion reduces the quality of transfer. We present a variety of alternatives proposed by various groups to achieve perfect quantum state transfer through spin chains. We conclude with a brief discussion of the various directions in which the topic is developing.
---
paper_title: Dynamical Localization of Quantum Walks in Random Environments

paper_content:

The dynamics of a one dimensional quantum walker on the lattice with two internal degrees of freedom, the coin states, is considered. The discrete time unitary dynamics is determined by the repeated action of a coin operator in U(2) on the internal degrees of freedom followed by a one step shift to the right or left, conditioned on the state of the coin. For a fixed coin operator, the dynamics is known to be ballistic. We prove that when the coin operator depends on the position of the walker and is given by a certain i.i.d. random process, the phenomenon of Anderson localization takes place in its dynamical form. When the coin operator depends on the time variable only and is determined by an i.i.d. random process, the averaged motion is known to be diffusive and we compute the diffusion constants for all moments of the position.
---
paper_title: Quantum mechanical computers

paper_content:

The physical limitations, due to quantum mechanics, on the functioning of computers are analyzed.
---
paper_title: Discrete Lorentz covariance for Quantum Walks and Quantum Cellular Automata

paper_content:

We formalize a notion of discrete Lorentz transforms for quantum walks (QW) and quantum cellular automata (QCA), in -dimensional discrete spacetime. The theory admits a diagrammatic representation in terms of a few local, circuit equivalence rules. Within this framework, we show the first-order-only covariance of the Dirac QW. We then introduce the clock QW and the clock QCA, and prove that they are exactly discrete Lorentz covariant. The theory also allows for non-homogeneous Lorentz transforms, between non-inertial frames.
---
paper_title: Entanglement dynamics and quantum-state transport in spin chains

paper_content:

We study the dynamics of a Heisenberg $XY$ spin chain with an unknown state coded into one qubit or a pair of entangled qubits, with the rest of the spins being in a polarized state. The time evolution involves magnon excitations, and through them the entanglement is transported across the channel. For a large number of qubits, explicit formulas for the concurrences, measures for two-qubit entanglements, and the fidelity for recovering the state some distance away are calculated as functions of time. Initial states with an entangled pair of qubits show better fidelity, which takes its first maximum value at earlier times, compared to initial states with no entangled pair. In particular initial states with a pair of qubits in an unknown state $\ensuremath{\alpha}\ensuremath{\uparrow}\ensuremath{\uparrow}+\ensuremath{\beta}\ensuremath{\downarrow}\ensuremath{\downarrow}$ are best suited for quantum-state transport.
---
paper_title: Quantum Walks With Neutral Atoms: Quantum Interference Effects of One and Two Particles

paper_content:

We report on the state of the art of quantum walk experiments with neutral atoms in state-dependent optical lattices. We demonstrate a novel state-dependent transport technique enabling the control of two spin-selective sublattices in a fully independent fashion. This transport technique allowed us to carry out a test of single-particle quantum interference based on the violation of the Leggett-Garg inequality and, more recently, to probe two-particle quantum interference effects with neutral atoms cooled into the motional ground state. These experiments lay the groundwork for the study of discrete-time quantum walks of strongly interacting, indistinguishable particles to demonstrate quantum cellular automata of neutral atoms.
---
paper_title: Ultracold quantum gases in optical lattices

paper_content:

Artificial crystals of light, consisting of hundreds of thousands of optical microtraps, are routinely created by interfering optical laser beams. These so-called optical lattices act as versatile potential landscapes to trap ultracold quantum gases of bosons and fermions. They form powerful model systems of quantum many-body systems in periodic potentials for probing nonlinear wave dynamics and strongly correlated quantum phases, building fundamental quantum gates or observing Fermi surfaces in periodic potentials. Optical lattices represent a fast-paced modern and interdisciplinary field of research.
---
paper_title: Two-dimensional Lattice Gauge Theories with Superconducting Quantum Circuits

paper_content:

A quantum simulator of U(1) lattice gauge theories can be implemented with superconducting circuits. This allows the investigation of confined and deconfined phases in quantum link models, and of valence bond solid and spin liquid phases in quantum dimer models. Fractionalized confining strings and the real-time dynamics of quantum phase transitions are accessible as well. Here we show how state-of-the-art superconducting technology allows us to simulate these phenomena in relatively small circuit lattices. By exploiting the strong non-linear couplings between quantized excitations emerging when superconducting qubits are coupled, we show how to engineer gauge invariant Hamiltonians, including ring-exchange and four-body Ising interactions. We demonstrate that, despite decoherence and disorder effects, minimal circuit instances allow us to investigate properties such as the dynamics of electric flux strings, signaling confinement in gauge invariant field theories. The experimental realization of these models in larger superconducting circuits could address open questions beyond current computational capability.
---
paper_title: Two-particle bosonic-fermionic quantum walk via 3D integrated photonics

paper_content:

Quantum walk represents one of the most promising resources for the simulation of physical quantum systems, and has also emerged as an alternative to the standard circuit model for quantum computing. Here we investigate how the particle statistics, either bosonic or fermionic, influences a two-particle discrete quantum walk. Such an experiment has been realized by exploiting polarization entanglement to simulate the bunching-antibunching feature of noninteracting bosons and fermions. To this scope a novel three-dimensional geometry for the waveguide circuit is introduced, which allows accurate polarization independent behavior, maintaining remarkable control on both phase and balancement.
---
paper_title: Quantum Causal Graph Dynamics

paper_content:

Consider a graph having quantum systems lying at each node. Suppose that the whole thing evolves in discrete time steps, according to a global, unitary causal operator. By causal we mean that information can only propagate at a bounded speed, with respect to the distance given by the graph. Suppose, moreover, that the graph itself is subject to the evolution, and may be driven to be in a quantum superposition of graphs—in accordance to the superposition principle. We show that these unitary causal operators must decompose as a finite-depth circuit of local unitary gates. This unifies a result on Quantum Cellular Automata with another on Reversible Causal Graph Dynamics. Along the way we formalize a notion of causality which is valid in the context of quantum superpositions of time-varying graphs, and has a number of good properties.
---

Title: An Overview of Quantum Cellular Automata

Section 1: Introduction
Description 1: Write about the historical background and motivations for studying Quantum Cellular Automata (QCA), including the contributions of Von Neumann, Feynman, and the relevance to quantum computation and physical simulation.

Section 2: State Space
Description 2: Explain the concept of the state space in QCA, including definitions and configurations of cells as quantum systems.

Section 3: QCA
Description 3: Define the global evolution of QCA, emphasizing its translation-invariance and causality, and the need for structure theorems to describe the constructive nature of QCA.

Section 4: Structure Theorems
Description 4: Discuss the theorems that reveal QCA can be simulated by finite-depth quantum circuits and other formal representations.

Section 5: Advanced Structure Theorems
Description 5: Explore further structure theorems and their implications, including fermionic QCA, and distinguish between various types of QCA and RCA.

Section 6: Classical Bijective CA, MPU
Description 6: Describe reversible cellular automata (RCA), matrix product unitaries (MPU), and their relationships with QCA.

Section 7: Historical Notes
Description 7: Summarize the development and refinement of QCA definitions, highlighting significant milestones and contributions in the field.

Section 8: Intrinsic Universality
Description 8: Explain the concept of intrinsic simulation and how PQCA can simulate all other types of QCA, along with universal instances.

Section 9: Other Kinds of Universality
Description 9: Discuss other universality aspects including quantum turing machines, quantum circuit universality, and computability principles relating to QCA.

Section 10: Simulation
Description 10: Provide insights into how QCA can simulate various quantum physics phenomena and the practical implementations including the Dirac QCA and other related results.

Section 11: Conclusion
Description 11: Summarize the progress made in QCA theory, potential areas for practical implementation, and encourage future research directions.