  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.
