Clifford recompilation for faster classical simulation of quantum circuits

Abstract

Simulating quantum circuits classically is an important area of research in quantum information, with applications in computational complexity and validation of quantum devices. One of the state-of-the-art simulators, that of Bravyi et al, utilizes a randomized sparsification technique to approximate the output state of a quantum circuit by a stabilizer sum with a reduced number of terms. In this paper, we describe an improved Monte Carlo algorithm for performing randomized sparsification. This algorithm reduces the runtime of computing the approximate state by the factor $\ell /m$, where $\ell$ and $m$ are respectively the total and non-Clifford gate counts. The main technique is a circuit recompilation routine based on manipulating exponentiated Pauli operators. The recompilation routine also facilitates numerical search for Clifford decompositions of products of gates, which can further reduce the runtime in certain cases. It may additionally lead to a framework for optimizing circuit implementations over a gate set, reducing the overhead for state-injection in fault-tolerant implementations. We provide a concise exposition of randomized sparsification, and describe how to use it to estimate circuit amplitudes in a way which can be generalized to a broader class of gates and states. This latter method can be used to obtain additive error estimates of circuit probabilities with a faster runtime than the full techniques of Bravyi et al. Such estimates are useful for validating near-term quantum devices provided that the target probability is not exponentially small.

References in corpus (15)

• Quantum Computing in the NISQ era and beyond
• Surface codes: Towards practical large-scale quantum computation
• Quantum Computational Supremacy
• A blueprint for demonstrating quantum supremacy with superconducting qubits
• Application of a resource theory for magic states to fault-tolerant quantum computing
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Classical simulation of noninteracting-fermion quantum circuits
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Trading classical and quantum computational resources
• Simulation of quantum circuits by low-rank stabilizer decompositions
• 64-Qubit Quantum Circuit Simulation
• Massively parallel quantum computer simulator, eleven years later
• Robustness of Magic and Symmetries of the Stabiliser Polytope
• Quantum interference as a resource for quantum speedup
• Unbiased Simulation of Near-Clifford Quantum Circuits

Cited by in corpus (9)

• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance
• Fast estimation of outcome probabilities for quantum circuits
• Quantifying dynamical magic with completely stabilizer preserving operations as free
• Quantum circuit compilation and hybrid computation using Pauli-based computation
• Faster Born probability estimation via gate merging and frame optimisation
• Automatic Test Pattern Generation for Robust Quantum Circuit Testing
• Logical Error Rates for the Surface Code Under a Mixed Coherent and Stochastic Circuit-Level Noise Model Inspired by Trapped Ions
• Symmetry-Accelerated Classical Simulation of Clifford-Dominated Circuits