In studying the resources necessary to achieve a quantum speedup it is useful to distinguish between operations that are (a) free, or (b) costly. The fact that stabilizer circuits can be efficiently classically simulated suggests that stabilizer operations be designated as free. This begs the question of whether it is possible to augment the free stabilizer operations with an additional costly resource (to be consumed) which promotes stabilizer circuits to quantum universality. Bravyi and Kitaev (arXiv:quant-ph/0403025) demonstrate that there are certain quantum states (deemed “magic”) which achieve precisely this. They also detail a protocol for distilling such magic states from a collection of noisy ancilla states.

References: arXiv:quant-ph/040302