Classical simulability of Clifford+T circuits with Clifford-augmented matrix product states

Abstract

Determining the quantum-classical boundary between quantum circuits which can be efficiently simulated classically and those which cannot remains a fundamental question. One approach to classical simulation is to represent the output of a quantum circuit as a Clifford-augmented Matrix Product State (CAMPS) which, via a disentangling algorithm, decomposes the wave function into Clifford and MPS components and from which Pauli expectation values can be computed in time polynomial in the MPS bond-dimension. In this work, we develop an optimization-free disentangling (OFD) algorithm for Clifford circuits either doped with multi-qubit gates of the form $\alpha I+\beta P$. We give a simple algebraic criterion which characterizes the individual quantum circuits for which OFD generates an efficient CAMPS - the bond-dimension is exponential in the null space of a GF(2) matrix induced by a tableau of the twisted Pauli strings $P$. This significantly increases the number of circuits with rigorous polynomial time classical simulations. We also give evidence that the typical $N$ qubit random Clifford circuit doped with $N$ uniformly distributed $T$ gates of poly-logarithmic depth or greater has a CAMPS with polynomial bond-dimension. In addition, we compare OFD against disentangling by optimization. We further explore the representability of CAMPS for random Clifford circuits doped with more than $N$ $T$-gates. We also propose algorithms for sampling, probability and amplitude estimation of bitstrings, and evaluation of entanglement Rényi entropy from CAMPS, which, though still having exponential complexity, are more efficient than standard MPS simulations. This work establishes a versatile framework for understanding classical simulatability of Clifford+$T$ circuits and explores the interplay between quantum entanglement and quantum magic in quantum systems.

References in corpus (26)

• Efficient classical simulation of slightly entangled quantum computations
• A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
• Efficient simulation of one-dimensional quantum many-body systems
• Improved Simulation of Stabilizer Circuits
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Stim: a fast stabilizer circuit simulator
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Matchgates and classical simulation of quantum circuits
• What limits the simulation of quantum computers?
• Magic state distillation in all prime dimensions using quantum Reed-Muller codes
• Efficient classical simulation of random shallow 2D quantum circuits
• Computational advantage of quantum random sampling
• Solving the sampling problem of the Sycamore quantum circuits
• Efficient tensor network simulation of IBM's Eagle kicked Ising experiment
• Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance
• A density-matrix renormalization group algorithm for simulating quantum circuits with a finite fidelity
• Dynamical Magic Transitions in Monitored Clifford+T Circuits
• Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions
• Augmenting Density Matrix Renormalization Group with Clifford Circuits
• Fast estimation of outcome probabilities for quantum circuits
• Clifford Dressed Time-Dependent Variational Principle
• Stabilizer Tensor Networks with Magic State Injection
• Interplay of entanglement structures and stabilizer entropy in spin models
• Disentangling magic states with classically simulable quantum circuits
• Clifford-Dressed Variational Principles for Precise Loschmidt Echoes

Cited by in corpus (3)

• Anticoncentration and State Design of Doped Real Clifford Circuits and Tensor Networks
• Limits of Clifford Disentangling in Tensor Network States
• GCAMPS: A Scalable Classical Simulator for Qudit Systems