Quantum Computing

接前文，继续聊量子信息的不可克隆性这个话题。在前文中，我们用最简单的CNOT门为例子，演示了为什么CNOT量子电路只能复制经典信息，而并不能复制处于一般态的量子位。今天把这个讨论扩展到一般的情况，来证明 复制量子态的机器不可能存在 。 基本思路是用反证法。假设我们有个能复制一个量子位的机器，那么这个机器构成的系统，至少包含这些部分： 被克隆的量子位， \(|\psi\rangle = \alpha|0\rangle + \beta|1\rangle\) 辅助量子位， \(|\phi\rangle\) 机器本身的状态 \(|A\rangle\) ，初始状态用 \(|A_i\rangle\) 表示 既然这个机器是量子电路构成的，这个“克隆”过程也必然是一个幺正变换。把这个幺正变换记作U，那么我们要达到的是这样的一个变换过程： \begin{matrix} U |\psi\rangle |\phi\rangle |A_i\rangle \rightarrow |\psi\rangle |\psi\rangle |A_{f\psi}\rangle \end{matrix} 也就是输入的 \(|\psi\rangle\) 被复制成了2个，而机器的状态由初始的 \(|A_i\rangle\) 变成了某个终态，这个终态必然是依赖于输入 \(|\psi\rangle\) ，所以记作 \(|A_{f\psi}\rangle\) 。 显然，如果输入是 \(|0\rangle\) 或 \(|1\rangle\) 的话，我们有： \begin{matrix} U |0\rangle |\phi\rangle |A_i\rangle \rightarrow |0\rangle |0\rangle |A_{f0}\rangle \\ U |1\rangle |\phi\rangle |A_i\rangle \rightarrow |1\rangle |1\rangle |A_{f1}\rangle \\ \end{matrix} 那么如果输入是一般的量子态呢？也就是 \(|\psi\rangle = \alpha|0\rangle + \beta|1\rangle\) 把它代入到前面的变换过程里： \begin{matrix} U |\psi\rangle |\phi\rangle |A_i\rangle \\ = U (\alpha|0\rangle + \beta|1\rangle) |\phi\rangle |A_i\rangle \\ \rightarrow \alpha U |0\rangle |\phi\rangle |A_{f0}\rangle + \beta U |1\rangle |\phi\rangle |A_{f1}\rangle \\ = \alpha |0\rangle |0\rangle |A_{f0}\rangle + \beta |1\rangle |1\rangle |A_{f1}\rangle \\ = \alpha |00\rangle |A_{f0}\rangle + \beta |11\rangle |A_{f1}\rangle \\ \end{matrix} 但是，这是不是我们想要的“克隆”效果呢？显然不是啊！我们要的“克隆”变换，变换后的状态应该是这样的： ...

如果你关注过量子通信或量子信息的动态，应该会经常听到量子信息的“不可克隆性”这个概念。那么这个概念是怎么来的？今天就来聊一聊。 先从一个简单的例子出发。从以前对CNOT门的讨论，它似乎可以用来“复制”信息： 看起来当辅助量子位是 \(|0\rangle\) 的时候，输出就得到了两个 \(|x\rangle\) ，真的是这样吗？ 实际上，CNOT门只能复制经典信息（也就是输入为 \(|0\rangle\) 或 \(|1\rangle\) 的情况）。如果输入是一般状态 \(|\psi\rangle=a|0\rangle+b|1\rangle\) ，CNOT并不能复制它！ 咱们来具体推导一下。首先在输入端，要复制的量子位是 \(a|0\rangle+b|1\rangle\) ，辅助量子位 \(|0\rangle\) ，合起来输入端状态就是 \begin{matrix} (a|0\rangle + b|1\rangle)|0\rangle = a|00\rangle + b|10\rangle \end{matrix} CNOT的作用是当第一个量子位为1的时候翻转第二个量子位，所以我们在输出端得到的状态是 \begin{matrix} a|00\rangle + b|11\rangle & (1) \\ \end{matrix} 但是，我们要的是在输出端复制 \(|\psi\rangle\) ，也就是在输出端得到 \(|\psi\rangle|\psi\rangle\) ，这个状态展开写就是这样： \begin{matrix} |\psi\rangle|\psi\rangle = (a|0\rangle+b|1\rangle)(a|0\rangle+b|1\rangle) & \\ = a^2|00\rangle + ab|01\rangle + ab|10\rangle + b^2|11\rangle & (2) \\ \end{matrix} 比较一下(1)和(2)，只有当 \(ab=0\) ，也就是要复制的量子位为 \(|0\rangle\) 或 \(|1\rangle\) 时，这两个式子才有可能相等，而在一般情况下，(1)和(2)不可能相等。 这个推导告诉我们，CNOT组成的“复制”电路，只能复制经典比特，不能复制处于一般态的量子位。 ...

