Simulation of low-depth quantum circuits as complex undirected graphical models

Abstract

Near term quantum computers with a high quantity (around 50) and quality (around 0.995 fidelity for two-qubit gates) of qubits will approximately sample from certain probability distributions beyond the capabilities of known classical algorithms on state-of-the-art computers, achieving the first milestone of so-called quantum supremacy. This has stimulated recent progress in classical algorithms to simulate quantum circuits. Classical simulations are also necessary to approximate the fidelity of multiqubit quantum computers using cross entropy benchmarking. Here we present numerical results of a classical simulation algorithm to sample universal random circuits, on a single workstation, with more qubits and depth than previously reported. For example, circuits with $5\times 9$ qubits of depth 37, $7\times 8$ qubits of depth 27, and $10\times (\kappa >10)$) qubits of depth 19 are all easy to sample. We also show up to what depth the sampling, or estimation of observables, is trivially parallelizable. The algorithm is related to the "Feynmann path" method to simulate quantum circuits. For low-depth circuits, the algorithm scales exponentially in the depth times the smaller lateral dimension, or the treewidth, as explained in Boixo et. al., and therefore confirms the bounds in that paper. In particular, circuits with $7\times 7$ qubits and depth 40 remain currently out of reach. Follow up work on a supercomputer environment will tighten this bound.

12 pages, 6 figures. Added plot with simulations of a circuit of 7x8 qubits and depth 30, and appendices with pseudo-code and review of cross entropy benchmarking

Cited by in corpus (49)

• Validating quantum computers using randomized model circuits
• Qulacs: a fast and versatile quantum circuit simulator for research purpose
• Information Scrambling in Computationally Complex Quantum Circuits
• Simulating Large Quantum Circuits on a Small Quantum Computer
• A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware
• Quantum advantage with noisy shallow circuits in 3D
• 64-Qubit Quantum Circuit Simulation
• Full-State Quantum Circuit Simulation by Using Data Compression
• Qibo: a framework for quantum simulation with hardware acceleration
• Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits
• Massively parallel quantum computer simulator, eleven years later
• Closing the "Quantum Supremacy" Gap: Achieving Real-Time Simulation of a Random Quantum Circuit Using a New Sunway Supercomputer
• General-purpose quantum circuit simulator with Projected Entangled-Pair States and the quantum supremacy frontier
• Contracting Arbitrary Tensor Networks: General Approximate Algorithm and Applications in Graphical Models and Quantum Circuit Simulations
• Tropical Tensor Network for Ground States of Spin Glasses
• Boundaries of quantum supremacy via random circuit sampling
• qTorch: The Quantum Tensor Contraction Handler
• Quantum Supremacy Is Both Closer and Farther than It Appears
• Jet: Fast quantum circuit simulations with parallel task-based tensor-network contraction
• Effective quantum volume, fidelity and computational cost of noisy quantum processing experiments
• Simulating the Sycamore quantum supremacy circuits
• Neural-network states for the classical simulation of quantum computing
• GPU-accelerated simulations of quantum annealing and the quantum approximate optimization algorithm
• Pareto-Efficient Quantum Circuit Simulation Using Tensor Contraction Deferral
• Quantum Teleportation-Inspired Algorithm for Sampling Large Random Quantum Circuits
• An adaptive algorithm for quantum circuit simulation
• The Fermionic Quantum Emulator
• Performance Evaluation and Acceleration of the QTensor Quantum Circuit Simulator on GPUs
• Simulating Quantum Computers Using OpenCL
• Alibaba Cloud Quantum Development Platform: Applications to Quantum Algorithm Design
• Simulation Paths for Quantum Circuit Simulation with Decision Diagrams
• Approximate stabilizer rank and improved weak simulation of Clifford-dominated circuits for qudits
• Embedding Learning in Hybrid Quantum-Classical Neural Networks
• A quantum circuit simulator and its applications on Sunway TaihuLight supercomputer
• Lifetime-based Optimization for Simulating Quantum Circuits on a New Sunway Supercomputer
• Hückel Molecular Orbital Theory on a Quantum Computer: A Scalable System-Agnostic Variational Implementation with Compact Encoding
• Explicit lower bounds on strong quantum simulation
• Memory-Efficient Quantum Circuit Simulation by Using Lossy Data Compression
• Entanglement Scaling in Quantum Advantage Benchmarks
• Fast simulation of planar Clifford circuits
• Feynman-path type simulation using stabilizer projector decomposition of unitaries
• Amplitude-Aware Lossy Compression for Quantum Circuit Simulation
• Supercomputer simulations of transmon quantum computers
• Importance of Diagonal Gates in Tensor Network Simulations
• Efficient approximation of experimental Gaussian boson sampling
• Speedup in Classical Simulation of Gaussian Boson Sampling
• Logical Abstractions for Noisy Variational Quantum Algorithm Simulation
• Benchmarking Supercomputers with the Jülich Universal Quantum Computer Simulator
• Graph Convolutional Policy for Solving Tree Decomposition via Reinforcement Learning Heuristics