CN110417545A

CN110417545A - 有限域离散对数量子求解线路优化构造方法

Info

Publication number: CN110417545A
Application number: CN201910578711.XA
Authority: CN
Inventors: 张凯; 马智
Original assignee: PLA Information Engineering University
Current assignee: PLA Information Engineering University
Priority date: 2019-06-28
Filing date: 2019-06-28
Publication date: 2019-11-05
Anticipated expiration: 2039-06-28
Also published as: CN110417545B

Abstract

本发明涉及一种有限域离散对数量子求解线路优化构造方法，包含：针对有限域离散对数，构造加法进位门线路，以实现对乘法循环群生成元进行等价转换；设定加法进位门辅助比特，并通过加法量子线路实现递归执行加法进位门的操作；利用加法进位门线路进行比较操作，判断量子寄存器和常数相加时的进位信息，以实现模N加法量子线路优化；通过模N加法操作实现乘法操作，构造模N乘法量子线路；通过模N乘法操作实现模幂操作，构造模幂量子线路；组合模幂量子线路与已有量子傅里叶变换量子线路，构造实现有限域上求解离散对数的量子算法线路。本发明通过逻辑量子线路实现模加过程，降低对数求解计算量和复杂度，减轻软硬件运算负荷，具有较强应用前景。

Description

有限域离散对数量子求解线路优化构造方法

技术领域

本发明属于量子计算和密码学技术领域，特别涉及一种有限域离散对数量子求解线路优化构造方法。

背景技术

对于任一素数p，存在一个模p的乘法循环群G。设该循环群的生成元是g，则该循环群可表示为{g，g²，...，g^p-1}。给定群中任一元素x＝g^r∈G，求幂指数r的问题就是离散对数问题(Discrete Logarithm Problem，DLP)。DLP是第一个被用来设计公钥密码协议的困难问题。1976年，Diffie和Hellman提出的基于DLP的密钥交换协议，成为研究公钥密码协议的开端。1985年，ElGamal提出了基于DLP的密码算法和数字签名协议。如今，DLP被广泛用于设计密码方案和数字签名协议，基于DLP的密码算法和数字签名协议已成为密码领域内的一类重要研究方向。而这些密码方案和数字签名协议的安全性都依赖于DLP的计算困难假设上。Silver-Pohlig-Hellman算法、Pollar ρ算法和Index Calculus算法等是一些常见的求解DLP的经典算法，其中效果最好的经典算法是Gordon提出的数域筛法，该算法在上求解DLP的时间复杂度为exp(o((log p)^1/3(log log p)^2/3))，仍不是一个有效的多项式时间算法。对于(p不光滑)上的DLP，至今仍不存在有效的经典算法在多项式时间内求解该问题。1994年，Shor提出了可在多项式时间内求解任意群上DLP的量子算法，在给定问题规模为n比特时，算法时间复杂度为O(n³)。求解离散对数问题量子算法的量子计算部分包括两个模块：量子傅立叶变换和模幂，这也是求解整数分解问题量子算法的量子计算模块，而对Shor算法量子线路的优化构造设计也主要集中在这两个模块。模幂模块量子线路设计工作总体技术思路是：设计具备可逆逻辑运算功能的基本加法单元、模加单元、模乘单元，在此基础上实现量子线路的模幂功能。目前还没有针对求解有限域上离散对数问题量子算法的线路设计工作。

发明内容

为此，本发明提供一种有限域离散对数量子求解线路优化构造方法，降低对数求解过程中计算量和复杂度，减轻软硬件运算负荷，具有较强的应用前景。

按照本发明所提供的设计方案，一种有限域离散对数量子求解线路优化构造方法，包含如下内容：

A)针对有限域离散对数，构造加法进位门线路，以实现对乘法循环群生成元进行等价转换；

B)设定加法进位门辅助比特，并通过加法量子线路实现递归执行加法进位门的操作；

C)利用加法进位门线路进行比较操作，判断量子寄存器和常数相加时的进位信息，以实现模N加法量子线路优化；

D)通过模N加法操作实现乘法操作，构造模N乘法量子线路；

E)通过模N乘法操作实现模幂操作，构造模幂量子线路；

F)组合模幂量子线路与已有的量子傅里叶变换量子线路，构造实现有限域上求解离散对数的量子算法线路，以通过逻辑量子线路实现量子线路模幂功能。

上述的，B)中递归执行加法进位门操作的实现过程，包含如下内容：

利用|a_H>加法进位门的辅助比特，保存|a_L>+c_L的最高位进位信息；

根据进位信息对高位部分|a_H>做控制加1操作；

