We study the physical quantum resources required to implement general quantum operations, and provide bounds on the minimum possible size which an environment must be in order to perform certain quantum operations. We prove that contrary to a previous conjecture, not all quantum operations on a single qubit can be implemented with a single-qubit environment, even if that environment is initially prepared in a mixed state. We show that a mixed single-qutrit environment is sufficient to implement a special class of operations, the generalized depolarizing channels.