Simulation of quantum circuits by low-rank stabilizer decompositions
Simulation of quantum circuits by low-rank stabilizer decompositions
复制标题
DOI：
10.22331/q-2019-09-02-181
复制
发表时间：
2019-08-27
期刊：
影响因子：
6.4
通讯作者：
Howard, Mark
中科院分区：
文献类型：
--
作者：
Bravyi, Sergey;Browne, Dan;Howard, Mark
最近的工作探索了使用稳定器形式主义来经典地模拟包含一些非Clifford门的量子电路。这种方法的计算成本与稳定器秩的概念直接相关，对于纯状态phi，稳定器秩被定义为最小整数chi，使得phi是稳定器状态的叠加。在这里，我们开发了一个全面的数学理论的chi稳定器秩和相关的近似稳定器秩。我们还提出了一套经典的模拟算法，具有更广泛的适用性和显着提高性能比以前的国家的最先进的。一个新的功能是能够模拟电路组成的Clifford门和任意对角门，扩展了以前的算法专门的Clifford+T门集的范围。我们实现了新的模拟方法，并使用它们来模拟具有40-50个量子比特和60多个非Clifford门的量子算法，而无需求助于高性能计算机。我们报告了量子近似优化算法的模拟，其中我们处理类似于10（6）稳定器状态的chi的叠加，并从完整的n位输出分布中采样，改进了以前的模拟，该模拟使用类似于10（3）稳定器状态，仅从单量子位边缘采样。我们还模拟了隐藏移位算法的电路实例，包括多达64个T门或16个CCZ门;这些模拟展示了通过优化电路的非Clifford组件的分解而获得的性能增益。
Recent work has explored using the stabilizer formalism to classically simulate quantum circuits containing a few non-Clifford gates. The computational cost of such methods is directly related to the notion of stabilizer rank, which for a pure state phi is defined to be the smallest integer chi such that phi is a superposition of stabilizer states. Here we develop a comprehensive mathematical theory of the chi stabilizer rank and the related approximate stabilizer rank. We also present a suite of classical simulation algorithms with broader applicability and significantly improved performance over the previous state-of-the-art. A new feature is the capability to simulate circuits composed of Clifford gates and arbitrary diagonal gates, extending the reach of a previous algorithm specialized to the Clifford+T gate set. We implemented the new simulation methods and used them to simulate quantum algorithms with 40-50 qubits and over 60 non-Clifford gates, without resorting to high-performance computers. We report a simulation of the Quantum Approximate Optimization Algorithm in which we process superpositions of chi similar to 10(6) stabilizer states and sample from the full n-bit output dis- tribution, improving on previous simulations which used similar to 10(3) stabilizer states and sampled only from single-qubit marginals. We also simulated instances of the Hidden Shift algorithm with circuits including up to 64 T gates or 16 CCZ gates; these simulations showcase the performance gains available by optimizing the decomposition of a circuit's non-Clifford components.