  The development of a framework for quantifying "non-stabiliserness" of
quantum operations is motivated by the magic state model of fault-tolerant
quantum computation, and by the need to estimate classical simulation cost for
noisy intermediate-scale quantum (NISQ) devices. The robustness of magic was
recently proposed as a well-behaved magic monotone for multi-qubit states and
quantifies the simulation overhead of circuits composed of Clifford+T gates, or
circuits using other gates from the Clifford hierarchy. Here we present a
general theory of the "non-stabiliserness" of quantum operations rather than
states, which are useful for classical simulation of more general circuits. We
introduce two magic monotones, called channel robustness and magic capacity,
which are well-defined for general n-qubit channels and treat all
stabiliser-preserving CPTP maps as free operations. We present two
complementary Monte Carlo-type classical simulation algorithms with sample
complexity given by these quantities and provide examples of channels where the
complexity of our algorithms is exponentially better than previous known
simulators. We present additional techniques that ease the difficulty of
calculating our monotones for special classes of channels.
