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 II

We establish the pumping lemma in automata theory based on quantum logicunder certain conditions on implication, and discuss the recognizability by theproduct and union of orthomodular lattice-valued (quantum) automata. Inparticular, we show that the equivalence between the recognizabilty by the productof automata and the conjunction of the recognizabilities by the factor automatais equivalent to the distributivity of meet over union in the truth-value set.     

New Design for Quantum Dots Cellular Automata to obtain Fault Tolerant Logic Gates

In this paper, we analyze fault tolerance properties of the Majority Gate, as the main logic gate for implementation with Quantum dots Cellular Automata (QCA), in terms of fabrication defect. Our results demonstrate the poor fault tolerance properties of the conventional design of Majority Gate and thus the difficulty in its practical application. We propose a new approach to the design of QCA-based Majority Gate by considering two-dimensional arrays of QCA cells rather than a single cell for the design of such a gate. We analyze fault tolerance properties of such Block Majority Gates in terms of inputs misalignment and irregularity and defect (missing cells) in assembly of the array. We present simulation results based on semiconductor implementation of QCA with an intermediate dimensional dot of about 5 nm in size as opposed to magnetic dots of greater than 100 nm or molecular dots of 2–5Å. Our results clearly demonstrate the superior fault tolerance properties of the Block Majority Gate and its greater potential for a practical realization. We also show the possibility of designing fault tolerant QCA circuits by using Block Majority Gates.     

Automata Theory Based on Quantum Logic. (I)

We present a basic framework of automata theory based on quantum logic. Inparticular, we introduce the orthomodular lattice-valued (quantum) predicate ofrecognizability and establish some of its fundamental properties.     

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.     

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

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

A Link between Quantum Logic and Categorical Quantum Mechanics

Abramsky and Coecke (Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science, pp. 415–425, IEEE Comput. Soc., New York, 2004) have recently introduced an approach to finite dimensional quantum mechanics based on strongly compact closed categories with biproducts. In this note it is shown that the projections of any object A in such a category form an orthoalgebra Proj  A. Sufficient conditions are given to ensure this orthoalgebra is an orthomodular poset. A notion of a preparation for such an object is given by Abramsky and Coecke, and it is shown that each preparation induces a finitely additive map from Proj  A to the unit interval of the semiring of scalars for this category. The tensor product for the category is shown to induce an orthoalgebra bimorphism Proj  A×Proj  B→Proj (A ⊗ B) that shares some of the properties required of a tensor product of orthoalgebras. These results are established in a setting more general than that of strongly compact closed categories. Many are valid in dagger biproduct categories, others require also a symmetric monoidal tensor compatible with the dagger and biproducts. Examples are considered for several familiar strongly compact closed categories.     

用腔场中的二能级势阱离子实现量子逻辑门

利用光腔中的势阱粒子同时与外激光场和腔场发生相互作用的特性，我们提出了一种量子逻辑门的实现方案。在该方案中，我们采用文献[10-12]中的模型。文献[11-12]中实现的逻辑门是以离子内态和运动态作为量子比特，腔态充当辅助比特在计算过程中保持在基态。而[10]要求离子内态保持为基态，利用离子运动态和腔态构成量子比特。与文献[10-12]不同的是，我们实现的量子逻辑门是以粒子内态和腔态作为比特，而势阱离子的运动态作为辅助比特始终保持在基态。而且，我们对该方案的实验要求进行了讨论。     

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.     

Quantum Logic Gates and Cluster States with Four-level Atoms in Cavity QED

We propose a model to implement the two-qubit quantum logic gates, i.e., the quantum phase gate and the Controlled-NOT gate, and generate the atomic qubits cluster states with a large detuned interaction between four-level atoms and a single-mode cavity field. In the presented protocol, the quantum information is encoded on the stable ground states of the atoms, and the effect of decoherence from atomic spontaneous emission is negligible. In addition, the interaction between atoms and the cavity is large detuned, and the cavity is only virtually excited. Therefore, the scheme is insensitive to the cavity decay. The experimental feasibility of our proposal is also discussed.     

Quantum Computational Logics and Possible Applications

