量子计算机:量子算法与物理实现

量子算法与物理实现是量子计算机研究中的两个基本问题。本文首先总结了相关领域的主要进展,并讨论了有代表性的量子算法,特别介绍了用于求解线性方程组的量子算法,分析了影响新量子算法提出的因素。然后,探讨了物理实现的迪文森佐判据,并介绍了典型的实现方案及性能比较。同时,也关注了对量子计算机研究持有异议的观点。最后,对量子计算机的新研究方向作了探讨。     

混合量子进化算法及其应用

文章将量子进化算法(QEA)和粒子群算法(PSO)互相结合,提出了两种混合量子进化算法。第一种算法叫做嵌入式粒子群量子进化算法,其主要思想是将简化的PSO进化方程嵌入QEA的进化操作中,简化了QEA算法的结构,增强了QEA跳出局部极值的能力。第二种算法叫做量子二进制粒子群算法,其主要思想是将QEA中的量子染色体的概念引入二进制粒子群算法(BPSO),提高了BPSO算法保持种群多样性的能力和运算速度。通过对0-1背包问题和多用户检测问题的求解表明,新的算法不仅操作更简单,而且全局搜索能力有了显著的提高。     

改进实数编码量子进化算法及其在参数估计中的应用

借鉴量子计算的相关概念和原理,提出一种改进实数编码量子进化算法(IRCQEA).算法的核心是依据染色体的具体形式和目标函数的梯度信息设计互补变异进化染色体,以实现局部搜索和全局搜索的平衡;根据算法的进化过程动态缩小搜索空间,以加快收敛速度.对标准数值优化问题的求解结果表明,该算法具有寻优能力强、搜索精度高和稳定性好等优点.以非线性系统参数估计问题为例进行的仿真实验表明,所提出的算法能够有效提高估计参数的精度.     

求解背包问题的演化算法

背包问题(Knapsack Problem, KP)是一类著名的组合优化问题,也是一类NP难问题,它包括0-1背包问题、有界背包问题、多维背包问题、多背包问题、多选择背包问题、二次背包问题、动态背包问题和折扣背包问题等多种形式,在众多领域有着广泛的应用.演化算法(EAs)是一类有效的快速近似求解KP的算法.本文对近十余年来利用EAs求解KP的研究情况进行一个较为详细的总结,它一方面讨论了利用EAs求解各种KP问题时个体的编码方法与处理不可行解的有效方法,另一方面为今后进一步利用最新提出的EAs求解KP问题提供一个可借鉴的思路.     

Evolutionary design of Evolutionary Algorithms

Manual design of Evolutionary Algorithms (EAs) capable of performing very well on a wide range of problems is a difficult task. This is why we have to find other manners to construct algorithms that perform very well on some problems. One possibility (which is explored in this paper) is to let the evolution discover the optimal structure and parameters of the EA used for solving a specific problem. To this end a new model for automatic generation of EAs by evolutionary means is proposed here. The model is based on a simple Genetic Algorithm (GA). Every GA chromosome encodes an EA, which is used for solving a particular problem. Several Evolutionary Algorithms for function optimization are generated by using the considered model. Numerical experiments show that the EAs perform similarly and sometimes even better than standard approaches for several well-known benchmarking problems.     

Score-Based Resampling Method for Evolutionary Algorithms

In this paper, a gene-handling method for evolutionary algorithms (EAs) is proposed. Such algorithms are characterized by a nonanalytic optimization process when dealing with complex systems as multiple behavioral responses occur in the realization of intelligent tasks. In generic EAs which optimize internal parameters of a given system, evaluation and selection are performed at the chromosome level. When a survived chromosome includes noneffective genes, the solution can be trapped in a local optimum during evolution, which causes an increase in the uncertainty of the results and reduces the quality of the overall system. This phenomenon also results in an unbalanced performance of partial behaviors. To alleviate this problem, a score-based resampling method is proposed, where a score function of a gene is introduced as a criterion of handling genes in each allele. The proposed method was empirically evaluated with various test functions, and the results show its effectiveness.      

Quantum Algorithms for Matching Problems

We present quantum algorithms for the following matching problems in unweighted and weighted graphs with n vertices and m edges:

Towards Scalable Linear-Optical Quantum Computers

