O(logN) Algorithm for Amplitude Amplification and O(logN) Algorithms for Amplitude Transfer in Grover’s Algorithm

Grovers algorithm is a category of quantum algorithms that can be applied to many problems through the exploitation of quantum parallelism. The Amplitude Amplification in Grovers algorithm is T = O(N). This paper introduces two new algorithms for Amplitude Amplification in Grovers algorithm with a time complexity of T = O(logN), aiming to improve efficiency in quantum computing. The difference between Grovers algorithm and our first algorithm is that the Amplitude Amplification ratio in Grovers algorithm is an arithmetic series and ours, a geometric one. Because our Amplitude Amplification ratios converge much faster, the time complexity is improved significantly. In our second algorithm, we introduced a new concept, Amplitude Transfer where the marked state is transferred to a new set of qubits such that the new qubit state is an eigenstate of measurable variables. When the new qubit quantum state is measured, with high probability, the correct solution will be obtained.

Time Complexity of the Oracle Phase in Grover’s Algorithm

Since Grover’s algorithm was first introduced, it has become a category of quantum algorithms that can be applied to many problems through the exploitation of quantum parallelism. The original application was the unstructured search problems with the time complexity of O(). In Grover’s algorithm, the key is Oracle and Amplitude Amplification. In this paper, our purpose is to show through examples that, in general, the time complexity of the Oracle Phase is O(N), not O(1). As a result, the time complexity of Grover’s algorithm is O(N), not O(). As a secondary purpose, we also attempt to restore the time complexity of Grover’s algorithm to its original form, O(), by introducing an O(1) parallel algorithm for unstructured search without repeated items, which will work for most cases. In the worst-case scenarios where the number of repeated items is O(N), the time complexity of the Oracle Phase is still O(N) even after additional preprocessing.

基于Grover量子搜索算法的MD5碰撞攻击模型

量子计算天然的并行性使其在密码学领域具有巨大潜力,而在信息安全领域,Hash函数的安全性至关重要。因此,后量子密码学概念的提出使得Hash函数在后量子时代的研究价值凸显。文章提出了一种基于Grover量子搜索算法的MD5碰撞攻击模型,运用模差分分析法,通过对输入的量子叠加态进行约束搜索以找到满足碰撞条件的目标态,再根据差分构造出与之相碰撞的消息。此外,文章探讨了量子搜索算法中的迭代过程及其关键操作,设计了相应的Oracle黑盒的量子线路,并对其进行性能分析,结果表明,与经典算法相比,该模型显著降低了攻击的计算复杂度,为后量子密码时期Hash函数的研究提供了新的思路和方法,也为防御此类攻击提供了有益参考。

Grover量子搜索算法在“嵩山”超级计算机系统中的模拟

量子计算凭借其叠加性和纠缠性,具有强大的并行计算能力。然而,目前的量子计算机不能在保证大规模量子比特处于稳定叠加态的同时,进行干涉、纠缠等量子操作。因此,当前研究和推动量子计算的有效途径是使用经典计算机模拟量子计算。Grover量子搜索算法针对无序数据库搜索问题设计,将搜索的时间复杂度加速至开平方级,能加速机器学习中的主成分分析。因此,研究和模拟Grover算法,可以促进量子计算与机器学习结合领域的发展,为Grover量子搜索算法的应用以及量子机器学习在“嵩山”超级计算机系统中的模拟奠定基础。通过研究Grover量子搜索算法,模拟出了算法的量子线路。使用Toffoli量子门优化该量子线路,在减少了两个辅助量子比特的同时,提出了Grover算法的通用量子线路。实验基于“嵩山”超级计算机系统的CPU+DCU异构体系,使用了MPI多进程+HIP多线程的两级并行策略。通过调整辅助比特在量子线路中的位置,减少了MPI进程间的通信;使用分片的方式传输数据依赖的量子态。对比串行版本,并行化的模拟算法取得了最高560.33倍的加速,首次实现了31qubits规模的Grover量子搜索算法。

Grover quantum searching algorithm based on weighted targets

