[發(fā)明專利]一種基于Grover算法的大數(shù)據(jù)集搜索方法、量子計算機(jī)

有效

• 申請?zhí)枺?/td>: 202010172778.6
• 申請日: 2020-03-12
• 公開（公告）號: CN111598245B
• 公開（公告）日: 2023-04-07
• 發(fā)明（設(shè)計）人: 賀晨;蘇劍穎;張宸昊;陳陽
• 申請（專利權(quán)）人: 西北大學(xué)
• 主分類號: G06N10/60
• 分類號: G06N10/60;G06N10/20;G06F16/903
• 代理公司: 西安長和專利代理有限公司 61227
• 代理人: 黃偉洪

本發(fā)明屬于量子計算技術(shù)領(lǐng)域，公開了一種基于Grover算法的大數(shù)據(jù)集搜索方法、量子計算機(jī)，根據(jù)量子處理器的容量對數(shù)據(jù)集分塊，每塊數(shù)據(jù)集的大小為處理器一次能處理的最大數(shù)據(jù)量；以每塊數(shù)據(jù)的迭代次數(shù)為自變量，列出搜到解時迭代次數(shù)的總期望值等式；列出搜索問題的約束條件，并將總期望值等式作為目標(biāo)函數(shù)，對優(yōu)化方程求解；按照求得的每塊數(shù)據(jù)的迭代次數(shù)對相應(yīng)數(shù)據(jù)塊進(jìn)行搜索；與完整Grover算法進(jìn)行對比，得到優(yōu)化搜索算法的優(yōu)化率。本發(fā)明對較大數(shù)據(jù)集進(jìn)行搜索可以有效減少查找次數(shù)，最優(yōu)情況下優(yōu)化率可以提高6％左右。相同搜索成功率的條件下減少查找次數(shù)，可以使整個系統(tǒng)中由錯誤率和退相干性產(chǎn)生的影響得到抵消。

技術(shù)領(lǐng)域

本發(fā)明屬于量子計算技術(shù)領(lǐng)域，尤其涉及一種基于Grover算法的大數(shù)據(jù)集?搜索方法、量子計算機(jī)。

背景技術(shù)

目前，量子計算是基于量子邏輯，利用量子態(tài)進(jìn)行信息處理的方法。隨著?量子計算機(jī)的發(fā)展，基于量子計算機(jī)運行的量子算法被人們發(fā)現(xiàn)，它解決一些?問題的效率將有可能遠(yuǎn)遠(yuǎn)超過經(jīng)典算法，甚至可以解決經(jīng)典計算機(jī)無法解決的?一些問題。Grover算法是一種量子搜索算法，該算法被證實可以對經(jīng)典算法進(jìn)?行二次加速從而更快速地解決問題。目前現(xiàn)有的能有效解決搜索問題的量子算?法絕大多數(shù)都是Grover算法的變體，這些Grover算法的改進(jìn)算法在解決大數(shù)據(jù)?集上的搜索問題時需要消耗大量的量子比特來進(jìn)行計算。由于量子的糾纏態(tài)難?以控制，因此處理器的量子比特數(shù)始終存在限制，目前谷歌所發(fā)布的量子計算?機(jī)僅72量子比特，IBM推出的僅53量子比特，如果搜索空間的大小超過了該?量子處理器所能承載的最大數(shù)據(jù)量時，便無法直接通過Grover算法搜索目標(biāo)?項。因此，對于在量子計算機(jī)上，如何使用有限量子比特的處理器對大型的無?結(jié)構(gòu)數(shù)據(jù)進(jìn)行搜索是需要解決的重要問題。

綜上所述，現(xiàn)有技術(shù)存在的問題是：

(1)現(xiàn)有技術(shù)在解決大數(shù)據(jù)集上的搜索問題時需要消耗大量的量子比特，?當(dāng)搜索空間的大小超過處理器的量子比特限制時便無法直接找到問題的解。

(2)由于量子系統(tǒng)存在消相干性，所以搜索算法的查找次數(shù)越多系統(tǒng)的錯?誤率就越高，在數(shù)據(jù)量較大的情況下甚至?xí)l(fā)生系統(tǒng)完全消相干從而導(dǎo)致無法?完成計算的情況。本發(fā)明的優(yōu)化方法從Grover算法的迭代次數(shù)與對應(yīng)的搜索概?率之間的關(guān)系入手，通過減少查找次數(shù)的方式提高搜索效率。

解決上述技術(shù)問題的難度：通用量子計算機(jī)利用量子的相干性和糾纏態(tài)來?實現(xiàn)量子計算，由于量子的自身特性，糾纏態(tài)的制備和保持是有嚴(yán)苛的條件限?制的，在實現(xiàn)計算過程中必須要想辦法降低量子算法的運算復(fù)雜性和計算時間?來減少中間態(tài)，以求得算法的結(jié)果在保持一定準(zhǔn)確率的同時有較高的實用性。?想要構(gòu)建通用量子計算機(jī)幫助解決一些問題，如何實現(xiàn)高效搜索是一個至關(guān)重?要的技術(shù)節(jié)點。

解決上述技術(shù)問題的意義：本發(fā)明的搜索方法可以實現(xiàn)使用較少量子比特?的處理器完成大數(shù)據(jù)集上的搜索問題，解決了量子處理器在搜索問題上的比特?限制問題。同時，本發(fā)明的優(yōu)化方法有效減少了搜索問題的查找次數(shù)，一定程?度上抵消了部分由于系統(tǒng)的消相干性帶來的錯誤率。

發(fā)明內(nèi)容

針對現(xiàn)有技術(shù)存在的問題，本發(fā)明提供了一種基于Grover算法的大數(shù)據(jù)集?搜索方法、量子計算機(jī)。

本發(fā)明是這樣實現(xiàn)的，一種基于Grover算法的大數(shù)據(jù)集搜索方法，所述基?于Grover算法的大數(shù)據(jù)集搜索方法包括：

第一步，根據(jù)量子處理器的容量對數(shù)據(jù)集分塊，每塊數(shù)據(jù)集的大小為處理?器一次能處理的最大數(shù)據(jù)量；

第二步，以每塊數(shù)據(jù)的迭代次數(shù)為自變量，列出搜到解時迭代次數(shù)的總期?望值等式；

第三步，列出搜索問題的約束條件，并將總期望值等式作為目標(biāo)函數(shù)，對?優(yōu)化方程求解；