量子计算及量子算法研究进展

量子相干性和量子纠缠等特性为量子计算带来了完全不同于经典计算的独特运算方式,量子计算表现出的并行性更是令经典运算望尘莫及。Shor算法的提出完全展示了量子算法在解决某些经典问题时的优势,接踵而至的Grover搜索算法进一步诠释了量子计算的威力。此后,算法“量子化”在国际上掀起了研究的热潮,尤其在量子智能算法方面取得了不错的成果。文章首先介绍量子计算的发展现状和基本原理;然后列举三种典型的量子算法,展示量子计算的优越性;最后介绍该领域的研究进展。     

量子退火算法研究进展

在数学和应用领域,量子退火算法是一类新的量子优化算法.不同于经典模拟退火算法利用热波动来搜寻问题的最优解,量子退火算法利用量子波动产生的量子隧穿效应来使算法摆脱局部最优,而实现全局优化.在已有的研究中,量子退火算法在某些问题上展现出良好的优化效果.系统地综述了量子退火算法的基本原理和近年来的主要研究进展,较为详细地介绍了几个主要的量子退火算法,对量子退火算法的优点和可能的不足进行了分析评述,并对今后的研究方向进行了展望.     

量子计算进展与展望*

评述量子计算的历史、研究现状以及进一步发展的方向.着重论述量子算法的机理,对已知量子算法特征进行总结分析;归纳量子计算与经典智能计算的结合模式,比较其与传统智能计算的异同.在总结量子计算存在问题的基础上,探讨了今后的研究方向.     

量子谱回归算法

子空间学习是机器学习领域的重要研究方向.为了降低子空间学习的复杂度,Cai等人提出了谱回归降维框架,并针对结合标签构造对应图的子空间学习提出了高效谱回归.近年来,量子计算的发展使进一步降低子空间学习算法的复杂度成为了可能.Meng等人率先提出了量子谱回归算法(MYXZ算法).MYXZ算法用了稀疏哈密顿量模拟技术来处理由权重矩阵生成的矩阵,但这个矩阵在较多的情况下是稠密矩阵.针对这种情况,指出了MYXZ算法的局限性,提出了一个改进的量子谱回归算法.改进算法采用了量子奇异值估计技术,在处理稠密矩阵时相对MYXZ算法有多项式加速.另外,提出了一个新的量子算法,对经典的高效谱回归进行加速.新算法能处理的这类问题是MYXZ算法无法处理的.新算法利用了量子岭回归和量子矩阵向量乘技术,在相同的参数条件下相对经典算法具有多项式加速效果.     

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

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

量子计算与量子计算机

量子计算的强大运算能力使得量子计算机具有广阔的应用前景。该文简要介绍了量子计算的发展现状和基本原理,列举了典型的量子算法,阐明了量子计算机的优越性,最后预测了量子计算及量子计算机的应用方向。     

量子优化算法综述

量子优化是量子计算领域近年来颇受关注的一个研究分支,主要研究如何利用量子计算加速优化问题的求解.根据优化问题的变量是否连续分类梳理量子优化算法,侧重介绍连续变量优化算法.通过对现存工作的调研梳理得到一些观察:1)5～20年前的研究主要集中在离散变量的量子优化技术,近5年的研究则更关注连续变量的量子优化技术;2)量子优化使用的主要基础技术都是10～20年前提出的,在基础技术方面需要进一步革新;3)量子优化算法相比于对应的经典算法通常在理论上有加速优势,既有体现在时间复杂度的加速,也有体现在查询复杂度的加速,但仍然有待更为严格的理论分析;4)优化领域依然存在许多值得量子计算研究人员探索的问题,特别是非凸优化领域,亦即经典计算上认为较难的优化问题.     

基于量子傅里叶变换算法的量子乘法器

乘法运算是许多量子算法中的基本运算之一.为了实现量子乘法运算并且尽可能少地使用辅助量子比特,提出了一种基于量子傅里叶变换算法的量子乘法器.在量子傅里叶加法电路基础上,设计了量子移位电路,并实现了两个n位二进制无符号数相乘的量子电路,其时间复杂度为O(n3).使用IBM提供的开源量子计算工具包Qiskit分别验证了两个2...     

量子进化算法在生产调度中的应用综述

量子进化算法是量子计算和进化计算相融合的产物,具有种群多样性好、全局搜索能力强、收敛速度快等优点。综述了量子进化算法在Job-Shop调度、Flow-Shop调度、车辆路径规划、项目调度等生产调度领域中的应用现状,讨论了面向生产调度的量子进化算法的编码转换方式和进化策略以及存在的问题,并指明了其进一步的研究方向。     

绝热量子优化算法研究进展

绝热量子优化计算于2001年首次提出,它基于绝热量子演化研究NPC组合优化问题,是量子计算的领域热点。主要回顾了绝热量子优化算法研究领域所取得的进展,阐述绝热量子优化算法研究所采用的主要方法和关键技术,最后分析绝热量子优化计算的发展趋势。     

绝热量子搜索算法中的纠缠与能量分析

为了进一步研究量子纠缠与量子计算速度及能量的关系,通过计算von Neumann纠缠熵,分析了时间复杂度分别为O(N )和O(1)的绝热量子搜索算法的量子纠缠度随时间的变化关系,并对两者进行了比较.实验结果表明,量子纠缠对绝热量子计算的运行时间具有明显的影响,较大的纠缠可以导致更短的运行时间,反之亦然.同时对纠缠与能量的关系给出了一般性解释,即注入能量导致系统的纠缠增大,并因此缩短算法的运行时间.此外还分析了纠缠与量子系统初态的关系.实验表明系统初态形式不同,其纠缠度也不一样.初态为等幅叠加态的算法涉及的纠缠度明显大于初态为非等幅叠加态的算法.     

