基于Grover 算法的布爾二次方程組求解

錢宇梁 舒國強 封聰聰 邸詩秦

摘要：布爾方程組求解問題在密碼等領(lǐng)域有著廣泛而重要的研究意義，其中主要是非線性的布爾方程組求解較為困難。已知的經(jīng)典求解算法的復(fù)雜度高，求解效率低下，而目前量子算法的加速優(yōu)勢為量子計算求解布爾方程組帶來的新的可能，文章旨在應(yīng)用已知的Grover算法進行求解，可為求解帶來開平方的加速優(yōu)勢。同時，為了在量子計算機有限的資源上發(fā)揮最大求解能力，文章提出比特資源優(yōu)化和線路深度優(yōu)化的方案，通過實驗證明了該方案的有效性，大大提高了當(dāng)前設(shè)備的求解能力。

關(guān)鍵詞：布爾二次方程;Grover 算法;二次加速;量子計算;線路優(yōu)化

中圖法分類號：0413文獻標(biāo)識碼：A

Solving Boolean quadratic equations based on grover algorithm

QIAN Yuliang'，SHUGuoqiang，F(xiàn)ENG Congcong2，DI Shiqin

（1.XuteliSchool，Beijing Institute of Technology，Beijing 102488，China;

2.State Key Laboratory of Mathematical Engineering and Advanced Computing，Zhengzhou 450000，China）

Abstract：The problem of solving Boolean equations has extensive and important research significance in cryptography and other fields， and it is mainly difficult to solve nonlinear Boolean equations. The known classical solution algorithms have high complexity and low efficiency. The current acceleration advantage of quantum algorithms brings new possibilities for quantum computing to solve Boolean equations. This paper aims to use the known Grover algorithm， which can bring quadratic acceleration advantages. At the same time， for maximizing the computing ability on the limited resources of the quantum computers， we propose a scheme of bit resource optimization and circuit depth optimization. The effectiveness of the scheme is demonstrated by experiments， which greatly improves the computing ability of the current equipments.

Key words： Boolean quadratic equations， Grover algorithm， quadratic acceleration，quantumcomputing，circuit optimization

1相關(guān)工作

一直以來，布爾方程組求解問題都是密碼學(xué)等領(lǐng)域的重要研究問題。序列密碼、分組密碼和 Hash 函數(shù)的設(shè)計與分析是目前信息安全領(lǐng)域的前沿、熱點問題。布爾函數(shù)作為序列密碼、分組密碼和 Hash 函數(shù)中的重要組件，其密碼學(xué)性質(zhì)的好壞直接關(guān)系到密碼體制的安全性。近年來，代數(shù)攻擊引起了國內(nèi)外的密碼學(xué)者的注意，代數(shù)攻擊的基本思想就是：一個密碼算法可以表示為一個大的多變元多項式方程組，求解這個方程組就可以得到密鑰，并且這些方程組以非線性居多。

當(dāng)前，求解多元非線性的布爾方程組的方法通常有g(shù)robner基方法，其求解的復(fù)雜度的上限是 O（2n ）[1]。暴力搜索法的復(fù)雜度是 O（ n2n ）[2]。XL 方法的復(fù)雜度是nO（1/ε）[3～4]等。其他的求解思路是通過增加變元的方式將非線性方程組轉(zhuǎn)化為線性方程組，再利用線性方程組的求解方法求解，常見的如 Gauss 消元法，復(fù)雜度是 O（ n3）[5];回溯法，復(fù)雜度是 O（ n?。┑确椒ㄟM行求解。然而，這些算法的求解效率并不高。量子計算是以量子物理學(xué)為基本原理，通過對多個量子疊加態(tài)并行處理，實現(xiàn)對經(jīng)典算法速度的二次加速甚至指數(shù)級加速。近年來，量子算法已經(jīng)展示了量子計算的巨大潛力。其中，HHl算法在求解高維稀疏方程組問題上展現(xiàn)了指數(shù)級的加速，且廣泛應(yīng)用于機器學(xué)習(xí)等領(lǐng)域。GAO 等[6]將改進HHl算法應(yīng)用到布爾方程組的求解問題上，展示了指數(shù)級的加速。但是，該算法目前面臨很多實際的應(yīng)用困難，比如初態(tài)的制備問題還無法取得突破。