施加加法进位门操作，清楚比特|0>所携带的进位信息，还原比特状态。

优选的，根据进位信息对高位部分|a_H>做控制加1操作过程中，当加数中的某一位需要向高一位进位时，对该某一位辅助比特施加X操作，反转其状态，通过未初始化辅助量子比特的状态切换传递进位信息；若存在进位信息，则在辅助量子比特状态转换前后各设置一个由比特作为控制位的CNOT门，对目标量子位执行一次X操作；若不存在进位信息时，则目标量子位的状态保持不变。

上述的，C)中利用加法进位门线路进行比较操作，具体实现过程包含如下内容：

利用加法进位门线路对a+c和N做比较操作，判断量子寄存器|a>和常数c-N相加时的最高位进位信息，若存在进位，则设定a+c-N≥0，否则，a+c-N＜0；

利用加法量子线路，将|a>与常数c-N做加法操作，得到|a+c-N>；

对存储进位信息的进位比特做X操作；

根据进位比特状态对寄存器|a+c-N>做控制加N操作，得到|(a+c)modN>；

利用加法进位门对|(a+c)modN>和-c做加法操作，将进位比特还原为初始态|0>。

上述的，D)中模N乘法量子线路中，在模N加法量子线路基础上，构造量子线路实现模N乘法功能，其中，辅助量子寄存器恢复全零状态包含如下内容：

将存在在辅助量子寄存器中的模N乘法结果转存在第一个量子寄存器中，获取量子寄存器状态转换过程；

通过扩展欧几里得算法获取常数值，利用该常数值对第一个寄存器做模乘法操作，将结果累加到第二个寄存器中，以实现辅助量子寄存器恢复全零状态。

上述的，E)中，模幂操作中，将初始化为|1>的n比特量子寄存器，用于存储连乘操作结果、通过调用模N乘法量子线路n次模实现模幂运算。

本发明的有益效果：

本发明针对现有离散对数多项式求解问题，通过对量子求解算法线路进行优化设计，便于通过逻辑量子线路实现的模加法过程；构造的量子线路在求解上离散对数问题时，需要量子比特数量为4n+1，量子线路Toffoli门数量为O(n³logn)，相比现有的求解算法，降低计算量和运算复杂度，减轻软硬件运行负荷，具有较强应用前景。

附图说明：

图1为实施例中量子求解线路优化构造方法流程图；

图2为实施例中加法进位门线路示意；

图3为实施例中加法进位门量子线路优化效果图；

图4为实施例中常数加法量子线路示意；

图5为实施例中量子寄存器加法线路示意；

图6为实施例中模N加法量子线路优化示意；

图7为实施例中模N乘法量子线路示意；

图8为实施例中模幂量子线路示意；

图9为实施例中量子求解线路整体优化示意。

具体实施方式：

为使本发明的目的、技术方案和优点更加清楚、明白，下面结合附图和技术方案对本发明作进一步详细的说明。

针对目前多项式限域离散对数求解问题，本发明实施例中，参见图1所示，提供一种有限域离散对数量子求解线路优化构造方法，包含如下内容：

S101)针对有限域离散对数，构造加法进位门线路，以实现对乘法循环群生成元进行等价转换；

S102)设定加法进位门辅助比特，并通过加法量子线路实现递归执行加法进位门的操作；

S103)利用加法进位门线路进行比较操作，判断量子寄存器和常数相加时的进位信息，以实现模N加法量子线路优化；

S104)通过模N加法操作实现乘法操作，构造模N乘法量子线路；

S105)通过模N乘法操作实现模幂操作，构造模幂量子线路；

S106)组合模幂量子线路与已有的量子傅里叶变换量子线路，构造实现有限域上求解离散对数的量子算法线路，以通过逻辑量子线路实现量子线路模幂功能。

针对有限域上离散对数问题中，乘法循环群的生成元一般有多个，通过一定形式的等价转换，替换生成元后仍然可以得到待求离散对数问题的解r这一特性，对Thomas构造的量子常数加法线路结构做优化设计。

进一步地，本发明实施例中，加法进位门利用|a_H>作为辅助比特，保存|a_L>+c_L的最高位的进位信息；根据进位信息对高位部分|a_H>做控制加1操作；再次施加一次加法进位门操作，清除比特|0>所携带的进位信息，还原其状态；递归地进行下去，实现量子加法计算过程。

进一步地，本发明实施例中，将a做二进制展开，a_i∈{0，1}，可通过做n次由a_i控制的模N加法操作实现乘法操作，构造模N乘法量子线路。

进一步地，本发明实施例中，将a做二进制展开，a_i∈{0，1}，可通过做n次由a_i控制的模N乘法操作实现模幂操作，构造模幂量子线路。

