量程算法Quantum Algorithms

振幅放大Amplitude Amplification

振幅放大是量程计算的一项基本工具。Amplitude Amplification is one of the fundamental tools of Quantum Computing. 这是一种基本的概念,即 Grover 的搜索、幅度估算和许多量程机器学习算法。It is the fundamental idea that underlies Grover's search, amplitude estimation and many quantum machine learning algorithms. 有很多变体,在 Q # 中,我们提供了一个基于在意波幅放大的通用版本,并提供了部分反射,以允许最广泛的应用程序区域。There are many variants, and in Q# we provide a general version based on Oblivious Amplitude Amplification with Partial Reflections to allow for the widest area of application.

振幅放大的中心思想是通过执行一系列反射来放大所需结果的概率。The central idea behind amplitude amplification is to amplify the probability of a desired outcome occurring by performing a sequence of reflections. 这些反射会使初始状态更接近所需的目标状态,通常称为标记的状态。These reflections rotate the initial state closer towards a desired target state, often called a marked state. 具体来说,如果将初始状态测量为标记状态的概率为 $ \sin ^ 2 (\theta) $,然后在应用振幅放大后 $m $ 次,则成功的概率为 $ \sin ^ 2 ((2m + 1) \theta) $。Specifically, if the probability of measuring the initial state to be in a marked state is $\sin^2(\theta)$ then after applying amplitude amplification $m$ times the probability of success becomes $\sin^2((2m+1)\theta)$. 这意味着,如果 $ \theta = \ pi/[2 (2n + 1)] $\$n $ 的某些值,则幅度放大功能能够提高 $n $ 迭代幅度放大后成功 $100% $ 的概率。This means that if $\theta = \pi/[2(2n+1)]$ for some value of $n$ then amplitude amplification is capable of boosting the probability of success to $100\%$ after $n$ iterations of amplitude amplification. 由于 $ \theta = \sin ^{-1}(\sqrt{\Pr (success)}) $ 这意味着,要明确获取成功所需的迭代次数几率低于需要使用随机抽样来确定标记状态的不确定状态所需的次数。Since $\theta = \sin^{-1}(\sqrt{\Pr(success)})$ this means that the number of iterations needed to obtain a success deterministically is quadratically lower than the expected number needed to find a marked state non-deterministically using random sampling.

振幅放大的每个迭代都需要指定两个反射运算符。Each iteration of Amplitude amplification requires that two reflection operators be specified. 具体而言,如果 $Q $ 是振幅放大循环访问,$P _0 $ 是在初始子空间上的一个投影仪运算符,并且 $P _1 $ 就是投影仪到标记的子空间,然后 $Q =-(\boldone-2P_0)(\boldone-2P_1) $。Specifically, if $Q$ is the amplitude amplification iterate and $P_0$ is a projector operator onto the initial subspace and $P_1$ is the projector onto the marked subspace then $Q=-(\boldone-2P_0)(\boldone -2P_1)$. 回忆一下,投影仪是 Hermitian 运算符,其中包含本征值 $ + $1 和 $0 $,因此 $ (\boldone 2P_0) $ 是单一的,因为它具有作为 unity 根的本征值(在本例中为 $ \pm $1)。Recall that a projector is a Hermitian operator that has eigenvalues $+1$ and $0$ and as a result $(\boldone -2P_0)$ is unitary because it has eigenvalues that are roots of unity (in this case $\pm 1$). 作为示例,请考虑使用初始状态 $H ^ {\otimes n} \ket{0}$ and 标记状态 $ \ket{m} $,$P _0 = H ^ {\otimes n} \ket{0}\bra{0}H ^ {\otimes n} $ 和 $P _1 = \ket{m}\bra{m} $ 的情况。As an example, consider the case of Grover's search with initial state $H^{\otimes n} \ket{0}$ and marked state $\ket{m}$, $P_0 = H^{\otimes n}\ket{0}\bra{0}H^{\otimes n}$ and $P_1= \ket{m}\bra{m}$. 在幅度放大的大多数应用程序中 $P _0 $ 将成为初始状态的投影仪,这意味着 $P _0 = \boldone-2 \ 票证 {\ psi} \ 寄存器 {\ psi} $ for a vector $ \ket{\psi} $;但对于在意波幅 amplication $P _0 $ 通常投影到许多量程状态(即,$P _0 $ 的 $ + $1 eigenvalue 的重数大于 $1 $)。In most applications of amplitude amplification $P_0$ will be a projector onto an initial state meaning that $P_0 = \boldone -2\ket{\psi}\bra{\psi}$ for some vector $\ket{\psi}$; however, for oblivious amplitude amplication $P_0$ will typically project onto many quantum states (i.e. the multiplicity of the $+1$ eigenvalue of $P_0$ is greater than $1$).

