We study interplay between magic and entanglement in quantum ?many-body systems. We show that non-local magic which is supported by ?the quantum correlations is lower bounded by the flatness of ?entanglement spectrum and upper bounded by the amount of entanglement ?in the system. We then argue that a smoothed version of non-local ?magic bounds the hardness of classical simulations for incompressible ?states. In conformal field theories, we conjecture that the non-local ?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 non-local magic vanishes if ?and only if there is no gravitational back-reaction. Furthermore, we ?show that non-local magic approximately equals the rate of change of ?minimal surface area in response to the change of the tension of ?cosmic branes in the bulk.