Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFinding optimal solutions by stochastic cellular automata
281
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Finding a ground state of a given Hamiltonian is an important but hard problem. One of the potential methods is to use a Markov chain Monte Carlo (MCMC) to sample the Gibbs distribution whose highest peaks correspond to the ground states. In this short paper, we use stochastic cellular automata (SCA) and see if it is possible to find a ground state faster than the conventional MCMCs, such as the Glauber dynamics. We show that, if the temperature is sufficiently high, it is possible for SCA to have more spin-flips per update in average than Glauber and, at the same time, to have an equilibrium distribution ``close to the one for Glauber, i.e., the Gibbs distribution. During the course, we also propose a new way to characterize how close a probability measure is to the target Gibbs.
rate research
Read More
Finding a ground state of a given Hamiltonian on a graph $G=(V,E)$ is an important but hard problem. One of the potential methods is to use a Markov chain Monte Carlo to sample the Gibbs distribution whose highest peaks correspond to the ground states. In this short paper, we investigate the stochastic cellular automata, in which all spins are updated independently and simultaneously. We prove that (i) if the temperature is sufficiently high and fixed, then the mixing time is at most of order $log|V|$, and that (ii) if the temperature drops in time $n$ as $1/log n$, then the limiting measure is uniformly distributed over the ground states.
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.
We consider the group structure of quantum cellular automata (QCA) modulo circuits and show that it is abelian even without assuming the presence of ancillas, at least for most reasonable choices of control space; this is a corollary of a general method of ancilla removal. Further, we show how to define a group of QCA that is well-defined without needing to use families, by showing how to construct a coherent family containing an arbitrary finite QCA; the coherent family consists of QCA on progressively finer systems of qudits where any two members are related by a shallow quantum circuit. This construction applied to translation invariant QCA shows that all translation invariant QCA in three dimensions and all translation invariant Clifford QCA in any dimension are coherent.
We study matrix product unitary operators (MPUs) for fermionic one-dimensional (1D) chains. In stark contrast with the case of 1D qudit systems, we show that (i) fermionic MPUs do not necessarily feature a strict causal cone and (ii) not all fermionic Quantum Cellular Automata (QCA) can be represented as fermionic MPUs. We then introduce a natural generalization of the latter, obtained by allowing for an additional operator acting on their auxiliary space. We characterize a family of such generalized MPUs that are locality-preserving, and show that, up to appending inert ancillary fermionic degrees of freedom, any representative of this family is a fermionic QCA and viceversa. Finally, we prove an index theorem for generalized MPUs, recovering the recently derived classification of fermionic QCA in one dimension. As a technical tool for our analysis, we also introduce a graded canonical form for fermionic matrix product states, proving its uniqueness up to similarity transformations.
The paper proposes a simple formalism for dealing with deterministic, non-deterministic and stochastic cellular automata in a unifying and composable manner. Armed with this formalism, we extend the notion of intrinsic simulation between deterministic cellular automata, to the non-deterministic and stochastic settings. We then provide explicit tools to prove or disprove the existence of such a simulation between two stochastic cellular automata, even though the intrinsic simulation relation is shown to be undecidable in dimension two and higher. The key result behind this is the caracterization of equality of stochastic global maps by the existence of a coupling between the random sources. We then prove that there is a universal non-deterministic cellular automaton, but no universal stochastic cellular automaton. Yet we provide stochastic cellular automata achieving optimal partial universality.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
