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.     

Automata Theory Based on Quantum Logic: Recognizability and Accessibility

Inspired by Ying’s work on automata theory based on quantum logic and classical automata theory, we introduce the concepts of reversal, accessible, coaccessible and complete part of finite state automata based on quantum logic. Some properties of them are discussed. More importantly we investigate the recognizability and accessibility properties of these types on the framework of quantum logic by employing the approach of semantic analysis. Foundation: supported by the National Natural Science Foundation of China (No. 10671030).     

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.     

Finite State and Finite Stop Quantum Languages

We propose the concept of finite stop quantum automata (ftqa) based on Hilbert space and compare it with the finite state quantum automata (fsqa) proposed by Moore and Crutchfield (Theoretical Computer Science 237(1–2), 2000, 275–306). The languages accepted by fsqa form a proper subset of the languages accepted by ftqa. In addition, the fsqa form an infinite hierarchy of language inclusion with respect to the dimensionality of unitary matrices. We introduce complex-valued acceptance degrees and two types of finite stop quantum automata based on them: the invariant ftqa (icftq) and the variant ftqa (vcftq). The languages accepted by icftq form a proper subset of the languages accepted by vcftq. In addition, the icftq form an infinite hierarchy of language inclusion with respect to the dimensionality of unitary matrices. In this way, we establish two proper inclusion relations (fsqa) ⊂ (ftqa) and (icftq) ⊂ (vcftq), where the symbol means languages, and two infinite language hierarchies (fsqa) ⊂ (fsqa), (icftq) (icftq).     

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).     

Pumping Lemma for Quantum Automata

Not all lattice-valued quantum automata possess the pumping property in its strict form. However the pumping lemma can be generalized, and all lattice-valued quantum automata possess the generalized pumping property.     

Properties of Quantum Languages

The class of quantum languages Q() over an alphabet is the class of languages accepted by quantum automata. We study properties of Q() and compare Q() with the class of regular languages R(). It is shown that Q() is closed under union, intersection, and reversal but is not closed under complementation, concatenation, or Kleene star. It is also shown that Q() and R() are incomparable. Finally, we prove that L Q() if and only if L admits a transition amplitude function satisfying a certain property and a similar characterization is given for R().     

Parrondo Games as Lattice Gas Automata

Parrondo games are coin flipping games with the surprising property that alternating plays of two losing games can produce a winning game. We show that this phenomenon can be modelled by probabilistic lattice gas automata. Furthermore, motivated by the recent introduction of quantum coin flipping games, we show that quantum lattice gas automata provide an interesting definition for quantum Parrondo games.     

Computational Power of Asynchronously Tuned Automata Enhancing the Unfolded Edge of Chaos

Asynchronously tuned elementary cellular automata (AT-ECA) are described with respect to the relationship between active and passive updating, and that spells out the relationship between synchronous and asynchronous updating. Mutual tuning between synchronous and asynchronous updating can be interpreted as the model for dissipative structure, and that can reveal the critical property in the phase transition from order to chaos. Since asynchronous tuning easily makes behavior at the edge of chaos, the property of AT-ECA is called the unfolded edge of chaos. The computational power of AT-ECA is evaluated by the quantitative measure of computational universality and efficiency. It shows that the computational efficiency of AT-ECA is much higher than that of synchronous ECA and asynchronous ECA.     

Quantum secure direct communication over the collective amplitude damping channel

An efficient quantum secure direct communication protocol is presented over the amplitude damping channel. The protocol encodes logical bits in two-qubit noiseless states, and so it can function over a quantum channel subjected to collective amplitude damping. The feature of this protocol is that the sender encodes the secret directly on the quantum states, the receiver decodes the secret by performing determinate measurements, and there is no basis mismatch. The transmission’s safety is ensured by the nonorthogonality of the noiseless states traveling forward and backward on the quantum channel. Moreover, we construct the efficient quantum circuits to implement channel encoding and information encoding by means of primitive operations in quantum computation. Supported by the National Natural Science Foundation of China (Grant Nos. 60873191 and 60821001), the Specialized Research Fund for the Doctoral Program of Higher Education (Grant No. 200800131016), the Natural Science Foundation of Beijing (Grant No. 4072020), the National Laboratory for Modern Communications Science Foundation of China (Grant No. 9140C1101010601), and the ISN Open Foundation     

Quantum entanglement and quantum operation

It is a simple introduction to quantum entanglement and quantum operations. The authors focus on some applications of quantum entanglement and relations between two-qubit entangled states and unitary operations. It includes remote state preparation by using any pure entangled states, nonlocal operation implementation using entangled states, entanglement capacity of two-qubit gates and two-qubit gates construction. Supported by the National Fundamental Research Program of China (Grant No. 2001CB309306), the National Natural Science Foundation of China (Grant Nos. 60621064 and 10674127) and the Innovation Funds from Chinese Academy of Sciences     

