论文标题
经典模拟量子至上IQP电路通过随机图方法
Classically Simulating Quantum Supremacy IQP Circuits through a Random Graph Approach
论文作者
论文摘要
量子至高无上是通过量子计算机在合理时间内由最佳的古典计算机执行的量子计算机的计算。在近期量子计算机上证明这一点的一种精心研究的方法是使用随机电路采样。已经提出，用随机电路采样来证明量子至上的良好候选者是使用\ emph {iqp电路}。这些是量子电路，其中统一的IT具有对角线。在本文中，我们介绍了改进的技术，用于经典模拟随机IQP电路。我们找到了一种简单的算法来计算$ n $ qubit IQP电路的振幅，并在时间$ o（\ frac {\ frac {\ log^2 n} {n} {n} 2^n）$中具有密集的随机两量相互作用$ O（2^n/\ text {poly}（n））$对于任何给定的多项式。使用更复杂的稳定器分解方法，我们将密集电路的算法改进到$ o \ left（\ frac {（\ log n）^{4-β}}} {n^{2-β}}}}}}} 2^n \ right）$ lese $β\ lith $β\ lote of约0.396 $。我们对算法进行了基准测试，发现我们可以在笔记本电脑的几分钟内模拟多达50 Qubit的电路。我们估计一个大型计算集群即可到达70个Qubit的电路。
Quantum Supremacy is a demonstration of a computation by a quantum computer that can not be performed by the best classical computer in a reasonable time. A well-studied approach to demonstrating this on near-term quantum computers is to use random circuit sampling. It has been suggested that a good candidate for demonstrating quantum supremacy with random circuit sampling is to use \emph{IQP circuits}. These are quantum circuits where the unitary it implements is diagonal. In this paper we introduce improved techniques for classically simulating random IQP circuits. We find a simple algorithm to calculate an amplitude of an $n$-qubit IQP circuit with dense random two-qubit interactions in time $O(\frac{\log^2 n}{n} 2^n )$, which for sparse circuits (where each qubit interacts with $O(\log n)$ other qubits) runs in $o(2^n/\text{poly}(n))$ for any given polynomial. Using a more complicated stabiliser decomposition approach we improve the algorithm for dense circuits to $O\left(\frac{(\log n)^{4-β}}{n^{2-β}} 2^n \right)$ where $β\approx 0.396$. We benchmarked our algorithm and found that we can simulate up to 50-qubit circuits in a couple of minutes on a laptop. We estimate that 70-qubit circuits are within reach for a large computing cluster.
