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

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

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

關鍵詞：布爾二次方程;Grover 算法;二次加速;量子計算;線路優化

中圖法分類號：0413文獻標識碼：A

Solving Boolean quadratic equations based on grover algorithm

QIAN Yuliang'，SHUGuoqiang，FENG 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相關工作

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

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

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

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

2背景知識

2.1布爾方程組

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

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

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

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

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

2.2 Grover 算法

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

其中，T 是要找到的目標解的集合，元素數量是 t。 Grover 算法是一個需要重復應用下面的操作多次的算法。

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

式（6）中，H? n 是一個 Hadamard 算符的集合，|τ）是一個由所有目標態構成的一個等概率疊加態構成的態。

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

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

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

3 Grover 算法優化方法

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

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

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

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

4實驗和結論

4.1案例實驗

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

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

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

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

4.2案例優化

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

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

5分析討論

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

參考文獻：

[1]劉連浩，段紹華，崔杰.一種基于Grobner基的代數攻擊方法[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].計算機學報，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—），本科，研究方向：量子計算和量子機器學習。