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%.

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.

Optimizing Connections:Applied Shortest Path Algorithms for MANETs

This study is trying to address the critical need for efficient routing in Mobile Ad Hoc Networks(MANETs)from dynamic topologies that pose great challenges because of the mobility of nodes.Themain objective was to delve into and refine the application of the Dijkstra’s algorithm in this context,a method conventionally esteemed for its efficiency in static networks.Thus,this paper has carried out a comparative theoretical analysis with the Bellman-Ford algorithm,considering adaptation to the dynamic network conditions that are typical for MANETs.This paper has shown through detailed algorithmic analysis that Dijkstra’s algorithm,when adapted for dynamic updates,yields a very workable solution to the problem of real-time routing in MANETs.The results indicate that with these changes,Dijkstra’s algorithm performs much better computationally and 30%better in routing optimization than Bellman-Ford when working with configurations of sparse networks.The theoretical framework adapted,with the adaptation of the Dijkstra’s algorithm for dynamically changing network topologies,is novel in this work and quite different from any traditional application.The adaptation should offer more efficient routing and less computational overhead,most apt in the limited resource environment of MANETs.Thus,from these findings,one may derive a conclusion that the proposed version of Dijkstra’s algorithm is the best and most feasible choice of the routing protocol for MANETs given all pertinent key performance and resource consumption indicators and further that the proposed method offers a marked improvement over traditional methods.This paper,therefore,operationalizes the theoretical model into practical scenarios and also further research with empirical simulations to understand more about its operational effectiveness.

Representation of an Integer by a Quadratic Form through the Cornacchia Algorithm

Cornachia’s algorithm can be adapted to the case of the equation x2+dy2=nand even to the case of ax2+bxy+cy2=n. For the sake of completeness, we have given modalities without proofs (the proof in the case of the equation x2+y2=n). Starting from a quadratic form with two variables f(x,y)=ax2+bxy+cy2and n an integer. We have shown that a primitive positive solution (u,v)of the equation f(x,y)=nis admissible if it is obtained in the following way: we take α modulo n such that f(α,1)≡0modn, u is the first of the remainders of Euclid’s algorithm associated with n and α that is less than 4cn/| D |) (possibly α itself) and the equation f(x,y)=n. has an integer solution u in y. At the end of our work, it also appears that the Cornacchia algorithm is good for the form n=ax2+bxy+cy2if all the primitive positive integer solutions of the equation f(x,y)=nare admissible, i.e. computable by the algorithmic process.

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

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

基于多目标遗传算法的8×8 S盒的优化设计方法

混沌系统具有非线性、伪随机性、初始值敏感等特性,为基于动力系统构造性能良好的S盒提供了基础,进一步保证了分组加密算法安全性.目前,基于混沌构造S盒的方法大多数针对单个性能指标进行优化,难以获得全面的性能提升.针对此问题,结合混沌映射与多目标遗传算法,提出了一种新的S盒设计方法.首先,利用混沌映射的特性产生初始S盒种群;然后,以S盒的非线性度和差分均匀性为优化目标,基于遗传算法框架对上述两指标进行优化.针对S盒的特点,在优化算法中引入了交换操作,设计了新的变异操作以及非支配序集计算,有效提升了S盒的非线性度和差分均匀性.实验结果表明该算法产生的S盒其差分均匀度为6,非线性度值至少为110,有效提升了S盒的综合性能.

基于量子衍生涡流算法和T⁃S模糊推理模型的储层岩性识别

鉴于梯度下降法易陷入局部极值、普通群智能优化算法易早熟收敛,提出一种基于量子衍生涡流算法(Quantum Vortex Search Algorithm,QVSA)和T⁃S模糊推理模型的岩性识别方法,QVSA具有操作简单、收敛速度快、寻优能力强等优点,有助于T⁃S模糊推理模型获得最优参数配置,从而实现储层岩性的准确识别。首先利用具有全局搜索能力的QVSA优化T⁃S模糊推理模型的各种参数;然后利用主成分分析方法降低获取的地震属性维度;再利用优化的T⁃S模糊推理模型识别储层岩性。实验结果表明,利用反映储层特征的8个地震属性识别储层岩性时,所提方法的识别正确率达到92%,比普通BP网络方法高5.1%,同时查准率、查全率、F1分数等指标也较BP网络方法提升明显。

基于XGBoost算法的v_(P)/v_(S)预测及其在储层检测中的应用