进一步地，本发明实施例中，组合模幂量子线路与已有的量子傅里叶变换量子线路，构造有限域上求解离散对数问题的量子算法线路结构。

本发明实施例中所提供的加法进位门量子线路，是可以获得加法最高位比特进位信息的量子线路。如图2所示，当加数中的某一位需要向高一位进位时，对该位辅助比特施加X操作，反转其状态，通过未初始化辅助量子比特的状态切换传递进位信息。若存在进位信息，在该辅助量子比特状态转换前后各设置一个由该比特作为控制位的CNOT门，则只执行了一次对目标量子位的X操作；若不存在进位信息，则对目标量子位连续做了两次X操作或者零次X操作，目标量子位的状态保持不变。

当i＞0时，考虑到无论c_i＝0与否，当第i-1位存在进位且a_i＝1时，均存在第i位向第i+1位的进位。因此在g_i-1状态切换前后各设置一个以g_i-1和a_i为控制位g_i为目标位的Toffoli门，可实现第i-1位进位信息的传递。考虑当c_i＝1时：若a_i＝1则可施加一个由a_i作为控制位g_i作为目标位的CNOT门，对g_i进行状态转换，为避免后续的Toffoli门对g_i重复翻转，需对a_i位做X门操作；若a_i＝0且第i-1位存在进位时，仍能通过上述构造实现对g_i进行状态转换。

当i＝0时，显然只需要在c₀＝1时，设置一个由a₀作为控制位g₀作为目标位的CNOT门，就可以实现进位时对g₀的状态切换。注意到，此时可直接施加一个a₀和a₁为控制位g₀为目标位的Toffoli门，从而取代g₀的作用，减少使用一个辅助比特。而当c₀＝0时，a₀不产生进位，对整个加法进位过程没有影响，此时可将a₁作为起始比特进行加法进位操作。

图3中，在乘法循环群中，群中元素6、7均为的生成元，以6、7为常数构造的加法进位门线路如图3所示。

如图4所示，线路图中包含量子寄存器加1操作，Takahashi设计了一种量子加法线路，只需要2n+1个量子比特就能实现两个n比特量子寄存器的加法操作，即|a>|b>→|a+b>|b>。为形象描述其过程，图5根据Takahashi的方法，构造了两个4比特量子寄存器做加法操作的量子线路。重复利用上述加法操作就能实现量子寄存器的加1操作。

在构造了模N加法量子线路的基础上，可进一步构造量子线路实现模N乘法功能，即实现|a>→|(c·a)mod N>过程。模N乘法量子线路的设计方法比较单一，其思路是：将乘法操作转换为加法操作。图6为本发明实施例提供的模N加法量子线路优化设计图，图7为本发明实施例提供的模N乘法量子线路设计图。下详细介绍将图6中的辅助量子寄存器恢复全零状态的具体过程：

首先，将存储在辅助量子寄存器中的模N乘法结果转存在第一个量子寄存器中，量子寄存器的状态转换过程为：|a>|(c·a)mod N>→|(c·a)mod N>|a>。

其次，通过经典的扩展欧几里得算法求出(-c^-1)mod N的值，以该值作为常数对第一个寄存器|(c·a)mod N>做模乘法操作，将结果累加到第二个寄存器|a>中。

通过以上两个过程，辅助量子寄存器就恢复到全零状态。实现完整的模N乘法操作共做了2n次控制模N加法操作和一次量子寄存器比特交换操作。实现整个模N乘法量子线路共需2n+1个量子比特，其中2n个量子比特用作两个量子寄存器，额外的一个量子比特用于在模加法操作中存储进位信息。

图8为本发明实施例提供的模幂量子线路设计图。类似于模N乘法操作的实现思路，在做模幂运算|a>→|c^amod N>时，将a做二进制展开，则模幂运算可通过调用模N乘法量子线路n次模实现。模幂操作也需要一个初始化为|1>的n比特量子寄存器存储连乘操作结果。

图9为本发明实施例提供的求解有限域上离散对数问题量子算法线路优化设计图，图中包扩重复执行两次的模幂操作和量子傅里叶变换操作。图中U_a表示|x>→|(a·x)mod p>的模乘法运算，量子傅里叶变换模块的量子线路设计方式比较固定，设计方法较成熟，可参考相应材料。

在Shor算法分解n比特整数的量子线路设计中，若采用半经典量子傅立叶变换，在做模幂操作|a>|1>→|a>|c^amod N>时，量子寄存器|a>可只由一个量子比特构成。因此模幂操作量子线路的比特需求量可降为2n+2个，而在求解离散对数的量子算法线路设计中，构造的量子线路没有采用半经典量子傅立叶变换方法，构造的整个求解离散对数问题量子算法的线路共需4n+1个量子比特。