The current Grover quantum searching algorithm cannot identify the difference in importance of the search targets when it is applied to an unsorted quantum database, and the probability for each search target is equal. To solve this problem, a Grover searching algorithm based on weighted targets is proposed. First, each target is endowed a weight coefficient according to its importance. Applying these different weight coefficients, the targets are represented as quantum superposition states. Second, the novel Grover searching algorithm based on the quantum superposition of the weighted targets is constructed. Using this algorithm, the probability of getting each target can be approximated to the corresponding weight coefficient, which shows the flexibility of this algorithm. Finally, the validity of the algorithm is proved by a simple searching example.

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

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

Eavesdropping in a quantum secret sharing protocol based on Grover algorithm and its solution

A detailed analysis has showed that the quantum secret sharing protocol based on the Grover algorithm (Phys Rev A, 2003, 68: 022306) is insecure. A dishonest receiver may obtain the full information without being detected. A quantum secret-sharing protocol is presents here, which mends the security loophole of the original secret-sharing protocol, and doubles the information capacity.

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

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

Effects of initial states on the quantum correlations in the generalized Grover search algorithm

We investigate the correlations between two qubits in the Grover search algorithm with arbitrary initial states by numerical simulation.Using a set of suitable bases,we construct the reduced density matrix and give the numerical expression of correlations relating to the iterations.For different initial states,we obtain the concurrence and quantum discord compared with the success probability in the algorithm.The results show that the initial states affect the correlations and the limit point of the correlations in the searching process.However,the initial states do not influence the whole cyclical trend.

A Four-Phase Improvement of Grover＇s Algorithm

When applying Grover＇s algorithm to an unordered database, the probabifity of obtaining correct results usually decreases as the quantity of target increases. A four-phase improvement of Grover＇s algorithm is proposed to fix the deficiency, and the unitary and the phase-matching condition are also proposed. With this improved scheme, when the proportion of target is over 1/3, the probability of obtaining correct results is greater than 97.82% with only one iteration using two phases. When the computational complexity is O（ √M/N）, the algorithm can succeed with a probability no less than 99.63%.

Adaptive Phase Matching in Grover’s Algorithm

When the Grover’s algorithm is applied to search an unordered database, the successful probability usually decreases with the increase of marked items. In order to solve this problem, an adaptive phase matching is proposed. With application of the new phase matching, when the fraction of marked items is greater , the successful probability is equal to 1 with at most two Grover iterations. The validity of the new phase matching is verified by a search example.

Grover search algorithm in an ion trap systen

Two schemes for the implementation of the two-qubit Grover search algorithm in the ion trap system are proposed. These schemes might be experimentally realizable with presently available techniques. The experimental implementation of the schemes would be an important step toward more complex quantum computation in the ion trap system.

A Memory-efficient Simulation Method of Grover’s Search Algorithm

Grover’s search algorithm is one of the most significant quantum algorithms,which can obtain quadratic speedup of the extensive search problems.Since Grover's search algorithm cannot be implemented on a real quantum computer at present,its quantum simulation is regarded as an effective method to study the search performance.When simulating the Grover's algorithm,the storage space required is exponential,which makes it difficult to simulate the high-qubit Grover’s algorithm.To this end,we deeply study the storage problem of probability amplitude,which is the core of the Grover simulation algorithm.We propose a novel memory-efficient method via amplitudes compression,and validate the effectiveness of the method by theoretical analysis and simulation experimentation.The results demonstrate that our compressed simulation search algorithm can help to save nearly 87.5%of the storage space than the uncompressed one.Thus under the same hardware conditions,our method can dramatically reduce the required computing nodes,and at the same time,it can simulate at least 3 qubits more than the uncompressed one.Particularly,our memory-efficient simulation method can also be used to simulate other quantum algorithms to effectively reduce the storage costs required in simulation.

Grover’s Algorithm in a 4-Qubit Search Space

This paper provides an introduction to a quantum search algorithm,known as Grover’s Algorithm,for unsorted search purposes.The algorithm is implemented in a search space of 4 qubits using the Python-based Qiskit SDK by IBM.While providing detailed proof,the computational complexity of the algorithm is generalized to n qubits.The implementation results obtained from the IBM QASM Simulator and IBMQ Santiago quantum backend are analyzed and compared.Finally,the paper discusses the challenges faced in implementation and real-life applications of the algorithm hitherto.Overall,the implementation and analysis depict the advantages of this quantum search algorithm over its classical counterparts.

