Probing quantum complexity via universal saturation of stabilizer entropies

Abstract

Nonstabilizerness or `magic' is a key resource for quantum computing and a necessary condition for quantum advantage. Non-Clifford operations turn stabilizer states into resourceful states, where the amount of nonstabilizerness is quantified by resource measures such as stabilizer Rényi entropies (SREs). Here, we show that SREs saturate their maximum value at a critical number of non-Clifford operations. Close to the critical point SREs show universal behavior. Remarkably, the derivative of the SRE crosses at the same point independent of the number of qubits and can be rescaled onto a single curve. We find that the critical point depends non-trivially on Rényi index $\alpha$. For random Clifford circuits doped with T-gates, the critical T-gate density scales independently of $\alpha$. In contrast, for random Hamiltonian evolution, the critical time scales linearly with qubit number for $\alpha >1$, while is a constant for $\alpha <1$. This highlights that $\alpha$-SREs reveal fundamentally different aspects of nonstabilizerness depending on $\alpha$: $\alpha$-SREs with $\alpha <1$ relate to Clifford simulation complexity, while $\alpha >1$ probe the distance to the closest stabilizer state and approximate state certification cost via Pauli measurements. As technical contributions, we observe that the Pauli spectrum of random evolution can be approximated by two highly concentrated peaks which allows us to compute its SRE. Further, we introduce a class of random evolution that can be expressed as random Clifford circuits and rotations, where we provide its exact SRE. Our results opens up new approaches to characterize the complexity of quantum systems.

12+5 pages, 6+5 figures. Corrected typo in Eq.28

References in corpus (45)

• Scaling of Entanglement close to a Quantum Phase Transitions
• Logical quantum processor based on reconfigurable atom arrays
• The foundations of statistical mechanics from entanglement: Individual states vs. averages
• The Resource Theory of Stabilizer Computation
• Direct Fidelity Estimation from Few Pauli Measurements
• Application of a resource theory for magic states to fault-tolerant quantum computing
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Trading classical and quantum computational resources
• Stabilizer Rényi entropy
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Chaos, Complexity, and Random Matrices
• Quantifying nonstabilizerness of matrix product states
• Stabilizer entropies and nonstabilizerness monotones
• Measuring magic on a quantum processor
• Scalable measures of magic resource for quantum computers
• Conformal field theories are magical
• Many-body magic via Pauli-Markov chains -- from criticality to gauge theories
• Quantum Chaos is Quantum
• Stabilizer entropies are monotones for magic-state resource theory
• Measuring nonstabilizerness via multifractal flatness
• Phase transition in magic with random quantum circuits
• Nonstabilizerness determining the hardness of direct fidelity estimation
• Pauli Spectrum and Non-stabilizerness of Typical Quantum Many-Body States
• Simulation of Qubit Quantum Circuits via Pauli Propagation
• Efficient quantum algorithms for stabilizer entropies
• Resource theory of quantum scrambling
• Efficient unitary designs with a system-size independent number of non-Clifford gates
• Non-stabilizerness versus entanglement in matrix product states
• Complexity of frustration: a new source of non-local non-stabilizerness
• Symmetry-protected sign problem and magic in quantum phases of matter
• Learning t-doped stabilizer states
• Pseudomagic Quantum States
• Characterization of an operational quantum resource in a critical many-body system
• Quantum Computational Phase Transition in Combinatorial Problems
• Magic-induced computational separation in entanglement theory
• Bell sampling from quantum circuits
• Phase transition in Stabilizer Entropy and efficient purity estimation
• Exact solution of long-range stabilizer Rényi entropy in the dual-unitary XXZ model
• Hybrid Stabilizer Matrix Product Operator
• Pseudorandom unitaries are neither real nor sparse nor noise-robust
• Doped stabilizer states in many-body physics and where to find them
• Stability of classical shadows under gate-dependent noise
• Efficient distributed inner product estimation via Pauli sampling
• Non-Clifford Cost of Random Unitaries
• Estimating Non-Stabilizerness Dynamics Without Simulating It

Cited by in corpus (15)

• Non-Stabilizerness of Sachdev-Ye-Kitaev Model
• Stabilizer Rényi Entropy and Conformal Field Theory
• Fermionic Magic Resources of Quantum Many-Body Systems
• Efficient witnessing and testing of magic in mixed quantum states
• Disentangling magic states with classically simulable quantum circuits
• Computing quantum magic of state vectors
• Non-stabilizerness in quantum-enhanced metrological protocols
• Anticoncentration and State Design of Doped Real Clifford Circuits and Tensor Networks
• Local spreading of stabilizer Rényi entropy in a brickwork random Clifford circuit
• Stabilizer-Accelerated Quantum Many-Body Ground-State Estimation
• Rise and fall of nonstabilizerness via random measurements
• Optimal quantum reservoir learning in proximity to universality
• Spectral signatures of nonstabilizerness and criticality in infinite matrix product states
• Connecting Magic Dynamics in Thermofield Double States to Spectral Form Factors
• Quantum Complexity in Rule-Based Constrained Many-Body Models: Scars, Fragmentation, and Chaos