在無序數(shù)據(jù)庫搜索問題上，Grover 算法能夠以開平方級的加速實現(xiàn)求解。且對其的研究也有了一定的成果[7～9]。Grover 算法在實際問題的應(yīng)用方面，相關(guān)學(xué)者已經(jīng)做出了大量有關(guān)的研究。早在2000年時，ZALKA 等[10]就已經(jīng)提出使用 Grover 搜索算法進行數(shù)據(jù)庫搜索。2006年，YAMASHITA[11]提出了如何在通用編程中使用 Grover 搜索算法加速程序。近年來，國內(nèi)學(xué)者也開始重視 Grover 搜索算法的應(yīng)用，如在2014年，阮越等[12]提出了基于 Grover 搜索算法的人臉識別算法，將人臉識別的效率在經(jīng)典基礎(chǔ)上進行了二次加速;同年，PENG 等[13]提出了基于 Grover 搜索算法的無線量子網(wǎng)絡(luò)路由算法，可以在限定跳數(shù)內(nèi)搜索出目標(biāo)路徑。2015年，SUN 等[14]提出了基于 Grover 搜索算法的量子求根算法，將算法復(fù)雜度降低到了 O??? 。從大量的文獻中可以看出，Grover 搜索算法的應(yīng)用范圍較廣，具有很高的研究價值。

本文的主要工作是研究應(yīng)用 Grover 算法求解二次非線性布爾方程組。已知布爾方程組求解具有廣泛的應(yīng)用，且目前經(jīng)典算法求解效率不高。針對 n 元2次布爾方程組，本文基于量子 Grover 算法實現(xiàn)對方程組解的搜索，能夠?qū)崿F(xiàn)對布爾方程組求解的二次加速，并通過改進和優(yōu)化算法的線路，實現(xiàn)比特資源和線路深度的優(yōu)化，從而發(fā)揮量子計算機的最大潛力。

2背景知識

2.1布爾方程組

用 F2表示只包括元素0和1的二元域，用 F2（n） 表示二元域 F2={0，1}上的 n 維向量空間，用+和∑i表示實數(shù)中整數(shù)的加法，用和i表示實數(shù)中整數(shù)的模2加法，同時用表示 F2（n） 中向量的加法。因為 F2（n）中的向量與[0，2n-1]的整數(shù)之間存在自然的一一對應(yīng)關(guān)系，所以可以按照它們對應(yīng)整數(shù)從小到大的順序來排列Vn中的向量，并且記：

為了方便計算，F(xiàn)2（n） 中的向量αi同時表示它對應(yīng)的整數(shù)i，從 F2（n） 到 F2的映射f（ x）稱為 F2（n） 上的布爾函數(shù)，其中 x ∈F2（n） 。布爾函數(shù)f（ x ）可以唯一表示成 n 個變量的多項式，即：

其中，x=（ x1，…，xn ）∈F2（n） ，u=（ u1，…，un ）∈F2（n） ，λu ∈ F2。這種表示稱為 f（ x ）的代數(shù)式（ Algebraic NormalForm，簡稱為 ANF），多項式中的每一項∏i（n）=1 x i（u）i稱為f（x）的單項式（Monomial），它的次數(shù)定義為其中不同變量的個數(shù)，而f（ x）的所有單項式次數(shù)的最大值稱為布爾函數(shù)f（x）的代數(shù)次數(shù)，記為 deg（f）。

F2（n） 上次數(shù)小于或等于1的布爾函數(shù)稱為仿射函數(shù)，它們具有如下形式：

其中，ai ∈F2，i=0，1，…，n。特別地，a0=0，該仿射函數(shù)稱為線性函數(shù)。一般地，分別用 An 和 Ln 表示 F2（n）上所有仿射函數(shù)和線性函數(shù)的集合。

2.2 Grover 算法

給定一個集合 X，元素數(shù)目是 N，函數(shù)映射是f：X

其中，T 是要找到的目標(biāo)解的集合，元素數(shù)量是 t。 Grover 算法是一個需要重復(fù)應(yīng)用下面的操作多次的算法。

式（5）被稱為 Grover 迭代。對任意的初態(tài)|Ψ）= A |0），有：

式（6）中，H? n 是一個 Hadamard 算符的集合，|τ）是一個由所有目標(biāo)態(tài)構(gòu)成的一個等概率疊加態(tài)構(gòu)成的態(tài)。

S0和 Sf 的作用分別是將態(tài)|0）和態(tài)|τ）進行翻轉(zhuǎn)。其中，Sf 和-AS0A-1分別被稱為黑盒和振幅翻轉(zhuǎn)操作。

通過將黑盒作用到初始態(tài)上，只有目標(biāo)態(tài)的振幅發(fā)生反轉(zhuǎn)，被標(biāo)記。振幅翻轉(zhuǎn)操作將振幅按照均值進行翻轉(zhuǎn)。測量的成功概率是關(guān)于迭代次數(shù)的函數(shù)，已被研究[15]，最佳的迭代次數(shù)可以讓成功的概率最大化。通過應(yīng)用 Q 在初始態(tài)上i?次，找到這 t 個目標(biāo)解的概率表示為pt N：

