  Completely positive and trace-preserving maps characterize physically
implementable quantum operations. On the other hand, general linear maps, such
as positive but not completely positive maps, which can not be physically
implemented, are fundamental ingredients in quantum information, both in
theoretical and practical perspectives. This raises the question of how well
one can simulate or approximate the action of a general linear map by
physically implementable operations. In this work, we introduce a systematic
framework to resolve this task using the quasiprobability decomposition
technique. We decompose a target linear map into a linear combination of
physically implementable operations and introduce the physical implementability
measure as the least amount of negative portion that the quasiprobability must
pertain, which directly quantifies the cost of simulating a given map using
physically implementable quantum operations. We show this measure is
efficiently computable by semidefinite programs and prove several properties of
this measure, such as faithfulness, additivity, and unitary invariance. We
derive lower and upper bounds in terms of the Choi operator's trace norm and
obtain analytic expressions for several linear maps of practical interests.
Furthermore, we endow this measure with an operational meaning within the
quantum error mitigation scenario: it establishes the lower bound of the
sampling cost achievable via the quasiprobability decomposition technique. In
particular, for parallel quantum noises, we show that global error mitigation
has no advantage over local error mitigation.