Scalable quantum computation with linear optics was considered to be impossible due to the lack of efficient two-qubit logic gates, despite the ease of implementation of one-qubit gates. Two-qubit gates necessarily need a non-linear interaction between the two photons, and the efficiency of this non-linear interaction is typically very small in bulk materials. However, it has recently been shown that this barrier can be circumvented with effective non-linearities produced by projective measurements, and with this work linear-optical quantum computing becomes a new avenue towards scalable quantum computation. We review several issues concerning the principles and requirements of this scheme. PACS: 03.67.Lx, 03.67.Pp, 42.50.Dv, 42.65.Lm     

量子计算机进入实验阶段

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

量子算法与量子衍生算法

随着经典计算发展日趋缓慢,量子计算正逐渐成为研究领域的关注热点.该文简要介绍了量子计算的基本原理.接着,从当前量子计算领域中的两个活跃研究方向——量子算法和量子衍生技术研究出发对整个量子算法领域主要发展脉络进行梳理并总结目前量子计算研究的发展规律.最后,该文针对这两个方向提出了若干量子计算领域的发展趋势.通过对量子计算研究领域的综述和展望,对后续量子计算研究发展具有一定的指导意义.     

求解随机时变背包问题的精确算法与进化算法

随机时变背包问题(RTVKP)是一种新的动态背包问题,也是一种新的动态组合优化问题,目前它的求解算法主要是动态规划的精确算法、近似算法和遗传算法.本文首先利用动态规划提出了一个求解RTVKP问题的新精确算法,对算法时间复杂度的比较结果表明:它比已有的精确算法更适于求解背包载重较大的一类RTVKP实例.然后,分别基于差分演化和粒子群优化与贪心修正策略相结合,提出了求解RTVKP问题的两个进化算法.对5个RTVKP实例的数值计算结果比较表明: 精确算法一般不宜求解大规模的RTVKP实例,而基于差分演化、粒子群优化和遗传算法与贪心修正策略相结合的进化算法却不受实例规模与数据大小的影响,对于振荡频率大且具有较大数据的大规模RTVKP实例均能求得的一个极好的近似解.     

量子计算机进展

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

基于量子计算机的数据库搜索

Grover提出的量子搜索算法,可以用O(N1/2)的时间复杂度完成对规模为N的非结构化数据集的搜索,这在经典计算机上需要O(N)的复杂度。其中量子黑盒(又称为Oracle)依赖于具体问题,根据数据库搜索的要求,设计了量子黑盒的内部结构和相应的量子线路,给出了适合于数据库搜索的量子算法。     

约束优化进化算法

约束优化问题是科学和工程应用领域经常会遇到的一类数学规划问题.近年来,约束优化问题求解已成为进化计算研究的一个重要方向.从约束优化进化算法=约束处理技术+进化算法的研究框架出发,从约束处理技术和进化算法两个基本方面对约束优化进化算法的研究及进展进行了综述.此外,对约束优化进化算法中的一些重要问题进行了探讨.最后进行了各种算法的比较性总结,深入分析了目前约束优化进化算法中亟待解决的问题,并指出了值得进一步研究的方向.     

高维多目标进化算法研究综述

传统的多目标进化算法能够有效地解决2个或3个目标的优化问题,但当优化目标超过4维即具有高维目标时,其优化效果将大大下降,因此高维多目标进化算法的研究得到了较多的关注.鉴于此,对高维多目标进化算法的研究进展进行系统地分类综述,分析了高维目标对优化算法造成的困难以及改进的可视化技术;总结了各类算法的特点与缺陷,并给出进一步可能的研究方向.     

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.      

Parallel Algorithms for Image Template Matching on Hypercube SIMD Computers

This correspondence presents several parallel algorithms for image template matching on an SIMD array processor with a hypercube interconnection network. For an N by N image and an M by M window, the time complexity is reduced from O(N2M2) for the serial algorithm to O(M2/K2 + M * log2 N/K + log2 N * log2 K) for the N2K2-PE system (1 ? K ? M), or to O(N2M2/L2) for the L2-PE system (L ? N). With efficient use of the inter-PE communication network, each PE requires only a small local memory, many unnecessary data transmissions are eliminated, and the time complexity is greatly reduced.     

多目标进化算法性能评价指标研究综述

多目标进化算法根据性能评价指标衡量其优劣,主要从算法所求解集的质量、算法求解效率以及算法鲁棒性三方面来评价,并侧重于解集的质量,现有的相关工作缺乏对评价指标数学性质的分析.本文将评价指标按性能标准分为四类:计数指标、收敛性指标、多样性指标、综合性指标,其中计数指标统计符合指标要求的解个数或比例,收敛性指标衡量解集与参考...