Lattices of Quantum Automata

We defined and studied three different types of lattice-valued finite state quantum automata (LQA) and four different kinds of LQA operations, discussed their advantages, disadvantages, and various properties. There are four major results obtained in this paper. First, no one of the above mentioned LQA follows the law of lattice value conservation. Second, the theorem of classical automata theory, that each nondeterministic finite state automaton has an equivalent deterministic one, is not necessarily valid for finite state quantum automata. Third, we proved the existence of semilattices and also lattices formed by different types of LQA. Fourth, there are tight relations between properties of the original lattice l and those of the l-valued lattice formed by LQA.     

Rotators,periodicity, and absence of diffusion in cyclic cellular automata

Cyclic cellular automata are two-dimensional cellular automata which generalize lattice versions of the Lorentz gas and certain biochemistry models of artificial life. We show that rotators and time reversibility play a special role in the creation of closed orbits in cyclic cellular automata. We also prove that almost every orbit is closed (periodic) and the absence of diffusion for the flipping rotator model (also known as the ant).     

From quantum cellular automata to quantum lattice gases

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.     

A quantum walk in phase space with resonator-assisted double quantum dots

We implement a quantum walk in phase space with a new mechanism based on the superconducting resonator-assisted double quantum dots.By analyzing the hybrid system,we obtain the necessary factors implementing a quantum walk in phase space:the walker,coin,coin flipping and conditional phase shift.The coin flipping is implemented by adding a driving field to the resonator.The interaction between the quantum dots and resonator is used to implement conditional phase shift.Furthermore,we show that with different driving fields the quantum walk in phase space exhibits a ballistic behavior over 25 steps and numerically analyze the factors influencing the spreading of the walker in phase space.     

Grammar Theory Based on Quantum Logic

Motivated by Ying' work on automata theory based on quantum logic (Ying, M. S. (2000). International Journal of Therotical Physics, 39(4): 985–996; 39(11): 2545–2557) and inspired by the close relationship between the automata theory and the theory of formal grammars, we have established a basic framework of grammar theory on quantum logic and shown that the set of l-valued quantum regular languages generated by l-valued quantum regular grammars coincides with the set of l-valued quantum languages recognized by l-valued quantum automata.     

Maximal Parrondo’s Paradox for Classical and Quantum Markov Chains

Parrondo’s paradox refers to the situation where two, multi-round games with a fixed winning criteria, both with probability greater than one-half for one player to win, are combined. Using a possibly biased coin to determine the rule to employ for each round, paradoxically, the previously losing player now wins the combined game with probability greater than one-half. In this paper, we will analyze classical observed, classical hidden, and quantum versions of a game that displays this paradox. The game we have utilized is simpler than games for which this behavior has been previously noted in the classical and quantum cases. We will show that in certain situations the paradox can occur to a greater degree in the quantum version than is possible in the classical versions.     

Weakly Regular Quantum Grammars and Asynchronous Quantum Automata

In this paper, we define weakly regular quantum grammars (WRQG), regular quantum grammars (RQG), asynchronous quantum automata (AQA) and synchronous quantum automata (SQA). Moreover, we investigate the relationships between quantum languages generated by weakly quantum regular grammars and by asynchronous quantum automata. At the mean time, we discuss the relationships between regular quantum grammars and synchronous quantum automata. This work is supported by National Science Foundation of China (Grant No. 10571112) and 973 Program of China (No. 2002CB312200).     

鼓泡床内气固两相流的变尺度格子气模拟

基于格子气自动机的建模思想,建立气固两相流的变尺度格子气模型,用微观层次的气固作用规则描述两相流的宏观行为.二维流场空间被离散成两层不同尺度的正六边形网格,固体颗粒和气体粒子分别在各自的网格上运动;在格子气自动机基本规则基础上设计气固相作用规则和附加演化规则;确定模型宏观物理量的统计计算方法,并根据相似原理建立模型物理量与真实物理量之间的转换关系.用建立的模型对鼓泡床内气固流动行为进行模拟,通过比较发现,变尺度格子气模型的模拟结果与文献中的实验结果和双流体模型的模拟结果吻合较好,且平均相对误差更小,表明建模方法的正确性和模型的有效性.     

Generalized Boltzmann equation for lattice gas automata

In this paper a theory is formulated that predicts velocity and spatial correlations between occupation numbers that occur in lattice gas automata violating semi-detailed balance. Starting from a coupled BBGKY hierarchy for then-particle distribution functions, cluster expansion techniques are used to derive approximate kinetic equations. In zeroth approximation the standard nonlnear Boltzmann equation is obtained; the next approximation yields the ring kinetic equation, similar to that for hard-sphere systems, describing the time evolution of pair correlations. The ring equation is solved to determine the (nonvanishing) pair correlation functions in equilibrium for two models that violate semidetailed balance. One is a model of interacting random walkers on a line, the other one is a two-dimensional fluid-type model on a triangular lattice. The numerical predictions agree very well with computer simulations.     

