前置知识

Quantum Fourier Transformation; Grover Search; Phase estimation。

总述

量子算法解决了这样一个问题，就是在某个数域当中，给出某个函数 $f(x) = 0$ 解的数量。

所谓的计数就是“统计这个解的数量”。

参考资料是 Nielsen 的 QCQI。（其实就是把他书上的内容翻译了一下）

动机

Quantum Counting Algorithm 的提出是与 Grover Search 一脉相承的。因为在实现Grover算法的时候，那个Grover 迭代子 的迭代次数是与那个搜索函数 f 解的数量M有关的。

那么对于一个搜索问题，如果一开始我们不知道符合搜索条件的结果的数量M，或者说不知道搜索函数 f 解的数量，那么我们就没法很好地实现Grover算法。（对这部分有问题可能需要去看一看Grover算法，尤其是那个 Grover Iteration 的迭代次数。如果不想回去看Grover算法，只需要知道这个算法的实现与搜索函数的解有关就行了。）

为了知道有多少个解，经典算法需要的复杂度是O(N)，而量子算法的复杂度是 O(\sqrt N) 。也就是说，如果为了使用Grover算法，我们还要先使用经典计数方法获得M，那么其实我们还是需要O(N)的复杂度去做一次搜索。这就不太好。

所以我们想设计一个量子算法，使得对M的计数过程也可以降到 O(\sqrt{N}) ，这样就大大提高了Grover算法的能力。而这个算法就是 Quantum Counting。

细节

Set-up

令G为Grover 迭代子

G = (2|\psi\rangle\langle\psi|-I)O

其中 |\psi\rangle = H^{\otimes n}|0\rangle^{\otimes n} , I 为单位矩阵，O为查找的oracle。O实现了这样的一个功能，如果x是想要的搜索结果，那么 O|x\rangle = -|x\rangle , 如果x不是我们想要的结果，那么 O|x\rangle = |x\rangle 。我们令 \sum ' 对所有的搜索结果求和， \sum'' 对所有的非搜索结果求和。构造

\begin{align} |\alpha\rangle &= \frac{1}{\sqrt{2N-M}}\sum''|x\rangle\ \\|\beta\rangle &= \frac{1}{\sqrt{M}}\sum'|x\rangle \end{align}

那如果对 |\alpha\rangle 进行测量，那其中的态都不是搜索的结果。而对 |\beta\rangle 测量，其中的态都是搜索的结果。我们想要的就是这个 β 。我们把上述这两个向量当成基，对 |\psi\rangle 进行展开

\begin{align} |\psi\rangle &= \frac{\sqrt{2N-M}}{\sqrt{2N}}|\alpha\rangle+\frac{\sqrt{M}}{\sqrt{2N}} |\beta\rangle\ \\:&=\cos\frac\theta2|\alpha\rangle+\sin\frac\theta2|\beta\rangle \end{align}............ (1)

那么我们可以计算出来，G的功能相当于在空间里做一定的旋转（你可以算一算check一下） G = \begin{bmatrix} \cos\theta & -\sin\theta\\\ \sin\theta & \cos \theta \end{bmatrix}................ (2)

其实Grover算法就是把 |\psi\rangle 转到 |\beta\rangle 那个地方。只要转到 |\beta\rangle 附近，那么对这个态测一下不就大概率都是搜索的解了吗！G作用一次就转 θ 角，那就多转几次就可以转到 β 那边了，那就实现了搜索了嘛。

OK，那么（1）式中我们其实定义了什么是 θ 。

\sin^2\frac\theta 2 =\frac M {2N}~~~~........(3)

而（2）式中我们令 G 的两个eigenvectors 为 |a\rangle ~~ and ~~~ | b\rangle ，可以计算出它们的 eigenvalues 为 e^{i\theta} 和 e^{i(2\pi-\theta)} . 那结合式(3)来看，我们就知道，如果我们得到了 θ ，那其实就可以估计那个M了。

那如何获得这个 θ 呢？其实看到这个特征值的时候大家也能够想到了，就是使用相位估计 Phase Estimation.

Get M

众所周知，旋转矩阵的 eigenvectors 为

|a\rangle = \frac 1 {\sqrt{2}} (-i|\alpha\rangle+|\beta\rangle)~~;~~|b\rangle = \frac 1 {\sqrt{2}}(i|\alpha\rangle+|\beta\rangle)

那么我们可以得到

\begin{align} |\psi\rangle &=\cos(\theta/2)|\alpha\rangle+\sin(\theta/2)|\beta\rangle\\ &= \cos(\theta/2)\frac 1 {i\sqrt{2}}(|b\rangle-|a\rangle) + \sin(\theta/2)\frac 1 {\sqrt{2}}(|b\rangle+|a\rangle)\\ &= \frac 1 {i\sqrt{2}}\left[e^{i\theta/2}|b\rangle-e^{-i\theta/2}|a\rangle\right] \end{align}

那么如果我们施加

G^x \frac 1 {i\sqrt{2}}\left[e^{i\theta/2}|b\rangle-e^{-i\theta/2}|a\rangle\right] = \frac 1 {i\sqrt{2}}\left[e^{i\theta(1/2+x)}|b\rangle-e^{-i\theta(1/2+x)\theta}|a\rangle\right]

那么下面这样一个量子线路，就能够完成对θ的相位估计

I^{\otimes t}\otimes \prod G^{2^i}\sum_x|x\rangle|\psi\rangle = e^{i\theta/2}\sum e^{i\theta x}|x\rangle|b\rangle + e^{-i\theta/2}\sum e^{-i\theta x}|x\rangle|a\rangle

所以相位估计的结果要么是 θ 要么是 2\pi-\theta 。但是都无所谓，因为我们知道θ一般比较小，所以如果它是后者，我们其实是可以看得出来的。那么，由此我们就得到了θ的估计，然后由式（3）就可以得到M了。

至此，我们就完成了Quantum Counting，得到了函数解的个数。

后记

这里应该讨论一下这个算法的误差，但是我很懒，就不讨论了。作为学习者而言，我是不太care这玩意儿的准确率到底能到多少，反正挺高的。

它的准确度其实就是由 Phase Estimation 的准确度导出来的，差不多就是这样。