Designs from magic-augmented Clifford circuits

Abstract

We introduce magic-augmented Clifford circuits -- architectures in which Clifford circuits are preceded and/or followed by constant-depth circuits of non-Clifford (``magic") gates -- as a resource-efficient way to realize approximate $k$-designs, with reduced circuit depth and usage of magic. We prove that shallow Clifford circuits, when augmented with constant-depth circuits of magic gates, can generate approximate unitary and state $k$-designs with $\epsilon$ relative error. The total circuit depth for these constructions on $N$ qubits is $O(\log (N/\epsilon ))+2^{O(k\log k)}$ in one dimension and $O(\log \log (N/\epsilon ))+2^{O(k\log k)}$ in all-to-all circuits using ancillas, which improves upon previous results for small $k\ge 4$. Furthermore, our construction of relative-error state $k$-designs only involves states with strictly local magic. The required number of magic gates is parametrically reduced when considering $k$-designs with bounded additive error. As an example, we show that shallow Clifford circuits followed by $O(k^2)$ single-qubit magic gates, independent of system size, can generate an additive-error state $k$-design. We develop a classical statistical mechanics description of our random circuit architectures, which provides a quantitative understanding of the required depth and number of magic gates for additive-error state $k$-designs. We also prove no-go theorems for various architectures to generate designs with bounded relative error.

61 pages

References in corpus (56)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Black holes as mirrors: quantum information in random subsystems
• Fast Scramblers
• Matrix Product States and Projected Entangled Pair States: Concepts, Symmetries, and Theorems
• Operator Spreading in Random Unitary Circuits
• Measurement-Induced Phase Transitions in the Dynamics of Entanglement
• Quantum Zeno Effect and the Many-body Entanglement Transition
• Chaos in quantum channels
• Quantum Entanglement Growth Under Random Unitary Dynamics
• Operator hydrodynamics, OTOCs, and entanglement growth in systems without conservation laws
• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• Theory of the phase transition in random unitary circuits with measurements
• Scalable Noise Estimation with Random Unitary Operators
• Measurement-induced criticality in random quantum circuits
• Random Quantum Circuits
• Holographic duality from random tensor networks
• Characterizing Quantum Gates via Randomized Benchmarking
• Chaos and complexity by design
• Restrictions on Transversal Encoded Quantum Gate Sets
• Evenly distributed unitaries: on the structure of unitary designs
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Local random quantum circuits are approximate polynomial-designs
• Stabilizer Rényi entropy
• Random Quantum Circuits and Pseudo-Random Operators: Theory and Applications
• Entanglement Transitions from Holographic Random Tensor Networks
• Efficient classical simulation of random shallow 2D quantum circuits
• Classification of topologically protected gates for local stabilizer codes
• The entanglement membrane in chaotic many-body systems
• Schur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations
• Hadamard-free circuits expose the structure of the Clifford group
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(n{t}^{5+o(1)}\right)$
• Efficient unitary designs with nearly time-independent Hamiltonian dynamics
• A polynomial-time classical algorithm for noisy random circuit sampling
• Entanglement Domain Walls in Monitored Quantum Circuits and the Directed Polymer in a Random Environment
• Magic spreading in random quantum circuits
• Single T gate in a Clifford circuit drives transition to universal entanglement spectrum statistics
• Mixing properties of stochastic quantum Hamiltonians
• Efficient unitary designs with a system-size independent number of non-Clifford gates
• Augmenting Density Matrix Renormalization Group with Clifford Circuits
• Learning t-doped stabilizer states
• Transitions in Entanglement Complexity in Random Circuits
• Finite-time teleportation phase transition in random quantum circuits
• Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions
• Statistical mechanics model for Clifford random tensor networks and monitored quantum circuits
• Augmenting Density Matrix Renormalization Group with Disentanglers
• Spectral Properties Versus Magic Generation in $T$-doped Random Clifford Circuits
• Efficient Unitary T-designs from Random Sums
• Efficient unitary designs and pseudorandom unitaries from permutations
• Long-range nonstabilizerness and phases of matter
• Quantum Complexity and Chaos in Many-Qudit Doped Clifford Circuits
• Approximate Unitary $k$-Designs from Shallow, Low-Communication Circuits
• Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates
• Disentangling magic states with classically simulable quantum circuits
• An Exact Link between Nonlocal Nonstabilizerness and Operator Entanglement
• Efficient approximate unitary designs from random Pauli rotations

Cited by in corpus (4)

• Computing quantum magic of state vectors
• Anticoncentration and State Design of Doped Real Clifford Circuits and Tensor Networks
• Noisy Monitored Quantum Circuits
• Adaptively secure unitary designs with constant non-Clifford cost