其中，sin（θt，N ）==（Ψ∣τ））。讓成功概率最大化需要的 Q 的重復(fù)次數(shù)可表示為 I ∈N，I=·

3 Grover 算法優(yōu)化方法

綜上可知，Grover 算法主要分為兩個部分，即量子黑盒運算和相位翻轉(zhuǎn)運算。布爾方程的計算只包含布爾加法“+”和乘法“×”，對應(yīng)到邏輯門操作為異或（ xor）和與（ and）。在量子黑盒中，xor運算可以用量子非門 x 實現(xiàn)，and 運算可以用量子toffoli門 ccx 或者多比特控制門 mcx 實現(xiàn)。

求解 n 個變元的方程組的線路理論需要的總比特個數(shù)為2n+1，每表示一個變元需要一個量子比特，共需要 n 個量子比特;由于量子計算過程是可逆的，所以量子黑盒還需要增加一些輔助比特存儲計算結(jié)果。每表示一個方程需要一個輔助比特，共需要 n 個輔助比特;最后還需要一個輔助的標(biāo)記比特位，因此共需要2n+1個量子比特。但是，由于種種原因，目前不論是模擬器還是量子計算機，能夠使用的比特數(shù)量是有限的，同時支持的線路深度也是有限的。因此，本文提出了一種 Grover 算法的線路優(yōu)化方案，該方案包含兩個方面。

（1）優(yōu)化線路深度。理論上，Grover 算法的迭代次數(shù)為解空間的開根號級別，此時可以以接近1的概率得到正確解，但是這樣的線路深度執(zhí)行起來有難度。為了降低線路深度，應(yīng)用精度換深度的思想，啟發(fā)式的選用一個遠(yuǎn)小于理論值的迭代次數(shù)（p× n），同時將最優(yōu)解限定在前 m 個概率最高的結(jié)果中，最后在這20個高概率的結(jié)果中尋找正確解。這種回代驗證的方式代價是很小的，實現(xiàn)了用較小的精度確損失換來深度的大幅減少。

（2）優(yōu)化線路比特資源。求解 n 個變元的方程組的量子門線路理論需要的總量子比特個數(shù)為2n+1。表示變元的量子比特數(shù)目是無法改變的，因此將優(yōu)化目標(biāo)放在了輔助比特上。為減少需要的輔助量子比特數(shù)，設(shè)計了輔助比特重復(fù)利用的思想，在使用過一些輔助量子比特后，再將其還原至初始狀態(tài)，隨著 n 的增加，總結(jié)規(guī)律可知輔助比特數(shù)量滿足1+2+…+k<=n，滿足此不等式的最小 k 值，即為（? ），此時輔助比特只需要 n+1+（? ）。不難看出，（? ）< n（ n>2），需要的量子比特數(shù)減少。

4實驗和結(jié)論

4.1案例實驗

以3變元的方程組為例，方程組如下：

由于變元是3個，因此需要量子比特 q0，q1和 q2表示變元 x1，x2和 x3。黑盒構(gòu)造參照之前提到的方法，以其中一個方程 x1x2+x3=1舉例，x1x2是乘法對應(yīng)的是 ccx 門，同時需要輔助比特 q3保存結(jié)果，x3和 x1x2是xor關(guān)系，因此將 x3和 x1x2結(jié)果應(yīng)用量子非門。基于此，將第一個方程的計算結(jié)果保存在量子比特 q3上。依次類推，即可表示每個方程，共需要7個量子比特。最后，根據(jù) Grover 算法，用額外的一個輔助比特位標(biāo)記所有的方程的正確解。三個方程之間是 and 的關(guān)系（ x1x2+x3）^not（ x2x3）^（ x1+x2+x2x3）=1，因此用的是 mcx 門實現(xiàn)標(biāo)記。對應(yīng)的黑盒線路如圖1所示。

因為量子計算是可逆的，同時為了后面算法迭代，需要將線路中輔助量子比特還原，通過對稱作用相同的門，即可實現(xiàn)。相位翻轉(zhuǎn)是 Grover 算法的一個固定的結(jié)構(gòu)，需要的比特數(shù)和變元數(shù)一致，即如圖2所示。

根據(jù) Grover 算法給出的理論最佳迭代次數(shù)是 pi/4×sqrt（8）～=2。結(jié)果是101，為正確解，概率是95%，接近1。線路深度是45。圖3和圖4分別為 Grover 求解線路圖和 Grover 求解結(jié)果圖。

