High-performance parallel classical scheme for simulating shallow quantum circuits

Abstract

Recently, constant-depth quantum circuits are proved more powerful than their classical counterparts at solving certain problems, e.g., the two-dimensional (2D) hidden linear function (HLF) problem regarding a symmetric binary matrix. To further investigate the boundary between classical and quantum computing models, in this work we propose a high-performance two-stage classical scheme to solve a full-sampling variant of the 2D HLF problem, which combines traditional classical parallel algorithms and a gate-based classical circuit model together for exactly simulating the target shallow quantum circuits. Under reasonable parameter assumptions, a theoretical analysis reveals our classical simulator consumes less runtime than that of near-term quantum processors for most problem instances. Furthermore, we demonstrate the typical all-connected 2D grid instances by moderate FPGA circuits, and show our designed parallel scheme is a practically scalable, high-efficient and operationally convenient tool for simulating and verifying graph-state circuits performed by current quantum hardware.

25 pages; 7 figures

References in corpus (5)

• Experimental Comparison of Two Quantum Computing Architectures
• The Communication Cost of Simulating Bell Correlations
• Fast simulation of stabilizer circuits using a graph state representation
• Quantum computing and the entanglement frontier
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model