鄂尔多斯盆地碳酸盐岩地层蕴含着丰富的油气资源。在勘探实践中发现,大牛地气田马家沟组断层发育、断距小,类型多样且成因复杂,给勘探、开发带来了较多挑战。为了应对这些挑战,提高储层预测的精度变得至关重要。在分析大牛地气田敏感弹性参数的基础上,建立地震属性与储层纵横波速度比(v_(P)/v_(S))的关系,提出一种基于XGBoost算法的地震多属性v_(P)/v_(S)预测方法。为了进一步提升XGBoost算法的预测精度和泛化能力,采用贝叶斯算法对XGBoost算法的超参数进行优化,从而找到最佳的超参数组合,以确保模型在训练集和测试集上的性能均能得到提升。将XGBoost算法应用于Marmousi 2模型进行横波速度预测,预测值与实际值相关系数超过0.88,而均方误差、平均绝对百分比误差分别低于6.55×10^(-7)和4%,验证了该方法的准确性和可靠性。在鄂尔多斯盆地大牛地气田,应用该方法获得的v_(P)/v_(S)成功识别出含气储层,结果与实际钻井数据一致。理论模型和实际数据应用结果表明,XGBoost作为一种强大的机器学习算法预测精度较高,为直接由叠后地震属性预测v_(P)/v_(S)提供了一种有效的途径。

三种基于Cesium的重庆市漫游飞行算法及其对比分析

漫游飞行在数字地球、虚拟现实和仿真等领域有着广泛的应用。以往的研究多集中于客户机/服务器(client/server,C/S)结构的桌面端应用程序,本文以浏览器/服务器(browser/server,B/S)结构下的Web端开源三维地理框架Cesium为基础构建虚拟地球,设计了三种不同的漫游算法:常规漫游算法、回调函数漫游算法、拉格朗日插值漫游算法,并在地球表面成功加载了重庆市主城区的倾斜摄影模型以实现漫游飞行功能,从帧率(frames per second,FPS)和网络延迟(network latency,NL)两方面对比分析三种算法的有效性。结果表明,常规漫游算法、回调函数漫游算法、拉格朗日插值漫游算法前50 s的平均FPS分别为70、74、80 Hz,平均NL分别为14.145、13.166、12.419 ms。就FPS而言,回调函数漫游算法较常规漫游算法提升了5.714%,拉格朗日插值漫游算法较常规漫游算法提升了14.286%。就NL而言,回调函数漫游算法较常规漫游算法缩短了6.921%,拉格朗日插值漫游算法较常规漫游算法缩短了12.202%。总体而言,算法运行效率从大到小最终排序为:拉格朗日插值漫游算法、回调函数漫游算法、常规漫游算法,即在漫游飞行过程中,回调函数漫游算法、拉格朗日插值漫游算法较常规漫游算法有一定的提升,拉格朗日插值漫游算法可实现更高效、流畅的渲染效果。

Routing Protocol Based on Grover’s Searching Algorithm for Mobile Ad-hoc Networks

In Mobile Ad-hoc Networks (MANETs), routing protocols directly affect various indices of network Quality of Service (QoS), so they play an important role in network performance. To address the drawbacks associated with traditional routing protocols in MANETs, such as poor anti-fading performance and slow convergence rate, for basic Dynamic Source Routing (DSR), we propose a new routing model based on Grover's searching algorithm. With this new routing model, each node maintains a node vector function, and all the nodes can obtain a node probability vector using Grover's algorithm, and then select an optimal routing according to node probability. Simulation results show that compared with DSR, this new routing protocol can effectively extend the network lifetime, as well as reduce the network delay and the number of routing hops. It can also significantly improve the anti-jamming capability of the network.

基于FPGA的SM4算法高效实现方案

针对SM4算法的FPGA实现方案存在数据处理速度不够高和逻辑资源占用过高的问题,提出了基于现场可编程门阵列(FPGA)的高性能、低资源消耗的SM4算法实现方案。所提方案采用循环密钥扩展与32级流水线加解密相结合的架构,循环密钥扩展的方式降低了逻辑资源消耗,32级流水线加解密的方式提高了数据吞吐率。同时,所提方案采用代数式S盒并通过合并线性运算以及在不可约多项式的合并矩阵中筛选最优矩阵运算的方式进一步减少S盒变换的运算量,从而达到降低逻辑资源占用与提高工程数据吞吐率的目的。测试结果显示,该方案比现有最佳方案在数据吞吐率上提升了43%,且资源占用率降低了10%。

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.

基于遗传粒子群算法的超混沌S盒设计