4.2案例優(yōu)化

按照之前的分析，線路深度優(yōu)化方面，選用一個遠(yuǎn)小于理論值的迭代次數(shù)（0.5× n）=1。測量概率較高的前幾個結(jié)果，并帶回驗證是否是正確解。同時，按照比特重復(fù)利用思想，量子比特的數(shù)量是 n+1+（? ）=6。優(yōu)化的線路和結(jié)果如圖5和圖6所示。

不難發(fā)現(xiàn)，優(yōu)化后的線路深度是24。在概率較高的3個結(jié)果（011、100、101）中，通過帶回驗證發(fā)現(xiàn)，解101就在其中。這也就證明了通過精度換深度的思想是可行的。此外，測試了全部的不超過28變元的方程組，歸納得到一個遠(yuǎn)小于理論值的迭代次數(shù)（0.5×n），同時在前 m（ m<20）個概率最高的結(jié)果中尋找最優(yōu)解。同時，發(fā)現(xiàn)比特數(shù)量的增加比線路深度的增加帶來的時間復(fù)雜度更高這一結(jié)論，因此優(yōu)化比特數(shù)量更重要。

5分析討論

對于方程組，特別是非線性布爾方程組的求解問題，基于 Grover 搜索算法是一種可行的量子解決方案，在求解過程中，可以利用精度換時間及量子比特復(fù)用的技術(shù)實現(xiàn)線路深度和量子比特數(shù)的減少，可在更多的應(yīng)用中發(fā)揮作用。另外，受限于當(dāng)前的量子計算機的資源和深度，這種以理論為參考、啟發(fā)式的工程實現(xiàn)方案是一種不錯的選擇，同時對已知線路的優(yōu)化都可極大地激發(fā)當(dāng)前量子計算機的計算潛力。

參考文獻：

[1]劉連浩，段紹華，崔杰.一種基于Grobner基的代數(shù)攻擊方法[J].計算機工程，2008（16）：157?158+167.

[2] Faugere J C，JouxA.Algebraic cryptanalysis of hidden field equation （ HFE ） cryptosystems using Grbner bases [ J ]. Springer，2003：1?17.

[3]左鑫平，李俊全.一種改進的 XL 算法[ J].計算機工程，2008，34（19）：157?159.

[4]張帆，李蕾，熊炎.XL 算法的冗余分析與改進[ J].計算機工程，2011，37（16）：60?61+64.

[5] Strang G.Introduction to Linear Algebra [ M ].Wellesley? Cambridge Press Wellesley，2016.

[6] CHEN Y A，GAO X S.Quantum Algorithm for BooleanEquation? Solving? and? Quantum? Algebraic? Attack? onCryptosystems [ J ]. Journal? of? Systems? Science? and Complexity，2021，35（1）：373?412.

[7] Grover L K.Quantum Mechanics Helps in Searching for aNeedle in a Haystack[ J].Physical Review Letters，1997，79（2）：235.

[8] LONG G L，LI Y S，ZHANG W L，et al.Dominant gateimperfection in Grover，s quantum search algorithm [ J ]. Physical Review A，2000，61（4）：042305.

[9] CHUANG I? L， KUBINEC? M ， GERSHENFELD? N.Experimental implementation of fast quantum searching[J].Physical review letters，1998，80（15）：3408?3411.

[10] ZALKA C.UsingGrover，s quantum algorithm for searchingactual databases ? art.no.052305[J].Physical Review，A，2000，62（5）：2305?01?2305?04.

[11] YAMASHITA S.How to utilize a Grover search in general programming[ J].Laser Physics： An International Journaldevoted to Theoretical and Experimental Laser Research andApplication，2006，16（4）：730?734.

[12]阮越，陳漢武，劉志昊，等.量子主成分分析算法[ J].計算機學(xué)報，2014，37（3）：666?676.

[13] PENG H，JING J.Research on routing algorithm of Grover for wireless ad hoc quantum communication network[J].Journal of Zhejiang University of Technology ，2014，42（6）：612?615.

[14] SUN G D，SU S H，XU M Z.Quantum mechanical algorithms for solving root finding problem [ J ].Journal of Beijing University of Technology，2015，41（3）：366?371.

[15] Boyer M，Brassard G，H?yer P，et al.Tight Bounds onQuantum Searching [ J ].Fortschritte der Physik，1998，46（4?5）：493?505.

作者簡介：

錢宇梁（2001—），本科，研究方向：量子計算和量子機器學(xué)習(xí)。