振幅放大后的逻辑直接在 $Q $ 的本征分解之后。The logic behind amplitude amplification follows directly from the eigen-decomposition of $Q$. 具体而言,$Q $ 的的本征向量 $ 表明初始状态具有非零支持可以显示为 $P 0 $ 和 $P 1 $ 的 $ + $1 本征向量的线性组合。Specifically, the eigenvectors of $Q$ that the initial state has non-zero support over can be shown to be linear combinations of the $+1$ eigenvectors of $P_0$ and $P_1$. 具体而言,振幅放大的初始状态(假设它为 $P 0 $ 的 $ + $1 eigenvector)可以编写为 $ $ \ket{\psi} = \frac{-i}{\sqrt{2}} \left (e ^ {i\theta} \ 票证 {\ psi} \ i\theta {\ psi-} 票证),$ $ (其中 $ \ket{\ psi \pm} $)本征向量 $Q $ with 本征值 $e ^ {\pm 2i \ theta} $,并且仅支持 $P 本征向量 $ 和 $P 1 $ 的 $ + $1 0。Specifically, the initial state for amplitude amplification (assuming it is a $+1$ eigenvector of $P_0$) can be written as $$ \ket{\psi}=\frac{-i}{\sqrt{2}}\left(e^{i\theta}\ket{\psi+} + e^{-i\theta}\ket{\psi-}\right), $$ where $\ket{\psi_\pm}$ are eigenvectors of $Q$ with eigenvalues $e^{\pm 2i\theta}$ and only have support on the $+1$ eigenvectors of $P_0$ and $P_1$. 本征值 $e 是 ^ {\pm i \theta} $ 这一事实意味着运算符 $Q $ 在两个投影仪指定的二维子空间中执行旋转,而初始状态则为 ""。The fact that the eigenvalues are $e^{\pm i \theta}$ implies that the operator $Q$ performs a rotation in a two-dimensional subspace specified by the two projectors and the initial state where the rotation angle is $2\theta$. 这就是 $m $ $Q $ 迭代的原因是 $ \sin ^ 2 ([2m + 1] \theta) $ 的成功概率。This is why after $m$ iterations of $Q$ the success probability is $\sin^2([2m+1]\theta)$.

这一问题的另一个有用的属性是 eigenvalue $ \theta $ 直接与初始状态要标记的概率相关,在 $P 这种情况下,只会将一个投影仪置于初始状态。Another useful property that comes out of this is that the eigenvalue $\theta$ is directly related to probability that the initial state would be marked (in the case where $P_0$ is a projector onto only the initial state). 由于 $Q $ 的 eigenphases 是 $ 2 \ theta = 2 \ sin ^{-1}(\sqrt{\Pr (success)}) $,因此,如果我们将阶段估算应用到 $Q $,则我们可以了解单一量程过程成功的概率。Since the eigenphases of $Q$ are $2\theta = 2\sin^{-1}(\sqrt{\Pr(success)})$ it then follows that if we apply phase estimation to $Q$ then we can learn the probability of success for a unitary quantum procedure. 这很有用,因为它需要几率更少的量程过程应用程序,以了解与其他情况下的成功概率。This is useful because it requires quadratically fewer applications of the quantum procedure to learn the success probability than would otherwise be needed.

Q # 将振幅放大引入为在意波幅放大的专用化。Q# introduces amplitude amplification as a specialization of oblivious amplitude amplification. 在意波幅放大盈利此名字对象,因为投影仪到初始 eigenspace 无需投影仪到初始状态。Oblivious amplitude amplification earns this moniker because the projector onto the initial eigenspace need not be a projector onto the initial state. 从这种意义上讲,该协议在意初始状态。In this sense, the protocol is oblivious to the initial state. 在意波幅放大的关键应用是单一 Hamiltonian 模拟方法的一些线性组合,其中初始状态是未知的,但会在模拟协议中与 ancilla 注册放大。The key application of oblivious amplitude amplification is in certain linear combinations of unitary Hamiltonian simulation methods, wherein the initial state is unknown but becomes entangled with an ancilla register in the simulation protocol. 如果将此 ancilla 寄存器测量为固定值(如 $0 $),则此类模拟方法会将所需的单一转换应用到剩余的 qubits (称为系统注册)。If this ancilla register were to be measured to be a fixed value, say $0$, then such simulation methods apply the desired unitary transformation to the remaining qubits (called the system register). 但是,所有其他测量结果都会导致故障。All other measurement outcomes lead to failure however. 在意波幅放大允许使用以上推理将此度量值的成功提升为 $100\% $。Oblivious amplitude amplification allows the probability of success of this measurement to be boosted to $100\%$ using the above reasoning. 而且,普通幅度放大对应于系统注册为空的情况。Further, ordinary amplitude amplification corresponds to the case where the system register is empty. 这就是 Q # 使用在意波幅放大子例程的原因。This is why Q# uses oblivious amplitude amplification as its fundamental amplitude amplification subroutine.

