High-performance parallel classical scheme for simulating shallow quantum circuits
arXiv:2103.00693
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.
arXiv comment25 pages; 7 figures
References in corpus (27)
- A Quantum Engineer's Guide to Superconducting Qubits
- Improved Simulation of Stabilizer Circuits
- Characterizing Quantum Supremacy in Near-Term Devices
- Quantum Computational Supremacy
- Generation and manipulation of Schrödinger cat states in Rydberg atom arrays
- Non-locality and Communication Complexity
- Experimental Comparison of Two Quantum Computing Architectures
- ProjectQ: An Open Source Software Framework for Quantum Computing
- Quantum advantage with shallow circuits
- Observation of multi-component atomic Schrödinger cat states of up to 20 qubits
- The Communication Cost of Simulating Bell Correlations
- Average-case complexity versus approximate simulation of commuting quantum computations
- Genuine 12-qubit entanglement on a superconducting quantum processor
- Quantum Sampling Problems, BosonSampling and Quantum Supremacy
- Popescu-Rohrlich correlations as a unit of nonlocality
- No imminent quantum supremacy by boson sampling
- Fast simulation of stabilizer circuits using a graph state representation
- A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware
- Quantum computing and the entanglement frontier
- Verifying Multipartite Entangled GHZ States via Multiple Quantum Coherences
- 64-Qubit Quantum Circuit Simulation
- Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
- Simulating quantum correlations as a distributed sampling problem
- Measurement of the entanglement spectrum of a symmetry-protected topological state using the IBM quantum computer
- Quantum Teleportation-Inspired Algorithm for Sampling Large Random Quantum Circuits
- Fast simulation of planar Clifford circuits
- Graph reductions, binary rank, and pivots in gene assembly