论文标题
更快的古典玻色子抽样
Faster classical Boson Sampling
论文作者
论文摘要
自引入以来，玻色子采样一直是量子计算领域的激烈研究的主题。任务是根据与子膜的永久物相关的概率分布，从较大$ m \ times n $复杂矩阵的可能重复行构建的所有$ n \ times n $ subsatrices独立采样。利用量子光子效应的实验系统原则上可以以极高的速度执行任务。在经典计算的框架中，Aaronson和Arkhipov（2011）表明，除非多项式层次结构倒入第三级，否则无法在多项式时间内解决精确的玻色子采样问题。实际上，多年来，最快的已知精确经典算法在$ o中运行（{m+n-1 \ select n} n 2^n）$每个样品，强调了量子计算的潜在速度优势。 Clifford和Clifford（2018）降低了优势，他们给了一个$ O（n 2^n + \ operatorname {poly}（m，n））$ time和线性空间的经典解决方案，当$ m $是$ n $ n $ n $ n $ n $ n $中时，计算单个矩阵的永久性的复杂性。 我们继续提出一种玻色子采样算法，当$ m $与$ n $成比例时，其平均案例时间复杂性要快得多。特别是，当$ m = n $时，我们的算法以$ o（n \ cdot1.69^n）$平均时间运行。该结果进一步增加了通过玻色子采样建立量子计算至上所需的问题大小。
Since its introduction Boson Sampling has been the subject of intense study in the world of quantum computing. The task is to sample independently from the set of all $n \times n$ submatrices built from possibly repeated rows of a larger $m \times n$ complex matrix according to a probability distribution related to the permanents of the submatrices. Experimental systems exploiting quantum photonic effects can in principle perform the task at great speed. In the framework of classical computing, Aaronson and Arkhipov (2011) showed that exact Boson Sampling problem cannot be solved in polynomial time unless the polynomial hierarchy collapses to the third level. Indeed for a number of years the fastest known exact classical algorithm ran in $O({m+n-1 \choose n} n 2^n )$ time per sample, emphasising the potential speed advantage of quantum computation. The advantage was reduced by Clifford and Clifford (2018) who gave a significantly faster classical solution taking $O(n 2^n + \operatorname{poly}(m,n))$ time and linear space, matching the complexity of computing the permanent of a single matrix when $m$ is polynomial in $n$. We continue by presenting an algorithm for Boson Sampling whose average-case time complexity is much faster when $m$ is proportional to $n$. In particular, when $m = n$ our algorithm runs in approximately $O(n\cdot1.69^n)$ time on average. This result further increases the problem size needed to establish quantum computational supremacy via Boson Sampling.