常规例程(AmpAmpObliviousByReflectionPhases)具有两个注册 ancillaRegistersystemRegisterThe general routine (AmpAmpObliviousByReflectionPhases) has two registers that we call ancillaRegister and systemRegister. 它还接受两个 oracles 来实现必要的反射。It also accepts two oracles for the necessary reflections. ReflectionOracle 仅在 ancillaRegister 上起作用,而 ObliviousOracle 在两个寄存器上共同操作。The ReflectionOracle acts only on the ancillaRegister while the ObliviousOracle acts jointly on both registers. ancillaRegister 的输入必须初始化为第一个反射运算符 $ \boldone-2P_1 $ 的第1个 eigenstate。The input to ancillaRegister must be initialized to a -1 eigenstate of the first reflection operator $\boldone -2P_1$.

通常,oracle 在计算基础 $ \ket{0...0} $ 中准备状态。Typically, the oracle prepares the state in the computational basis $\ket{0...0}$. 在我们的实现中,有一个 qubit (flagQubit)的 ancillaRegister consistes,用于控制 stateOracle 和所需的其余 ancillas。In our implementation, the ancillaRegister consistes of one qubit (flagQubit) that controls the stateOracle and the rest of the desired ancillas. flagQubit 为 $ \ket{1}$ 时应用 stateOracleThe stateOracle is applied when the flagQubit is $\ket{1}$.

还可以通过调用 AmpAmpObliviousByOraclePhases提供 oracles StateOracleObliviousOracle 而不是反射。One may also provide oracles StateOracle and ObliviousOracle instead of reflections via a call to AmpAmpObliviousByOraclePhases.

如前所述,传统的振幅放大只是这些例程的一种特殊情况,其中 ObliviousOracle 是标识运算符,并且没有系统 qubits (即 systemRegister 为空)。As mentioned, traditional Amplitude Amplification is just a special case of these routines where ObliviousOracle is the identity operator and there are no system qubits (i.e., systemRegister is empty). 如果要获取部分反射的阶段(例如,对于 Grover 搜索),可以使用函数 AmpAmpPhasesStandardIf you wish to obtain phases for partial reflections (e.g., for Grover search), the function AmpAmpPhasesStandard is available. 有关 Grover 算法的示例实现,请参阅 DatabaseSearch.qsPlease refer to DatabaseSearch.qs for a sample implementation of Grover's algorithm.

我们将 qubit 轮换阶段与反射运算符阶段相关联,如 G.H. Low,语中所述。We relate the single-qubit rotation phases to the reflection operator phases as described in the paper by G.H. Low, I. L. Chuang. 使用的固定点阶段在Yoder、low 和语以及low、Yoder 和语的阶段中进行了详细说明。The fixed point phases that are used are detailed in Yoder, Low and Chuang along with the phases in Low, Yoder and Chuang.

对于背景,你可以从标准幅度放大开始,转到在意波幅放大简介,最后展示为Low 和语For background, you could start from Standard Amplitude Amplification then move to an introduction to Oblivious Amplitude Amplification and finally generalizations presented in Low and Chuang. Dominic Berry提供了这一整个区域(与 Hamiltonian 模拟相关)的良好概述演示。A nice overview presentation of this entire area (as it relates to Hamiltonian Simulation) was given by Dominic Berry.

量程傅立叶转换Quantum Fourier Transform

傅立叶转换是一种古典型分析工具,与量程计算一样重要。The Fourier transform is a fundamental tool of classical analysis and is just as important for quantum computations. 此外,量程傅立叶转换(QFT)的效率远远超过了传统计算机上可能的功能,因此,在设计量程算法时,首先要选择的工具之一。In addition, the efficiency of the quantum Fourier transform (QFT) far surpasses what is possible on a classical machine making it one of the first tools of choice when designing a quantum algorithm.

作为 QFT 的大致通用化,我们提供了 ApproximateQFT 操作,该操作允许通过修剪旋转(对所需的算法准确性并不是绝对必需的)进行进一步的优化。As an approximate generalization of the QFT, we provide the ApproximateQFT operation that allows for further optimizations by pruning rotations that aren't strictly necessary for the desired algorithmic accuracy. 大致的 QFT 要求 dyadic $Z $-旋转操作 RFracH 操作。The approximate QFT requires the dyadic $Z$-rotation operation RFrac as well as the H operation. 输入和输出假设编码为大字节序编码---也就是说,具有索引 0 的 qubit 在二进制整数表示形式的最左端(最高)位进行编码。The input and output are assumed to be encoded in big endian encoding---that is, the qubit with index 0 is encoded in the left-most (highest) bit of the binary integer representation. 这与票证表示法一致,因为状态 $ \ket 中的三个 qubits 的寄存器{100}$ 对应于 $q _0 $ 处于状态 $ \ket{1}$,同时 $q _1 $ 和 $q _2 $ 都处于状态 $ \ket{0}$。This aligns with ket notation, as a register of three qubits in the state $\ket{100}$ corresponds to $q_0$ being in the state $\ket{1}$ while $q_1$ and $q_2$ are both in state $\ket{0}$. 近似值参数 $a $ 确定 $Z $ 旋转的修剪级别,即 $a \in [0 ... n] $。The approximation parameter $a$ determines the pruning level of the $Z$-rotations, i.e., $a \in [0..n]$. 在这种情况下,所有 $Z $-循环 $ 2 \ pi/2 ^ k $,其中 $k > $ 将从 QFT 线路中删除。In this case all $Z$-rotations $2\pi/2^k$ where $k > a$ are removed from the QFT circuit. 已知 $k \ge \ log_2 (n) + \ log_2 (1/\epsilon) + $3。It is known that for $k \ge \log_2(n) + \log_2(1 / \epsilon) + 3$. 一个可以绑定 $\|\operatorname{QFT}-\operatorname{AQFT} \|< \epsilon $。one can bound $\| \operatorname{QFT} - \operatorname{AQFT} \| < \epsilon$. 此处 $\| \cdot\| $ 是运算符标准,这种情况下,这种情况下是 $ (\operatorname{QFT}-\operatorname{AQFT})(\operatorname{QFT}-\operatorname{AQFT}) ^ \dagger $ 的最大eigenvalue的平方根。Here $\|\cdot\|$ is the operator norm which in this case is the square root of the largest eigenvalue of $(\operatorname{QFT} - \operatorname{AQFT})(\operatorname{QFT} - \operatorname{AQFT})^\dagger$.

