高斯玻色采样enhance量子近似优化算法

上篇博文，我们已经接触了QAOA量子近似优化算法，我们已经知道近似优化算法一般用于求解组合优化问题。这里我们再说明一下什么是组合优化问题：
给定一个数据集 $X=｛{x_{1},x_{2},...x_{N}}｝$X=｛x1​,x2​,...xN​｝，和一个映射函数$ｆ$ｆ，令$y_{i}=f(x_{i})$yi​=f(xi​)，$Y=｛{y_{1},y_{2},...y_{N}}｝$Y=｛y1​,y2​,...yN​｝，目标是找到一个元素$x^{*}\in X$x∗∈X，使得$f(x^{*})>f(x),x\in X$f(x∗)>f(x),x∈X，即找到最大的一个$y$y．
这篇博文，打算就依照参考论文[1]的步骤一步步的为大家解读，如果在解读过程中有问题欢迎大家评论。希望我们都能够共同进步，努力成为一名合格的科研dog。

玻色采样

至今，提出的玻色采样装置有很多种，包括scattershot boson sampling 和 Gaussian boson sampling. 玻色采样的概念是在2014年被首次提出，其具体过程可以描述如下：

其中输入端可以是玻色子$|1_{0}\rangle...|0_{m}\rangle$∣10​⟩...∣0m​⟩，然后经过线性光学网络$U$U的作用，可以输出各种玻色配置。在光子探测器未探测光子之前，各种输出配置会处于叠加状态，其Hilbert空间可以达到$\left( \begin{array}{c} n \\ m+n-1 \\ \end{array} \right)$(nm+n−1​)大小，$m$m是模数，$n$n表示光子数。当然对于Gaussian boson sampling来说，输入端输入的不是玻色子，而是Gaussian state。
但无论是哪一种玻色采样装置，由于其具有巨大的采样空间及其输出配置的概率分布和积和式(NP-Hard问题)有关，因此在经典计算机上很难以模拟出来。所以玻色采样可能具有量子霸权的前景，但是在实际应用中似乎还没有崭露头角。
玻色采样的理念就补充到这里了，如果没有理解的伙伴，可以多多查找一些文献，比如文献[2]。

统一采样和比例采样

• 统一采样（uniform samples）
  每个值$x_{i}$xi​被采样的概率均为$1/N$1/N,即$P_{U}{(x_{i})}=1/N$PU​(xi​)=1/N.那么总目标值$Y$Y的期望值为：
  $E(Y)=\sum_{i=1}^{N}y_{i}P(y_{i})=\sum_{i=1}^{N}y_{i}*1/N=\frac{\|y\|_{1}}{N}$E(Y)=∑i=1N​yi​P(yi​)=∑i=1N​yi​∗1/N=N∥y∥1​​.

• 比例采样
  每个值$x_{i}$xi​被采样的概率和目标值$y_{i}$yi​在总目标值的概率相等，即$P(x_{i})=\frac{y_{i}}{\sum_{i=1}^{N}y_{i}}$P(xi​)=∑i=1N​yi​yi​​,所以总目标值$Y$Y的期望值为:
  $E(Y)=\sum_{i=1}^{N}y_{i}P(y_{i})=\sum_{i=1}^{N}y_{i}\frac{y_{i}}{\sum_{i=1}^{N}y_{i}}=\frac{(\|y\|_{2})^{2}}{\|y_{1}\|}$E(Y)=∑i=1N​yi​P(yi​)=∑i=1N​yi​∑i=1N​yi​yi​​=∥y1​∥(∥y∥2​)2​.
  因为：
  
  其中$p< q$p<q.所以：
  
  这个不等式说明了，比例采样永远不会比统一采样要差。而Gaussian boson sampling属于比例采样。

[1]Arrazola J M, Bromley T R, Rebentrost P. Quantum approximate optimization with Gaussian boson sampling[J]. Physical Review A, 2018, 98(1): 012322.
[2]Gard B T, Motes K R, Olson J P, et al. An introduction to boson-sampling[M]//From atomic to mesoscale: The role of quantum coherence in systems of various complexities. 2015: 167-192.