Gravitational back-reaction is the Holographic Dual of Magic

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.