基于Grover 算法的布尔二次方程组求解
作者：钱宇梁 舒国强 封聪聪 邸诗秦
来源：《计算机应用文摘》2022年第17期
        摘要：布爾方程组求解问题在密码等领域有着广泛而重要的研究意义，其中主要是非线性的布尔方程组求解较为困难。已知的经典求解算法的复杂度高，求解效率低下，而目前量
二项式分布的正则化子算法的加速优势为量子计算求解布尔方程组带来的新的可能，文章旨在应用已知的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 res
earch 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）上所有仿射函数和线性函数的集合。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。