之前聊了不少量子计算的算法，今天换个话题，回到量子计算的一个根本问题，聊聊为什么量子计算机这么难制造。 经典计算机里的晶体管，工作时状态是确定的0或1，这样的可靠性是因为晶体管的状态并不取决于单个电子，而是许多电子的平均。这样一来，即使有少数电子的状态受到干扰翻转了（例如电子在线路中逃逸了），也不影响整个晶体管的状态。这也是经典计算机能可靠工作的关键。 举个例子来说，假如一个经典计算机里的比特由3个电子的状态表示，每个电子可能处于两种状态之一，记作 \(|\uparrow\rangle\) 和 \(|\downarrow\rangle\) 。在工作的时候，假如某个电子发生了翻转： \begin{matrix} |\uparrow\uparrow\uparrow\rangle \Rightarrow |\uparrow\downarrow\uparrow\rangle \end{matrix} 这种情况并不会造成经典比特的翻转。实际情况里，一个经典比特会由多得多的电子状态来表示，少数电子造成翻转的可能性就更小了，由此保证了经典计算机的可靠性。 但是，这个性质也决定了经典计算机的『经典』特性，使它无法表现出『量子』的一面。 设想一下，假如我们想用两个经典比特构造一个量子相干态： \begin{matrix} |\uparrow\uparrow\uparrow\rangle |\downarrow\downarrow\uparrow\rangle + |\downarrow\downarrow\downarrow\rangle |\uparrow\uparrow\uparrow\rangle \end{matrix} 在逻辑上，这个状态可以写成 \begin{matrix} |L\rangle = |1\rangle |0\rangle + |0\rangle |1\rangle \end{matrix} 假如某个电子翻转了，例如第一个晶体管的状态从 \(|\uparrow\uparrow\uparrow\rangle\) 变成了 \(|\uparrow\uparrow\downarrow\rangle\) ，物理状态发生了变化，但逻辑状态没有变： \begin{matrix} |P\rangle = |\uparrow\uparrow\uparrow\rangle |\downarrow\downarrow\uparrow\rangle + |\downarrow\downarrow\downarrow\rangle |\uparrow\uparrow\uparrow\rangle \\ \Rightarrow |\uparrow\uparrow\downarrow\rangle |\downarrow\downarrow\uparrow\rangle + |\downarrow\downarrow\downarrow\rangle |\uparrow\uparrow\uparrow\rangle \\ \\ |L\rangle = |1\rangle |0\rangle + |0\rangle |1\rangle \\ \Rightarrow |1\rangle |0\rangle + |0\rangle |1\rangle \end{matrix} 您可能会问：这不挺好么？物理上虽然有电子发生了翻转，但逻辑上就像什么也没发生一样！ ...

