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

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•7 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•138 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•61 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•109 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
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.
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.
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.
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.
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.