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

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

On algorithms, separability and cellular automata in quantum computing

Donny Cheung

Published Jan 1, 2007• 0 citations
OpenAlex

Abstract

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.

Related papers

Quantum Cellular Automata: Theory and Applications

Pérez Delgado, Carlos Alberto Conceição António

This thesis presents a model of Quantum Cellular Automata (QCA). The presented formalism is a natural quantization of the classical Cellular Automata (CA). It is based on a lattice of qudits, and an update rule consisting of local unitary operators that commute with their own lattice translations. One purpose of this model is to act as a theoretical model of quantum computation, similar to the quantum circuit model. The main advantage that QCA have over quantum circuits is that QCA make considerably fewer demands on the underlying hardware. In particular, as opposed to direct implementations of quantum circuits, the global evolution of the lattice in the QCA model does not assume independent control over individual \emph{qudits}. Rather, all qudits are to be addressed collectively in parallel. The QCA model is also shown to be an appropriate abstraction for space-homogeneous quantum phenomena, such as quantum lattice gases, spin chains and others. Some results that show the benefits of basing the model on local unitary operators are shown: computational universality, strong connections to the circuit model, simple implementation on quantum hardware, and a series of applications. A detailed discussion will be given on one particular application of QCA that lies outside either computation or simulation: single-spin measurement. This algorithm uses the techniques developed in this thesis to achieve a result normally considered hard in physics. It serves well as an example of why QCA are interesting in their own right.

•Sep 26, 2007•4 citations

A review of Quantum Cellular Automata

Terry Farrelly

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.

arXiv:1904.13318•Quantum•Nov 30, 2020•196 citations

Entanglement dynamics in one-dimensional quantum cellular automata

Gavin K. Brennen, Jamie Williams

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.

arXiv:quant-ph/0306056•Physical Review A•Oct 13, 2003•62 citations

Models of Quantum Cellular Automata

Carlos A. Pérez-Delgado, Donny Cheung

In this paper we present a systematic view of Quantum Cellular Automata (QCA), a mathematical formalism of quantum computation. First we give a general mathematical framework with which to study QCA models. Then we present four different QCA models, and compare them. One model we discuss is the traditional QCA, similar to those introduced by Shumacher and Werner, Watrous, and Van Dam. We discuss also Margolus QCA, also discussed by Schumacher and Werner. We introduce two new models, Coloured QCA, and Continuous-Time QCA. We also compare our models with the established models. We give proofs of computational equivalence for several of these models. We show the strengths of each model, and provide examples of how our models can be useful to come up with algorithms, and implement them in real-world physical devices.

arXiv:quant-ph/0508164•Aug 23, 2005•15 citations

A review of quantum cellular automata

Terry Farrelly

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. © 2020 Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften. All rights reserved.

•Jan 1, 2020•0 citations

Quantum Walks via Quantum Cellular Automata for Simulating Quantum Computation

Tanish Singh

The quantum walk is a subset of classical random walks.Considerable research has lately been conducted on quantum walks in relation to quantum computing.The walk may be thought of as a type of quantum cellular automata.In a broader sense, there is a one-to-one link between them.Furthermore, we look at another type of quantum cellular automata that may be thought of as a quantum version of stochastic cellular automata.The quantum walk formalism is a widely used and quite practical paradigm for modelling quantum systems such as Dirac equation simulations, discrete dynamics in both the low and high energy regimes, and the development of a multitude of quantum algorithms.The walker in a QW moves in a quantum superposition of pathways, and the ensuing interference serves as the foundation for a broad range of quantum algorithms, including quantum search, graph isomorphism issues, and rating nodes in a network.To generate a block representation of n-dimensional quantum cellular automata, we apply the following general result to them.As a result, we have demonstrated that their generic, axiomatic formulation nevertheless produces a unifying, operational representation of them.Some non-trivial ramifications are investigated, such as the fact that bijective non-reversible CA are not physical as closed systems, or that quantum information can move faster than classical informationwithin some specified dynamics.Finally, we present n-dimensional quantum cellular automata that can simulate anything else.This means that the initial configuration and local transition rule of any one-dimensional QCA may be stored within the universal QCA's initial configuration.The simulated QCA will then correspond to many phases of the universal QCA.In the sense that each cell in the simulated QCA is represented as a group of nearby cells in the universal QCA, the simulation preserves the topology.Because the encoding is linear, it bears no cost of the calculation.

