关键词:
有限域
乘法运算
矩阵乘法
量子电路
摘要:
量子计算机具有强大的计算能力,相比于经典计算机,可以同时进行多个操作,计算速度大幅度提升,在解决优化问题和处理NP难问题方面更有优势,能够更快地找到最优解。有限域上的基本运算是现代密码学的重要理论基础,很多加密算法的设计和分析都是在有限域中完成的。实现与优化有限域上基本运算的量子电路对现代密码学中的加密算法研究有重要意义。本文主要研究有限域上的乘法运算,矩阵和布尔矩阵乘法运算的量子电路实现和优化,具体如下:
对于有限域上的乘法运算,首先,用矩阵的形式表示有限域中两个元素的乘积,实现有限域(2~4)上乘法运算的量子电路。其次,简化乘法运算的布尔表达式,优化有限域(2~4)上乘法运算的量子电路。然后,通过复合域的方法,选择不可约多项式和同构矩阵,进一步优化有限域(2~4)上乘法运算的量子电路。最后,通过量子电路等效替换的方法,优化有限域(2~8)上乘法运算的量子电路,共使用24个量子比特,118个CNOT门,27个Toffoli门,与现有的方法比较,使用的量子资源最少。
对于有限域上的矩阵实现,提出了一个*搜索算法,首先定义矩阵的汉明距离,检查汉明距离的减少来选择CNOT门,然后将CNOT门序列转换为一系列初等矩阵的乘积,使用初等矩阵乘法的简化规则,减少初等矩阵的个数,优化矩阵实现的量子电路。以高级加密标准AES的列混合矩阵为例,只使用CNOT门实现其量子电路,仅需107个CNOT门。
对于两个布尔矩阵的乘法运算,给出了一种直接实现其量子电路的方法,在布尔矩阵元素相乘的位置添加Toffoli门。在含有可逆矩阵或满秩矩阵的布尔矩阵乘法中,提出了将可逆矩阵或满秩矩阵的量子电路作用在另一个矩阵对应列向量上的方法,优化其量子电路。比较两种方法,对于两个n阶可逆矩阵相乘的量子电路,直接实现的方法共使用3n2个量子比特和n3个Toffoli门,优化后的方法共使用n2个量子比特和n3个CNOT门。