Many-body quantum magic

Abstract

Magic (non-stabilizerness) is a necessary but "expensive" kind of "fuel" to drive universal fault-tolerant quantum computation. To properly study and characterize the origin of quantum "complexity" in computation as well as physics, it is crucial to develop a rigorous understanding of the quantification of magic. Previous studies of magic mostly focused on small systems and largely relied on the discrete Wigner formalism (which is only well behaved in odd prime power dimensions). Here we present an initiatory study of the magic of genuinely many-body quantum states that may be strongly entangled, with focus on the important case of many qubits, at a quantitative level. We first address the basic question of how "magical" a many-body state can be, and show that the maximum magic of an $n$-qubit state is essentially $n$, simultaneously for a range of "good" magic measures. We then show that, in fact, almost all $n$-qubit pure states have magic of nearly $n$. In the quest for explicit, scalable cases of highly entangled states whose magic can be understood, we connect the magic of hypergraph states with the second-order nonlinearity of their underlying Boolean functions. Next, we go on and investigate many-body magic in practical and physical contexts. We first consider a variant of MBQC where the client is restricted to Pauli measurements, in which magic is a necessary feature of the initial "resource" state. We show that $n$-qubit states with nearly $n$ magic, or indeed almost all states, cannot supply nontrivial speedups over classical computers. We then present an example of analyzing the magic of "natural" condensed matter systems of physical interest. We apply the Boolean function techniques to derive explicit bounds on the magic of certain representative 2D SPT states, and comment on possible further connections between magic and the quantum complexity of phases of matter.

18 pages, 3 figures. Close to published version

References in corpus (14)

• Black holes as mirrors: quantum information in random subsystems
• Complexity and Shock Wave Geometries
• Restrictions on Transversal Encoded Quantum Gate Sets
• Application of a resource theory for magic states to fault-tolerant quantum computing
• Aspects of generic entanglement
• Extending Noether's theorem by quantifying the asymmetry of quantum states
• Universal resources for measurement-based quantum computation
• One-Shot Operational Quantum Resource Theory
• Conformal field theories are magical
• Fundamentals of universality in one-way quantum computation
• Diagonal gates in the Clifford hierarchy
• Symmetry-protected sign problem and magic in quantum phases of matter
• Quantum spin systems for measurement-based quantum computation
• Optimal Extensions of Resource Measures and their Applications

Cited by in corpus (24)

• Stabilizer Rényi entropy
• Quantifying nonstabilizerness of matrix product states
• Measuring magic on a quantum processor
• Scalable measures of magic resource for quantum computers
• Magic-state resource theory for the ground state of the transverse-field Ising model
• Complexity of frustration: a new source of non-local non-stabilizerness
• Symmetry-protected sign problem and magic in quantum phases of matter
• Resource theory of quantum uncomplexity
• Quantifying dynamical magic with completely stabilizer preserving operations as free
• Magic State Distillation from Entangled States
• Efficient mutual magic and magic capacity with matrix product states
• Stabilizer rank and higher-order Fourier analysis
• Entanglement of random hypergraph states
• Entanglement complexity of the Rokhsar-Kivelson-sign wavefunctions
• Magic of Random Matrix Product States
• Non-Stabilizerness of Sachdev-Ye-Kitaev Model
• The axiomatic and the operational approaches to resource theories of magic do not coincide
• Magic phase transition and non-local complexity in generalized $W$ State
• Interplay of entanglement structures and stabilizer entropy in spin models
• Symmetry-resolved entanglement of 2D symmetry-protected topological states
• Computational self-testing for entangled magic states
• Finite-Function-Encoding Quantum States
• Level-rank duality of SU(2)k Chern-Simons theory, and of hypergraph and magic states
• Hypergraph States in SU(N)1, N odd prime, Chern-Simons Theory