求最优装载的量子算法

随着Grover量子搜索算法的不断发展,它的实际应用价值也在逐渐体现.通过介绍量子并行计算和量子算法的基本思想以及对改进的Grover搜索算法进行研究的基础上,分析给出了一个时间复杂度为O(√N)的求解最优装载问题的量子算法.对于最优装载问题,分别用经典计算机上的贪心算法和量子算法来求解,得出了这两种算法的时间复杂度,从而可以看出量子算法相对于经典算法具有更快的搜索速度.     

改进的多目标元素量子搜索算法

Grover量子搜索算法解决了未加排序的数据库搜索问题,在2ⁿ个元素中搜索M个目标元素,其计算复杂度为O（（2ⁿ/M）^-2）,相对于经典算法实现了二次加速,但是,当目标元素个数接近2ⁿ/2时该算法成功率只达到50%。从任意相位的Grover变换从发,给出一种改进的多目标元素量子搜索算法,该算法在目标元素个数M≥2ⁿ/4时,只用一次Grover变换就能以概率1完成搜索。     

逼近全概率Grover算法的搜索次数计算

文章研究了Grover量子搜索算法,该算法进行o(N√)次搜索后只能以大于0.5的概率获得正确结果,并且没有确定最佳的搜索次数。针对这两个问题,提出了一种确定搜索次数的计算方法,使Grover算法逼近全概率地获得搜索目标。仿真结果表明,该计算方法行之有效。     

Grover算法改进与应用综述

量子信息科学是一门新兴的交叉学科,它在信息领域中有着独特的性能,在提高运算速度、确保信息安全、增大信息容量和提高检测精度等方面可突破现有经典信息系统的极限.Grover算法是一类典型的量子算法,能够对任意经典暴力穷举搜索问题实现二次加速,进一步推动了量子计算的发展,如何有效地改进和应用Grover算法成为量子计算的一个重要研究领域.文中综述了Grover算法的优化改进和应用,对Grover算法在不同领域应用及不同方面的改进进行了概述,并对Grover算法未来的改进和相关应用的若干研究方向进行了探讨.     

背包问题的量子计算算法

背包问题属于NP完全问题,经典算法对规模为n的背包问题求解的时间复杂度为O（n²）。给出了基于固定相位的背包问题量子计算算法,证明了该算法在多解的情况下,能够以不低于98%的成功率在O（√N/M）步完成对规模为n的背包问题求解（M是解的数目）,而基于原始Grover算法的背包问题量子计算算法计算复杂度为O（√N/M）,成功率是50%～100%。     

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

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

多目标元素的量子搜索算法

Grover量子搜索算法解决了未加整理的数据库搜索问题,在2ⁿ个元素中搜索M个目标元素时,计算复杂度为O（√2ⁿ/M）,相对于经典算法实现了二次加速,但Grover算法在目标元素个数接近2ⁿ/2时成功率较低。提出了一种针对多目标元素的量子搜索算法,当目标元素个数大于2ⁿ/3时,能以不低于97.36%的概率找到目标元素。     

基于Grover算法的图着色问题求解

Grover量子搜索算法是针对非结构化搜索问题设计的著名量子算法，可用于解决图着色、最短路径排序等问题，也可以有效破译密码系统。图着色问题是最著名的NP-完全问题之一，文中首先将图着色问题转化为数学上的无向图；然后采用布尔表达式将其转换为布尔可满足性问题，介绍了量子线路图解决布尔表达式的步骤原理以及图着色问题向布尔可满足性问题的转换过程；最后在IBMQ云平台上，对三节点的2-着色问题以及4-着色问题进行模拟仿真。实验结果验证了使用Grover算法求解图着色问题的可行性，在搜索空间为8的2-着色问题和搜索空间为64的4-着色问题中，分别以近82%和97%的成功概率搜索到目标项。文中使用Grover算法解决了4-着色问题，拓展了该算法在此问题领域上的实验规模，且改进了现有实验的量子线路，使量子位成本更低，结果的成功率更高，展示了Grover算法在大型搜索问题中显著的加速效果。     

Grover量子搜索算法的线路优化

Grover算法是能够高效查找到目标态的量子搜索算法，但随着搜索数据量的增大，它的量子线路面临着复杂的门分解问题。在如今的NISQ时代资源非常有限，因此线路的深度成为一种重要的度量标准。介绍了一种基于分治思想的二阶段量子搜索算法，能够在量子计算机上快速地并行运行。提出一种线路优化方法，应用块级的Oracle线路来减少迭代次数。将该方法与分治思想相结合，提出2P-Grover算法。在量子计算框架Cirq上进行模拟实验，与Grover算法进行对比。实验结果表明，2P-Grover算法能够使线路的深度至少减少60%,并且保持了较高的搜索成功率。     

求列表极小值的量子算法

