Many-Body Quantum Magic

Magic (nonstabilizerness) 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. As a corollary, the resource theory of magic has asymptotic golden currency states. 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 measurement-based quantum computation 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 two-dimensional symmetry-protected topological states, and comment on possible further connections between magic and the quantum complexity of phases of matter.

Automated summary

Understanding and studying the magic in quantum computation and physics is essential to comprehend quantum complexity. This study examines the magic in strongly entangled many-body quantum states, particularly in systems with multiple qubits. The research finds that the maximum magic of an n-qubit state is closely related to the number of qubits, and nearly all pure n-qubit states have magic values close to n. The analysis also connects the magic of hypergraph states with the nonlinearity of Boolean functions and applies the concept of magic to measurement-based quantum computation and condensed matter systems.