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

錢宇梁 舒國(guó)強(qiáng) 封聰聰 邸詩(shī)秦

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

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

中圖法分類號(hào)：0413文獻(xiàn)標(biāo)識(shí)碼：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)工作

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

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

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

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

2背景知識(shí)

2.1布爾方程組

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

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

其中，x=（ x1，…，xn ）∈F2（n） ，u=（ u1，…，un ）∈F2（n） ，λu ∈ F2。這種表示稱為 f（ x ）的代數(shù)式（ Algebraic NormalForm，簡(jiǎn)稱為 ANF），多項(xiàng)式中的每一項(xiàng)∏i（n）=1 x i（u）i稱為f（x）的單項(xiàng)式（Monomial），它的次數(shù)定義為其中不同變量的個(gè)數(shù)，而f（ x）的所有單項(xiàng)式次數(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 算法

給定一個(gè)集合 X，元素?cái)?shù)目是 N，函數(shù)映射是f：X

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

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

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

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

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

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

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

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

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

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

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

4實(shí)驗(yàn)和結(jié)論

4.1案例實(shí)驗(yàn)

以3變?cè)姆匠探M為例，方程組如下：

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

因?yàn)榱孔佑?jì)算是可逆的，同時(shí)為了后面算法迭代，需要將線路中輔助量子比特還原，通過(guò)對(duì)稱作用相同的門，即可實(shí)現(xiàn)。相位翻轉(zhuǎn)是 Grover 算法的一個(gè)固定的結(jié)構(gòu)，需要的比特?cái)?shù)和變?cè)獢?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)化方面，選用一個(gè)遠(yuǎn)小于理論值的迭代次數(shù)（0.5× n）=1。測(cè)量概率較高的前幾個(gè)結(jié)果，并帶回驗(yàn)證是否是正確解。同時(shí)，按照比特重復(fù)利用思想，量子比特的數(shù)量是 n+1+（? ）=6。優(yōu)化的線路和結(jié)果如圖5和圖6所示。

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

5分析討論

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

參考文獻(xiàn)：

[1]劉連浩，段紹華，崔杰.一種基于Grobner基的代數(shù)攻擊方法[J].計(jì)算機(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]左鑫平，李俊全.一種改進(jìn)的 XL 算法[ J].計(jì)算機(jī)工程，2008，34（19）：157?159.

[4]張帆，李蕾，熊炎.XL 算法的冗余分析與改進(jìn)[ J].計(jì)算機(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].計(jì)算機(jī)學(xué)報(bào)，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.

作者簡(jiǎn)介：

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