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

• URL: http://arxiv.org/abs/2412.17209v2
• Date: Tue, 26 Aug 2025 05:12:51 GMT
• Title: Classical simulability of Clifford+T circuits with Clifford-augmented matrix product states
• Authors: Zejun Liu, Bryan K. Clark,
• Abstract summary: One approach to classical simulation is to represent the output of a quantum circuit as a Clifford-augmented Matrix Product State ( CAMPS)<n>We develop an optimization-free disentangling algorithm for Clifford circuits either doped with multi-qubit gates of the form $alpha I+beta P$.<n>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.
• Score: 0.6580655899524989
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• 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\'enyi 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.

Related papers

• Quantum Complexity and Chaos in Many-Qudit Doped Clifford Circuits [0.0]
  We investigate the emergence of quantum complexity and chaos in doped Clifford circuits acting on qudits of odd prime dimension $d$.<n>Using doped Clifford Weingarten calculus and a replica tensor network formalism, we derive exact results and perform large-scale simulations.
  arXiv  Detail & Related papers  (2025-06-02T18:01:01Z)
• Augmenting Density Matrix Renormalization Group with Matchgates and Clifford circuits [1.6249398255272316]
  We propose a new wave-function ansatz in which matrix product states are augmented with the combination of Matchgates and Clifford circuits (dubbed MCA-MPS)<n>Our benchmark results on one-dimensional hydrogen chain show that MCA-MPS can improve the accuracy of the ground-state calculation by several orders of magnitude over MPS with the same bond dimension.
  arXiv  Detail & Related papers  (2025-05-13T14:53:09Z)
• Efficient mutual magic and magic capacity with matrix product states [0.0]
  We introduce the mutual von-Neumann SRE and magic capacity, which can be efficiently computed in time. We find that mutual SRE characterizes the critical point of ground states of the transverse-field Ising model. The magic capacity characterizes transitions in the ground state of the Heisenberg and Ising model, randomness of Clifford+T circuits, and distinguishes typical and atypical states.
  arXiv  Detail & Related papers  (2025-04-09T19:12:26Z)
• Classical Simulability of Quantum Circuits with Shallow Magic Depth [12.757419723444956]
  Quantum magic is a resource that allows quantum computation to surpass classical simulation. Previous results have linked the amount of quantum magic, characterized by the number of $T$ gates or stabilizer rank, to classical simulability. In this work, we investigate the classical simulability of quantum circuits with alternating Clifford and $T$ layers.
  arXiv  Detail & Related papers  (2024-09-20T18:00:00Z)
• QuCLEAR: Clifford Extraction and Absorption for Quantum Circuit Optimization [8.043057448895343]
  Currently available quantum devices suffer from noisy quantum gates, which degrade the fidelity of executed quantum circuits.<n>We present QuCLEAR, a compilation framework designed to optimize quantum circuits.
  arXiv  Detail & Related papers  (2024-08-23T18:03:57Z)
• Quantum advantage from measurement-induced entanglement in random shallow circuits [0.18749305679160366]
  We show that long-range measurement-induced entanglement (MIE) proliferates when the circuit depth is at least a constant critical value. We introduce a two-dimensional, depth-2, "coarse-grained" circuit architecture, composed of random Clifford gates acting on O(log n) qubits.
  arXiv  Detail & Related papers  (2024-07-30T21:39:23Z)
• Pauli path simulations of noisy quantum circuits beyond average case [0.3277163122167433]
  For random quantum circuits on $n$ qubits of depth, the task of sampling from the output state can be efficiently performed classically using a Pauli path method. We derive sufficient conditions for simulatability in terms of noise rate and the fraction of gates that are T gates, and show that if noise is introduced at a faster rate, the simulation becomes classically easy.
  arXiv  Detail & Related papers  (2024-07-22T21:58:37Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer. Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model. We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• Sachdev-Ye-Kitaev model on a noisy quantum computer [1.0377683220196874]
  We study the SYK model -- an important toy model for quantum gravity on IBM's superconducting qubit quantum computers. We compute return probability after time $t$ and out-of-time order correlators (OTOC) which is a standard observable of quantifying the chaotic nature of quantum systems.
  arXiv  Detail & Related papers  (2023-11-29T19:00:00Z)
• Simulation of IBM's kicked Ising experiment with Projected Entangled Pair Operator [71.10376783074766]
  We perform classical simulations of the 127-qubit kicked Ising model, which was recently emulated using a quantum circuit with error mitigation. Our approach is based on the projected entangled pair operator (PEPO) in the Heisenberg picture. We develop a Clifford expansion theory to compute exact expectation values and use them to evaluate algorithms.
  arXiv  Detail & Related papers  (2023-08-06T10:24:23Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• Quantum circuit compilation and hybrid computation using Pauli-based computation [0.0]
  Pauli-based computation (PBC) is driven by a sequence of adaptively chosen, non-destructive measurements of Pauli observables. We propose practical ways of implementing PBC as adaptive quantum circuits and provide code to do the required classical side-processing.
  arXiv  Detail & Related papers  (2022-03-03T16:01:55Z)
• An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation [55.41644538483948]
  Current generation noisy intermediate-scale quantum (NISQ) computers are severely limited in chip size and error rates. We derive localized circuit transformations to efficiently compress quantum circuits for simulation of certain spin Hamiltonians known as free fermions. The proposed numerical circuit compression algorithm behaves backward stable and scales cubically in the number of spins enabling circuit synthesis beyond $mathcalO(103)$ spins.
  arXiv  Detail & Related papers  (2021-08-06T19:38:03Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations. We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
  arXiv  Detail & Related papers  (2021-03-12T20:58:41Z)
• Quadratic Clifford expansion for efficient benchmarking and initialization of variational quantum algorithms [0.8808007156832224]
  Variational quantum algorithms are considered to be appealing applications of near-term quantum computers. We propose a perturbative approach for efficient benchmarking of variational quantum algorithms.
  arXiv  Detail & Related papers  (2020-11-19T16:09:00Z)
• Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
  Random quantum circuits are commonly viewed as hard to simulate classically. We show that approximate simulation of typical instances is almost as hard as exact simulation. We also conjecture that sufficiently shallow random circuits are efficiently simulable more generally.
  arXiv  Detail & Related papers  (2019-12-31T19:00:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.