The density classification (DC) task, a computation which maps global density information to local density, is studied using one-dimensional non-unitary quantum cellular automata (QCAs). Two approaches are considered: one that preserves the number density and one that performs majority voting. For number-preserving DC, two QCAs are introduced that reach the fixed-point solution in a time scaling quadratically with the system size. One of the QCAs is based on a known classical probabilistic cellular automaton which has been studied in the context of DC. The second is a new quantum model that is designed to demonstrate additional quantum features and is restricted to only two-body interactions. Both can be generated by continuous-time Lindblad dynamics. A third QCA is a hybrid rule defined by both discrete-time and continuous-time three-body interactions that is shown to solve the majority voting problem within a time that scales linearly with the system size.
The density classification (DC) task, a computation which maps global density information to local density, is studied using one-dimensional non-unitary quantum cellular automata (QCAs). Two approaches are considered: one that preserves the number density and one that performs majority voting. For number-preserving DC, two QCAs are introduced that reach the fixed-point solution in a time scaling quadratically with the system size. One of the QCAs is based on a known classical probabilistic cellular automaton which has been studied in the context of DC. The second is a new quantum model that is designed to demonstrate additional quantum features and is restricted to only two-body interactions. Both can be generated by continuous-time Lindblad dynamics. A third QCA is a hybrid rule defined by both discrete-time and continuous-time three-body interactions that is shown to solve the majority voting problem within a time that scales linearly with the system size.
We investigate the density classification task (DCT) -- determining the majority bit in a one-dimensional binary lattice -- within a quantum cellular automaton (CA) framework. While there is no one-dimensional two-state, radius r≥1, deterministic CA with periodic boundary conditions that solves the DCT perfectly, we explore whether a unitary quantum model can succeed. We employ the Partitioned Unitary Quantum Cellular Automaton (PUQCA), a number-conserving model, and, via evolutionary search, find solutions to the DCT where the success condition is stipulated in terms of measurement probabilities rather than convergence to fixed-point configurations. Finally, we identify a classically simulable regime of the PUQCA in which we find rules that solve the DCT at fixed system sizes and analyze their performance.
Quantum cellular automata are alternative quantum-computing paradigms to quantum Turing machines and quantum circuits. Their working mechanisms are inherently automated, therefore measurement free, and they act in a translation invariant manner on all cells or qudits of a register, generating a global rule that updates cell states locally, i.e., based solely on the states of their neighbors. Although desirable features in many applications, it is generally not clear to which extent these fully automated discrete-time local updates can generate and sustain long-range order in the (noisy) systems they act upon. In particular, whether and how quantum cellular automata can perform quantum error correction remain open questions. We close this conceptual gap by proposing quantum cellular automata with quantum-error-correction capabilities. We design and investigate two (quasi)one dimensional quantum cellular automata based on known classical cellular-automata rules with density-classification capabilities, namely the local majority voting and the two-line voting. We investigate the performances of those quantum cellular automata as quantum-memory components by simulating the number of update steps required for the logical information they act upon to be afflicted by a logical bit flip. The proposed designs pave a way to further explore the potential of new types of quantum cellular automata with built-in quantum-error-correction capabilities.
The information flow in a quantum system is a fundamental feature of its dynamics. An important class of dynamics are quantum cellular automata (QCA), systems with discrete updates invariant in time and space, for which an index theory has been proposed for the quantification of the net flow of quantum information across a boundary. While the index is rigid in the sense of begin invariant under finite-depth local circuits, it is not defined when the system is coupled to an environment, i.e.for non-unitary time evolution of open quantum systems. We propose a new measure of information flow for non-unitary QCA denoted the information current which is not rigid, but can be computed locally based on the matrix-product operator representation of the map.
A quantum cellular automaton (QCA) is a unitary discrete-time evolution of a quantum many-body system, which can be described as a dynamics system , where A is any matrix and is a unitary operator representing the global evolution of QCA. And QCAs are characterized by locality (or causality). Among them, quantum circuits are the special classes of QCAs, which use unitary operators to control and transform the initial quantum state of qubit into a final quantum state, quantum circuits are special and widely studied in quantum information. A group is a set of elements combined with an operation, which satisfies associativity, identity and invertibility. This article shows that group theory provides the right language for studying the relation between QCAs and quantum circuits among them.
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 found application in understanding topological phases of matter and have} been proposed as models of periodically driven (Floquet) quantum systems, where QCA methods were used to classify their phases. QCAs have also been used as a natural discretization of quantum field theory, and some interesting examples of QCAs have been introduced that become interacting quantum field theories 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 tensor-network unitary approach, the index theory and higher dimensional classifications of QCAs.
In Part I of this thesis, we present a new model of quantum cellular automata \n(QCA) based on local unitary operations. We will describe a set of desirable \nproperties for any QCA model, and show that all of these properties are \nsatisfied by the new model, while previous models of QCA do not. We will also \nshow that the computation model based on Local Unitary QCA is equivalent to \nthe Quantum Circuit model of computation, and give a number of applications of \nthis new model of QCA. We also present a physical model of classical CA, on \nwhich the Local Unitary QCA model is based, and Coloured QCA, which is an \nalternative to the Local Unitary QCA model that can be used as the basis for \nimplementing QCA in actual physical systems. \n \nIn Part II, we explore the quantum separability problem, where we are given a \ndensity matrix for a state over two quantum systems, and we are to determine \nwhether the state is separable with respect to these systems. We also look at \nthe converse problem of finding an entanglement witness, which is an \nobservable operator which can give a verification that a particular quantum \nstate is indeed entangled. Although the combined problem is known to be \nNP-hard in general, it reduces to a convex optimization problem, and by \nexploiting specific properties of the set of separable states, we introduce a \nclassical algorithm for solving this problem based on an Interior Point \nAlgorithm introduced by Atkinson and Vaidya in 1995. \n \nIn Part III, we explore the use of a low-depth AQFT (approximate quantum \nFourier transform) in quantum phase estimation. It has been shown previously \nthat the logarithmic-depth AQFT is as effective as the full QFT for the \npurposes of phase estimation. However, with sub-logarithmic depth, the phase \nestimation algorithm no longer works directly. In this case, results of the \nphase estimation algorithm need classical post-processing in order to retrieve \nthe desired phase information. A generic technique such as the method of \nmaximum likelihood can be used in order to recover the original phase. \n \nUnfortunately, working with the likelihood function analytically is \nintractable for the phase estimation algorithm. We develop some computational \ntechniques to handle likelihood functions that occur in phase estimation \nalgorithms. These computational techniques may potentially aid in the analysis \nof certain likelihood functions.