[發(fā)明專利]一種量子并行搜索方法

有效

• 申請?zhí)枺?/td>: 202010055786.2
• 申請日: 2020-01-17
• 公開（公告）號: CN111291892B
• 公開（公告）日: 2023-01-17
• 發(fā)明（設(shè)計(jì)）人: 王平;劉光強(qiáng)
• 申請（專利權(quán)）人: 深圳大學(xué)
• 主分類號: G06N10/60
• 分類號: G06N10/60
• 代理公司: 廣州粵高專利商標(biāo)代理有限公司 44102
• 代理人: 張金福

1.一種量子并行搜索方法，其特征在于，所述方法基于量子并行搜索系統(tǒng)來實(shí)現(xiàn)，所述系統(tǒng)包括可調(diào)用的：寄存器1、寄存器2、寄存器3、G算子、輔助比特0、輔助比特1、Hadamard門、compare線路、受控U_H門；

輔助比特0的初始化狀態(tài)為|0＞、輔助比特1的初始化狀態(tài)為|1＞；

寄存器對應(yīng)問題的輸入；

G算子包括Oracle量子線路，算子U量子線路；

初始化為|0狀態(tài)的輔助比特0，作用是在Oracle算子里控制寄存器中的量子比特；

初始化為|1狀態(tài)的輔助比特1輔助翻轉(zhuǎn)解的位置；

Oracle量子線路，用來檢查輔助比特的相位來判斷x是否為搜索問題的一個解；

算子U量子線路，用來放大搜索問題的解的概率幅值；測量線路，是對算法最后輸出狀態(tài)作測量；

U算子由單位矩陣、Hadamard門和條件相移U_x算子組成；

Hadamard門用于變換

條件相移U_x算子的作用是使得狀態(tài)|0＞以外的每一個計(jì)算基態(tài)獲得-1的相位移動；

所述方法包括以下步驟：

S1：構(gòu)建一個搜索問題；

S2：應(yīng)用Hadamard門于寄存器2和寄存器3，使得寄存器2和寄存器3為均衡狀態(tài)；

S3：應(yīng)用迭代算子G，更新寄存器2和寄存器3的量子狀態(tài)，增加目標(biāo)狀態(tài)的概率幅值同時(shí)降低非目標(biāo)狀態(tài)的概率幅值；

S4：對寄存器2更新后的狀態(tài)進(jìn)行測量；

S5：尋找搜索問題的解。

2.根據(jù)權(quán)利要求1所述的量子并行搜索方法，其特征在于，S1具體為：假設(shè)一個搜索問題f(x)，其搜索空間為N＝2ⁿ，即用n個比特表示其搜索空間大小，將搜索問題表示為一個輸入x的函數(shù)f(x)，則x取值范圍是[0，2ⁿ-1]，函數(shù)f的定義是，若x是一個搜索問題的解，則f(x)＝1，否則f(x)＝0，如果f(x)有唯一解，為了方便起見，令x₀表示搜索問題的唯一解，則f(x₀)＝1，當(dāng)x≠x₀使得f(x)＝0；找到f(x)的解時(shí)即是找到了一個搜索問題的解；

對于搜索問題f(x)，先求出g(x)的唯一解x′₀，再由x′₀求f(x)的x₀；

其中，x的取值范圍是符號是模二運(yùn)算。

3.根據(jù)權(quán)利要求2所述的量子并行搜索方法，其特征在于，S2包括以下步驟：

S2.1：設(shè)每一個經(jīng)典取值x₁取值范圍為并將其經(jīng)典值轉(zhuǎn)變?yōu)槎M(jìn)制值，存儲于寄存器1中；寄存器2初始化為狀態(tài)寄存器3初始化為狀態(tài)輔助量子比特0初始化為|0；輔助量子比特1初始化為|1；

其中，表示n₂個量子比特的狀態(tài)都是|0狀態(tài)；

S2.2：對寄存器2、寄存器3中的量子比特做Hadamard變換，即分別應(yīng)用和于寄存器2和寄存器3，得到系統(tǒng)所需的均衡疊加狀態(tài)；對輔助量子比特1做Hadamard變換；

S2.3：應(yīng)用Oracle算子于S2.2所得的狀態(tài)，若存在解，則標(biāo)志解的位置，否則保持不變；

S2.4：應(yīng)用U算子于系統(tǒng)，假設(shè)g(x)存在解，則增大解的概率幅，同時(shí)減小非解的概率幅；

其中，U算子由單位矩陣、Hadamard變換和條件相移U_x算子組成；

S2.5：將步驟S2.3和步驟S2.4整合為一個G算子，G＝UO，使用G算子對S2.2后的系統(tǒng)的量子均衡疊加態(tài)進(jìn)行次迭代；

其中，O表示Oracle算子。