Quantum Algorithm for Mining Frequent Patterns for Association Rule Mining

Maximum frequent pattern generation from a large database of transactions and items for association rule mining is an important research topic in data mining. Association rule mining aims to discover interesting correlations, frequent patterns, associations, or causal structures between items hidden in a large database. By exploiting quantum computing, we propose an efficient quantum search algorithm design to discover the maximum frequent patterns. We modified Grover’s search algorithm so that a subspace of arbitrary symmetric states is used instead of the whole search space. We presented a novel quantum oracle design that employs a quantum counter to count the maximum frequent items and a quantum comparator to check with a minimum support threshold. The proposed derived algorithm increases the rate of the correct solutions since the search is only in a subspace. Furthermore, our algorithm significantly scales and optimizes the required number of qubits in design, which directly reflected positively on the performance. Our proposed design can accommodate more transactions and items and still have a good performance with a small number of qubits.

Grover量子搜索算法及改进

简单地介绍了量子搜索算法中的相位匹配条件、改进的成功率为 10 0 %的量子搜索算法和量子搜索算法中的主要误差等 .

量子均值估计算法研究进展

随机变量的均值估计问题一直是经典数据分析中研究的热点,均值估计算法的目的是通过对随机变量尽可能少地采样从而获得尽可能准确的均值估计值。量子计算作为一项革命性的技术,在一些问题上具有超越经典计算的优势。量子算法在均值估计问题上相对于经典算法具有平方加速,展现了量子计算的优越性。该文系统梳理了量子均值估计算法的发展历程,详细介绍了各阶段的算法流程及其优缺点,并对其主要应用场景进行了展示,最后讨论了量子均值估计算法的潜在发展方向。

一种改进的Grover量子搜索算法

Grover量子搜索算法以O(N^(1/2))的时间复杂度进行非结构化数据库穷举搜索,但当问题的解的个数增加,得到解的概率反而减少.本文分析了这种现象的原因,并提出了基于扩大搜索空间的改进算法.同时,为了在成功概率与迭代次数之间折中,增加一个新参数i使得算法可调。求逆问题的仿真实验表明该方法在同等迭代次数的条件下,成功概率高于传统Grover算法;且如果迭代次数不限,则成功概率可以更高。因此,本文算法更加有效。

基于Grover算法的ECC扫描式攻击

相对于传统的RSA等公钥密码,ECC具有密钥长度短,计算复杂度高等特点,因此针对ECC加密体制的攻击复杂度高、难度大。研究针对ECC公钥密码的攻击方法有利于提前完善和防止不必要的损失。Grover算法作为一种量子搜索算法,将搜索步数从经典算法的N缩小到N^(1/2),实现了对经典搜索算法的二次方加速作用,能更快速地寻找所需的解。扫描式攻击作为一种新生的侧信道攻击技术,它的出现给当前密码系统的安全性带来了极大的威胁。文章利用量子Grover搜索算法的快速搜索优点,对Rynuta提出的针对ECC密码芯片的扫描式攻击进行了改进,提出了基于Grover算法的ECC扫描式攻击方法。该算法对于密钥长度为N的ECC,计算复杂度由2~N降低到2N^(3/2),进一步提高了破解效率。由于Grover搜索算法的确定性,该算法的攻击成功率为100%。

基于Grover融合理论的无线传感网络路由算法研究

如何在各种网络资源受限制的情况,实现高质量的信息传输是无线传感网络研究领域的关键问题之一。首先,分析了网络传输中所需要考虑的受限制因素,并提出各种因素的计算办法;然后,针对确保服务质量的多目标规划算法存在计算量过大的缺陷,借鉴量子搜索算法中的Grover理论用以降低信息传输过程的搜索计算量;最后,通过Grover理论得到的各种资源路由选择方案,本文采用了计算机控制中的D-S信息融合理论,将多目标规划转化为单目标规划。为了验证本文所提出的Grover融合路由算法,文章建立MATLAB仿真环境,对比传统的DSR路由协议与多目标规划TOPSIS算法,可见本文所提出的算法在降低网络搜索计算量、延长网络生存时间、降低网络时延方面具有较大的改善。