算术Arithmetic

正如算术在传统计算中扮演中心角色一样,在量程计算中也是必不可少的。Just as arithmetic plays a central role in classical computing, it is also indispensable in quantum computing. 诸如选定的分解算法、量程模拟方法以及许多 oracular 算法等算法依赖于一致的算术运算。Algorithms such as Shor's factoring algorithm, quantum simulation methods as well as many oracular algorithms rely upon coherent arithmetic operations. 用于在量程创建线路上进行算法生成的大多数方法。Most approaches to arithmetic build upon quantum adder circuits. 最简单的添加程序会将传统输入 $b $,并将值添加到包含整数 $ \ket{a} $ 的量程状态。The simplest adder takes a classical input $b$ and adds the value to a quantum state holding an integer $\ket{a}$. 从数学上来说,\operatorname{Add} 的 "提供程序" (我们表示 "用于经典 $b 输入的 $ (b) $")具有属性,该属性Mathematically, the adder (which we denote $\operatorname{Add}(b)$ for classical input $b$) has the property that

$ $ \operatorname{Add} (b) \ket{a} = \ket{a + b}。$$ \operatorname{Add}(b)\ket{a}=\ket{a + b}. $ $ 这一基本的增加,incrementer 比一个增加程序更多。$$ This basic adder circuit is more of an incrementer than an adder. 它可以通过 $ $ \operatorname{Add}\ket{a}\ket{b} = \ket{a}\ket{a + b} 转换为具有两个量程输入的合并程序,$ $ 使用添加器的 $ 受控应用程序 \begin{align} \operatorname{Add} \Ket{a} \ket{b} & = \Lambda_{a_0} \left $n (\operatorname{Add} (1) \right) \Lambda_{a_1} \left (\operatorname{Add} (2) \right) \Lambda_{a_2} \left (\operatorname{Add} (4) \right} \cdots \Lambda (\o {Add} ({{\right}})) \ket{a}\ket{b} \\ & = \ket{a} \ket{b + a},\end{align} $n $ 位整数 $a $ and $b $,加法取模 $ 2 ^ n $。__It can be converted into an adder that has two quantum inputs via $$ \operatorname{Add}\ket{a}\ket{b}=\ket{a}\ket{a+b}, $$ using $n$ controlled applications of adders of the form \begin{align} \operatorname{Add} \ket{a} \ket{b} & = \Lambda_{a_0} \left(\operatorname{Add}(1) \right) \Lambda_{a_1} \left(\operatorname{Add}(2) \right) \Lambda_{a_2} \left(\operatorname{Add}(4) \right) \cdots \Lambda_{a_{n-1}} \left(\operatorname{Add}({{n-1}}) \right) \ket{a}\ket{b} \\ & = \ket{a} \ket{b + a}, \end{align} for $n$-bit integers $a$ and $b$ and addition modulo $2^n$. 请记住,notation $ \Lambda_x (A) $ 将 qubit $x $ 作为控件的操作的受控版本 $A 引用。Recall that the notation $\Lambda_x(A)$ refers, for any operation $A$, to the controlled version of that operation with the qubit $x$ as control.

