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.     

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

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.     

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

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.     

Adiabatic Quantum Gates

We discuss the logic implementation of quantum gates in the framework of the quantum adiabatic method, which uses the language of ground states, spectral gaps and Hamiltonians instead of the standard unitary transformation language.     

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

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.     

Qubit Semantics and Quantum Trees

In the qubit semantics the meaning of any sentence α is represented by a quregister: a unit vector of the n–fold tensor product ⊗ⁿ ℂ², where n depends on the number of occurrences of atomic sentences in α (see Cattaneo et al.). The logic characterized by this semantics, called quantum computational logic (QCL), is unsharp, because the noncontradiction principle is violated. We show that QCL does not admit any logical truth. In this framework, any sentence α gives rise to a quantum tree, consisting of a sequence of unitary operators. The quantum tree of α can be regarded as a quantum circuit that transforms the quregister associated to the occurrences of atomic subformulas of α into the quregister associated to α.     

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

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

Unstructured Adiabatic Quantum Search

In the adiabatic quantum computation model, a computational procedure is described by the continuous time evolution of a time dependent Hamiltonian. We apply this method to the Grover's problem, i.e., searching a marked item in an unstructured database. Classically, the problem can be solved only in a running time of order O(N) (where N is the number of items in the database), whereas in the quantum model a speed up of order has been obtained. We show that in the adiabatic quantum model, by a suitable choice of the time-dependent Hamiltonian, it is possible to do the calculation in constant time, independent of the the number of items in the database. However, in this case the initial time-complexity of is replaced by the complexity of implementing the driving Hamiltonian.     

Quantum Algorithms in Hilbert Database

A fast quantum algorithm for a search and pattern recognition in a Hilbert space memory structure is proposed. All the memory information is mapped onto a unitary operator acting upon a quantum state which represents a piece of information to be retrieved. As a result of only one quantum measurement, the address of the required information encoded in a number of the corresponding row of the unitary matrix is determined. By combining direct and dot products, the dimensionality of the memory space can be made exponentially large, using only linear resources. However, since the preprocessing, i.e., mapping the memory information into a Hilbert space can appear to be exponentially expensive, the proposed algorithm will be effective for NASA applications when the preprocessing is implemented on the ground, while the memory search is performed on remote objects.     

Maximum Speed of Quantum Evolution

In this paper, we discuss the question of the minimum time needed for any state of a given quantum system to evolve into a distinct (orthogonal) state. This problem is relevant to deriving physical limits in quantum computation and quantum information processing. Here, we consider both cases of nonadiabatic and adiabatic evolution and we derive the Hamiltonians corresponding to the minimum time evolution predicted by the Margolus–Levitin theorem.     

Measurement-Based Interference in Quantum Computation

The interference has been measured by the visibility in two-level systems,which,however,does not work for multi-level systems.We generalize a measure of the interference based on decoherence process,consistent with the visibility in qubit systems.By taking cluster states as examples,we show in the one-way quantum computation that the gate fidelity is proportional to the interference of the measured qubit and is inversely proportional to the interference of all register qubits.We also find that the interference increases with the number of the computing steps.So we conjecture that the interference may be the source of the speedup of the one-way quantum computation.     

Quantum Density Peak Clustering Algorithm

A widely used clustering algorithm, density peak clustering (DPC), assigns different attribute values to data points through the distance between data points, and then determines the number and range of clustering by attribute values. However, DPC is inefficient when dealing with scenes with a large amount of data, and the range of parameters is not easy to determine. To fix these problems, we propose a quantum DPC (QDPC) algorithm based on a quantum DistCalc circuit and a Grover circuit. The time complexity is reduced to O(log(N2)+6N+N), whereas that of the traditional algorithm is O(N2). The space complexity is also decreased from O(N·⌈logN⌉) to O(⌈logN⌉).     

Measurement-Based Interference in Quantum Computation

The interference has been measured by the visibility in two-level systems, which, however, does not work for multi-level systems. We generalize a measure of the interference based on decoherence process, consistent with the visibility in qubit systems. By taking cluster states as examples, we show in the one-way quantum computation that the gate fidelity is proportional to the interference of the measured qubit and is inversely proportional to the interference of all register qubits. We also find that the interference increases with the number of the computing steps. So we conjecture that the interference may be the source of the speedup of the one-way quantum computation.     

量子计算与量子模拟

量子计算和量子模拟在过去的几年里发展迅速,今后涉及多量子比特的量子计算和量子模拟将是一个发展的重点.本文回顾了该领域的主要进展,包括量子多体模拟、量子计算、量子计算模拟器、量子计算云平台、量子软件等内容,其中量子多体模拟又涵盖量子多体动力学、时间晶体及多体局域化、量子统计和量子化学等的模拟.这些研究方向的回顾是基于对现阶段量子计算和量子模拟研究特点的考虑,即量子比特数处于中等规模而量子操控精度还不具有大规模逻辑门实现的能力,研究处于基础科研和实用化的过渡阶段,因此综述的内容主要还是希望管窥今后的发展.