Efficient quantum algorithms for stabilizer entropies

Abstract

Stabilizer entropies (SEs) are measures of nonstabilizerness or `magic' that quantify the degree to which a state is described by stabilizers. SEs are especially interesting due to their connections to scrambling, localization and property testing. However, applications have been limited so far as previously known measurement protocols for SEs scale exponentially with the number of qubits. Here, we efficiently measure SEs for integer Rényi index $n>1$ via Bell measurements. The SE of $N$-qubit quantum states can be measured with $O(n)$ copies and $O(nN)$ classical computational time, where for even $n$ we additionally require the complex conjugate of the state. We provide efficient bounds of various nonstabilizerness monotones which are intractable to compute beyond a few qubits. Using the IonQ quantum computer, we measure SEs of random Clifford circuits doped with non-Clifford gates and give bounds for the stabilizer fidelity, stabilizer extent and robustness of magic. We provide efficient algorithms to measure Clifford-averaged $4n$-point out-of-time-order correlators and multifractal flatness. With these measures we study the scrambling time of doped Clifford circuits and random Hamiltonian evolution depending on nonstabilizerness. Counter-intuitively, random Hamiltonian evolution becomes less scrambled at long times which we reveal with the multifractal flatness. Our results open up the exploration of nonstabilizerness with quantum computers.

26 pages, 14 figures

References in corpus (51)

• Fault-tolerant quantum computation by anyons
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum Circuit Learning
• Improved Simulation of Stabilizer Circuits
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Quantum Resource Theories
• Measuring entanglement entropy through the interference of quantum many-body twins
• Logical quantum processor based on reconfigurable atom arrays
• Many body localization in Heisenberg XXZ magnet in a random field
• Measuring out-of-time-order correlations and multiple quantum spectra in a trapped ion quantum magnet
• Roads towards fault-tolerant universal quantum computation
• Quantum advantage in learning from experiments
• The Resource Theory of Stabilizer Computation
• Chaos and complexity by design
• Application of a resource theory for magic states to fault-tolerant quantum computing
• Measuring out-of-time-order correlators on a nuclear magnetic resonance quantum simulator
• Quantum-assisted quantum compiling
• Local random quantum circuits are approximate polynomial-designs
• Information Scrambling in Computationally Complex Quantum Circuits
• Stabilizer Rényi entropy
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Chaos, Complexity, and Random Matrices
• Shannon and entanglement entropies of one- and two-dimensional critical wave functions
• The SWAP test and the Hong-Ou-Mandel effect are equivalent
• Universal behavior beyond multifractality of wave-functions at measurement--induced phase transitions
• Quantifying the magic of quantum channels
• Quantifying nonstabilizerness of matrix product states
• Stabilizer entropies and nonstabilizerness monotones
• Scalable measures of magic resource for quantum computers
• Measuring magic on a quantum processor
• Schur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations
• Scrambling Dynamics and Out-of-Time Ordered Correlators in Quantum Many-Body Systems: a Tutorial
• Quantum Chaos is Quantum
• Magic-state resource theory for the ground state of the transverse-field Ising model
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(n{t}^{5+o(1)}\right)$
• Catalysis and activation of magic states in fault tolerant architectures
• Scrambling is Necessary but Not Sufficient for Chaos
• Measuring nonstabilizerness via multifractal flatness
• Nonstabilizerness determining the hardness of direct fidelity estimation
• Resource theory of quantum scrambling
• Quantum scrambling with classical shadows
• Complexity of frustration: a new source of non-local non-stabilizerness
• Lower bound for the T count via unitary stabilizer nullity
• Learning quantum circuits of some $T$ gates
• Isospectral twirling and quantum chaos
• Phase transition in Stabilizer Entropy and efficient purity estimation
• Certifying quantumness: Benchmarks for the optimal processing of generalized coherent and squeezed states
• Complex conjugation supermap of unitary quantum maps and its universal implementation protocol
• Measuring out-of-time-ordered correlation functions without reversing time evolution
• Entanglement complexity of the Rokhsar-Kivelson-sign wavefunctions
• Magic of Random Matrix Product States

Cited by in corpus (46)

• Stabilizer entropies are monotones for magic-state resource theory
• Pauli Spectrum and Non-stabilizerness of Typical Quantum Many-Body States
• Nonstabilizerness in U(1) lattice gauge theory
• Magic Resources of the Heisenberg Picture
• Hilbert space delocalization under random unitary circuits
• Probing quantum complexity via universal saturation of stabilizer entropies
• Efficient mutual magic and magic capacity with matrix product states
• Handbook for Quantifying Robustness of Magic
• Pseudorandom unitaries are neither real nor sparse nor noise-robust
• Stabilizer Entropy and entanglement complexity in the Sachdev-Ye-Kitaev model
• Quantum Non-Local Nonstabilizerness
• Gravitational back-reaction is magical
• Independent stabilizer Rényi entropy and entanglement fluctuations in random unitary circuits
• Spectral Properties Versus Magic Generation in $T$-doped Random Clifford Circuits
• Bridging magic and non-Gaussian resources via Gottesman-Kitaev-Preskill encoding
• Pseudorandom density matrices
• Quantum Algorithms for Inverse Participation Ratio Estimation in multi-qubit and multi-qudit systems
• Stabilizer Rényi Entropy and Conformal Field Theory
• Extracting randomness from magic quantum states
• A nonstabilizerness monotone from stabilizerness asymmetry
• Fermionic Magic Resources of Quantum Many-Body Systems
• Efficient distributed inner product estimation via Pauli sampling
• Efficient witnessing and testing of magic in mixed quantum states
• Disentangling magic states with classically simulable quantum circuits
• Operational interpretation of the Stabilizer Entropy
• Maximal Magic for Two-qubit States
• Computing quantum magic of state vectors
• Non-stabilizerness of Neural Quantum States
• Anticoncentration and State Design of Doped Real Clifford Circuits and Tensor Networks
• Non-stabilizerness in quantum-enhanced metrological protocols
• Prepare-and-Magic: Semi-Device Independent Magic Certification in the Prepare-and-Measure Scenario
• Certifying nonstabilizerness in quantum processors
• Faster computation of nonstabilizerness
• A trace distance-based geometric analysis of the stabilizer polytope for few-qubit systems
• Single-copy stabilizer testing
• Rise and fall of nonstabilizerness via random measurements
• Robustness of Magic in the quantum Ising chain via Quantum Monte Carlo tomography
• Experimental measurement and a physical interpretation of quantum shadow enumerators
• On the Hardness of Measuring Magic
• Quantum Magic in Discrete-Time Quantum Walk
• Virtual Quantum Markov Chains
• Shallow quantum circuit for generating extremely low-entangled approximate state designs
• Van Hove singularities in stabilizer entropy densities
• Bell sampling in Quantum Monte Carlo simulations
• Equivalence of Stabilizer and Shannon Rényi Entropies: Exact Results for Quantum Critical Chains
• An Algorithm for Estimating $\alpha$-Stabilizer Rényi Entropies via Purity