Non-Clifford Cost of Random Unitaries

Abstract

Recent years have enjoyed a strong interest in exploring properties and applications of random quantum circuits. In this work, we explore the ensemble of $t$-doped Clifford circuits on $n$ qubits, consisting of Clifford circuits interspersed with $t$ single-qubit non-Clifford gates. We establish rigorous convergence bounds towards unitary $k$-designs, revealing the intrinsic cost in terms of non-Clifford resources in various flavors. First, we analyze the $k$-th order frame potential, which quantifies how well the ensemble of doped Clifford circuits is spread within the unitary group. We prove that a quadratic doping level, $t=\tilde{\Theta }(k^2)$, is both necessary and sufficient to approximate the frame potential of the full unitary group. As a consequence, we refine existing upper bounds on the convergence of the ensemble towards state $k$-designs. Second, we derive tight bounds on the convergence of $t$-doped Clifford circuits towards relative-error $k$-designs, showing that $t=\tilde{\Theta }(nk)$ is both necessary and sufficient for the ensemble to form a relative $\epsilon$-approximate $k$-design. Similarly, $t=\tilde{\Theta }(n)$ is required to generate pseudo-random unitaries. All these results highlight that generating random unitaries is extremely costly in terms of non-Clifford resources, and that such ensembles fundamentally lie beyond the classical simulability barrier. Additionally, we introduce doped-Clifford Weingarten functions to derive analytic expressions for the twirling operator over the ensemble of random doped Clifford circuits, and we establish their asymptotic behavior in relevant regimes.

References in corpus (71)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A bound on chaos
• Black holes as mirrors: quantum information in random subsystems
• Characterizing Quantum Supremacy in Near-Term Devices
• Fast Scramblers
• The foundations of statistical mechanics from entanglement: Individual states vs. averages
• Equilibration, thermalisation, and the emergence of statistical mechanics in closed quantum systems
• Robust randomized benchmarking of quantum processes
• Measurement-Induced Phase Transitions in the Dynamics of Entanglement
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Quantum mechanical evolution towards thermal equilibrium
• On the quantum, classical and total amount of correlations in a quantum state
• Quantum information can be negative
• Chaos and complexity by design
• Restrictions on Transversal Encoded Quantum Gate Sets
• Towards the fast scrambling conjecture
• Evenly distributed unitaries: on the structure of unitary designs
• Randomizing quantum states: Constructions and applications
• Quantum certification and benchmarking
• Random Quantum Circuits are Approximate 2-designs
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Local random quantum circuits are approximate polynomial-designs
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Quantum state merging and negative information
• Chaos, Complexity, and Random Matrices
• The mother of all protocols: Restructuring quantum information's family tree
• Random Quantum Circuits and Pseudo-Random Operators: Theory and Applications
• Multiqubit Clifford groups are unitary 3-designs
• Onset of Random Matrix Behavior in Scrambling Systems
• Randomized Benchmarking with Confidence
• Linear growth of quantum circuit complexity
• One-shot decoupling
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates
• Pseudorandom States, Non-Cloning Theorems and Quantum Money
• Optimizing quantum process tomography with unitary 2-designs
• Relating quantum privacy and quantum coherence: an operational approach
• Spectral form factors and late time quantum chaos
• Schur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations
• Quantum Chaos is Quantum
• Randomized benchmarking with gate-dependent noise
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(n{t}^{5+o(1)}\right)$
• Random bosonic states for robust quantum metrology
• Quantum commitments and signatures without one-way functions
• Solvable model of deep thermalization with distinct design times
• Decoupling with unitary approximate two-designs
• Recovering quantum gates from few average gate fidelities
• Entanglement, quantum randomness, and complexity beyond scrambling
• Mixing properties of stochastic quantum Hamiltonians
• Efficient unitary designs with a system-size independent number of non-Clifford gates
• A Maximum Entropy Principle in Deep Thermalization and in Hilbert-Space Ergodicity
• Transitions in entanglement complexity in random quantum circuits by measurements
• Learning efficient decoders for quasi-chaotic quantum scramblers
• Characterizing complexity of many-body quantum dynamics by higher-order eigenstate thermalization
• Isospectral twirling and quantum chaos
• Random Matrix Theory of the Isospectral twirling
• Relative Thermalization
• Unscrambling Quantum Information with Clifford decoders
• Learning quantum states and unitaries of bounded gate complexity
• Magic-induced computational separation in entanglement theory
• Black holes as clouded mirrors: the Hayden-Preskill protocol with symmetry
• Clifford Dressed Time-Dependent Variational Principle
• Pseudorandom unitaries are neither real nor sparse nor noise-robust
• One-shot quantum error correction of classical and quantum information
• Phase Retrieval Using Unitary 2-Designs
• Hilbert-Space Ergodicity in Driven Quantum Systems: Obstructions and Designs
• Complexity-constrained quantum thermodynamics
• Approximate Unitary $k$-Designs from Shallow, Low-Communication Circuits
• Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates
• One-Shot Triple-Resource Trade-Off in Quantum Channel Coding
• On Computational Complexity of Unitary and State Design Properties
• Random measurement bases, quantum state distinction and applications to the hidden subgroup problem

Cited by in corpus (3)

• Probing quantum complexity via universal saturation of stabilizer entropies
• Anticoncentration and State Design of Doped Real Clifford Circuits and Tensor Networks
• Anticoncentration is (almost) all you need