量子计算机进入实验阶段

首先简要介绍分层计算的制约;其次介绍最近量子信息的开发,在理论和实践两方面的通信和计算,诸如量子逻辑门、量子密码学、量子交缠性、超距传输的实验性实现、量子算法的首次实验性实现、量子因子分解、量子纪错码以及基于硅片的原子自旋量子计算机;最后讨论克服非相干性困难的方法。     

量子计算机进展

对近几年量子计算机从实验室走向实用化的重要进展作了一个简要综述。概述了量子计算机的优点,给出了不需要量子交缠的量子计算方法以及量子计算机的程序——量子幺正操作的特性,介绍在克服退相干所带来的困难方面所取得的进展以及大尺度和实用化方面的进展,最后给出概要的评述。     

三值量子基本门及其对量子Fourier变换的电路实现

理论上可以把量子基本门组合在一起来实现任何量子电路和构建可伸缩的量子计算机。但由于构建量子线路的量子基本门数量庞大,要正确控制这些量子门十分困难。因此,如何减少构建量子线路的基本门数量是一个非常重要和非常有意义的课题。提出采用三值量子态系统构建量子计算机,并给出了一组三值量子基本门的功能定义、算子矩阵和量子线路图。定义的基本门主要包括三值量子非门、三值控制非门、三值Hadamard门、三值量子交换门和三值控制CR_k门等。通过把量子Fourier变换推广到三值量子态,成功运用部分三值量子基本门构建出能实现量子Fourier变换的量子线路。通过定量分析发现,三值量子Fourier变换的线路复杂度比二值情况降低了至少50%,表明三值量子基本门在降低量子计算线路复杂度方面具有巨大优势。     

Mathematical Theory of Duality Quantum Computers

We present a mathematical theory for a new type of quantum computer called a duality quantum computer that has recently been proposed. We discuss the nonunitarity of certain circuits of a duality quantum computer and point out a paradoxical situation that occurs when mixed states are considered. It is shown that a duality quantum computer can measure itself without needing a separate measurement apparatus to determine its final state.      

Quantum Communication and Information Processing with Quantum Dots

This paper reviews the single photon sources based on semiconductor quantum dots and their applications to quantum information systems. By optically pumping a system consisting of a semiconductor single quantum dot confined in a monolithic microcavity, it is possible to produce a single photon pulse stream at the Fourier transform limit with a negligible jitter. This single photon source is not only useful for BB84 quantum key distribution (QKD), but also find applications in other quantum information systems such as Ekert91/BBM92 QKD and quantum teleportation gate linear optical quantum computers.     

Scaling and Renormalization in Fault-Tolerant Quantum Computers

This work is concerned with phrasing the concepts of fault-tolerant quantum computation within the framework of disordered systems, Bernoulli site percolation in particular. We show how the so-called threshold theorems on the possibility of fault-tolerant quantum computation with constant error rate can be cast as a renormalization (coarse-graining) of the site percolation process describing the occurrence of errors during computation. We also use percolation techniques to derive a trade-off between the complexity overhead of the fault-tolerant circuit and the threshold error rate. PACS: 03.67.Pp; 03.67.Lx     

Quantum Computation Violates Mirror Symmetry

The CNOT gate is asymmetric with respect to parity. It requires interaction with the environment, and cannot be realized as an isolated quantum collision.     

Scalable Parallel Matrix Multiplication on Distributed Memory Parallel Computers

Consider any known sequential algorithm for matrix multiplication over an arbitrary ring with time complexity O(N^α), where 2<α3. We show that such an algorithm can be parallelized on a distributed memory parallel computer (DMPC) in O(log N) time by using N^α/log N processors. Such a parallel computation is cost optimal and matches the performance of PRAM. Furthermore, our parallelization on a DMPC can be made fully scalable, that is, for all 1pN^α/log N, multiplying two N×N matrices can be performed by a DMPC with p processors in O(N^α/p) time, i.e., linear speedup and cost optimality can be achieved in the range [1..N^α/log N]. This unifies all known algorithms for matrix multiplication on DMPC, standard or non- standard, sequential or parallel. Extensions of our methods and results to other parallel systems are also presented. For instance, for all 1p N^α /log N, multiplying two N×N matrices can be performed by p processors connected by a hypercubic network in O(N^α/p+(N²/p^2/α)(log p)^2(α−1)/α) time, which implies that if p=O(N^α/(log N)^{2(α−1)/(α−2)}), linear speedup can be achieved. Such a parallelization is highly scalable. The above claims result in significant progress in scalable parallel matrix multiplication (as well as solving many other important problems) on distributed memory systems, both theoretically and practically.     

Quantum optical realization of classical linear stochastic systems

The purpose of this paper is to show how a class of classical linear stochastic systems can be physically implemented using quantum optical components. Quantum optical systems typically have much higher bandwidth than electronic devices, meaning faster response and processing times, and hence have the potential for providing better performance than classical systems. A procedure is provided for constructing the quantum optical realization. The paper also describes the use of the quantum optical realization in a measurement feedback loop. Some examples are given to illustrate the application of the main results.     

