We study the interplay between magic and entanglement in quantum many-body systems. We show that nonlocal magic, which is supported by the quantum correlations is lower bounded by the nonflatness of entanglement spectrum and upper bounded by the amount of entanglement in the system. We then argue that a smoothed version of nonlocal magic bounds the hardness of classical simulations for incompressible states. In conformal field theories (CFTs), we conjecture that the nonlocal magic should scale linearly with entanglement entropy but sublinearly when an approximation of the state is allowed. We support the conjectures using both analytical arguments based on unitary distillation and numerical data from an Ising CFT. If the CFT has a holographic dual, then we prove that the nonlocal magic vanishes if and only if there is no gravitational backreaction. Furthermore, we show that nonlocal magic is approximately equal to the rate of change of the minimal surface area in response to the change of cosmic brane tension in the bulk.
