量子计算中Shor算法的电路实现中的一个问题

Question

我正在研究Shor算法的量子电路实现，该算法使用python包Qiskit将15分解为质数的乘积。有关详细信息，请参阅此website。

我的问题是关于U-gate在这个网站上的实现。在本网站中，U-gate的实现方式如下

def c_amod15(a, power):
    """Controlled multiplication by a mod 15"""
    if a not in [2,7,8,11,13]:
        raise ValueError("'a' must be 2,7,8,11 or 13")
    U = QuantumCircuit(4)        
    for iteration in range(power):
        if a in [2,13]:
            U.swap(0,1)
            U.swap(1,2)
            U.swap(2,3)
        if a in [7,8]:
            U.swap(2,3)
            U.swap(1,2)
            U.swap(0,1)
        if a == 11:
            U.swap(1,3)
            U.swap(0,2)
        if a in [7,11,13]:
            for q in range(4):
                U.x(q)
    U = U.to_gate()
    U.name = "%i^%i mod 15" % (a, power)
    c_U = U.control()
    return c_U

我的问题是，为什么这个U门是通过交换量子位来设计的。'a‘的值到底会如何影响交换方案？如果我想要因数33呢？我应该如何将此交换方案更改为因子33？

Answer 1

a的值是Shor算法的相位估计部分的一部分，其中操作

|y> -> |ay mod N>

是否已应用。因此，a会影响算术运算，并且根据实现模乘的方式，会对最终电路产生不同的影响。

Qiskit教科书实现似乎只支持a的特殊值，但软件包本身具有所有a值的通用代码：https://github.com/Qiskit/qiskit-terra/blob/main/qiskit/algorithms/factorizers/shor.py

该代码使用傅里叶变换进行乘法，因此a将影响傅里叶变换后应用的相移。Qiskit的实现是基于this paper的，您可以在这里找到更多信息。

Answer 2

尝试在评论中回答您的问题：

我想我的问题是，为什么交换寄存器位可以给我们提供一个实现顺序发现算法的门。

Shor算法的一种方式是将其作为输入：

启动状态|ψ⟩的启动状态A

• * U和

Shor的算法告诉我们电路的周期，即你需要重复U的次数才能回到你的初始输入。然后，我们使用经典算法通过设置U|y⟩≡|ay mod N⟩和|ψ⟩=|1⟩将因式分解映射到此问题。

你可以通过模拟确认Qiskit教科书中的电路具有该属性，尽管它没有给出生成该电路的方法(我假设它是类似于this answer的训练有素的猜测，但你需要阅读另一个答案中的that paper以获得一般方法)。

如果我们已经知道使用算法的答案，那么我们可以找到任何具有正确周期的旧电路，并将其插入。例如，作用在|1⟩上的单个交换门的周期为2。虽然这不能真正算作“做肖尔算法”，但它经常被用来演示算法在1 2上的工作。

*为了使算法高效，输入确实是“为U^(2^x)制作电路的一种有效方式”。幸运的是，我们知道如何在分解所需的电路中做到这一点，但为了演示，Qiskit教科书只是低效地重复了U。