Simulating quantum computers with probabilistic methods
Simulating quantum computers with probabilistic methods
复制标题
用概率方法模拟量子计算机
DOI：
10.26421/qic11.9-10-5
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
M. Nest
中科院分区：
文献类型：
--
作者：
M. Nest
我们研究经典和量子计算能力之间的边界。这项工作包括两个部分。首先，我们开发新的经典的模拟算法，以采样方法为中心。使用这些技术，我们生成新的类的经典可模拟的量子电路，依赖于测量概率的精确计算的标准技术无法提供有效的模拟。例如，我们展示了如何将匹配门、Toffoli、Clifford、有界深度、傅立叶变换和其他电路串联起来，这些电路都是经典的可模拟电路。我们还证明了稀疏量子电路以及由CNOT和exp[i θ;X]门组成的电路可以经典地模拟。在第二部分中，我们将我们的结果应用于量子算法的模拟。结果表明，最近一种涉及波茨模型配分函数估计的量子算法可以有效地进行经典模拟。最后，我们表明，西蒙和肖尔的算法的指数加速至关重要地取决于在这些算法的最后一个阶段，处理经典的测量结果的后处理。具体来说，我们证明了这两种算法将是经典的模拟，如果在这一步中经典计算的功能有一个充分峰值的傅立叶频谱。
We investigate the boundary between classical and quantum computational power. This work consists of two parts. First we develop new classical simulation algorithms that are centered on sampling methods. Using these techniques we generate new classes of classically simulatable quantum circuits where standard techniques relying on the exact computation of measurement probabilities fail to provide efficient simulations. For example, we show how various concatenations of matchgate, Toffoli, Clifford, bounded-depth, Fourier transform and other circuits are classically simulatable. We also prove that sparse quantum circuits as well as circuits composed of CNOT and exp[itheta;X] gates can be simulated classically. In a second part, we apply our results to the simulation of quantum algorithms. It is shown that a recent quantum algorithm, concerned with the estimation of Potts model partition functions, can be simulated efficiently classically. Finally, we show that the exponential speed-ups of Simon's and Shor's algorithms crucially depend on the very last stage in these algorithms, dealing with the classical postprocessing of the measurement outcomes. Specifically, we prove that both algorithms would be classically simulatable if the function classically computed in this step had a sufficiently peaked Fourier spectrum.