加载中，请稍后....
量子算法 Quantum Algorithm
量子算法是以量子态作为输入，量子逻辑门作为操作序列的算法。对于n个量子比特的系统，由于态的叠加和相位的存在，相当于会有 $2^n$ 那么多的独立分量。此时，每一个门操作都会涉及到所有分量的同时变化，所以量子计算机具有（随量子比特数目的增长）指数级增长的运算能力。Deutsch-Jozsa算法 Deutsch-Jozsa Algorithm
首先介绍一种最简单的量子算法，Deutsch-Jozsa算法。 D-J算法是一种经过设计的情况，它证明了量子算法相对于经典算法有指数级别的加速能力。D-J算法的问题描述是这样的： 如果你具有一个黑盒子，黑盒子里面是一些逻辑门，这个黑盒子可以接受n位的输入，并且产生一个1位的输出。并且我们已知黑盒子有两种可能性： 1、对于所有的输入，它只输出0或者1——我们称之为“常数”； 2、恰好对于一半的输入，输出为0，另一半输入，输出为1——我们称之为“平衡”。问题是：对于一个随机的盒子，要区分盒子到底是“平衡”的还是“常数”的。注意，我们不考虑这两种情况之外的输出分布情况，例如对于一个2位输入的黑盒子，输入00输出0，而输入01,10,11都输出1，此时它既不属于“平衡”也不属于“常数”，故被排除到了讨论之外。 如果在经典计算的角度上去看，我们要一个一个地检查输出的情况。因为输入是n位的，所以一共具有 $2^n$ 种情况（每位上都是0/1两种可能）。不需要检查所有的情况来验证它到底是哪一种盒子，但是最坏的情况下，你检查了一半的情况（ $2^{n-1}$ ），得到了一样的结果，例如全为0。这时，你需要再检查一种情况，如果它是0，那么一定是“常数”的；如果它是1，那么一定是“平衡”的。 其中Target_Function就是这个黑盒子，而bitNum代表输入比特个数。 然而，量子计算机只需要通过一步运算就可以得到结果。
如图：是这个过程的量子算法线路图。图中H代表Hadamard门，Oracle就是这个黑盒子。Readout表示在这里对量子比特进行测量。下面对整个过程进行理论分析。
第一步，制备n个工作（Working）比特到 $|0\rangle$ 态，与一个辅助（Ancillary）比特到 $|1\rangle$。
第二步，所有比特都经过Hadamard变换到叠加态上。由Hadamard门和量子态的矩阵形式，我们可得
$$\begin{align*}
H|0\rangle&=\frac{1}{\sqrt{2}}\left(\begin{matrix}
1&&1\\
1&&-1
\end{matrix}
\right)
\left(\begin{matrix}
1\\
0
\end{matrix}\right)=\frac{1}{\sqrt{2}}\left(\begin{matrix}
1\\
1
\end{matrix}\right)\\
H|1\rangle&=\frac{1}{\sqrt{2}}\left(\begin{matrix}
1&&1\\
1&&-1
\end{matrix}
\right)
\left(\begin{matrix}
0\\
1
\end{matrix}\right)=\frac{1}{\sqrt{2}}\left(\begin{matrix}
1\\
-1
\end{matrix}\right)
\end{align*}$$
我们发现 $1/\sqrt{2}$ 是个很让人讨厌的系数，而且它在整个操作过程中也只会出现在所有表达式的最外面，所以接下来的计算里面我们忽略归一化条件。忽略这个系数不会影响矩阵分量之间的比例关系，所以忽略它完全不会受到影响。除非我们马上要开始计算概率了，这个时候我们再去对矩阵做归一化就行了。
那么简化的描述就变成了
$$\begin{align*}
H: \quad |0\rangle &\rightarrow |0\rangle+|1\rangle\\
\quad |1\rangle &\rightarrow |0\rangle-|1\rangle
\end{align*}$$
此时我们可以将所有的n个工作比特直积起来。回顾直积的定义，我们将两个工作比特直积起来
$$\begin{align*}
(|0\rangle+|1\rangle)\otimes(|0\rangle+|1\rangle)&=|00\rangle+|01\rangle+|10\rangle+|11\rangle\\
&=|0\rangle+|1\rangle+|2\rangle+|3\rangle
\end{align*}$$
第二个等式单纯是二进制到十进制的转换。这样我们就得到了2位量子态所有情况的和。并且所有的相位项都为1。在此基础上再直积一个 $|0\rangle+|1\rangle$，就得到了3位量子态所有情况的和，即 $0\sim 7$ ……最后，一直直积n次，就可以得到 $0\sim 2^n-1$ 的态之和。这样，我们得到所有比特的共同量子态表达式为
$$|\text{Working}\rangle|\text{Ancilla}\rangle=\left(\sum_{x=0}^{2^n-1} |x\rangle\right)\left(|0\rangle-|1\rangle\right)$$
第三步，将这个系统通过代表这个黑盒子的Oracle。Oracle是一种酉变换，它具有如下的形式
$\text{Oracle}:\quad |x\rangle|y\rangle\rightarrow |x\rangle|y\oplus f(x)\rangle$
（如果你不能理解为什么Oracle要写成这种形式，请看下一章“Oracle是什么”。）
Oracle中的 $f(x)$ 是n位输入，1位输出的函数，也就是这个黑盒子的函数形式。其中 $\oplus$ 代表模2加法（异或）。所以，将量子态通过Oracle的时候，我们会得到：
$$\begin{align*}
\text{Oracle}&:\quad|\text{Working}\rangle|\text{Ancilla}\rangle\\
&\rightarrow \left(\sum_{x=0}^{2^n-1} |x\rangle\right)\left(|0\oplus f(x)\rangle-|1\oplus f(x)\rangle\right)\\
&=\ \left(\sum_{x=0}^{2^n-1} (-1)^{f(x)}|x\rangle\right)\left(|0\rangle-|1\rangle\right)
\end{align*}$$
意即 $f(x)=1$ 时，这一项会使 $|0\rangle-|1\rangle \rightarrow |1\rangle-|0\rangle$，即附带了一个-1的相位。当 $f(x)=0$ 时，不附带这个相位。
第四步，丢弃辅助比特，仅对前面的n个工作比特全部执行Hadamard操作。如果所有的 $f(x)$ 都具有相同的值，那么工作比特将继续保持所有分量的相位一致（全为1或者-1）；如果 $f(x)$ 具有一半0一半1的输出，那么工作比特将有一半的分量为1，另一半的分量为-1。
简单而言，如果Oracle是常数的，那么经过Oracle前后，量子态不会发生任何变化，此时将工作比特全部通过Hadamard门操作，必然会返回到初始的态（全部为 $|0\rangle$ )。如果Oracle是平衡的，那么经过Oracle前后，量子态会变成和初态不同的态，再经过Hadamard门之后，必然不会得到初始态。（之所以要求0和1必须恰好各为一半，是为了保证此时量子态在初始态上面的概率分量为0，详见下面数学描述）
此时对所有比特进行测量。如果我们测到所有的量子比特都在0上，说明黑盒子是常数的。否则说明黑盒子是平衡的。
下面对这个过程进行数学描述。
任意基矢态（非叠加态）的Hadamard变换形式如下
$$H^{\otimes n}|x\rangle=\sum_{x=1}^{2^n-1}(-1)^{x\cdot y} |y\rangle$$
其中 $x\cdot y$ 代表按位或操作。将它带入到上面的表达式中，可得
$$\begin{align*}
H^{\otimes n}\left(\sum_{x=0}^{2^n-1} (-1)^{f(x)}|x\rangle\right)&=\sum_{x=0}^{2^n-1} (-1)^{f(x)}\sum_{y=0}^{2^n-1}(-1)^{x\cdot y}|y\rangle\\
&=\sum_{x,y=0\sim 2^n-1}(-1)^{f(x)+x\cdot y}|y\rangle
\end{align*}$$
因为我们仅考察测量结果是否全部为0，所以令 $|y\rangle=|0\rangle^{\otimes n}$，计算这个分量上的系数，即
$$P(y=0)=|\sum_{x=0}^{2^n-1}(-1)^{f(x)}|^2=\begin{cases}
1\quad f(x)\text{为常数}\\
0\quad f(x)\text{为平衡}\\
\end{cases}$$
所以要么概率为1，要么概率正好一半一半抵消掉变成0。至此就是D-J算法的完全描述。我们发现量子算法的不同点在于它向黑盒子内部输入的是叠加态，所以只需要一步计算就能得到问题的答案。
经典算法的验证次数是 $O(2^n)$ 的，量子算法算上叠加态的准备和测量的时间，需要的操作步骤为 $O(n)$。所以我们说明量子算法相对于经典算法具有指数级别加速的特性。
D-J算法的问题在于它解决的问题既不实用，又具有很大的限制（要求平衡函数中必须恰好为一半0一半1）。另外，我们还对黑盒子本身的形态有要求。所以说D-J算法的理论意义是远大于其实用意义的。真正实用的量子算法将在后面进行介绍。
Oracle是什么？
在介绍其它的量子算法之前，我们要对Oracle进行一些必要的说明。 最早在图灵的博士论文中，提到了一种新的计算模型： “假定我们拥有某种解决数论问题的未知方法；比如说某种谕示。我们不深入这个谕示的本质，除了它不可能是一台机器这一点。通过谕示的帮助，我们可以构筑一种新的机器，它的基本过程之一就是解决某个给定的数论问题。” 图灵的这一段话描述的“谕示”即为Oracle。因为Oracle本身就能解决某种问题，在我们不深入Oracle本身时，我们可以通过Oracle扩展我们的计算能力。 这里的D-J算法，包括其它的某些量子算法都借用了图灵提到的这种新模型：谕示机。这里的Oracle是一种酉变换。它通常具有下面的两种形式： $$\begin{align*} \text{Oracle}:\quad |x\rangle|y\rangle&=|x\rangle|y+f(x)\rangle\\ |x\rangle|y\rangle&=|x\rangle|y\cdot f(x)\rangle \end{align*}$$ 注意：第一，这里的乘法不是按位乘法而是普通乘法。第二，在讨论这里的 $|x\rangle$,$|y\rangle$ 代表的量子态时，并没有指定它们的位数。但是无论是加法还是乘法，它们的运算也是要做取模运算的（不存在溢出的情况）。 不论是哪种形式，都是在一组量子态为 $|x\rangle$ 时将函数 $f(x)$ 的值引入到另一个和它并列的一组量子态中。我们在讨论包含Oracle的算法时，我们都会假定Oracle能在一个单位时间内输出“谕示”内容的黑盒子——就像D-J算法中描述的那样。它内部的量子线路究竟如何，我们是不关心的。 但是也有另一种情况——我们要通过函数的解析表达式将一个函数用量子线路表达出来。这一种就像是分析Oracle的“内部构造”。虽然一般来说它具有和Oracle相同的酉变换形式，但是不能被看作一个单位时间内能告诉你“谕示”内容的黑盒子，所以它的构造方式决定了它的执行时间。我们称这种构造为“量子函数(Quantum function)”。 接下来的部分，我们会举两个相对实用的量子算法的例子。其中一个是用了一个代表数据库的Oracle，然后进行搜索的Grover算法；另一个是用量子线路构建“量子函数”，解决质因数分解问题的Shor算法。Grover搜索算法 Grover's Searching Algorithm
接下来，我们介绍一种更有实用意义的算法，Grover搜索算法。
什么是搜索算法呢？举一个简单的例子，在下班的高峰期，我们要从公司回到家里。开车走怎样的路线才能够耗时最短呢？我们最简单的想法，当然是把所有可能的路线一次一次的计算，根据路况计算每条路线所消耗的时间，最终可以得到用时最短的路线，即为我们要找的最快路线。这样依次的将每一种路线计算出来，最终对比得到最短路线。搜索的速度与总路线数N相关，记为 $O(N)$
。而采用量子搜索算法，则可以以 $O\left(\sqrt N\right)$ 的速度进行搜索，要远快于传统的搜索算法。
那么我们怎么实现Grover搜索算法呢？
首先，我们先化简一下搜索模型。我们将所有数据存在数据库中，假设我们有n个量子比特，用来记录数据库中的每一个数据的索引，一共可以表示 $2^n$
个数据，记为N个。我们希望搜索得到的数据有M个。为了表示一个数据是否我我们搜索的结果。我们建立一个函数：
$$f(x)=\left\{
\begin{aligned}
& 0 & (x\neq x_0) \\
&1& (x=x_0) \\
\end{aligned}
\right.$$
其中 $x_0$ 为我们的搜索目标的索引值。也就是说，当我们搜索到我们的目标时，我们的函数值 $f(x)$ 置为1，如果搜索的结果不是我们的目标时，$f(x)$ 置为0。
接下来，我们假设有一个量子Oracle可以识别搜索问题的解，是别的结果通过Oracle的一个量子比特给出。我们可以将Oracle定义为 $$|x\rangle|q\rangle\xrightarrow{Oracle} |x\rangle|q\bigoplus f(x)\rangle$$ 其中 $|q\rangle$ 是一个结果寄存器,$\bigoplus$ 是二进制加法，通过Oracle，我们可以实现，当搜索的索引为我们的目标结果时，结果寄存器翻转；反之，结果寄存器值不变。从而我们可以通过判断结果寄存器的值，来确定搜索的对象是否为我们要的目标值。
如此描述Oracle有些抽象，Oracle对量子态的具体操作是什么样的呢？同D-J算法相似，我们先将初态制备在
$|0\rangle^{\bigotimes n}|1\rangle$态上，$|0\rangle^{\bigotimes n}$ 为查询寄存器，$|1\rangle$为结果寄存器。
经过Hardmard门操作后，可以将查询寄存器的量子态，变为所有结果的叠加态。换句话说，经过了Hardmard门，我们就可以得到所有结果的索引。而结果寄存器则变为 $\frac{|0\rangle-|1\rangle}{\sqrt{2}}$
接下来，使其通过Oracle，可以对每一个索引都进行一次检验，如果是我们的目标结果，则将答案寄存器的量子态进行0、1翻转，即答案寄存器变为
$\frac{|1\rangle-|0\rangle}{\sqrt{2}}=-\frac{|0\rangle-|1\rangle}{\sqrt{2}}$
，而查询寄存器不变。而当检验的索引不是我们要求的结果时，寄存器均不发生改变。因此，Oracle可以换一种表示方式
$$|x\rangle(\frac{|0\rangle-|1\rangle}{\sqrt{2}})\xrightarrow{\text{Oracle}}(-1)^{f(x)}|x\rangle(\frac{|0\rangle-|1\rangle}{\sqrt{2}})$$
其中，$|x\rangle$ 是查询寄存器的等额叠加态中的一种情况。
也就是说，Oracle的作用，是通过改变了解的相位，标记了搜索问题的解。
现在，我们已经将搜索问题的解通过相位标记区分出来了。那么如何能够将量子态的末态变为已标记出的态呢？
我们将问题换一种思路进行考虑。我们知道，当查询寄存器由初态经过Hardmard门后，会变为所有可能情况的等额叠加态。也就是说，它包含着所有搜索问题的解与非搜索问题的解。我们将这个态记为
$$|\psi\rangle=\frac{1}{\sqrt{N}} \sum\limits_{x}|x\rangle$$
我们将所有非搜索问题的解定义为一个量子态 $|\alpha\rangle$ ,其中$\sum\nolimits_{x_1}$ 代表着 $x$ 上所有非搜索问题的解的和。
$$|\alpha\rangle=\frac{1}{\sqrt{N-M}} \sum\limits_{x_1}|x\rangle$$
同理，我们将所有搜索问题的解定义为一个量子态 $|\beta\rangle$,其中 $\sum\nolimits_{x_2}$ 代表着 $x$ 上所有搜索问题的解的和。
$$|\beta\rangle=\frac{1}{\sqrt{M}} \sum\limits_{x_2}|x\rangle$$
显然，$|\beta\rangle$ 为我们期望的最终的量子态，而且 $|\alpha\rangle$ 和 $|\beta\rangle$ 相互正交。利用简单的代数运算，我们就可以将初态 $|\psi\rangle$ 重新表示为 $$|\psi\rangle=\sqrt{\frac{N-M}{N}}|\alpha\rangle+\sqrt{\frac{M}{N}}|\beta\rangle$$
也就是说，我们用搜索问题的解的集合和非搜索问题的解的集合，重新定义了初始态换句话说，我们的初态属于 $|\alpha\rangle$ 与 $|\beta\rangle$ 张成的空间。因此，我们可以用平面向量来表示这三个量子态，如图。
那么，Oracle作用在新的表示方法下的初态会产生怎样的影响呢？
我们知道，Oracle的作用是用负号标记搜索问题的解，因此相当于将 $|\beta\rangle$ 内每一个态前均增加一个负号，将所有的负号提取出来，可以得到： $$|\psi\rangle\xrightarrow{\text{Oracle}}\sqrt{\frac{N-M}{N}}|\alpha\rangle-\sqrt{\frac{M}{N}}|\beta\rangle$$ 对应在平面向量中，相当于将 $|\psi\rangle$ 做关于 $|\alpha\rangle$ 轴的对称。
但是，仅仅有这一种操作，是无法将量子态从 $|\psi\rangle$ 变为 $|\beta\rangle$。我们还需要另一种对称操作。
第二种对称操作，是将量子态关于$|\psi\rangle$ 对称的操作。这个操作由三个部分构成。
1、将量子态经过一个Hardmard门。
2、对量子态进行一个相位变换，将 $|0\rangle^{\bigotimes n} $态的系数保持不变，将其他的量子态的系数增加一个负号。相当于 $2|0\rangle\langle0|-I$ 酉变换算子。
3、再经过一个Hardmard门。
这三步操作的数学表述为
$$H^{\bigotimes n}(2|0\rangle\langle0|-I)H^{\bigotimes n}=2|\psi\rangle\langle\psi|-I$$
上述过程涉及到复杂的量子力学知识，如果你不理解，没关系。你只需要知道，这三部分的操作，只是为了实现将量子态关于$|\psi\rangle$
对称即可。如果你想了解为什么这三步操作可以实现，可以阅读关于量子计算相关书籍进一步理解。
前面介绍的两种对称操作，合在一起称为一次Grover迭代。假设初态$|\psi\rangle$与 $|\alpha\rangle$ 可以表示为 $$|\psi\rangle=cos\frac{\theta}{2}|\alpha\rangle+sin{\frac{\theta}{2}}|\beta\rangle$$
对比$(7)$ 式，很容易得到， $$cos\frac{\theta}{2}=\sqrt{\frac{N-M}{N}}$$
可以从几何图像上看到，每一次Grover迭代，可以使量子态逆时针旋转 $\theta$。经历了k次Grover迭代，末态的量子态为： $$G^k|\psi\rangle=cos(\frac{2k+1}{2}\theta)|\alpha\rangle+sin(\frac{2k+1}{2}\theta)|\beta\rangle$$
因此，经过多次迭代操作，总可以使末态在$|\beta\rangle$ 态上概率很大，满足精确度的要求。经过严格的数学推导，可证明，迭代的次数R满足 $$R\leq\frac{\pi}{4}\sqrt{\frac{N}{M}}$$
Shor算法质因数分解 Shor's Algorithm For Factoring
将两个质数乘起来，例如907*641=581387，是一件小学生都能做到的事情，用计算机去处理，看起来也没有什么难度。但是如果我给你581387，让你去找它的质因数，问题就变得很复杂了。也许你可以用计算机一个一个的去尝试，但是当数字变得更大，达到成百上千位的时候，就连计算机也无能为力。世界上面有很多问题都是这样，难以找到答案，但是一旦找到答案就很容易去验证。类似的问题我们称之为NP问题。NP问题之所以难于处理，是因为它的时间复杂度往往具有指数级别。这意味着随着问题规模的线性扩大，需要的时间却是指数增长的。利用这个原理，人们创造了RSA算法，它利用大数难以分解，但是易于验证的原理，对数据进行有效的加密。 量子计算机有将问题指数加速的能力，那是否意味着能攻克所有的NP问题呢？很遗憾，不能。但是幸运的是，我们有能力把“质因数分解”的时间复杂度降低到多项式级别，使大数分解问题的解决变为可能。这就是Shor算法。Shor算法的提出意味着RSA密钥的安全性受到了挑战。下面我们就来介绍Shor算法的内容。问题的转化
Shor算法首先将质因数分解问题转换成了一个子问题，下面我们来看问题的转换过程。假设我们待分解的数为 $N$， STEP 1：随机取一个正整数$ {1}<{a}<{N}$，定义一个函数: $f(x)=a^x\ mod\ N$ STEP 2：这个函数一定是一个周期函数，寻找到它的周期为 $r$。（这一步将使用量子计算机完成） STEP 3：如果 $r$ 为奇数，那么回到STEP 1。如果 $r$ 为偶数，那么计算 $f(r/2)$。 STEP 4：如果 $f(r/2)=-1$，那么回到STEP 1。否则，计算 $f(r/2)+1$ 和 $f(r/2)-1$ 分别对于N的最大公约数。 STEP 5：这两个最大公约数就是 $N$ 的两个质因数 举个例子，对于21而言，假设我们选择 $a=2$，那么 STEP 1：定义函数 $f(x)=2^x\ mod\ N$ STEP 2：发现它的周期为6。 STEP 3：计算出 $f(3)=8$ STEP 4：计算7和9分别对于21的最大公因数 $\text{gcd}(7,21)=7$， $\text{gcd}(9,21)=3$ 检验知7和3都是21的质因数，于是我们得到了问题的答案。函数的引入
我们要为STEP 1中描述的函数找到它引入量子计算机的方式。这种函数被称为模指数（Modular Exponential）函数，在经典逻辑电路中，它已经被以各种形式设计了出来。所以现在，我们要为它准备一个量子线路的版本。 根据在“Oracle是什么”这一节里面提到的量子函数概念，我们需要构建出一个酉变换U使得： $$U|x\rangle|y\rangle=|x\rangle|y\cdot a^x (mod N)\rangle$$ 这种情况是一种比较普适的情况，我们令 $y=1$，那么后面的这一组量子比特就作为辅助比特存储了 $f(x)$ 的计算结果。我们先来找一种比较简单的情况来分析具体问题，可以便于对其中的变量分解转换的理解。选取要分解的质因数15，和一个比15小的任意正整数7，所以我们要构建这样的酉变换： $$U|x\rangle|1\rangle=|x\rangle|7^x (mod 15)\rangle$$ 首先要提到的一点是要表示 $7^x (mod 15)\rangle$，就意味着我们的辅助比特的取值是从0~14的，为了表示这个数，需要用到4个比特，即从0000~1110。对于前面的工作比特来说，它的位数选择比较自由，而且选取的位数越多，我们得到正确结果的概率越大，这一点在后面会解释。 乍一看这个函数让我们有些无从下手，所以我们要对它进行一定的转换，比如先把x转化为二进制： $$7^x=7^{x_0+2x_1+2^2x_2+...}=7^{x_0}\cdot(7^2)^{x_1}\cdot(7^4)^{x_2}...\cdot(7^{2^n})^{x_n}$$ $x_i$ 是x转换为二进制后每一位上对应的数码，所以它的取值无非是0或者1。这样我们就可以简单的用一个控制酉操作得到每一项，即 $$\begin{align*} |x_i\rangle&=|1\rangle \ :\ U_a|y\rangle\rightarrow|y\cdot 7^{2^i} (mod15)\rangle\\ |x_i\rangle&=|0\rangle \ :\ U_a=I \end{align*}$$ 其中 $I$ 是单位操作。所以问题就转化为了构建“控制模乘”操作 $U_a$。 顺带一提，因为我们关注的点不是如何纯粹的用量子线路来描述里面的每一步操作，某些操作也不引入额外的计算时间复杂度，那么这些操作是可以用经典计算机代为完成的。就比如说这里的 $7^{2^i}$。注意到 $$y\cdot 7^{2^i}(mod15)=(y\cdot (7^{2^i}mod15))mod15$$ 我们只需要事先用经典计算机将 $7^{2^i}mod15(i=0\sim N-1)$（N是选取的工作位数）全部计算出来，就可以在接下来的设计时只考虑对应的几种情况。 我们可以看出， $a^{2^i}=a^{2^{i-1}+2^{i-1}}=(a^{2^{i-1}})^2$，根据这个公式，可以列举出来对于不同的 $i$ 的取值情况，上述表达式的取值（这个过程用经典计算机就可以完成）。在例子中的这种情况中，有 $$\begin{align*} i&=0 \quad 7^{2^i}mod15=7\\ i&=1 \quad 7^{2^i}mod15=4\\ i&=2 \quad 7^{2^i}mod15=1\\ i&\geq3 \quad 7^{2^i}mod15=1 \end{align*}$$ 也就是说我们只需要对应设计 $U_a|y\rangle\rightarrow|7y\ mod15\rangle$，$U_a|y\rangle\rightarrow|4y\ mod15\rangle$ 两种就可以达到设计目的了。 最后我们来看一下引入了函数，量子态变成了什么。 首先是一组Hadamard变换，它们只作用在一组N个工作比特上，所以这个总状态就会变成 $$|\text{Working}\rangle|\text{Ancilla}\rangle=\left(\sum_{x=0}^{2^{N}-1} |x\rangle\right) |00...001\rangle$$ 在量子函数作用在这一组量子态时，相当于这个函数的自变量从0到 $2^{N}-1$ 的所有取值都被保存到了辅助比特上。也就是说，工作比特的每个状态分量都和辅助比特的一个状态分量纠缠在了一起。 $\sum |x\rangle|f(x)\rangle$ 在之前的计算中，我们知道了 $f(x)=a^x (mod N)$ 是一个周期函数，假设它的周期是T。明显地， $f(x)=f(x+T)=f(x+2T)....$ 那么 $$|x\rangle|f(x)\rangle+|x+T\rangle|f(x+T)\rangle+|x+2T\rangle|f(x+2T)\rangle+...=\left(|x\rangle+|x+T\rangle+|x+2T\rangle+...\right)|f(x)\rangle$$ 回到 $a=7$， $N=15$的例子中，我们有 $$\begin{align*} |\text{Working}\rangle|\text{Ancilla}\rangle&=(|0\rangle+|4\rangle+|8\rangle+...)|1\rangle\\ &+(|1\rangle+|5\rangle+|9\rangle+...)|7\rangle\\ &+(|2\rangle+|6\rangle+|10\rangle+...)|4\rangle\\ &+(|3\rangle+|7\rangle+|11\rangle+...)|13\rangle \end{align*}$$ 因为这个态是一个纠缠态，所以当我们测量辅助比特时，工作比特就会坍缩成对应的那种情况。但是不论你得到辅助比特的测量值是什么，工作比特总是会只保留为每个分量都恰好为一组周期数的叠加态。那么这一组叠加态表示的数的周期将会通过量子傅里叶变换来快速完成。量子傅里叶变换
寻找态的周期可以通过量子傅里叶变换来快速完成。我们先以 $|0\rangle+|4\rangle+|8\rangle+...$为例子来看看量子傅里叶变换是怎么做的，之后你就会发现它对于1,5,9,13...或是2,6,10,14...都能得到类似的结果。 如图所示，量子傅里叶变换有两个重要的部分，第一是递归的依次控制旋转（CROT）操作，第二部分是改变比特的顺序。 数学表达上，每一项都是用离散傅里叶变换的形式去处理的。 $$y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j \omega^{jk}$$ 其中 $x_j$ 表示输入量子态的第 $j$ 个分量，而 $k$ 表示输出量子态的分量，如果用 $n$ 个量子比特表示，则 $\omega=e^{\frac{2\pi i}{2^n}}=e^{\frac{2\pi i}{N}}$。而从矩阵上来看，则为 $$F_N = \frac{1}{\sqrt{N}} \begin{bmatrix} 1&1&1&1&\cdots &1 \\ 1&\omega&\omega^2&\omega^3&\cdots&\omega^{N-1} \\ 1&\omega^2&\omega^4&\omega^6&\cdots&\omega^{2(N-1)}\\ 1&\omega^3&\omega^6&\omega^9&\cdots&\omega^{3(N-1)}\\ \vdots&\vdots&\vdots&\vdots&&\vdots\\ 1&\omega^{N-1}&\omega^{2(N-1)}&\omega^{3(N-1)}&\cdots&\omega^{(N-1)(N-1)} \end{bmatrix}$$ 不妨假设工作比特只有4个。那么输入的量子态则为 $|\text{Input}\rangle=|0\rangle+|4\rangle+|8\rangle+|12\rangle$ 这样就代表 $x_0=x_4=x_8=x_{12}=1$，并且 $\omega=e^{2\pi i/16}$，其它分量上都为0。根据傅里叶变换的公式我们可以计算出 $$\begin{align*} y_k &= \frac{1}{\sqrt{4}} (\omega^{0k}+\omega^{4k}+\omega^{8k}+\omega^{12k})\\ &=\frac{1}{2}(1+i^k+(-1)^k+(-i)^k) \end{align*}$$ 这里就是工作比特执行完量子傅里叶变换之后的输出态上的每个分量（第k个分量）的值。从而我们可以得到 $y_0=y_4=y_8=y_{12}=\frac{1}{2}$，其它情况下 $y_k=0\ (k\neq 0,4,8,12)$， 那么最后输出的量子态则为 $|\text{Output}\rangle=|0\rangle+|4\rangle+|8\rangle+|12\rangle$利用连分数分解得到周期
在最后的测量时，我们会随机得到0，4，8，12四个结果中的一个，但是这个结果并不是周期。但是量子傅里叶变换的结果揭示了一点： $$\omega^{irx}=e^{2\pi i rx/2^N}\sim 1$$ 其中我们假设测量结果是 $x$，总工作比特数为 $N$，函数的周期为 $r$。那么我们有 $$\frac{x}{2^N}=\frac{c}{r}$$ 其中 $c$ 为一个未知的整数。所以我们可以通过这个式子近似地找出函数周期。例如 $x=4$，$N=4$，我们有 $$\frac{c}{r}=\frac{1}{4}$$ 这样我们就找到了周期r=4。Shor算法的量子计算机部分至此解出。你可以检验一下 $f(x)=7^x (mod15)$ 这个函数的周期是否确实为4。你也可以检验一下$f(r/2)+1$ 和 $f(r/2)-1$ 和15的最大公因数是否就是15的质因数。 有时候 $x/2^N$ 并不一定能顺利约出合理的 $r$，这样我们就可以通过连分数分解法，得到一个逼近的分数，从而获得 $r$。这里就不再细讲了。Shor算法的总结
Shor算法首先把问题分解为了“经典计算机部分”和“量子计算机部分”。然后利用了量子态的叠加原理，快速取得了函数在一个很大范围内的取值（对于 $n$ 个工作比特而言，取值范围为 $0\sim2^n-1$。由于函数本身是周期的，所以自变量和函数值自动地纠缠了起来，从而对于某一个函数值来说，工作比特上的态就是一组周期数态的叠加态。在取得“周期数叠加态”之后，我们自然可以通过傅里叶变换得到这组周期数的周期，从而快速解决了这个问题。 反过来看，之所以找函数周期问题能被量子计算机快速解决，是因为在工作比特上执行了一组Hadamard变换。它在“量子函数”的作用下，相当于同时对指数级别的自变量上求出了函数值。在数据量足够大，周期足够长的情况下，这样执行的操作总量一定会小于逐个取值寻找这个函数值在之前是否出现过——这样的经典计算机“暴力破解”法要快得多。 Shor算法的难点在于如何通过给出的 $a$，$n$ 来得到对应的“量子函数”形式。进一步地讲，是否存在某种方法（准确地说是具有合理时间复杂度的方法）得到任意函数的“量子计算机版本”？限于笔者知识水平不足，我只能给出目前大概的研究结论是存在某些无法表示为量子计算机版本的函数，但是幸运地是Shor算法属于可以表示的那一类里面。 最后，我们可以发现，量子计算机之所以快，和量子计算机本身的叠加特性有关，它使得在处理特定问题时，比如数据库搜索，比如函数求周期……有着比经典计算机快得多的方法。但是如果经典计算机在解决某个问题时已经足够快了，我们就不需要用量子计算机来解决了。 就像Shor算法里面所描述的那样——我们将问题分解为了量子计算机去处理的“困难问题”和经典计算机去处理的“简单问题”两个部分一样。所以，量子计算机的出现，不代表经典计算机将会退出历史舞台，而是代表着人类将要向经典计算机力所不及的地方伸出探索之手。靠着量子计算机，或许我们能提出新的算法解决化学问题，从而研制出新型药物；或许我们可以建立包含所有信息的数据库，每次只需要一瞬间就能搜索到任何问题……量子云平台是我们帮助量子计算机走出的第一步，但接下来的路怎么走，我们就要和你一同见证了。
void rondamNumber()
{
init();
QProg & random = CreateEmptyQProg();
//Create an empty program named etangle
auto qbit0 = qAlloc();
auto qbit1 = qAlloc();
auto qbit2 = qAlloc();
auto qbit3 = qAlloc();
auto qbit4 = qAlloc();
auto qbit5 = qAlloc();
auto qbit6 = qAlloc();
// allocate 6 qubits
auto cbit0 = cAlloc();
auto cbit1 = cAlloc();
auto cbit2 = cAlloc();
auto cbit3 = cAlloc();
auto cbit4 = cAlloc();
auto cbit5 = cAlloc();
auto cbit6 = cAlloc();
// allocate 7 cbits
random
<< H(qbit0)
<< H(qbit1) << H(qbit2) << H(qbit3)
<< H(qbit4) << H(qbit5) << H(qbit6)
<< Measure(qbit0, cbit0) << Measure(qbit1, cbit1)
<< Measure(qbit2, cbit2) << Measure(qbit3, cbit3)
<< Measure(qbit4, cbit4) << Measure(qbit5, cbit5)
<< Measure(qbit6, cbit6);
// Required quantum circuit.
load(random);
// And then load it into the quantum computer.
run();
// simply run it.
auto resultMap = getResultMap();
// you can get the result map, which save all the
// measurement results in the classical register(CBit)
auto Num000 = resultMap["c0"];
auto Num001 = resultMap["c1"];
auto Num010 = resultMap["c2"];
auto Num011 = resultMap["c3"];
auto Num101 = resultMap["c4"];
auto Num110 = resultMap["c5"];
auto Num111 = resultMap["c6"];
cout <<"The random number of this production is;"
<< Num000 << Num001 << Num010
<< Num011 << Num101 << Num110 << Num111;
finalize();
// Use finalize() to tell the quantum computer to stop.
}
考虑函数：
$f:\{0,1\}^n \rightarrow \{0,1\} $
我们保证有如下两种可能性:
（1）$f$是常数的（Constant）,即是对$x\in\{0,1\}^n $,都有$f(x)=0$或$f(x)=1$.
（2）$f$是平衡的（Balanced）,对于输入的$x\in\{0,1\}^n $，$f(x)$出输出0和1的个数相同。
算法的目标：判断函数$f$是什么类型。
在最简单的情况下，最少也需要2次才能判断函数属于什么类型。因为需要第二个输出才能判断最终函数的类型。对于n位输入时，最坏的情况下需要次才能确认。
通过构造Oracle的方式，仅需运行一次就能确定函数属于哪一类。
第一步，制备n个工作（Working）比特到 $|0 \left. \right \rangle$态，与一个辅助（Ancillary）比特到 $|1 \left. \right \rangle$。第二步，所有比特都经过Hadamard变换，使系统处于叠加态上。
$$|0\left. \right \rangle^{\otimes_n}|1\left. \right \rangle\xrightarrow{H^{\otimes_{n+1}}}\frac{1}{ \sqrt{2^n}}\sum_{x=0}^{2^n-1}|x\left. \right \rangle{(\frac{|0\left. \right \rangle-|1\left. \right \rangle}{ \sqrt{2}})}$$
第三步，系统通过Oracle ，一种酉变换，满足：
$$U_f:|x\left. \right \rangle|y\left. \right \rangle \longrightarrow |x\left. \right \rangle|y\oplus f(x)\left. \right \rangle$$
这时候，系统状态为：
$$\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}|x\left. \right \rangle{(\frac{|0\left. \right \rangle-|1\left. \right \rangle}{ \sqrt{2}})}\xrightarrow{Oracle}\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1} {(-1)^{f(x)}} |x\left. \right \rangle{(\frac{|0\left. \right \rangle-|1\left. \right \rangle}{ \sqrt{2}})}$$
当时$f(x)=1$，会使得$\frac{|0\left. \right \rangle-|1\left. \right \rangle }{\sqrt{2}} \longrightarrow \frac{|1\left. \right \rangle-|0\left. \right \rangle }{\sqrt{2}}$，发生相位的翻转。
第四步：去除辅助比特，执行Bell测量。如果输出全部为0，则是$f$是常数的，反之，这是平衡的。
/*
Copyright (c) 2017-2018 Origin Quantum Computing. All Right Reserved.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/
#include "DJ_Algorithm.h"
void DJ_Algorithm()
{
bool fx0 = 0, fx1 = 0;
cout << "input the input function" << endl
<< "The function has a boolean input" << endl
<< "and has a boolean output" << endl
<< "f(0)= (0/1)?";
cin >> fx0;
cout << "f(1)=(0/1)?";
cin >> fx1;
vector<bool> oracle_function({ fx0,fx1 });
cout << "Programming the circuit..." << endl;
init();
auto q1 = qAlloc();
auto q2 = qAlloc();
auto c1 = cAlloc();
Reset_Qubit(q1, false);
Reset_Qubit(q2, true);
append(Two_Qubit_DJ_Algorithm_Circuit(q1, q2, c1, oracle_function));
run();
//auto resultMap = getResultMap();
if (getCBitValue(c1) == false)
{
cout << "Constant function!";
}
else if (getCBitValue(c1) == true)
{
cout << "Balanced function!";
}
}
QProg & Two_Qubit_DJ_Algorithm_Circuit(
Qubit * qubit1,
Qubit * qubit2,
CBit * cbit,
vector<bool> oracle_function)
{
auto &prog = CreateEmptyQProg();
//Firstly, create a circuit container
prog << H(qubit1) << H(qubit2);
// Perform Hadamard gate on all qubits
if (oracle_function[0] == false
&&
oracle_function[1] == false)
// different oracle leads to different circuit
// f(x) = oracle_function[x]
{
// f(x) = 0, do nothing
}
else if (oracle_function[0] == false
&&
oracle_function[1] == true
)
{
// f(x) = x;
prog << CNOT(qubit1, qubit2);
}
else if (oracle_function[0] == true
&&
oracle_function[1] == false
)
{
// f(x) = x + 1;
prog << RX(qubit2)
<< CNOT(qubit1, qubit2)
<< RX(qubit2);
}
else if (oracle_function[0] == true
&&
oracle_function[1] == true
)
{
// f(x) = 1
prog << RX(qubit2);
}
// Finally, Hadamard the first qubit and measure it
prog << H(qubit1) << Measure(qubit1, cbit);
return prog;
}
这是一个硬币（便士）反转的游戏，游戏由两个玩家和一个可翻转硬币组成。和以往的游戏一 样，玩家在游戏开始之前，彼此都可以接受任何的策略，但是游戏开始之后，彼此没有任何交流和通信。游戏开始之前，玩家彼此，而且双眼 被蒙住，不可以看到当前翻转投掷硬币的状态。考虑玩家P和Q，以及一枚初始化处于H面（数字1，表示H,国徽面是T面）的硬币，如下：
初始的硬币状态是朝上(H)。
P，Q共同可以翻转该硬币。每次翻转后，玩家不可以看自己翻转的情况。
每个玩家可以自由翻转或者不翻转。
翻转的顺序是：Q $\rightarrow $ P $\rightarrow $ Q。
游戏结束，如果硬币是H面，Q赢，如果是T面，P赢。
考虑编码硬币的两个状态，分别为：
$$H= \begin{pmatrix}0\\1\end{pmatrix} ,T= \begin{pmatrix}0\\1\end{pmatrix} $$
如上文，H和T分别表示硬币的正反面，下面给定翻转操作，F为翻转，I为不翻转，分别为：
$$ F=\begin{bmatrix}0&1\\1&0\end{bmatrix} , I=\begin{bmatrix}1&0\\0&1\end{bmatrix} $$
验证FH=T,FT=H,并且验证不翻转的情况：
$$ FH=\begin{bmatrix}0&1\\1&0\end{bmatrix}\begin{pmatrix}1\\0\end{pmatrix}=\begin{pmatrix}0\\1\end{pmatrix}=T ,FT=\begin{bmatrix}0&1\\1&0\end{bmatrix}\begin{pmatrix}0\\1\end{pmatrix}=\begin{pmatrix}1\\0\end{pmatrix}=H $$
$$ IH=\begin{bmatrix}1&0\\0&1\end{bmatrix} \begin{pmatrix}1\\0\end{pmatrix} = \begin{pmatrix}1\\0\end{pmatrix} =H,IT=\begin{bmatrix}1&0\\0&1\end{bmatrix} \begin{pmatrix}0\\1\end{pmatrix} = \begin{pmatrix}0\\1\end{pmatrix} =T $$
可见，F操作，可以翻转（Flip）硬币。在经典游戏中, 我们只限于使用F和I的翻转, 它可 以改变状态或保持状态，在量子世界中, 我们可有额外的操作, 数学上由酉矩阵（Unitary matrices） 表示。回顾基础部分所涉及到的叠加态（Superposition）的概念， 量子世界里，有办法将状态置于硬币正反面的一个叠加态（可以想象成硬币翻转的时候，处于在正面和反面的一个叠加态里）
这里，我们考虑一个酉矩阵U（Hadamard Gate）,在游戏博弈的时候，P将采用这种翻转。
$$U=\frac{1}{ \sqrt{2}}\begin{bmatrix}1&1\\1&-1\end{bmatrix}$$
在回顾游戏的步骤，第一步初始化的硬币处于$H= \begin{pmatrix}0\\1\end{pmatrix}$，第二步P执行翻转，此处P执行U翻转，把状态置为：
$$UH=\frac{1}{ \sqrt{2}}\begin{bmatrix}1&1\\1&-1\end{bmatrix} \begin{pmatrix}0\\1\end{pmatrix}=\frac{1}{ \sqrt{2}}\begin{pmatrix}1\\1\end{pmatrix}=S^{HT}$$
第三步，Q执行翻转，可以看到出，无论Q执行X或者I操作，状态始终保持不变。最后一步，P在执行一次U操作，状态变化为：
$$US^{HT}=\frac{1}{2}\begin{bmatrix}1&1\\1&-1\end{bmatrix} \begin{pmatrix}1\\1\end{pmatrix}=\begin{pmatrix}0\\1\end{pmatrix}=H$$
状态恢复到H,所以Q一直赢得游戏。
1.定义随机数生产，生成随机数，模拟P是否选择翻转。
2.询问用户，需要多少“硬币”（状态），定义为N。
3.初始化N个比特。
4.模拟Q的第一步操作，对N个状态执行U门（Hadamard gate）。
5.模拟P对任意状态执行F或者I操作（采用随机数的结果作为选择依据）。
6.模拟Q最后一步操作。对所有状态执行U门操作。
测量，输出结果，得到结果为00…0，告知恭喜胜利！
(1)初始态：$|0\left. \right \rangle|\phi\left. \right \rangle|\Psi \left. \right \rangle$
(2)给辅助比特加Hadamard操作后，态演化为：
$\frac{1}{\sqrt{2} }{(|0\left. \right \rangle+|1\left. \right \rangle)}|\phi\left. \right \rangle|\Psi \left. \right \rangle$
(3)辅助量子比特对和进行控制交换操作后，态演化为：
$\frac{1}{\sqrt{2} }{(|0\left. \right \rangle |\phi\left. \right \rangle|\Psi \left. \right \rangle+|1\left. \right \rangle|\Psi\left. \right \rangle| \phi\left. \right \rangle)}$
(4)再次给辅助量子比特加Hadamard操作后，态演化为：
$\frac{1}{2}|0\left. \right \rangle{(|\phi\left. \right \rangle|\Psi \left. \right \rangle+|\Psi\left. \right \rangle| \phi\left. \right \rangle)} + \frac{1}{2}|1\left. \right \rangle{(|\phi\left. \right \rangle|\Psi \left. \right \rangle-|\Psi\left. \right \rangle| \phi\left. \right \rangle)}$
(5)对辅助比特进行测量，测量到和的概率分别为：
$p_0=\frac{1}{2}{(1+|\left \langle {\phi|\Psi} \right \rangle|^2)}$
$p_1=\frac{1}{2}{(1-|\left \langle {\phi|\Psi} \right \rangle|^2)}$
从而根据测量得到的$p_0$或$p_1$即可得到$|\left \langle {\phi|\Psi} \right \rangle|^2$，判断$|\phi \left. \right \rangle$和$|\Psi \left. \right \rangle$的接近程度。
下面是一份用QPanda实现的Swap Test操作的程序源码，其中$|\phi \left. \right \rangle$和$|\Psi \left. \right \rangle$均是单比特态；
QProg swaptest_QProg(vector<Qubit*> qVec, vector<CBit*> cVec, vector<double>& phi)
{
QProg swaptest_qprog = CreateEmptyQProg();
swaptest_qprog << H(qVec[0]);
//initial state
swaptest_qprog << RY(qVec[1], phi[0])<<RZ(qVec[1], phi[1]);
swaptest_qprog << RY(qVec[2], phi[2]) << RZ(qVec[2], phi[3]);
//control swap
QCircuit controlswap = CreateEmptyCircuit();
controlswap << CNOT(qVec[1], qVec[2])<< CNOT(qVec[2], qVec[1])<<CNOT(qVec[1], qVec[2]);
vector<Qubit*> qvtemp;
qvtemp.push_back(qVec[0]);
controlswap.setControl(qvtemp);
swaptest_qprog << controlswap;
swaptest_qprog <<H(qVec[0])<< Measure(qVec[0], cVec[0]);
return swaptest_qprog;
}
void swaptest()
{
cout << "Swap Test Algorithm\n" << endl;
cout << "Initialize phi" << endl;
double theta1;
double alpha1;
double theta2;
double alpha2;
vector<double> phi;
cout << "input theta1:" << endl;
cin >> theta1;
cout << "input alpha1:" << endl;
cin >> alpha1;
cout << "input theta2:" << endl;
cin >> theta2;
cout << "input alpha2:" << endl;
cin >> alpha2;
cout << "phi=" << cos(theta1 / 2) << "*|0>+" << exp(1i*alpha1)*sin(theta1 / 2) << "|1>" << endl;
cout << "psi=" << cos(theta2 / 2) << "*|0>+" << exp(1i*alpha2)*sin(theta2 / 2) << "|1>" << endl;
phi.push_back(theta1);
phi.push_back(alpha1);
phi.push_back(theta2);
phi.push_back(alpha2);
cout<<" Programming the circuit..." << endl;
init();
vector<Qubit*> qVec;
vector<CBit*> cVec;
for (auto i = 0; i < 3 ; i++)
{
qVec.push_back(qAlloc());
}
cVec.push_back(cAlloc());
double prob;
size_t times=0;
for (auto i = 0; i < 1000; i++)
{
if (swaptest1(qVec, cVec, phi))
{
times++;
}
}
prob = times*0.001;
cout << "|<phi|psi>|^2=" << 1 - 2 * prob << endl;
return;
}
bool swaptest1(vector<Qubit*> qVec, vector<CBit*> cVec, vector<double>& phi)
{
init();
auto bvAlgorithm = swaptest_QProg(qVec, cVec, phi);
append(bvAlgorithm);
run();
return getCBitValue(cVec[0]);
}
[1].Nana Liu,Patrick Rebentrost,arXiv:1710.07405vl.
[2].CH Yu,F Gao,QY Wen.arXiv:1707.09524,2017.
[3].H.Buhrman,R.Cleve,J.Watrous,and R.de wolf, Quantum fingerprinting, Phys.Rev.Lett.87,167902.
给定一个方程：
$f:\{0,1\}^n\longrightarrow\{0,1\}^n$
存在$s\in\{0,1\}^n$，对所有的$x,y\in\{0,1\}^n$，满足下面的性质：
$f(x)=f(y)$当且仅当$x=y$或$x\oplus y=s$ （这里$\otimes$表示模2加。)
例：n=2的Simon问题,考虑2量子比特。注意，如果目标$s=0^n$，那这个函数是1对1（one-to-one）的， 此处不考虑。反之，则是一个二对一(two-to-one)的函数，几种情况如下图（函数值任意给定）：
| $x$ | $f(x)$ |
|---|---|
| 00 | 1 |
| 01 | 1 |
| 10 | 0 |
| 11 | 0 |
| $x$ | $f(x)$ |
|---|---|
| 00 | 1 |
| 01 | 2 |
| 10 | 1 |
| 11 | 2 |
| $x$ | $f(x)$ |
|---|---|
| 00 | 1 |
| 01 | 3 |
| 10 | 3 |
| 11 | 1 |
在（1）很容易看出$f(00)=f(01)=1$，$f(10)=f(11)=0$，因此$00\oplus01=01$，$10\oplus11=01$，推出$s=01$。经典算法最低需要2次的才能确定，一般情况下，对于n比特的问题估计找到目标s最糟糕的情况下要消耗多达$2^{n-1}+1$次。 但是在量子算法里，1次就解决了这个问题。
Simon问题的量子Oracle(考虑s=11)
考虑n=2的Simon问题，此时需要2量子比特的变量和2量子比特的函数，合计需要4量子比特。
$|x_ox_1\left. \right \rangle|00\left. \right \rangle\xrightarrow{uf}|x_ox_1\left. \right \rangle|00\oplus f(x_0x_1)\left. \right \rangle=|x_0x_1\left. \right \rangle|f(x_0x_1)\left. \right \rangle$
上面的这个量子Oracle可以加入Hadamard门，对前两个量子比特做H操作，等价于：
$$|0000\left. \right \rangle \xrightarrow{H \otimes H \otimes I\otimes I}|++\left. \right \rangle|00\left. \right \rangle\xrightarrow{u_f} \frac{1}{2}{[(|00\left. \right \rangle+|11\left. \right \rangle)|1\left. \right \rangle +(|01\left. \right \rangle+|10\left. \right \rangle)|3\left. \right \rangle } \xrightarrow{H \otimes H \otimes I\otimes I}\frac{1}{2}{[(|00\left. \right \rangle+|11\left. \right \rangle)|1\left. \right \rangle +(|00\left. \right \rangle-|11\left. \right \rangle)|3\left. \right \rangle ]}$$
(注意：$|3\left. \right \rangle$是我定义的函数值)
因此，最下面的两个位分别对应了$|1\left. \right \rangle$和$|3\left. \right \rangle$，测量上面的两量子位，$|00\left. \right \rangle$和$|11\left. \right \rangle$则会被以50%的概率被观察到。
1. 初始化4个量子比特。
2. 创建线路图: q[0], q[1]分别做Hadamard操作。
3. 对q[0]，q[2]和q[1], q[2]分别执行CNOT操作。
4. 对q[3]执行NOT操作。
5. 再对q[0]，q[1]分别做Hadamard操作
6. 最后测量全部量子逻辑位，输出结果。
QPanda代码 (s=11)
QProg Simon_QProg(vector<Qubit*> qVec, vector<CBit*> cVec, vector<int> funvalue)
{
size_t length = cVec.size();
auto simon_qprog = CreateEmptyQProg();
for (auto i = 0; i < length; i++)
{
simon_qprog << H(qVec[i]);
}
simon_qprog << oraclefunc(qVec,funvalue);
for (auto i = 0; i < length; i++)
{
simon_qprog << H(qVec[i]);
}
for (auto i = 0; i < length; i++)
{
simon_qprog << Measure(qVec[i],cVec[i]);
}
return simon_qprog;
}
//f(x),x is 2bits variable
QCircuit oraclefunc(vector<Qubit*> qVec, vector<int> funvalue)
{
auto length = qVec.size() / 2;
auto func = CreateEmptyCircuit();
for (auto i = 0; i < 4; i++)
{
func << controlfunc(qVec,i, funvalue[i]);
}
return func;
}
QCircuit controlfunc(vector<Qubit*> qVec,size_t index, int value)
{
auto length = qVec.size() / 2;
auto cfunc = CreateEmptyCircuit();
vector<Qubit*> qvtemp;
qvtemp.insert(qvtemp.begin(), qVec.begin(), qVec.begin() + length);
if (index == 1)
{
cfunc << X(qVec[0]);
}
else if (index == 2)
{
cfunc << X(qVec[1]);
}
else if (index == 0)
{
cfunc << X(qVec[0]);
cfunc << X(qVec[1]);
}
if (value == 1)
{
QGate temp = X(qVec[3]);
temp.setControl(qvtemp);
cfunc << temp;
}
else if (value == 2)
{
QGate temp1 = X(qVec[2]);
temp1.setControl(qvtemp);
cfunc << temp1;
}
else if (value == 3)
{
QGate temp2 = X(qVec[2]);
temp2.setControl(qvtemp);
cfunc << temp2;
QGate temp3 = X(qVec[3]);
temp3.setControl(qvtemp);
cfunc << temp3;
}
if (index == 1)
{
cfunc << X(qVec[0]);
}
else if (index == 2)
{
cfunc << X(qVec[1]);
}
else if (index == 0)
{
cfunc << X(qVec[0]);
cfunc << X(qVec[1]);
}
return cfunc;
}
这里，测定结果得$|00\left. \right \rangle$的时候，表示没有得到任何的信息，当测量得到$|11\left. \right \rangle$的时候，就得到了s=11，也就是说Simon量子算法里面，0以外的获取s的概率为50%。
input:
考虑一个经典的布尔函数：
$f:\{0,1\}^n\longrightarrow\{0,1\}$
存在$s\in \{0,1\}^n$，再定义一个函数：
$f_s(x)=\left \langle {s,x} \right \rangle,x\in \{0,1\}^n$
s是一个未知的向量，通常称s为隐藏字符串（Hidden string），其中$\left \langle {s,x} \right \rangle$表示内积（inner product），定义为：
$\left \langle {s,x} \right \rangle=s_0x_0\oplus s_1x_1\oplus..\oplus s_nx_n$
（符号$\otimes$在所出现的量子算法文中都表示布尔加或模2加。）:
Output：
算法目标：找到s.
由于对该函数的每个经典查询只能生成1位的信息, 而任意隐藏字符串 s 具有$n$位的信息, 所以经典查询复杂性是$O(n)$。
Bernstein-Vazirani的工作建立在Deutsch和Jozsa早期工作理论上来探索量子查询复杂度。他们对该领域的 贡献是一个用于隐藏字符串问题的量子算法, 该算法的非递归量子查询复杂度仅为1，同比经典情况$O(n)$。这一量子算法的真正突破在于加快查询复杂度, 而不是执行时间本身。
案例：考虑n=3时的Bernstein-Vazirani问题。变量是3比特时，二进制表示为$x_0x_1x_2$，常数s则表示为$s_0s_1s_2$，因此所求的常数s总共有8个。此时，问题函数描述如下：
$f_s(x_0x_1x_2)=s_0x_0\oplus s_1x_1 \oplus s_2x_2$
不难看出，对于经典算法而言，如果是$f_s(100)=s_0,f_s(010)=s_1,f_s(001)=s_2$， 那么最少也需要3次调用函数才可以确定常量$s=s_0s_1s_2$。但是对于量子算法而言，使用下面的量子Oracle计算，1次就可以决定$s=s_0s_1s_2$，其计算复杂度为$O(1)$。
分析上图：
$$|0\left. \right \rangle|1\left. \right \rangle\xrightarrow{H\otimes H\otimes H\otimes H} \frac{1}{ 2\sqrt{2}}\sum_{x=0}^{7}|X\left. \right \rangle\otimes {(\frac{|0\left. \right \rangle-|1\left. \right \rangle}{\sqrt{2}})} $$
$$\xrightarrow{uf}\frac{1}{ 2\sqrt{2}}\sum_{x=0}^{7}{(-1)^\left \langle {s,x} \right \rangle}|x\left. \right \rangle\otimes{(\frac{|0\left. \right \rangle-|1\left. \right \rangle}{\sqrt{2}})}$$
$$\xrightarrow{H\otimes H\otimes H\otimes H} \frac{1}{ 2\sqrt{2}}\sum_{x=0，y=0}^{7}{(-1)^{\left \langle {s,x} \right \rangle\otimes \left \langle {x,y} \right \rangle}} |y\left. \right \rangle\otimes{(\frac{|0\left. \right \rangle-|1\left. \right \rangle}{\sqrt{2}})}\Xi|s> \otimes{(\frac{|0\left. \right \rangle-|1\left. \right \rangle}{\sqrt{2}})}$$
不失一般性：
$$|0\left. \right \rangle^n|1\left. \right \rangle\xrightarrow{H^{\otimes(n+1)}}\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}|X\left. \right \rangle\otimes {(\frac{|0\left. \right \rangle-|1\left. \right \rangle}{\sqrt{2}})} $$
$$\xrightarrow{uf}\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}{(-1)^\left \langle {s,x} \right \rangle}|x\left. \right \rangle\otimes{(\frac{|0\left. \right \rangle-|1\left. \right \rangle}{\sqrt{2}})}$$
$$\xrightarrow{H^{\otimes(n+1)}} \frac{1}{ \sqrt{2^n}}\sum_{x=0，y=0}^{2^n-1}{(-1)^{\left \langle {s,x} \right \rangle\oplus \left \langle {x,y} \right \rangle}} |y\left. \right \rangle\otimes{(\frac{|0\left. \right \rangle-|1\left. \right \rangle}{\sqrt{2}})}\Xi|s\left. \right \rangle \otimes{(\frac{|0\left. \right \rangle-|1\left. \right \rangle}{\sqrt{2}})}$$
下面给出两组案例,分别是s=101和s=111
过程：略
量子语言 :
RX 3,"pi"
H 0
H 1
H 2
H 3
CNOT 0,3
CNOT 2,3
H 0
H 1
H 2
MEASURE 0,$0
MEASURE 1,$1
MEASURE 2,$2
这时，输出的结果，指代了s。通过验证,输出结果为：
线路图设计为：
测量结果：
量子语言 :
RX 3,"pi"
H 0
H 1
H 2
H 3
CNOT 0,3
CNOT 1,3
CNOT 2,3
H 0
H 1
H 2
MEASURE 0,$0
MEASURE 1,$1
MEASURE 2,$2
QProg BV_QProg(vector<Qubit*> qVec, vector<CBit*> cVec, vector<bool>& a, bool b)
{
if (qVec.size() != (a.size()+1))
{
throw exception("error");
}
size_t length = qVec.size();
QProg bv_qprog = CreateEmptyQProg();
bv_qprog << X(qVec[length - 1]);
for (auto iter = qVec.begin(); iter != qVec.end(); iter++)
{
bv_qprog << H(*iter);
}
for (auto i=0;i<length-1;i++)
{
if (a[i])
{
bv_qprog << CNOT(qVec[i], qVec[length - 1]);
}
}
for (auto i = 0; i < length - 1; i++)
{
bv_qprog << H(qVec[i]);
}
for (auto i = 0; i < length - 1; i++)
{
bv_qprog << Measure(qVec[i], cVec[i]);
}
return bv_qprog;
}
void BernsteinVaziraniAlgorithm()
{
cout << "Bernstein Vazirani Algorithm\n" << endl;
cout << "f(x)=a*x+b\n" << endl;
cout << "input a" << endl;
string stra;
cin >> stra;
vector<bool> a;
for (auto iter = stra.begin(); iter != stra.end(); iter++)
{
if (*iter == '0')
{
a.push_back(0);
}
else
{
a.push_back(1);
}
}
cout << "input b" << endl;
bool b;
cin >> b;
cout << "a=\t" << stra << endl;
cout << "b=\t" << b << endl;
cout<<" Programming the circuit..." << endl;
size_t qbitnum = a.size();
init();
vector<Qubit*> qVec;
vector<CBit*> cVec;
for (auto i = 0; i < qbitnum ; i++)
{
qVec.push_back(qAlloc());
cVec.push_back(cAlloc());
}
qVec.push_back(qAlloc());
auto bvAlgorithm = BV_QProg(qVec, cVec, a, b);
append(bvAlgorithm);
run();
string measure;
cout << "a=\t";
for (auto iter = cVec.begin(); iter != cVec.end(); iter++)
{
cout << getCBitValue(*iter);
}
cout << "\n"<<"b=\t" << b << endl;
return;
}
输入：一个n*n的矩阵A和一个n维向量b。
输出：n维向量x，满足Ax=b。
1.输入的矩阵，必须是adjoint矩阵，当A不是Hermitian时，需要构造成adjoint矩阵。算法的输入部分如图1中红色方框所标出。输入q[2]存放在底部寄存器中，输入A作为相位估计中酉算子的一个组成部分。
2.输出x的形式：算法的输出如红色部分标出（同一个寄存器）。底部寄存器存放的是一个蕴含了向量x的量子态。 此处不需要知道这个状态具体情况。
#include "HHL_Algorithm.h"
void HHL_Algorithm()
{
map<string, bool> temp;
int x0 = 0;
int x1 = 0;
for (size_t i = 0; i < 1000;i++)
{
temp = hhlalgorithm();
if (temp["c0"])
{
if (temp["c1"])
{
x1++;
}
else
{
x0++;
}
}
}
int sum = x0 + x1;
cout << "prob0:" << x0*1.0/sum << endl;
cout << "prob1:" << x1*1.0/sum << endl;
}
map<string, bool> hhlalgorithm()
{
init();
int qubitnum = 4;
vector<Qubit*> qv;
for (size_t i = 0; i < qubitnum; i++)
{
qv.push_back(qAlloc());
}
vector<CBit*> cv;
int cbitnum = 2;
for (size_t i = 0; i < cbitnum; i++)
{
cv.push_back(cAlloc());
}
auto hhlprog =CreateEmptyQProg();
hhlprog << RY(qv[3], PI / 2); // change vecotr b in equation Ax=b
hhlprog << hhl(qv, cv);
load(hhlprog);
run();
auto resultMap = getResultMap();
finalize();
return resultMap;
}
int HHL_Test(int repeat)
{
try
{
init();
int qubitnum = 4;
vector<Qubit*> qv;
for (size_t i = 0u; i < qubitnum; i++)
{
qv.push_back(qAlloc());
}
vector<CBit*> cv;
int cbitnum = 2;
for (size_t i = 0u; i < cbitnum; i++)
{
cv.push_back(cAlloc());
}
auto hhlprog = CreateEmptyQProg();
hhlprog << RY(qv[3], PI / 2);
hhlprog << hhl(qv, cv);
load(hhlprog);
int x0 = 0;
int x1 = 1;
for (size_t i = 0u; i < repeat; ++i)
{
run();
auto resultMap = getResultMap();
if (resultMap["c0"])
{
if (resultMap["c1"])
{
x1++;
}
else
{
x0++;
}
}
}
finalize();
cout << "x0: " << x0 << endl
<< "x1: " << x1 << endl;
}
catch (QPandaException &e)
{
cout << e.what();
return 1;
}
return 0;
}
QProg hhl(vector<Qubit*> qVec, vector<CBit*> cVec)
{
ClassicalCondition cc0=bind_a_cbit(cVec[0]);
// meaningless sentence
QCircuit ifcircuit = CreateEmptyCircuit();
QCircuit PSEcircuit = hhlPse(qVec);//PSE
QCircuit CRot = CRotate(qVec);//control-lambda
QCircuit PSEcircuitdag = hhlPse(qVec);
//hhl circuit
QProg PSEdagger = CreateEmptyQProg();
PSEdagger << PSEcircuitdag.dagger() << Measure(qVec[3], cVec[1]);
QIfProg ifnode = CreateIfProg(cc0, &PSEdagger);
QProg hhlProg = CreateEmptyQProg();
//hhlProg << PSEcircuit <<CRot<< Measure(qVec[0], cVec[0])<<ifnode;
hhlProg << PSEcircuit << CRot << Measure(qVec[0], cVec[0]) << ifnode;
return hhlProg;
}
QCircuit hhlPse(vector<Qubit*> qVec)
{
QCircuit PSEcircuit = CreateEmptyCircuit();
PSEcircuit << H(qVec[1]) << H(qVec[2]) << RZ(qVec[2], 0.75*PI);
QGate gat1 = CU(PI, 1.5*PI, -0.5*PI, PI / 2, qVec[2], qVec[3]);
QGate gat2 = CU(PI, 1.5*PI, -PI, PI / 2, qVec[1], qVec[3]);
PSEcircuit << gat1 << RZ(qVec[1], 1.5*PI) << gat2;
PSEcircuit << CNOT(qVec[1], qVec[2]) << CNOT(qVec[2], qVec[1]) << CNOT(qVec[1], qVec[2]);
//PSEcircuit << gat1 << RZ_GATE(q1, 1.5*PI)<<gat2 ;
QGate gat3 = CU(-0.25*PI, -0.5*PI, 0, 0, qVec[2], qVec[1]);
PSEcircuit << H(qVec[2]) << gat3 << H(qVec[1]); //PSE over
return PSEcircuit;
}
QCircuit CRotate(vector qVec)
{
QCircuit CRot = CreateEmptyCircuit();
vector<Qubit *> controlVector;
controlVector.push_back(qVec[1]);
controlVector.push_back(qVec[2]);
QGate gat4 = RY(qVec[0], PI);
gat4.setControl(controlVector);
QGate gat5 = RY(qVec[0], PI / 3);
gat5.setControl(controlVector);
QGate gat6 = RY(qVec[0], 0.679673818908); //arcsin(1/3)
gat6.setControl(controlVector);
CRot << X(qVec[1]) << gat4 << X(qVec[1]) << X(qVec[2]) << gat5 << X(qVec[2]) << gat6;
//CRot << X(qVec[1]) << gat4 << X(qVec[1]);
return CRot;
}
1.真币的重量均等，假币的质量也均等，假币的质量比真币轻。
2.天平只给我们提供两个信息，平衡（两组币的重量相同）或倾斜。
线路说明：紫色的if表示的是测量判断，根据输出的经典信息来判断是否需要执行下一步的操作。上面线路图里判定条 件，如果输出为0的时候，则需要执行0 对应的操作，实际上就是从新执 行一遍量子线路，反之，执行$U_f$操作，$U_f$指代了错误币所在位置的控制非门，目标位最后一位。
QProg counterfeitCoin_QProg(vector<Qubit*> qVec, vector<CBit*> cVec, int position)
{
QProg prog = CreateEmptyQProg();
QProg endprog = CreateEmptyQProg();
QProg whileprog = CreateEmptyQProg();
QCircuit qcir = CreateEmptyCircuit();
ClassicalCondition cc = bind_a_cbit(cVec[cVec.size() - 1]);
for (auto iter = qVec.begin(); iter != qVec.end() - 1; iter++)
{
qcir << H(*iter);
endprog << H(*iter);
}
for (auto iter = qVec.begin(); iter != qVec.end() - 1; iter++)
{
endprog << Measure(*iter, cVec[iter - qVec.begin()]);
}
for (auto iter = qVec.begin(); iter != qVec.end() - 1; iter++)
{
qcir << CNOT(*iter, *(qVec.end() - 1));
}
whileprog << qcir << Measure(qVec[qVec.size() - 1], cVec[cVec.size() - 1]);
QWhileProg WhileNode = CreateWhileProg(cc, &whileprog);
QIfProg ifnode = CreateIfProg(cc, &endprog);
prog << qcir << Measure(qVec[qVec.size() - 1], cVec[cVec.size() - 1]) << WhileNode
<< X(qVec[qVec.size() - 1]) << H(qVec[qVec.size() - 1])
<< CNOT(qVec[position], qVec[cVec.size() - 1])
<< endprog;
return prog;
}
void counterfeitCoinGame()
{
cout << "Counterfeit Coin Game Algorithm\n" << endl;
cout << "eight coins ,one coin is counterfeit" << endl;
cout << "choose the position of the counterfeit coin(0~7)" << endl;
int position;
cin >> position;
cout<<" Programming the circuit..." << endl;
init();
vector<Qubit*> qVec;
vector<CBit*> cVec;
for (auto i = 0; i < 9 ; i++)
{
qVec.push_back(qAlloc());
cVec.push_back(cAlloc());
}
auto ccAlgorithm = counterfeitCoin_QProg(qVec, cVec, position);
append(ccAlgorithm);
bool isSuccess=true;
run();
int itemp = 0;
for (auto i = 0; i < cVec.size() - 1; i++)
{
if (getCBitValue(cVec[i]))
{
itemp++;
}
}
if (itemp > 1)
{
for (auto i = 0; i < cVec.size() - 1; i++)
{
if (!getCBitValue(cVec[i]))
{
cout << "The position of counterfeit coin is :" << i << endl;
}
}
}
else
{
for (auto i = 0; i < cVec.size() - 1; i++)
{
if (getCBitValue(cVec[i]))
{
cout << "The position of counterfeit coin is :" << i << endl;
}
}
}
return;
}
[1].https://en.wikipedia.org/wiki/Balance_puzzle
[2].《Quantum Counterfeit Coin Problems》
