量子计算创新专利申请——第五部分：Shor 算法与结论

作者：Sinan Utku

示例 4：Shor 算法

Shor 算法通过将问题简化为周期寻找任务，从而有效地将大整数分解为其质因数，这在量子计算机上比在经典计算机上解决得更有效率。该算法涉及准备输入的量子叠加态，并准备一个量子门来评估模幂运算函数。然后，它应用量子相位估计来提取该函数的周期。这包括对模幂运算应用量子门的受控幂次，然后执行逆量子傅里叶变换以获取有关周期的信息。一旦确定了周期，经典算法就会利用它相对容易地计算出整数的质因数。由于 Shor 算法比目前已知的最佳经典分解算法快得多（呈指数级增长），它对广泛使用的公钥密码系统（如依赖于大整数分解难度的 RSA）构成了重大威胁。

一台在没有密钥的情况下解密 RSA 加密通信的量子计算机可能会执行 Shor 算法：

• 准备第一个量子寄存器，其中包含初始化为计算基态的特征值量子比特；准备第二个量子寄存器，其中包含由对应于希望分解的乘积数的特征向量量子比特初始化的量子比特；
• 对每个特征值量子比特应用 Hadamard 门，使其处于叠加态；
• 对第二个量子寄存器应用与模幂运算变换相关的一系列幺正操作的幂次，其中每个幺正操作幂的应用由相应的特征值量子比特控制，并且特征值量子比特通过相位回馈（phase kick-back）进行修改；
• 对第一个量子寄存器执行逆量子傅里叶变换，以进行量子相位估计，并获得对应于作用在第二个量子寄存器上的基础幺正算子 U 的相位估计值；
• 从相位估计值中推导出周期参数，并使用推导出的周期参数确定对应于该乘积数的质因数；以及
• 使用确定的质因数、相关的公钥和乘积数来解密加密消息。

这项发明的专利适格性很可能会受到挑战。具体而言，它很可能最初被认为是抽象的，因为它指向解决数论问题的数学方法，而不是对机器的技术改进。Shor 算法的算法组件包含一系列数学运算，例如通过量子相位估计和逆量子傅里叶变换寻找周期。在量子计算机上执行这些数学运算，如果没有对量子计算机本身运行的具体改进，可能无法赋予其专利适格性。可以说，该算法唯一的改进是在数学处理方面——即使用量子计算机更有效地分解数字。一位严苛的 PTO 审查员可能会将该发明描述为使用常规和已知的量子计算过程（如叠加、受控幺正门和量子傅里叶变换）来执行一种改进的数学方法。这样的 PTO 审查员还可能会强调，专利化此类发明可能会导致对基础数学原理使用的全面预占（preemption）风险。因此，这项发明最终很有可能在现行法律下被判定为不具备适格性。

有趣的是，PTO 在一份指导文件中提供的示例中表示，针对 RSA 加密（可以被定性为 Shor 算法的功能补充）的发明是具有专利适格性的。[i] 这个示例针对的是一种在第一台计算机终端和第二台计算机终端之间建立加密通信的方法，该发明执行的步骤包括：(i) 接收明文词信号；(ii) 将明文词信号转换为消息块；(iii) 使用数学过程对每个消息块进行编码；以及 (iv) 通过通信信道将生成的密文传输到第二台计算机终端。PTO 在其指南中最初表示该发明是抽象的。然而，它发现，加入诸如在第一台计算机终端接收明文词信号、将明文词信号转换为消息块词信号、以及通过通信信道将编码后的密文词信号传输到第二台计算机终端等步骤，将原本抽象的发明整合到了具有专利性的实际应用中。特别是，它发现“附加元素的组合以特定的方式使用了数学公式和计算，充分限制了数学概念在通过通信信道向计算机终端传输密文词信号这一实际应用中的使用。”^[ii]