针对目前基于混沌系统所构造的S盒难以拥有良好密码学性能的问题,提出一种基于超混沌系统及遗传粒子群优化算法的S盒设计方案.在一维混沌映射基础上,引入正余弦函数以及指数因子,构造一个二维超混沌系统,从系统分叉图、相图、Lyapunov指数图进行性能分析,该混沌系统在参数范围内有着连续的超混沌区间,混沌行为复杂.通过改变混沌系统的初值、参数以及迭代次数可以动态生成S盒,随后结合粒子群优化算法和遗传算法提出一种针对S盒的遗传粒子群优化算法,将混沌系统生成的S盒作为初始种群,利用粒子群算法改进遗传算法中的交叉操作,同时结合爬山算法提出一种新的变异策略.为验证所生成S盒性能,对S盒的双射特性、非线性度、严格雪崩准则、差分均匀性及输出比特间独立性进行仿真测试,仿真结果表明:所提出的优化算法能够生成非线性度、差分均匀性、输出比特间独立性方面表现良好的S盒.

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.

秘密共享:高阶掩码S盒和有限域安全乘法设计

在信息时代,信息安全是最不能忽视的重要问题,对密码设备的攻击和防护是该领域的研究热点。近年来,多种对密码设备的攻击已为人所知,其目的都是为了获取设备中的密钥,在众多攻击中,功耗侧信道攻击是最受关注的攻击技术之一。掩码技术是对抗功耗侧信道攻击的有效方法,然而随着攻击手段的不断进步,1阶掩码的防护已经不足以应对2阶及以上的功耗分析攻击,因此对高阶掩码的研究具有重要的意义。为了提升加密电路抗攻击能力,该文基于秘密共享的思想,对分组密码算法的S盒变换实施了高阶掩码防护——共享型掩码,并基于Ishai等人在Crypto 2003上发表的安全方案(ISW框架)提出了有限域安全乘法的通用设计方法。通过实验表明,该文提出的共享型掩码方案不影响加密算法的功能,同时能抵御1阶和2阶相关功耗分析攻击。

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.

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.

基于同步压缩广义S变换的电力系统次/超同步振荡检测

为实现电力系统次/超同步振荡的快速、准确辨识,提出了一种基于同步压缩广义S变换(synchrosqueezing generalized S transform, SSGST)和改进稀疏时域法(improved sparse time domain method,ISTD)结合的次/超同步振荡辨识方法。该方法首先利用能量比函数对电力系统广域量测信息实时检测,当检测到信号能量发生突变时,利用SSGST对检测到的振荡信号分解得到相应的SSGST时频系数矩阵;然后通过改进的脊线提取方法在时频域实现对各振荡分量的最优轨迹搜索;进一步,结合最优轨迹时频索引重构各振荡分量的时域分量,并利用ISTD辨识方法计算出各振荡分量的频率和阻尼比系数;最后,通过自合成模拟信号、双馈风电场经串补并网系统仿真信号和某实际风电场实测数据验证了所提方法的准确性和有效性。

A Spectral Convolutional Neural Network Model Based on Adaptive Fick’s Law for Hyperspectral Image Classification

Hyperspectral image classification stands as a pivotal task within the field of remote sensing,yet achieving highprecision classification remains a significant challenge.In response to this challenge,a Spectral Convolutional Neural Network model based on Adaptive Fick’s Law Algorithm(AFLA-SCNN)is proposed.The Adaptive Fick’s Law Algorithm(AFLA)constitutes a novel metaheuristic algorithm introduced herein,encompassing three new strategies:Adaptive weight factor,Gaussian mutation,and probability update policy.With adaptive weight factor,the algorithmcan adjust theweights according to the change in the number of iterations to improve the performance of the algorithm.Gaussianmutation helps the algorithm avoid falling into local optimal solutions and improves the searchability of the algorithm.The probability update strategy helps to improve the exploitability and adaptability of the algorithm.Within the AFLA-SCNN model,AFLA is employed to optimize two hyperparameters in the SCNN model,namely,“numEpochs”and“miniBatchSize”,to attain their optimal values.AFLA’s performance is initially validated across 28 functions in 10D,30D,and 50D for CEC2013 and 29 functions in 10D,30D,and 50D for CEC2017.Experimental results indicate AFLA’s marked performance superiority over nine other prominent optimization algorithms.Subsequently,the AFLA-SCNN model was compared with the Spectral Convolutional Neural Network model based on Fick’s Law Algorithm(FLA-SCNN),Spectral Convolutional Neural Network model based on Harris Hawks Optimization(HHO-SCNN),Spectral Convolutional Neural Network model based onDifferential Evolution(DE-SCNN),SpectralConvolutionalNeuralNetwork(SCNN)model,and SupportVector Machines(SVM)model using the Indian Pines dataset and PaviaUniversity dataset.The experimental results show that the AFLA-SCNN model outperforms other models in terms of Accuracy,Precision,Recall,and F1-score on Indian Pines and Pavia University.Among them,the Accuracy of the AFLA-SCNN model on Indian Pines reached 99.875%,and the Accuracy on PaviaUniversity reached 98.022%.In conclusion,our proposed AFLA-SCNN model is deemed to significantly enhance the precision of hyperspectral image classification.