最近和量子搜索干上了 :-) 聊聊另一个量子搜索的应用——加速NP完全问题的求解。 学计算机朋友的应该都听说过『NP完全问题』。 所谓NP完全问题（NP-complete problems），不是指某一个，而是指一类问题，它们的共同特征是，可以快速验证给定的答案是否正确（verify the solution），但是要找到正确的答案（find the solutions）则很难，目前还没有找到高效（多项式复杂度）的算法。并且这一类问题是可以互相转化的，也就是说如果某一个NP完全问题找到了高效的求解算法，那么所有其他的NP完全问题也都能够高效求解了。 哈密尔顿回路问题（Hamilton cycle problem）就是一个NP完全问题。这个问题是说，给你一个图（有向或无向都可），请你找到一个访问图中所有顶点各一次的回路。这个问题又称为“旅行推销员问题”。 用数学语言来分析，假设这个图有n个顶点 \(v_1, v_2, \dots, v_n\) ，我们要找的是一个包含n个顶点，也就是长度为n的路径。为方便讨论，我们假设允许顶点重复，那么把所有可能的长度为n的路径列出来，总共有 \(n^n\) 种可能，所以整个搜索空间有 \(n^n = 2^{n \log n}\) 个状态。哈密尔顿回路问题，就是要在这个搜索空间里找出符合条件的答案。 显然，给定一个路径，我们很容易就能判断它是否是哈密尔顿回路，但是要从给定的图找到一个哈密尔顿回路，目前还没有发现高效（多项式）的算法。在经典计算机上，寻找哈密尔顿回路的复杂度是： \begin{matrix} O(2^{n \lceil \log n \rceil}) \end{matrix} 那么在量子计算机上，是否可以做的更好呢？答案是肯定的。量子计算机可以对这个问题实现平方根（square root）加速： \begin{matrix} O(2^{n \lceil \log n \rceil / 2}) \end{matrix} 接下来看看量子计算机是怎么做到的。 首先我们得有个函数判断给定的路径是否是哈密尔顿回路： \begin{matrix} f(v_1 v_2 \dots v_n) = \left\{ \begin{array}{ll} 1 && v_1 v_2 \dots v_n \verb= is a Hamilton cycle= \\ 0 && otherwise \end{array} \right. \end{matrix} 然后，把路径 \(v_1 v_2 \dots v_n\) 看作是量子电路的一个状态 \(|v\rangle\) 。比如，给某个顶点编号1到n，那么每个状态就是由n个1到n的数字来组成。显然要用二进制表示这样的状态，需要的肯定不止n比特，而是需要 \(n\log n\) 比特。因此在量子电路里需要 \(n\log n\) 个量子位来表示状态。 ...

前文《量子搜索》讨论了Grover算法，今天来讨论量子搜索的一个扩展问题——量子计数。 在量子搜索里，我们有一个搜索空间以及一个判断函数f，给定一个状态，f告诉我们它是不是要找的目标状态。Grover算法把f包装成一个G变换，经过多次迭代后测量，可以以任意高的概率得到答案（目标状态）。 量子计数的问题和搜索有点类似，但它关注的是答案（目标状态）的数量：已知在N个项的搜索空间里有若干个（M个）答案，但是答案的数量M未知，如何高效的确定有多少个答案（也就是M的值）？ 如果用经典计算机来解决这个问题，就必须遍历整个搜索空间，也就是要查询 \(O(N)\) 次。 如果用量子计算机的话，我们只需要用 \(O(\sqrt N)\) 次查询。相对经典计算机，这是一个多项式级别的加速（polynomial improvement）。之前讨论的Shor算法对因式分解问题有指数级加速，量子计数相比没那么耀眼，但也是一个显著的进步了。 量子计数算法的思路其实很简单：把Grover算法中的G变换看作是相位估计里的U，放到量子相位估计电路里，根据估计出来的相位，就能得到目标状态的数量（M的值）。 在《Grover算法的可视化》一文中，我们知道G变换其实是一个旋转变换，画个图理解一下： 在这个图里， \(|\alpha\rangle\) 表示所有非目标状态的叠加，而 \(|\beta\rangle\) 是所有目标状态的叠加。显然它们互相是正交的，如果用它们作为两个轴张成一个平面，那么Grover算法里的G变换就是把输入向量 \(|\psi\rangle\) 朝着 \(|\beta\rangle\) 轴旋转一个角度 \(\theta\) 。因此G变换可以写成这样的矩阵： \begin{bmatrix} \cos\theta && -sin\theta \\ \sin\theta && \cos\theta \end{bmatrix} 不难证明， \(|\alpha\rangle\) 和 \(|\beta\rangle\) 是G的两个本征向量，并且它们对应的本征值分别是 \(e^{i\theta}\) 和 \(e^{i(2\pi-\theta)}\) 。如果你有兴趣，可以拿纸笔验证一下。:-) 总之，这个G变换可以作为量子相位估计里的U来使用。 把Grover算法里的G变换放到量子相位估计里： 假设搜索空间大小N可以用n位二进制数表示，这里输入用了n+1位，也就是把搜索空间扩大了一倍。为什么要这么做呢？ 还记得前文讨论Grover算法有个特殊情况吗？就是目标状态（答案）的数量M超过N的一半，这种情况下Grover算法的性能反而会变差，因为每次旋转的角度太大了，转过头了。解决的办法，就是把搜索空间扩大一倍，确保目标状态的数量少于搜索空间的一半。这里用了同样的思路，因为我们不知道M是多少，干脆先在输入端把N扩大成2N，确保M少于搜索空间的一半。 另一个寄存器需要的量子位数目t，是由我们需要的精度和成功率来决定。例如，假如我们需要相位估计达到m比特的精度，并且成功率大于 \(1-\epsilon\) ，那么t可以这样估算： \begin{matrix} t = m + \lceil \log (2+\frac{1}{2\epsilon}) \rceil \end{matrix} 运行这个电路，在右边测量得到相位估计的结果，也就是 \(\theta\) 的近似值。 而根据Grover算法的原理和G变换的性质，我们知道： \begin{matrix} \sin \frac{\theta}{2} = \sqrt \frac{M}{2N} \end{matrix} 因此： ...