IARJSET•Nov 30, 2021•0 citations
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.
This thesis presents a model of Quantum Cellular Automata (QCA). The presented formalism is a natural quantization of the classical Cellular Automata (CA). It is based on a lattice of qudits, and an update rule consisting of local unitary operators that commute with their own lattice translations. One purpose of this model is to act as a theoretical model of quantum computation, similar to the quantum circuit model. The main advantage that QCA have over quantum circuits is that QCA make considerably fewer demands on the underlying hardware. In particular, as opposed to direct implementations of quantum circuits, the global evolution of the lattice in the QCA model does not assume independent control over individual \emph{qudits}. Rather, all qudits are to be addressed collectively in parallel. The QCA model is also shown to be an appropriate abstraction for space-homogeneous quantum phenomena, such as quantum lattice gases, spin chains and others. Some results that show the benefits of basing the model on local unitary operators are shown: computational universality, strong connections to the circuit model, simple implementation on quantum hardware, and a series of applications. A detailed discussion will be given on one particular application of QCA that lies outside either computation or simulation: single-spin measurement. This algorithm uses the techniques developed in this thesis to achieve a result normally considered hard in physics. It serves well as an example of why QCA are interesting in their own right.
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.
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.
In this paper we present a systematic view of Quantum Cellular Automata (QCA), a mathematical formalism of quantum computation. First we give a general mathematical framework with which to study QCA models. Then we present four different QCA models, and compare them. One model we discuss is the traditional QCA, similar to those introduced by Shumacher and Werner, Watrous, and Van Dam. We discuss also Margolus QCA, also discussed by Schumacher and Werner. We introduce two new models, Coloured QCA, and Continuous-Time QCA. We also compare our models with the established models. We give proofs of computational equivalence for several of these models. We show the strengths of each model, and provide examples of how our models can be useful to come up with algorithms, and implement them in real-world physical devices.
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. © 2020 Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften. All rights reserved.
The quantum walk is a subset of classical random walks.Considerable research has lately been conducted on quantum walks in relation to quantum computing.The walk may be thought of as a type of quantum cellular automata.In a broader sense, there is a one-to-one link between them.Furthermore, we look at another type of quantum cellular automata that may be thought of as a quantum version of stochastic cellular automata.The quantum walk formalism is a widely used and quite practical paradigm for modelling quantum systems such as Dirac equation simulations, discrete dynamics in both the low and high energy regimes, and the development of a multitude of quantum algorithms.The walker in a QW moves in a quantum superposition of pathways, and the ensuing interference serves as the foundation for a broad range of quantum algorithms, including quantum search, graph isomorphism issues, and rating nodes in a network.To generate a block representation of n-dimensional quantum cellular automata, we apply the following general result to them.As a result, we have demonstrated that their generic, axiomatic formulation nevertheless produces a unifying, operational representation of them.Some non-trivial ramifications are investigated, such as the fact that bijective non-reversible CA are not physical as closed systems, or that quantum information can move faster than classical informationwithin some specified dynamics.Finally, we present n-dimensional quantum cellular automata that can simulate anything else.This means that the initial configuration and local transition rule of any one-dimensional QCA may be stored within the universal QCA's initial configuration.The simulated QCA will then correspond to many phases of the universal QCA.In the sense that each cell in the simulated QCA is represented as a group of nearby cells in the universal QCA, the simulation preserves the topology.Because the encoding is linear, it bears no cost of the calculation.