求列表极小值的算法具有广泛的应用。如果能够找到有效的求列表极小值的量子算法,那就可以找到求列表极大值的量子算法,从而与Grover量子搜索算法、求中值量子算法一起构成一套有效的量子算法体系。这些算法将构成用量子计算求解实际应用问题的核心和基础,并为量子算法的进一步研究提供坚实的基础。该文给出了一个时间复杂度为O(N√)的求列表极小值的量子算法。     

Improving Gate-Level Simulation of Quantum Circuits

Simulating quantum computation on a classical computer is a difficult problem. The matrices representing quantum gates, and the vectors modeling qubit states grow exponentially with an increase in the number of qubits. However, by using a novel data structure called the Quantum Information Decision Diagram (QuIDD) that exploits the structure of quantum operators, a useful subset of operator matrices and state vectors can be represented in a form that grows polynomially with the number of qubits. This subset contains, but is not limited to, any equal superposition of n qubits, any computational basis state, n-qubit Pauli matrices, and n-qubit Hadamard matrices. It does not, however, contain the discrete Fourier transform (employed in Shor's algorithm) and some oracles used in Grover's algorithm. We first introduce and motivate decision diagrams and QuIDDs. We then analyze the runtime and memory complexity of QuIDD operations. Finally, we empirically validate QuIDD-based simulation by means of a general-purpose quantum computing simulator QuIDDPro implemented in C++. We simulate various instances of Grover's algorithm with QuIDDPro, and the results demonstrate that QuIDDs asymptotically outperform all other known simulation techniques. Our simulations also show that well-known worst-case instances of classical searching can be circumvented in many specific cases by data compression techniques. PACS: 03.67.Lx, 03.65.Fd, 03.65.Vd, 07.05.Bx     

基于量子Grover算法的MIMO检测技术

最大似然译码(MLD)是MIMO系统中最佳接收算法,但是其运算计算量随发射天线数呈指数增长,这是一个NP问题,如果利用量子并行处理的优势,将量子搜索算法应用于MIMO系统的检测中去,会有效地解决以上问题,提高系统的性能.提出了基于量子Grover算法的MIMO检测方案,并分析了该方案的性能和特点.     

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

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

Image classification based on quantum K-Nearest-Neighbor algorithm

Image classification is an important task in the field of machine learning and image processing. However, common classification method, the K-Nearest-Neighbor algorithm, has high complexity, because its two main processes: similarity computing and searching, are time-consuming. Especially in the era of big data, the problem is prominent when the amount of images to be classified is large. In this paper, we try to use the powerful parallel computing ability of quantum computers to optimize the efficiency of image classification. The scheme is based on quantum K-Nearest-Neighbor algorithm. Firstly, the feature vectors of images are extracted on classical computers. Then, the feature vectors are inputted into a quantum superposition state, which is used to achieve parallel computing of similarity. Next, the quantum minimum search algorithm is used to speed up searching process for similarity. Finally, the image is classified by quantum measurement. The complexity of the quantum algorithm is only \(O(\sqrt{kM})\), which is superior to the classical algorithms. Moreover, the measurement step is executed only once to ensure the validity of the scheme. The experimental results show that the classification accuracy is \(83.1\%\) on Graz-01 dataset and \(78\%\) on Caltech-101 dataset, which is close to existing classical algorithms. Hence, our quantum scheme has a good classification performance while greatly improving the efficiency.     

Quantum Mechanical Search and Harmonic Perturbation

Perturbation theory in quantum mechanics studies how quantum systems interact with their environmental perturbations. Harmonic perturbation is a rare special case of time-dependent perturbations in which exact analysis exists. Some important technology advances, such as masers, lasers, nuclear magnetic resonance, etc., originated from it. Here we add quantum computation to this list with a theoretical demonstration. Based on harmonic perturbation, a quantum mechanical algorithm is devised to search the ground state of a given Hamiltonian. The intrinsic complexity of the algorithm is continuous and parametric in both time T and energy E. More precisely, the probability of locating a search target of a Hamiltonian in N-dimensional vector space is shown to be 1/(1 + c N E⁻²T⁻²) for some constant c. This result is optimal. As harmonic perturbation provides a different computation mechanism, the algorithm may suggest new directions in realizing quantum computers.      

第一寄存器小Qubit量子计算攻击RSA研究

提出了针对RSA的小Qubit量子攻击算法设计,量子攻击的第一量子寄存器所需的Qubit数目由原先至少2L降低到L1,总体空间复杂度记为(L1,L),其中2L1≥r,r为分解所得周期。由于第一寄存器量子比特数的减少,降低了算法复杂度和成功率,且改进原算法中模幂计算,提升运算速率。改进攻击算法的量子电路的时间复杂度为T=O(2L2)。在时间复杂度和空间复杂度上都有明显的进步。改进算法的成功率降低了,但实际成功求解时间,即每次分解时间/成功率,依然低于 Shor 算法目前的主要改进算法。完成了仿真模拟实验,分别用11、10、9 Qubit成功分解119的量子电路。