在前文《量子相位估计》里，我们讨论了量子相位估计算法，它也是很多量子算法能有指数级加速的关键。今天来讨论量子相位估计的另一个应用：求解给定幺正变换的平方根。 假如我们有一个幺正变换 \(U\) ，求解它的k次方 \(U^k\) 很容易，只要把k个 \(U\) 连起来就行，但是如果要求它的平方根 \(U^{1/2}\) 呢？事情就没那么简单了。今天来讨论一下，如何利用量子相位估计来求给定幺正变换的平方根，或者说，构造一个新的幺正变换，使它的平方等于给定的幺正变换。 先回顾一下什么是量子相位估计。 假如我们有一个幺正算符 \(U\) ， \(|u\rangle\) 是它的一个本征矢量，对应的本征值是 \(e^{i\phi}\) （ \(\phi\) 在0到 \(2\pi\) 之间）： \begin{matrix} U|u\rangle = e^{i\phi}|u\rangle \end{matrix} "量子相位估计"问题，就是从幺正算符 \(U\) 和 \(|u\rangle\) ，估算相应的本征值 \(e^{i\phi}\) 里的相位 \(\phi\) 。 量子相位估计的电路如下，输入 \(|u\rangle\) 是U的一个本征向量，在输出端测量，就能得到其本征值的相位 \(\psi=\phi/2\pi\) 的 n位二进制近似 。 你可能注意到，这里的输入 \(|u\rangle\) 是U的 一个 本征向量。但是，U可能有很多个本征向量，对不对？ 如果这个相位估计电路输入的不是某一个本征向量，而是U所有本征向量的叠加呢？右边输出会得到什么？也就是说，如果左边的输入是U的所有本征向量 \(|u_j\rangle\) 的叠加： \begin{matrix} |\psi\rangle = \sum_j \alpha_j |u_j\rangle \end{matrix} 猜猜右边会得到啥？ 答案很容易猜到，既然左边的输入是本征向量的叠加，那么右边的输出，就是对应的相位估计结果的叠加： \begin{matrix} U|\psi\rangle = \sum_j \alpha_j e^{i\phi_j} |u_j\rangle \end{matrix} 也就是说，如果在右边测量，会得到某一个本征向量 \(|u_j\rangle\) 的相位估计，其概率取决于它在输入的叠加态里的强度 \(|\alpha_i|^2\) 。 ...

线性独立 如果一组矢量 \(|\alpha_1\rangle, \dots, \alpha_m\rangle\) 满足： \begin{matrix} c_1|\alpha_1\rangle + c_2|\alpha_2\rangle + \dots + c_m|\alpha_m\rangle = 0 \end{matrix} 当且仅当 \begin{matrix} c_1 = c_2 = \dots = c_m = 0 \end{matrix} 那么称这组矢量就是线性独立的。 内积 模 柯西-施瓦茨不等式 正交归一 维数 Gram-Schmidt分解，构造正交归一基方法 线性算符 线性算符之积 完备性关系 线性算符的矩阵表示 Pauli矩阵 投影算符 多维子空间中的投影算符 本征值，本征矢量 厄米算符(Hermitian?) 逆算符 幺正算符

之前的Shor算法系列，其实还有个相关的坑，就是“量子相位估计” (Phase Estimation)，今天也来填一下。:-) 什么是“量子相位估计”？ 假如我们有一个幺正算符 \(U\) ，他的本征矢量是 \(|u\rangle\) ，本征值是 \(e^{i\phi}\) （ \(\phi\) 在0到 \(2\pi\) 之间）。 "量子相位估计“问题，就是从幺正算符 \(U\) 和它的本征矢量 \(|u\rangle\) ，估算它的本征值 \(e^{i\phi}\) 里的相位 \(\phi\) ： Estimate phase \(\phi\) of an eigenvalue of an unitary operator \(U\), given its eigenvector \(|u\rangle\). 量子相位估计算法 既然幺正算符 \(U\) 的本征矢量是 \(|u\rangle\) ，并且其对应的本征值是 \(e^{i\phi}\) ，那么根据本征矢量的定义： \begin{matrix} U|u\rangle = e^{i\phi}|u\rangle \end{matrix} 那么如果对 \(|u\rangle\) 进行多次U变换，不难推导出： \begin{matrix} U^k|u\rangle = e^{ik\phi}|u\rangle \end{matrix} 所以多次对 \(|u\rangle\) 进行 \(U\) 变换，得到的状态仍然是 \(|u\rangle\) ，只不过给它增加了一个全局相位。 我们可以从 \(U\) 制备出一组（n个）这样的幺正变换： \(U, U^2, U^4, U^8, \dots, U^{2^{n-1}}\) ...