Properly quantized history-dependent Parrondo games, Markov processes, and multiplexing circuits

In the context of quantum information theory, “quantization” of various mathematical and computational constructions is said to occur upon the replacement, at various points in the construction, of the classical randomization notion of probability distribution with higher order randomization notions from quantum mechanics such as quantum superposition with measurement. For this to be done “properly”, a faithful copy of the original construction is required to exist within the new quantum one, just as is required when a function is extended to a larger domain. Here procedures for extending history-dependent Parrondo games, Markov processes and multiplexing circuits to their quantum versions are analyzed from a game theoretic viewpoint, and from this viewpoint, proper quantizations developed.     

Algebraic spatial correlations in lattice gas automata violating detailed balance

In this paper we discuss the existence of generic long-range correlations in spatially homogeneous and stable equilibrium states of closed lattice gas automata whose stochastic collision rules violate the symmetry conditions of detailed balance and in addition satisfy local conservation laws. Such correlations occur even though the collision rules are strictly local and invariant under all symmetries of the lattice. First a phenomenological (Langevin equation) approach is discussed. Next we present a theoretical analysis on the basis of an approximate microscopic (ring kinetic) theory. This theory is used to calculate the amplitude ofr ^– tails in the spatial correlations, and the result is compared with computer simulations.     

二维卡门涡街的格子Boltzmann仿真

格子气自动机和格子Boltzmann方法的迅速发展提供了一类求解流体力学问题的新的方法。本文中，我们介绍了Boltzmann方法，解决了格子气方法中的缺点，通过选择适当平衡分布及其参数，导出了Navier－Stokers方程，并得到了声速和粘性系数。最后在微机上模拟了在无限长平板流动问题及绕单分离板的流动问题，得到了卡门涡街。结果表该模型有格子气方法及其它的数值方法所没有的优点，计算更精确、更直观、更有效。     

Quantum Pushdown Automata

Quantum automata are mathematical models for quantum computing. We analyze the existing quantum pushdown automata, propose a q quantum pushdown automata (qQPDA), and partially clarify their connections. We emphasize some advantages of our qQPDA over others. We demonstrate the equivalence between qQPDA and another QPDA. We indicate that qQPDA are at least as powerful as the QPDA of Moore and Crutchfield with accepting words by empty stack. We introduce the quantum languages accepted by qQPDA and prove that every -q quantum context-free language is also an -q quantum context-free language for any (0, 1) and (0, 1).     

Quantum Parrondo game based on a quantum ratchet effect

A Parrondo game is a counterintuitive game where two losing games can be combined to form a winning game. We construct a quantum version of a Parrondo game based on a quantum ratchet effect for a delta-kicked model, which can be realized in optical lattices. A game set is presented and a quantum anti-Parrondo game is also investigated.     

Local structure theory: Calculation on hexagonal arrays,and interaction of rule and lattice

Local structure theory calculations⁷ are applied to the study of cellular automata on the two-dimensional hexagonal lattice. A particular hexagonal lattice rule denoted (3422) is considered in detail. This rule has many features in common with Conway'sLife. The local structure theory captures many of the statistical properties of this rule; this supports hypotheses raised by a study ofLife itself⁽⁶⁾. As inLife, the state of a cell under (3422) depends only on the state of the cell itself and the sum of states in its neighborhood at the previous time step. This property implies that evolution rules which operate in the same way can be studied on different lattices. The differences between the behavior of these rules on different lattices are dramatic. The mean field theory cannot reflect these differences. However, a generalization of the mean field theory, the local structure theory, does account for the rule-lattice interaction.     

Monte Carlo Study of Localization on a One-Dimensional Lattice

We study the equilibrium properties of a single quantum particle interacting with a classical lattice gas. We develop a path-integral formalism in which the quantum particle is represented by a closed, variable-step random walk on the lattice. After demonstrating that a Metropolis algorithm correctly predicts the properties of a free particle, we extend it to investigate the behavior of the quantum particle interacting with the lattice gas. Evidence of weak localization is observed under conditions of quenched disorder, while self-trapping clearly occurs for the fully annealed system. Compared with continuous space systems, convergence of Monte Carlo simulations in this minimum model is orders of magnitude faster in cpu time. Therefore the system behavior can be investigated for a much larger domain of thermodynamic parameters (e.g., density and temperature) in a reasonable time.     

Velocity autocorrelation function in lattice gases from the ring kinetic theory. Comparison with numerical simulations

We obtain the complete time dependence of the velocity autocorrelation function (VACF) for lattice gas cellular automata, usingring kinetic theory. This theory accounts for the simplest correlated collisions that improve on the molecular chaos approach, and yields a closed equation for the VACF that we evaluate for both infinite and finite systems. We compare our analytical results with numerical simulations at all times, as well as with long-time results of the mode coupling theories, finding a very good agreement for all times at all densities.