What's the smallest change to physics required to allow magic?

None at all. Quantum weirdness is already indistinguishable from magic.