基于量子克隆的二面体群隐含子群问题量子算法的研究

基于最短向量问题的格公钥密码体制是典型的抗量子计算密码体制。格的唯一最短向量问题可转化为二面体群的隐含子群问题。有效地求解二面体群的隐含子群问题可攻破基于格的唯一最短向量问题的公钥密码体制。Kuperberg提出了二面体群隐含子群问题的半指数级量子算法。通过研究Kuperberg量子算法,利用概率量子克隆,文中提出了二面体群隐含子群问题的多项式时间量子算法。     

量子计算的表象无关性探讨

大因数分解和数据检索量子算法的提出带来了量子计算与量子信息的研究高潮。由于量子计算具有并行性、不可克隆性及量子态的不可测性,使得量子信息及量子计算在某些方面具有传统计算所无法比拟的优势。量子的态空间作为一个完备的Hilbert空间,在定义了内积和范数并赋予相应的物理意义后,就构成了理论意义上的量子计算系统。该文抽象了量子系统的本质,描述了量子计算及遵循的计算规则以及如何实现量子信息表示和进行信息的处理与测量,从理论上阐述了量子态系统迁移的线性同构和等距同构,说明了量子计算与量子信息的研究与具体的量子表象空间无关。     

基于混沌量子进化算法的单交叉口信号控制

城市道路各交叉口交通信号的配时优化和协同控制直接影响整个城市的交通状况.本文以单交叉口模型的交通信号控制问题为背景,构造了以单交叉口滞留的车辆数最少为目标的优化模型.用混沌量子进化算法进行仿真数据求解,得到实时控制的配时方案,并与其它算法的仿真结果进行比较,结果表明该算法对单交叉口的信号配时优化是非常有效的.     

基于通用量子门的量子遗传算法及应用

为加快量子遗传算法的参数更新速度,简化遗传操作步骤,提出了一种基于通用量子门的量子遗传算法（Quantum Genetic Algorithm with Universal Quantum Gate,UQGA）。该方法以通用量子门为逻辑计算单位,对染色体进行遗传操作。利用Hadamard门进行基础变换;通用量子门通过新的旋转角度函数,对各个基因位进行选择、变异操作;通过求解适应度函数,得到全局最优解;同时,算法经数学证明是收敛的。该算法应用到函数极值搜索和Iris数据集特征选择中。实验结果表明,UQGA具有较好的全局搜索和特征选择性能,尤其是在收敛速度、运算时间和分类准确率方面明显优于普通量子遗传算法和普通遗传算法。     

On the Role of Hadamard Gates in Quantum Circuits

We study a reduced quantum circuit computation paradigm in which the only allowable gates either permute the computational basis states or else apply a “global Hadamard operation”, i.e. apply a Hadamard operation to every qubit simultaneously. In this model, we discuss complexity bounds (lower-bounding the number of global Hadamard operations) for common quantum algorithms: we illustrate upper bounds for Shor’s Algorithm, and prove lower bounds for Grover’s Algorithm. We also use our formalism to display a gate that is neither quantum-universal nor classically simulable, on the assumption that Integer Factoring is not in BPP.     

A Presentation of Quantum Logic Based on an and then Connective

When a physicist performs a quantic measurement, new informationabout the system at hand is gathered. This article studies thelogical properties of how this new information is combined withprevious information. It presents Quantum Logic as a propositionallogic under two connectives: negation and the and then operationthat combines old and new information. The and then connectiveis neither commutative nor associative. Many properties of thislogic are exhibited, and some small elegant subset is shownto imply all the properties considered. No independence or completenessresult is claimed. Classical physical systems are exactly characterizedby the commutativity, the associativity, or the monotonicityof the and then connective. Entailment is defined in this logicand can be proved to be a partial order. In orthomodular lattices,the operation proposed by Finch in [3] satisfies all the propertiesstudied in this article. All properties satisfied by Finch's;operation in modular lattices are valid in Quantum Logic. Itis not known whether all properties of Quantum Logic are satisfiedby Finch's; operation in modular lattices. Non-commutative,non-associative algebraic structures generalizing Boolean algebrasare defined, ideals are characterized and a homomorphism theoremis proved.     

The Quantum Complexity of Set Membership

   Abstract. We study the quantum complexity of the static set membership problem: given a subset S (|S| ≤ n ) of a universe of size m ( >> n ), store it as a table, T: {0,1} ^r --> {0,1} , of bits so that queries of the form ``Is x in S ?' can be answered. The goal is to use a small table and yet answer queries using few bit probes. This problem was considered recently by Buhrman et al. [BMRV], who showed lower and upper bounds for this problem in the classical deterministic and randomized models. In this paper we formulate this problem in the ``quantum bit probe model'. We assume that access to the table T is provided by means of a black box (oracle) unitary transform O _T that takes the basis state | y,b > to the basis state | y,b