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.

Popular Summary

Clifford unitaries form a special, widely-used type of quantum evolution that brings many great things like good quantum error-correcting codes do the heavy work in fault-tolerant quantum computation, thanks to its capability of generating all kinds of entanglement structures. Nevertheless, it turns out that they can be efficiently simulated by classical means, meaning that they cannot supply any quantum computational advantage. “Magic states” provide a mechanism to complete the Clifford set to a universal one for quantum computation while maintaining desirable fault-tolerant properties, rendering them important “resources” for quantum computation. Here, the ensuing resource theory of magic for the first time is quantitatively studied in the regime of general-sized, entangled systems: we establish the behaviors of the maximum as well as typical amount of magic in n-qubit states under all reasonable measures of magic; we show that states with “too much” magic turn out to be essentially useless as a resource for stabilizer measurement-based quantum computation (a special type of Clifford architecture); and we study concrete state families inspired from algebra and many-body physics.

Figure 1

Two-dimensional triangulated lattices. The shaded area represents a unit cell, based on which we decompose the underlying Boolean functions of the systems and derive bounds on their nonquadracity (details in Appendix pp3).

Figure 2

Extensiveness of magic. After measuring the red vertices by Pauli observables, the system is left with decoupled $\mathit{C}\mathit{C}\mathit{Z}$ blocks (colored in blue).

Figure 3

Two-dimensional triangulated lattices. For each lattice, the shaded area is the unit cell we choose; the red vertex is the center vertex that only belongs to its cell; the yellow vertices are shared with neighboring cells. The Boolean functions are decomposed according to the cells.