同样,经典受控乘法(这是选定的分解算法必需的模块化形式)可以通过使用一系列类似的受控添加来执行: \begin{align} \operatorname{Mult} (a) \ket{x}\ket{b} & = \Lambda_{x_0} \left (\operatorname{Add} (2 ^ 0 a) \right) \Lambda_{a_1} \left (\operatorname{Add} (2 ^ 1a) \right) \Lambda_{a_2} \left (\operatorname{Add} (2 ^ 2 {n-1}} \left (\operatorname{Add} ({2 ^ {n-1}} a) \right) \ket{x}\ket{b} \\ & = \ket{x}\ket{b + ax}。__Similarly, classically controlled multiplication (a modular form of which is essential for Shor's factoring algorithm) can be performed by using a similar series of controlled additions: \begin{align} \operatorname{Mult}(a)\ket{x}\ket{b} & = \Lambda_{x_0}\left(\operatorname{Add}(2^0 a)\right) \Lambda_{a_1}\left(\operatorname{Add}(2^1a)\right) \Lambda_{a_2}\left(\operatorname{Add}(2^2 a)\right) \cdots \Lambda_{x_{n-1}} \left(\operatorname{Add}({2^{n-1}}a) \right)\ket{x}\ket{b} \\ & = \ket{x}\ket{b+ax}. \end{align} 在量程计算机上有一个个很微妙,你可能会注意到上面 $ \operatorname{Mult} $ 的定义。\end{align} There is a subtlety with multiplication on quantum computers that you may notice from the definition of $\operatorname{Mult}$ above. 与此不同,此线路的量程版本将输入的产品存储在辅助寄存器中而不是输入寄存器中。Unlike addition, the quantum version of this circuit stores the product of the inputs in an ancillary register rather than in the input register. 在此示例中,寄存器用值 $b $ 进行初始化,但它通常会开始将值保留为零。In this example, the register is initialized with the value $b$, but typically it will start holding the value zero. 这在中是必需的,因为一般情况下,一般 $a $ 和 $x $ 之间没有乘法逆。This is needed in because in general there is not a multiplicative inverse for general $a$ and $x$. 由于所有量程操作(节省度量值)都是可逆的,因此我们需要保留足够的信息来反转乘法。Since all quantum operations, save measurement, are reversible we need to keep enough information around to invert the multiplication. 出于此原因,结果将存储在单独的数组中。For this reason the result is stored in a separate array. 在单独的寄存器中保存不可逆操作(如乘法)输出的这一技巧称为 Charlie Bennett 后的 "Bennett 技巧",它是可逆计算和量程计算的一项基本工具。This trick of saving the output of an irreversible operation, like multiplication, in a separate register is known as the "Bennett trick" after Charlie Bennett and is a fundamental tool in both reversible and quantum computing.

已建议使用许多量程线路进行添加,并且每个线路在 qubits (空间)数和所需的入口操作(时间)数方面探讨了不同的折衷。Many quantum circuits have been proposed for addition and each explores a different tradeoff in terms of the number of qubits (space) and the number of gate operations (time) required. 我们将在以下两个高空间高效的添加器(称为 Draper 的 Beauregard 和的)中查看。We review two highly space efficient adders below known as the Draper adder and the Beauregard adder.

DraperDraper Adder

Draper 添加是最巧妙的量程添加器之一,因为它直接调用量程属性以执行添加。The Draper adder is arguably one of the most elegant quantum adders, as it directly invokes quantum properties to perform addition. Draper 加载程序背后的见解是,可以使用傅立叶变换将相位移位转换成移位。The insight behind the Draper adder is that the Fourier transform can be used to translate phase shifts into a bit shift. 接下来,通过应用傅立叶变换,应用适当的阶段移位,然后撤消傅立叶转换,可以实现一个转换程序。It then follows that by applying a Fourier transform, applying appropriate phase shifts, and then undoing the Fourier transform you can implement an adder. 与其他许多已建议的添加器不同,Draper 的创建程序显式使用通过量程傅立叶转换引入的量程效果。Unlike many other adders that have been proposed, the Draper adder explicitly uses quantum effects introduced through the quantum Fourier transform. 它没有典型的传统对应项。It does not have a natural classical counterpart. 下面给出了 Draper 提供的特定步骤。The specific steps of the Draper adder are given below.

假设您有两个 $n $ bit qubit 寄存器将整数 $a $ 和 $b $,然后针对所有 $a $ $ $ \operatorname{QFT}\ket{a} = \frac{1}{\sqrt{2 ^ n}} \sum_{j = 0} ^ {2 ^ n-1} e ^ {i2\pi (aj)/2 ^ n} \ket{j}。Assume that you have two $n$-bit qubit registers storing the integers $a$ and $b$ then for all $a$ $$ \operatorname{QFT}\ket{a}= \frac{1}{\sqrt{2^n}}\sum_{j=0}^{2^n-1} e^{i2\pi(aj)/2^n} \ket{j}. $ $ 如果我们定义 $ $ \ket{\phi_k (a)} = \frac{1}{\sqrt{2}} \left (\ket{0} + e ^ {i2\pi a/2 ^ k} \ket{1} \right),$ $ 则在某个代数后,可以看到 $ $ \operatorname{QFT}\ket{a} = \ket{\phi_1 (a)} \otimes \cdots \otimes \ket{\phi_n (a)}。$$ If we define $$ \ket{\phi_k(a)} = \frac{1}{\sqrt{2}}\left(\ket{0} + e^{i2\pi a /2^k}\ket{1} \right), $$ then after some algebra you can see that $$ \operatorname{QFT}\ket{a}=\ket{\phi_1(a)}\otimes \cdots \otimes \ket{\phi_n(a)}. $ $ 要执行转换程序的路径在观察到输入的总和可以写为 $ $ \ket{a + b} = \operatorname{QFT} ^{-1}\ket{\phi_1 (a + b)} \otimes \cdots \otimes \ket{\phi_n (a + b)} 后,就变得清楚。$$ The path towards performing an adder then becomes clear after observing that the sum of the inputs can be written as $$ \ket{a+b}=\operatorname{QFT}^{-1}\ket{\phi_1(a+b)}\otimes \cdots \otimes \ket{\phi_n(a+b)}. $ $ $B $ 和 $a $ 的整数,则可以通过使用 $b $ 的位作为控件,在分解中的每个 qubits 上执行受控制的阶段旋转。$$ The integers $b$ and $a$ can then be added by performing controlled-phase rotation on each of the qubits in the decomposition using the bits of $b$ as controls.

请注意,对于任何整数 $j $ 和实数 $x $,$e ^ {i2\pi (x + j)} = e ^ {i2\pi x} $,可以进一步简化此扩展。This expansion can be further simplified by noting that for any integer $j$ and real number $x$, $e^{i2\pi(x+j)}=e^{i2\pi x}$. 这是因为,如果在圆圈中旋转 $ 360 ^ {\circ} $ 度数($ 2 \ pi $ 弧度),则最终会精确到开始处。This is because if you rotate $360^{\circ}$ degrees ($2\pi$ radians) in a circle then you end up precisely where you started. 因此 $e ^ {i2\pi x} $ $x $ 的唯一重要部分是 $x $ 的小数部分。The only important part of $x$ for $e^{i2\pi x}$ is therefore the fractional part of $x$. 具体而言,如果我们的二进制扩展形式 $x = y +0_0x_2 \ ldots x_n $,则 $e ^ {i2\pi x} = e ^ {i2\pi (0)。 x_0x_2 \ ldots x_{n-1})} $,因此 $ $ \ket{\phi_k (a + b)} = \frac{1}{\sqrt{2}} \left (\ket{0} + e ^ {i2\pi [a/2 ^ k +0_k\ldots b_1]} \ket{1} \right)。 $ $ 这意味着,如果通过增加 $ tensor $ 的傅立叶转换的扩展中的每个 \ket{a} 因素来执行加法运算,随着 $k $ 减小,旋转收缩的数目。Specifically, if we have a binary expansion of the form $x=y+0.x_0x_2\ldots x_n$ then $e^{i2\pi x}=e^{i2\pi (0.x_0x_2\ldots x_{n-1})}$ and hence $$\ket{\phi_k(a+b)}=\frac{1}{\sqrt{2}}\left(\ket{0} + e^{i2\pi [a/2^k+0.b_k\ldots b_1]}\ket{1} \right).$$ This means that if we perform addition by incrementing each of the tensor factors in the expansion of the Fourier transform of $\ket{a}$ then the number of rotations shrinks as $k$ decreases. 这极大地减少了增加插件所需的量程入口数。This substantially reduces the number of quantum gates needed in the adder. 我们指出了傅立叶变换、相位加法和反傅立叶变换步骤,这些步骤包含 Draper 添加程序作为 $ \operatorname{QFT} ^{-1} \left (\phi\!\operatorname{ADD}\right) \operatorname{QFT} $。We denote the Fourier transform, phase addition and the inverse Fourier transform steps that comprise the Draper adder as $\operatorname{QFT}^{-1} \left(\phi\!\operatorname{ADD}\right) \operatorname{QFT}$. 下面显示了使用这种简化实现整个过程的量程线路。A quantum circuit that uses this simplification to implement the entire process can be seen below.

显示为线路关系图的 Draper

线路中的每个受控 $e ^ {i2 \ pi/k} $ 入口都指受控的阶段入口。Each controlled $e^{i2\pi/k}$ gate in the circuit refers to a controlled-phase gate. 此类入口的属性在其作用的 qubits 对上,$ \ket{00}\mapsto \ket{00}$ 但 $ \ket{11}\mapsto e ^ {i2 \ pi/k} \ 票证{11}$。Such gates have the property that on the pair of qubits on which they act, $\ket{00}\mapsto \ket{00}$ but $\ket{11}\mapsto e^{i2\pi/k}\ket{11}$. 利用此线路,我们可以使用除存储输入和输出所需的其他 qubits 以外的其他任何功能来执行添加。This circuit allows us to perform addition using no additional qubits apart from those needed to store the inputs and the outputs.

BeauregardBeauregard Adder

Beauregard 添加程序是一个量程模块化添加程序,它使用 Draper 添加程序来对任意值为正整数 $N $ 执行加法取模 $N $。The Beauregard adder is a quantum modular adder that uses the Draper adder in order to perform addition modulo $N$ for an arbitrary value positive integer $N$. 量程模块化添加器(如 Beauregard 外接程序)的重要性,就是在选定算法中用于因式分解的模块求幂步骤中,其使用范围很大。The significance of quantum modular adders, such as the Beauregard adder, stems to a large extent from their use in the modular exponentiation step within Shor's algorithm for factoring. 量程模块化外接程序对量程输入 $ \ket{b} $ 和经典输入 $a $ 具有以下操作,其中 $a $ 和 $b $ 被承诺为整数 mod $N $,这意味着它们处于 [0,\ldots,N-1] $ 的间隔。A quantum modular adder has the following action for quantum input $\ket{b}$ and classical input $a$ where $a$ and $b$ are promised to be integers mod $N$, meaning that they are in the interval $[0,\ldots, N-1]$.

$ $ \ket{b}\rightarrow \ket{b + a \text{mod} N} = \begin{cases} \ket{b + a},& b + a < N\\ \ket{b + a-N},& (b + a) \ge N \end{cases}。$$ \ket{b}\rightarrow \ket{b+a \text{ mod }N}=\begin{cases} \ket{b+a},& b+a < N\\ \ket{b+a-N},& (b+a)\ge N \end{cases}. $$

Beauregard 添加使用 Draper 添加,或更具体的 $ \phi\!\operatorname{ADD} $,以在阶段中添加 $a $ 和 $b $。The Beauregard adder uses the Draper adder, or more specifically $\phi\!\operatorname{ADD}$, to add $a$ and $b$ in phase. 然后,它将使用相同的操作来确定是否 $a + b < N $,方法是在 $a + b-N < 0 $ 减 $N $ 和测试。It then uses the same operation to identify whether $a+b <N$ by subtracting $N$ and testing if $a+b-N<0$. 线路将此信息存储在辅助 qubit 中,然后在 $a + b < N $ 时,将 $N $ 返回寄存器。The circuit stores this information in an ancillary qubit and then adds $N$ back the register if $a+b<N$. 然后,它会通过 uncomputing 此辅助位来结束(需要此步骤以确保在调用此项补充后可以取消分配 ancilla)。It then concludes by uncomputing this ancillary bit (this step is needed to ensure that the ancilla can be de-allocated after calling the adder). 下面给出了 Beauregard 提供程序的线路。The circuit for the Beauregard adder is given below.

显示为线路关系图的 Beauregard

此处的入口 $ \Phi\!\operatorname{ADD} $ 采用与 $ \Phi\!\operatorname{ADD} $ 相同的格式,但在此上下文中,输入为经典而不是量程。Here the gate $\Phi\!\operatorname{ADD}$ takes the same form as $\phi\!\operatorname{ADD}$ except that in this context the input is classical rather than quantum. 这允许将 $ \Phi 中的受控阶段\!\operatorname{ADD} $ 替换为阶段入口,然后可以将该入口编译成更少的操作,减少了执行程序所需的 qubits 数量和入口数。This allows the controlled phases in $\Phi\!\operatorname{ADD}$ to be replaced with phase gates that can then be compiled together into fewer operations to reduce both the number of qubits and number of gates needed for the adder.

有关更多详细信息,请参阅Roetteler、BethCoppersmithFor more details, please refer to M. Roetteler, Th. Beth and D. Coppersmith.

量子相位估计Quantum Phase Estimation

量程傅立叶转换的一个特别重要的应用是了解单一运算符(称为阶段估算的问题)的本征值。One particularly important application of the quantum Fourier transform is to learn the eigenvalues of unitary operators, a problem known as phase estimation. 假设单一 $U $ 和状态 $ \ket{\phi} $,$ \ket{\phi} $ 是包含未知 eigenvalue $ \phi $ 的 $U $ 的 eigenstate,\begin{equation} U\ket {\ phi} = \phi\ket{\phi}。Consider a unitary $U$ and a state $\ket{\phi}$ such that $\ket{\phi}$ is an eigenstate of $U$ with unknown eigenvalue $\phi$, \begin{equation} U\ket{\phi} = \phi\ket{\phi}. \end{equation} 如果仅有权访问作为 oracle $U $,则可以通过使用应用于受控操作目标的 $Z $ 旋转传播回控件来了解阶段 $ \phi $。\end{equation} If we only have access to $U$ as an oracle, then we can learn the phase $\phi$ by utilizing that $Z$ rotations applied to the target of a controlled operation propagate back onto the control.

假设 $V $ 是 $U $ 的受控应用程序,因此 \begin{align} V (\ket{0} \otimes \ket{\phi}) & = \ket{0} \otimes \ket{\phi} \\ \textrm{and} V (\ket{1} \otimes \ket{\phi}) & = e ^ {i \phi} \ket{1} \otimes \ket{\phi}。Suppose that $V$ is a controlled application of $U$, such that \begin{align} V (\ket{0} \otimes \ket{\phi}) & = \ket{0} \otimes \ket{\phi} \\ \textrm{ and } V (\ket{1} \otimes \ket{\phi}) & = e^{i \phi} \ket{1} \otimes \ket{\phi}. 然后,\end{align},通过线性,\begin{align} V (\ket{+} \otimes \ket{\phi}) & = \frac{(\ket{0} \otimes \ket{\phi}) + e ^ {i \phi} (\ket{1} \otimes \ket{\phi})} {\sqrt{2}}。\end{align} Then, by linearity, \begin{align} V(\ket{+} \otimes \ket{\phi}) & = \frac{ (\ket{0} \otimes \ket{\phi}) + e^{i \phi} (\ket{1} \otimes \ket{\phi}) }{\sqrt{2}}. \end{align} 我们可以收集术语来查找 \begin{align} V (\ket{+} \otimes \ket{\phi}) & = \frac{\ket{0} + e ^ {i \phi} \ket{1}} {\sqrt{2}} \otimes \ket{\phi} \\ & = (R_1 (\phi) \ket{+}) \otimes \ket{\phi},\end{align},其中 $R _1 $ 是 R1 操作应用的那个。\end{align} We can collect terms to find that \begin{align} V(\ket{+} \otimes \ket{\phi}) & = \frac{\ket{0} + e^{i \phi} \ket{1}}{\sqrt{2}} \otimes \ket{\phi} \\ & = (R_1(\phi) \ket{+}) \otimes \ket{\phi}, \end{align} where $R_1$ is the unitary applied by the R1 operation. 换句话说,应用 $V $ 的影响与将 $R _1 $ 应用于未知角度完全相同,即使我们仅有权访问作为 oracle $V $。Put differently, the effect of applying $V$ is precisely the same as applying $R_1$ with an unknown angle, even though we only have access to $V$ as an oracle. 因此,对于本文的其余部分,我们将根据 $R _1 (\phi) $ (通过使用所谓的阶段 kickback来实现)讨论阶段估算。Thus, for the rest of this discussion we will discuss phase estimation in terms of $R_1(\phi)$, which we implement by using so-called phase kickback.

由于在此过程后,控件和目标注册仍处于 untangled 状态,因此,我们可以将 $ \ket{\phi} $ 作为 $U ^ $2 的受控应用程序的目标,以便在州 $R 1 (2 \phi) \ket{+} $ 中准备第二个控制 qubit。Since the control and target register remain untangled after this process, we can reuse $\ket{\phi}$ as the target of a controlled application of $U^2$ to prepare a second control qubit in the state $R_1(2 \phi) \ket{+}$. 继续以这种方式,我们可以获取形式为 \begin{align} \ket{\psi} & = \ sum {j = 0} ^ n R_1 (2 ^ j \phi) \ket{+} \\ & \propto \ bigotimes_ {j = 0} ^ {n} \left (\ket{0} + \exp (i 2 ^ {j} \phi) \ket{1}\right) \\ & \propto \ sum_ {k = 0} ^ {2 ^ n-1} \exp (i \phi k) \ket{k} \end{align},其中 $n $ 是我们需要的精度位数。并且,我们已使用 ${} \propto $ {}$ 来指示我们抑制了 $1/\sqrt 的规范化系数{2 ^ n} $。Continuing in this way, we can obtain a register of the form \begin{align} \ket{\psi} & = \sum_{j = 0}^n R_1(2^j \phi) \ket{+} \\ & \propto \bigotimes_{j=0}^{n} \left(\ket{0} + \exp(i 2^{j} \phi) \ket{1}\right) \\ & \propto \sum_{k = 0}^{2^n - 1} \exp(i \phi k) \ket{k} \end{align} where $n$ is the number of bits of precision that we require, and where we have used ${} \propto {}$ to indicate that we have suppressed the normalization factor of $1 / \sqrt{2^n}$.

如果我们假设 $ \phi = 2 \pi p/2 ^ k $ 用于整数 $p $,则我们会将其识别为 $ \ket{\psi} = \operatorname{QFT} \ket{p_0 p_1 \dots . p_n} $,其中 $p _j $ 是 $2 \textrm{th}} \pi $ 的 $j ^ {\phi $ 位。If we assume that $\phi = 2 \pi p / 2^k$ for an integer $p$, then we recognize this as $\ket{\psi} = \operatorname{QFT} \ket{p_0 p_1 \dots p_n}$, where $p_j$ is the $j^{\textrm{th}}$ bit of $2 \pi \phi$. 通过应用 "量程傅立叶转换" 的 adjoint,我们将获得编码为量程状态的阶段的二进制表示形式。Applying the adjoint of the quantum Fourier transform, we therefore obtain the binary representation of the phase encoded as a quantum state.

在 Q # 中,这是由 QuantumPhaseEstimation 操作实现的,该操作采用 DiscreteOracle 实现 $U ^ m $ 的应用程序作为 $m $ 的正整数函数。In Q#, this is implemented by the QuantumPhaseEstimation operation, which takes a DiscreteOracle implementing application of $U^m$ as a function of positive integers $m$.