Order finding(求阶算法)

目录

1.阶的定义

1.1 构造|us>

1.2 构造受控U

2.求阶步骤

1.阶的定义

阶r的定义是使得x的r次方 mod N=1的最小正整数，其中x和N是互质的，同时1

x的整数倍mod N 可以遍历0~N-1之间所有的整数。

如果我们想要求解r的话，结合相位估计的原理，如果我们可以将阶转换为相位，只需要经过逆傅里叶变换便可以求得阶，但是相位估计是有两大前提条件的，第一个是存在|u>；第2个是受控U是可以实现的。

1.1 构造|us>

order-finding构造的|u>如下（其中整数𝑠（0≤𝑠≤𝑟−1）：

|us>存在以下两个非常巧妙的性质：

性质1：

证明如下，直接利用了黄皮书练习5.13的结论：

详细证明步骤：

性质2：

如果要制备|us>需要我们知道r，但是这是不可能的，利用性质2，我们可以回避|us>的制备问题，第二个量子寄存器的输入也不需要是|us>，|1>态作为第二寄存器的输入。

1.2 构造受控U

利用盒子5.2 求模幂，我们希望计算变换（这个讲述的是的实现）

电路图如下：

在这里第二寄存器中的|y>为|1>。

2.求阶步骤

线路如图：

步骤如下：

作为输入态第二个量子寄存器为1，这是因为：

推荐阅读博客《order finding before shor's algorithm》