Computing quantum magic of state vectors

Abstract

Non-stabilizerness, also known as ``magic,'' quantifies how far a quantum state departs from the stabilizer set. It is a central resource behind quantum advantage and a useful probe of the complexity of quantum many-body states. Yet standard magic quantifiers, such as the stabilizer Rényi entropy (SRE) for qubits and the mana for qutrits, are costly to evaluate numerically, with the computational complexity growing rapidly with the number $N$ of qudits. Here we introduce efficient, numerically exact algorithms that exploit the fast Hadamard transform to compute the SRE for qubits ($d=2$) and the mana for qutrits ($d=3$) for pure states given as state vectors. Our methods compute SRE and mana at cost $O(N{d}^{2N})$, providing an exponential improvement over the naive $O(d^{3N})$ scaling, with substantial parallelism and straightforward GPU acceleration. We further show how to combine the fast Hadamard transform with Monte Carlo sampling to estimate the SRE of state vectors, and we extend the approach to compute the mana of mixed states. All algorithms are implemented in the open-source Julia package HadaMAG ( https://github.com/bsc-quantic/HadaMAG.jl/ ), which provides a high-performance toolbox for computing SRE and mana with built-in support for multithreading, MPI-based distributed parallelism, and GPU acceleration. The package, together with the methods developed in this work, offers a practical route to large-scale numerical studies of magic in quantum many-body systems.

25 pages, 1 figure. Comments welcome!

References in corpus (87)

• The density-matrix renormalization group in the age of matrix product states
• Efficient classical simulation of slightly entangled quantum computations
• A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Improved Simulation of Stabilizer Circuits
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Tensor networks for complex quantum systems
• Quantum Many-Body Scars and Weak Breaking of Ergodicity
• The Resource Theory of Stabilizer Computation
• Instantaneous non-local computation of low T-depth quantum circuits
• Entropy scaling and simulability by Matrix Product States
• Application of a resource theory for magic states to fault-tolerant quantum computing
• Negative Quasi-Probability as a Resource for Quantum Computation
• Hudson's Theorem for finite-dimensional quantum systems
• Classical simulation of noninteracting-fermion quantum circuits
• 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
• Avalanches and many-body resonances in many-body localized systems
• Entanglement entropy and entanglement spectrum of the Kitaev model
• Estimating outcome probabilities of quantum circuits using quasiprobabilities
• How to generate random matrices from the classical compact groups
• Lecture Notes of Tensor Network Contractions
• Information propagation in isolated quantum systems
• Polynomially filtered exact diagonalization approach to many-body localization
• Tensor Network Algorithms: a Route Map
• Many-Body Localization in the Age of Classical Computing
• 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
• Robustness of Magic and Symmetries of the Stabiliser Polytope
• Conformal field theories are magical
• Many-body magic via Pauli-Markov chains -- from criticality to gauge theories
• Stabilizer entropies are monotones for magic-state resource theory
• Logarithmic terms in entanglement entropies of 2D quantum critical points and Shannon entropies of spin chains
• Nonstabilizerness via matrix product states in the Pauli basis
• Aspects of capacity of entanglement
• Out-of-equilibrium dynamics of quantum many-body systems with long-range interactions
• Measuring nonstabilizerness via multifractal flatness
• Entanglement Spectrum and Entanglement Thermodynamics of Quantum Hall Bilayers at nu=1
• Non-negative Wigner functions in prime dimensions
• Magic spreading in random quantum circuits
• Pauli Spectrum and Non-stabilizerness of Typical Quantum Many-Body States
• Efficient quantum algorithms for stabilizer entropies
• Dynamical Magic Transitions in Monitored Clifford+T Circuits
• Emergent locality in systems with power-law interactions
• Complexity of frustration: a new source of non-local non-stabilizerness
• Stabilizer entropy dynamics after a quantum quench
• Critical behaviors of non-stabilizerness in quantum spin chains
• Entanglement-magic separation in hybrid quantum circuits
• Magic in generalized Rokhsar-Kivelson wavefunctions
• Characterization of an operational quantum resource in a critical many-body system
• Nonstabilizerness in U(1) lattice gauge theory
• Stabilizer entropy in non-integrable quantum evolutions
• Quantum Magic and Multi-Partite Entanglement in the Structure of Nuclei
• Nonstabilizerness of Permutationally Invariant Systems
• Tensorized Pauli decomposition algorithm
• Exact solution of long-range stabilizer Rényi entropy in the dual-unitary XXZ model
• Probing quantum complexity via universal saturation of stabilizer entropies
• Constraints on magic state protocols from the statistical mechanics of Wigner negativity
• Quantifying non-stabilizerness via information scrambling
• Stabilizer Entropy and entanglement complexity in the Sachdev-Ye-Kitaev model
• Handbook for Quantifying Robustness of Magic
• Mana and thermalization: probing the feasibility of near-Clifford Hamiltonian simulation
• Efficient mutual magic and magic capacity with matrix product states
• Gravitational back-reaction is magical
• Massively parallel implementation and approaches to simulate quantum dynamics using Krylov subspace techniques
• Non-stabilizerness in kinetically-constrained Rydberg atom arrays
• Lagrangian representation for fermionic linear optics
• Quantum Complexity Fluctuations from Nuclear and Hypernuclear Forces
• Independent stabilizer Rényi entropy and entanglement fluctuations in random unitary circuits
• PauliComposer: Compute Tensor Products of Pauli Matrices Efficiently
• The axiomatic and the operational approaches to resource theories of magic do not coincide
• Non-Stabilizerness of Sachdev-Ye-Kitaev Model
• Nonstabilizerness dynamics in many-body localized systems
• Quantum Complexity and Chaos in Many-Qudit Doped Clifford Circuits
• Magic transition in measurement-only circuits
• Stabilizer Rényi Entropy and Conformal Field Theory
• Nonstabilizerness of a Boundary Time Crystal
• Zero and Finite Temperature Quantum Simulations Powered by Quantum Magic
• A nonstabilizerness monotone from stabilizerness asymmetry
• Fermionic Magic Resources of Quantum Many-Body Systems
• The qudit Pauli group: non-commuting pairs, non-commuting sets, and structure theorems
• Stabilizer Rényi Entropy Encodes Fusion Rules of Topological Defects and Boundaries
• Designs from magic-augmented Clifford circuits

Cited by in corpus (2)

• Connecting Magic Dynamics in Thermofield Double States to Spectral Form Factors
• Limits of Clifford Disentangling in Tensor Network States