Quantum threshold group signature

In most situations, the signer is generally a single person. However, when the message is written on behalf of an organization, a valid message may require the approval or consent of several persons. Threshold signature is a solution to this problem. Generally speaking, as an authority which can be trusted by all members does not exist, a threshold signature scheme without a trusted party appears more attractive. Following some ideas of the classical Shamir’s threshold signature scheme, a quantum threshold group signature one is proposed. In the proposed scheme, only t or more of n persons in the group can generate the group signature and any t − 1 or fewer ones cannot do that. In the verification phase, any t or more of n signature receivers can verify the message and any t − 1 or fewer receivers cannot verify the validity of the signature. Supported by the National Basic Research Program of China (973 Program)(Grant No. 2007CB311100), the National High-Technology Research and Development Program of China (Grant Nos. 2006AA01Z419 and 2006AA01Z440), the Major Research Plan of the National Natural Science Foundation of China (Grant No. 90604023), the Scientific Research Common Program of Beijing Municipal Commission of Education (Grant No. KM200810005004), the Scientific Research Foundation for the Youth of Beijing University of Technology (Grant No. 97007016200701), the Doctoral Scientific Research Activation Foundation of Beijing University of Technology (Grant No. 52007016200702), the ISN Open Foundation, and the National Laboratory for Modern Communications Science Foundation of China (Grant No. 9140C1101010601)     

A New Book of Numbers: On the Precise Definition of Quantum Variables and the Relationships between Mathematics and Physics in Quantum Theory

Following Asher Peres’s observation that, as in classical physics, in quantum theory, too, a given physical object considered “has a precise position and a precise momentum,” this article examines the question of the definition of quantum variables, and then the new type (as against classical physics) of relationships between mathematics and physics in quantum theory. The article argues that the possibility of the precise definition and determination of quantum variables depends on the particular nature of these relationships.     

Quantum corrections for Boltzmann equation

We present the lowest order quantum correction to the semiclassical Boltzmann distribution function, and the equation satisfied by this correction is given. Our equation for the quantum correction is obtained from the conventional quantum Boltzmann equation by explicitly expressing the Planck constant in the gradient approximation, and the quantum Wigner distribution function is expanded in powers of Planck constant, too. The negative quantum correlation in the Wigner distribution function which is just the quantum correction terms is naturally singled out, thus obviating the need for the Husimi’s coarse grain averaging that is usually done to remove the negative quantum part of the Wigner distribution function. We also discuss the classical limit of quantum thermodynamic entropy in the above framework. Supported by the National Natural Science Foundation of China (Grant No. 10404037) and the Scientific Research Fund of GUCAS (Grant No. 055101BM03)     

Basic Properties of Quantum Automata

This paper develops a theory of quantum automata and their slightly more general versions, q-automata. Quantum languages and -quantum languages, 0<1, are studied. Functions that can be realized as probability maps for q-automata are characterized. Quantum grammars are discussed and it is shown that quantum languages are precisely those languages that are induced by a quantum grammar. A quantum pumping lemma is employed to show that there are regular languages that are not -quantum, 0<1.     

Note on Generalized Quantum Gates and Quantum Operations

Recently, Gudder proved that the set of all generalized quantum gates coincides the set of all contractions in a finite-dimensional Hilbert space (S. Gudder, Int. J. Theor. Phys. 47:268–279, 2008). In this note, we proved that the set of all generalized quantum gates is a proper subset of the set of all contractions on an infinite dimensional separable Hilbert space ℋ. Meanwhile, we proved that the quantum operation deduced by an isometry is an extreme point of the set of all quantum operations on ℋ. This subject is supported by NSF of China (10571113).     

Free-Fall Non-Universality in Quantum Theory

The author shows by embodying the Einstein equivalence principle—local Poincaré invariance—and general covariance in quantum theory that wave-function spreading rules out the universality of free fall, that is, the free-fall trajectory of a quantum (test) particle depends on its internal properties. The author provides a quantitative estimate of the free-fall non-universality in terms of the Eötvös parameter, which turns out to be measurable in atom interferometry.     

Global and Local Spin Squeezing in Coupled Quantum Kicked Tops Model

We investigate the global and the local spin squeezing in a weakly coupled quantum kicked tops system. Two different situations are considered: (i) N=1 and (ii) N=30 for each subsystem, corresponding to quantum and classical cases, respectively. In the first case, since the two subsystems have no spin squeezing, the global squeezing completely originates from quantum correlations. For the second one, the global spin squeezing is enhanced over the local one. Due to the chaotic nature of the system, the spin squeezing is sensitive to the initial state. In chaotic region, the squeezing vanished time is much shorter than that in the regular region.