In quantum computational logics meanings of formulas are identified with quantum information quantities: systems of qubits or, more generally, mixtures of systems of qubits. We consider two kinds of quantum computational semantics: (1) a compositional semantics, where the meaning of a compound formula is determined by the meanings of its parts; (2) a holistic semantics, which makes essential use of the characteristic “holistic” features of the quantum-theoretic formalism. The compositional and the holistic semantics turn out to characterize the same logic. In this framework, one can introduce the notion of quantum-classical truth table, which corresponds to the most natural way for a quantum computer to calculate classical tautologies. Quantum computational logics can be applied to investigate different kinds of semantic phenomena where holistic, contextual and gestaltic patterns play an essential role (from natural languages to musical compositions).     

Typed Quantum Logic

The aim of this paper was to lift traditional quantum logic to its higher order version with the help of a type-theoretic method. A higher order axiomatic system is defined explicitly and then a sound and complete class of models is given. This is an attempt to provide a quantum counterpart of classical set theory or intuitionistic topos.     

Intuitionistic Quantum Logic of an <Emphasis Type="Italic">n</Emphasis>-level System

A decade ago, Isham and Butterfield proposed a topos-theoretic approach to quantum mechanics, which meanwhile has been extended by Döring and Isham so as to provide a new mathematical foundation for all of physics. Last year, three of the present authors redeveloped and refined these ideas by combining the C*-algebraic approach to quantum theory with the so-called internal language of topos theory (Heunen et al. in arXiv:0709.4364). The goal of the present paper is to illustrate our abstract setup through the concrete example of the C*-algebra M _n (?) of complex n×n matrices. This leads to an explicit expression for the pointfree quantum phase space Σ _n and the associated logical structure and Gelfand transform of an n-level system. We also determine the pertinent non-probabilisitic state-proposition pairing (or valuation) and give a very natural topos-theoretic reformulation of the Kochen–Specker Theorem.In our approach, the nondistributive lattice ?(M _n (?)) of projections in M _n (?) (which forms the basis of the traditional quantum logic of Birkhoff and von Neumann) is replaced by a specific distributive lattice \(\mathcal{O}(\Sigma_{n})\) of functions from the poset \(\mathcal{C}(M_{n}(\mathbb{C}))\) of all unital commutative C*-subalgebras C of M _n (?) to ?(M _n (?)). The lattice \(\mathcal{O}(\Sigma_{n})\) is essentially the (pointfree) topology of the quantum phase space Σ _n , and as such defines a Heyting algebra. Each element of \(\mathcal{O}(\Sigma_{n})\) corresponds to a “Bohrified” proposition, in the sense that to each classical context \(C\in\mathcal{C}(M_{n}(\mathbb{C}))\) it associates a yes-no question (i.e. an element of the Boolean lattice ?(C) of projections in C), rather than being a single projection as in standard quantum logic. Distributivity is recovered at the expense of the law of the excluded middle (Tertium Non Datur), whose demise is in our opinion to be welcomed, not just in intuitionistic logic in the spirit of Brouwer, but also in quantum logic in the spirit of von Neumann.     

Quantum walks and reversible cellular automata

We obtain a conserved quantity for a reversible cellular automaton derived from a discrete-time quantum walk in one dimension. As a corollary, we give detailed information regarding the evolution of the quantum walk.     

Quantum Computational Logic

A quantum computational logic is constructed by employing density operators on spaces of qubits and quantum gates represented by unitary operators. It is shown that this quantum computational logic is isomorphic to the basic sequential effect algebra [0, 1].     

An Operational Characterization for Optimal Observation of Potential Properties in Quantum Theory and Signal Analysis

Quantum logic introduced a paradigm shift in the axiomatization of quantum theory by looking directly at the structural relations between the closed subspaces of the Hilbert space of a system. The one dimensional closed subspaces correspond to testable properties of the system, forging an operational link between theory and experiment. Thus a property is called actual, if the corresponding test yields “yes” with certainty. We argue a truly operational definition should include a quantitative criterion that tells us when we ought to be satisfied that the test yields “yes” with certainty. This question becomes particularly pressing when we inquire how the usual definition can be extended to cover potential, rather than actual properties. We present a statistically operational candidate for such an extension and show that its representation automatically captures some essential Hilbert space structure. If it is the nature of observation that is responsible for the Hilbert space structure, then we should be able to give examples of theories with scope outside the domain of quantum theory, that employ its basic structure, and that describe the optimal extraction of information. We argue signal analysis is such an example. This work was supported by the Flemish Fund for Scientific Research (FWO) project G.0362.03N.