量子计算过程输出经典数据后，Shor在文献中给出了利用经典数据求解指数r的经典后处理过程。鉴于本发明内容只涉及量子算法线路优化设计部分，有关经典后处理过程的详细介绍可以参考原始文献。

Q#语言是微软公司于2017年推出的一款量子程序开发工具，可在Visual Studio集成开发环境中编译、调试、仿真运行量子程序。为验证本发明的有效性，可以利用Q#量子程序开发工具对本发明进行仿真实现。本发明实施例归纳综合主流量子线路设计，并对加法进位门线路以及模加法线路进行重点优化，首次完整实现了求解有限域上离散对数问题量子算法的量子线路。

除非另外具体说明，否则在这些实施例中阐述的部件和步骤的相对步骤、数字表达式和数值并不限制本发明的范围。

基于上述的方法，本发明实施例还提供一种服务器，包括：一个或多个处理器；存储装置，用于存储一个或多个程序，当所述一个或多个程序被所述一个或多个处理器执行，使得所述一个或多个处理器实现上述的方法。

基于上述的方法，本发明实施例还提供一种计算机可读介质，其上存储有计算机程序，其中，该程序被处理器执行时实现上述的方法。

本发明实施例所提供的装置，其实现原理及产生的技术效果和前述方法实施例相同，为简要描述，装置实施例部分未提及之处，可参考前述方法实施例中相应内容。

所属领域的技术人员可以清楚地了解到，为描述的方便和简洁，上述描述的系统和装置的具体工作过程，可以参考前述方法实施例中的对应过程，在此不再赘述。

在本申请所提供的几个实施例中，应该理解到，所揭露的系统、装置和方法，可以通过其它的方式实现。以上所描述的装置实施例仅仅是示意性的，例如，所述单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，又例如，多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些通信接口，装置或单元的间接耦合或通信连接，可以是电性，机械或其它的形式。

所述功能如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个处理器可执行的非易失的计算机可读取存储介质中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：U盘、移动硬盘、只读存储器(ROM，Read-Only Memory)、随机存取存储器(RAM，Random Access Memory)、磁碟或者光盘等各种可以存储程序代码的介质。

最后应说明的是：以上所述实施例，仅为本发明的具体实施方式，用以说明本发明的技术方案，而非对其限制，本发明的保护范围并不局限于此，尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，其依然可以对前述实施例所记载的技术方案进行修改或可轻易想到变化，或者对其中部分技术特征进行等同替换；而这些修改、变化或者替换，并不使相应技术方案的本质脱离本发明实施例技术方案的精神和范围，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应所述以权利要求的保护范围为准。

Claims

1.一种有限域离散对数量子求解线路优化构造方法，其特征在于，

D)通过模N加法操作实现乘法操作，构造模N乘法量子线路；

E)通过模N乘法操作实现模幂操作，构造模幂量子线路；

2.根据权利要求1所述的有限域离散对数量子求解线路优化构造方法，其特征在于，B)中递归执行加法进位门操作的实现过程，包含如下内容：

根据进位信息对高位部分|a_H>做控制加1操作；

3.根据权利要求1或2所述的有限域离散对数量子求解线路优化构造方法，其特征在于，根据进位信息对高位部分|a_H>做控制加1操作过程中，当加数中的某一位需要向高一位进位时，对该某一位辅助比特施加X操作，反转其状态，通过未初始化辅助量子比特的状态切换传递进位信息；若存在进位信息，则在辅助量子比特状态转换前后各设置一个由比特作为控制位的CNOT门，对目标量子位执行一次X操作；若不存在进位信息时，则目标量子位的状态保持不变。

4.根据权利要求1所述的有限域离散对数量子求解线路优化构造方法，其特征在于，C)中利用加法进位门线路进行比较操作，具体实现过程包含如下内容：

利用加法量子线路，将|a>与常数c-N做加法操作，得到|a+c-N>；

对存储进位信息的进位比特做X操作；

5.根据权利要求1所述的有限域离散对数量子求解线路优化构造方法，其特征在于，D)中模N乘法量子线路中，在模N加法量子线路基础上，构造量子线路实现模N乘法功能，其中，辅助量子寄存器恢复全零状态包含如下内容：

6.根据权利要求1所述的有限域离散对数量子求解线路优化构造方法，其特征在于，E)中，模幂操作中，将初始化为|1>的n比特量子寄存器，用于存储连乘操作结果、通过调用模N乘法量子线路n次模实现模幂运算。