Progress in Quantum Algorithms

We discuss the progress (or lack of it) that has been made in discovering algorithms for computation on a quantum computer. Some possible reasons are given for the paucity of quantum algorithms so far discovered, and a short survey is given of the state of the field. PACS: 03.67.Lx     

基于遗传算法的硬聚类算法改进

硬聚类算法HCM求解的结果通常都是局部的最优解,当模糊集合间的运算采用传统定义的时候,它的聚类结果中还会存在无意义的聚类集。本文通过研究表明,在HCM聚类算法中应用遗传算法,可以在一定程度上避免硬聚类算法收敛到局部最优解。因此,本文将遗传算法应用于硬聚类算法,并设计了相应的算法。但是,考虑到本算法实现时的开销 销和效率,又对该算法进行了改进,并最终提出一种新的算法--CHCM聚类算法。测试数据表明,采用改进后的聚类算法的结果90％以上能够取得全局的最优解,远远超过了采用硬聚类算法时所取得全局最优解的次数,证明了本算法的可推广性。     

Natural Majorization of the Quantum Fourier Transformation in Phase-Estimation Algorithms

We prove that majorization relations hold step by step in the Quantum Fourier Transformation (QFT) for phase-estimation algorithms. Our result relies on the fact that states which are mixed by Hadamard operators at any stage of the computation only differ by a phase. This property is a consequence of the structure of the initial state and of the QFT, based on controlled-phase operators and a single action of a Hadamard gate per qubit. The detail of our proof shows that Hadamard gates sort the probability distribution associated to the quantum state, whereas controlled-phase operators carry all the entanglement but are immaterial to majorization. We also prove that majorization in phase-estimation algorithms follows in a most natural way from unitary evolution, unlike its counterpart in Grover's algorithm. PACS: 03.67.-a, 03.67.Lx     

基于量子遗传算法的高效匹配搜索策略

在大规模源图像上进行图像匹配时,最佳匹配点的搜索策略是匹配算法时间性能的决定因素,设计高效匹配搜索策略是提高算法性能的关键。为了减少搜索时间和提高匹配实时性,本文基于匹配源图像划分和量子遗传算法基本原理,提出了面向大规模源图像匹配的目标淘汰搜索策略TESS。TESS将基于整幅源图像的全空间随机搜索的过程变成基于各个子图像的子空间并行搜索和逐步淘汰的过程,实现了匹配区域粗定位与匹配点精搜索的有效结合,从而大大缩短了最佳匹配点的搜索时间。实验结果表明,TESS搜索策略带来了匹配速度的极大提高,且时间加速比随匹配源图像规模的增大而增大。     

Quantum Algorithms for Learning and Testing Juntas

In this article we develop quantum algorithms for learning and testing juntas, i.e. Boolean functions which depend only on an unknown set of k out of n input variables. Our aim is to develop efficient algorithms: (1) whose sample complexity has no dependence on n, the dimension of the domain the Boolean functions are defined over; (2) with no access to any classical or quantum membership (“black-box”) queries. Instead, our algorithms use only classical examples generated uniformly at random and fixed quantum superpositions of such classical examples; (3) which require only a few quantum examples but possibly many classical random examples (which are considered quite “cheap” relative to quantum examples). Our quantum algorithms are based on a subroutine FS which enables sampling according to the Fourier spectrum of f; the FS subroutine was used in earlier work of Bshouty and Jackson on quantum learning. Our results are as follows: (1) We give an algorithm for testing k-juntas to accuracy ε that uses O(k/ϵ) quantum examples. This improves on the number of examples used by the best known classical algorithm. (2) We establish the following lower bound: any FS-based k-junta testing algorithm requires queries. (3) We give an algorithm for learning k-juntas to accuracy ϵ that uses O(ϵ⁻¹ k log k) quantum examples and O(2 ^k log(1/ϵ)) random examples. We show that this learning algorithm is close to optimal by giving a related lower bound. Supported in part by NSF award CCF-0347282, by NSF award CCF-0523664, and by a Sloan Foundation Fellowship.     

基于量子漫步的图形匹配算法进展与展望

图形匹配是图形研究中的重要问题,目前的经典算法受限于存储资源和计算复杂度,未能提供有效的解决方法.基于量子效应,将图形信息存储于量子比特,不仅能够极大减少存储资源的消耗,而且对量子比特进行操作可实现对存储信息的并行计算,从而为有效解决图形匹配问题提供了新的可能.量子漫步作为量子计算中的重要模型,是分析研究图形问题的有效工具.总结了量子计算的特点,介绍了量子漫步的2种模型并对二者进行了比较.然后对目前已有的基于量子漫步的图形匹配算法进行了介绍,对其算法思想、计算过程和优缺点进行了描述,同时还提出了相应的改进思路.在总结分析目前研究存在问题的基础上,探讨了今后的研究方向.     

Quantum Algorithms for Highly Structured Search Problems

We consider the problem of identifying a base k string given an oracle which returns information about the number of correct components in a query, specifically, the Hamming distance between the query and the solution, modulo r = max{2, 6 – k}. Classically this problem requires (nlog _r k) queries. For k {2, 3, 4}, we construct quantum algorithms requiring only a single quantum query. For k > 4, we show that O(k) quantum queries suffice. In both cases the quantum algorithms are optimal. PACS: 03.67.Lx