今天来填个坑 :-) 前面Shor算法系列里大量用到的“量子傅立叶变换”，具体要怎么实现？这次来详细讨论一下。 量子傅立叶变换 前文说过，量子傅立叶变换QFT是这么一块电路： 同样根据前文，当输入n个量子位的基态 \(|j\rangle\) 时，输出可以写成： \begin{matrix} QFT|j\rangle = \\ \frac{1}{\sqrt{2^n}} \otimes_{l=1}^n \left[ |0\rangle + e^{2\pi ij/2^l} |1\rangle \right] \\ = \frac{1}{\sqrt{2^n}} \left( |0\rangle + e^{2\pi i 0.j_0}|1\rangle \right) \left( |0\rangle + e^{2\pi i 0.j_1j_0}|1\rangle \right) \dots \left( |0\rangle + e^{2\pi i 0.j_{n-1}j_{n-2}\dots j_0}|1\rangle \right) \\ \end{matrix} 我们的任务是用基本量子电路门构造这样的变换。 基本构件：受控旋转门 就像搭积木一样，量子傅立叶变换的电路是由很多基本组件构成的。其中最重要的一个组件是“受控旋转门” \(R_k\) ： 这个量子门和CNOT门差不多，有一个控制输入，当控制输入是 \(|0\rangle\) 的时候，输入状态原样输出；而如果控制输入是 \(|1\rangle\) ，就对输入状态绕Z轴旋转一定的角度。旋转多少角度呢？这是由门的参数k决定的，具体来说就是 \(2\pi/2^k\) 。换句话说， \(R_k\) 的作用就是当控制输入为 \(|1\rangle\) 时，给输入作这样的一个变换： \begin{bmatrix} 1 & 0 \\ 0 & e^{\frac{2\pi i}{2^k}} \end{bmatrix} 量子傅立叶变换电路 有了受控旋转门 \(R_k\) ，接下来我们就可以来搭建量子傅里叶变换电路了！ ...

随手翻到一个Simon问题，今天就来聊聊它。Simon问题和之前讨论的Deutsch问题有点类似，也是一个用量子计算机能够达到指数级加速的问题。 什么是Simon问题？ 和Deutsch问题类似，假设有人给我们一个函数f(x)，内部实现未知，只知道它输入n位二进制数，输出也是n位二进制数。用数学语言描述就是这样： \begin{matrix} f: \{ 0,1 \}^n \rightarrow \{ 0,1 \}^n \end{matrix} 然后又知道存在某个数a，使得 \(f(y)=f(x)\) 当且仅当 \(y=x \oplus a\) ，这个a也称作函数f(x)的周期。为方便讨论，假设a不是0。 Simon问题要解决的，就是求解这个周期a的值。 在经典计算机上，这是一个困难的问题。因为f(x)是未知的，我们能做的就是从0到 \(2^n-1\) 中，每次选一个数作为输入计算f(x)，直到发现重复的输出。最坏情况下，需要遍历超过一半的输入，即 \(2^{n-1}+1\) 次。根据Birthday Paradox，这个问题在经典计算机上需要的查询次数（时间复杂度）是 \(O(2^{n/2})\) 。 而在量子计算机上，我们只需要运行电路 \(O(n)\) 次就能以任意高的成功率得到结果。相对经典计算机，这是 指数级别 的加速！ Simon问题的量子算法 和之前的其他量子算法一样，首先我们得把函数f(x)包装成可逆变换 \(U_f\) ： 然后放到Simon问题的量子电路里： 接下来我们来详细分析一下这个量子算法的过程。 t0时刻 第一个寄存器经过n位的H变换，变成 \(|0\rangle\) 到 \(|2^n-1\rangle\) 的叠加态，即 \(\frac{1}{2^{n/2}}\sum_{x=0}^{2^n-1}|x\rangle\) 。 第二个寄存器状态是 \(|0\rangle\) 。 所以合起来，t0时刻的状态是 \(\frac{1}{2^{n/2}}\sum_{x=0}^{2^n-1}|x\rangle|0\rangle\) t1时刻 经过 \(U_f\) 变换，两个寄存器进入纠缠态，第一个寄存器还是 \(\frac{1}{2^{n/2}}\sum_{x=0}^{2^n-1}|x\rangle\) ，第二个寄存器变成了 \(|f(x)\rangle\) 。所以系统状态是： \(\frac{1}{2^{n/2}}\sum_{x=0}^{2^n-1}|x\rangle|f(x)\rangle\) t2时刻 对第二个寄存器进行测量，使它坍缩到某个值 \(z=f(x_0)\) 。 ...