基于Qiskit的Shor算法U门设计逻辑及33因式分解改造问询

一、为什么该U门采用量子比特交换的方式设计 #

15的二进制表示为4位，刚好可以用4个量子比特完整存储0~14的所有整数取值。对于所有和15互素的整数a，乘以a mod 15的操作本质上是对4位二进制数的比特位执行置换操作，不需要复杂的算术运算逻辑。
使用swap交换门实现比特置换，相比使用通用量子加法器、乘法器搭建的模乘电路，门数更少、电路深度更低，能有效降低量子计算过程中的噪声干扰，是当前场景下的最优实现方案。

二、参数a的取值具体如何影响量子比特交换方案 #

我们将4个量子比特对应为数值的二进制位q3 q2 q1 q0，对应数值为8*q3 +4*q2 +2*q1 + q0，不同a对应的操作逻辑如下：

• 当a=2时，乘以2 mod15等价于4位二进制数循环左移1位，对应3次顺序swap操作：swap(0,1)→swap(1,2)→swap(2,3)
• 当a=13时，13 ≡ -2 mod15，等价于先执行乘以2的循环左移，再对所有比特执行X门翻转，因此复用a=2的swap逻辑后额外加4个X门
• 当a=8时，乘以8 mod15等价于4位二进制数循环右移1位，对应3次逆序swap操作：swap(2,3)→swap(1,2)→swap(0,1)
• 当a=7时，7 ≡ -8 mod15，等价于先执行乘以8的循环右移，再对所有比特执行X门翻转，复用a=8的swap逻辑后额外加4个X门
• 当a=11时，11 ≡ -4 mod15，等价于交换q0↔q2、q1↔q3后整体比特翻转，对应swap(1,3)→swap(0,2)后加4个X门
  代码中的分支判断逻辑完全匹配上述不同a对应的置换规则。

三、如果需要对33进行因式分解，应如何调整该交换方案 #

对33做因式分解时，核心是将U门的功能从乘以a mod15调整为乘以a mod33，对应调整逻辑如下：

1. 扩展量子寄存器位数：33小于2^6=64，需要将原来的4量子比特寄存器扩展为6量子比特，才能覆盖0~32的所有整数取值
2. 适配置换逻辑限制：15是2^4 -1，因此乘2的幂次刚好对应循环移位，可以纯用swap实现，但33不满足2^n -1的特性，乘以a mod33的操作大多无法直接对应纯比特置换，因此不能直接复用原有的纯swap实现方案：
   • 如果要尽量沿用swap的低开销特性，可以先枚举所有和33互素的a，筛选出其中乘a操作刚好对应比特置换+单比特翻转的取值，仅针对这些a设计swap组合的实现
   • 如果需要支持所有合法a的取值，需要改用通用量子模乘电路实现，比如基于量子加法器搭建的受控模乘电路

内容的提问来源于stack exchange，提问作者CoolGas