  The Eastin-Knill theorem states that no quantum error correcting code can
have a universal set of transversal gates. For self-dual CSS codes that can
implement Clifford gates transversally it suffices to provide one additional
non-Clifford gate, such as the $T$-gate, to achieve universality. Common
methods to implement fault-tolerant $T$-gates like magic state distillation
generate a significant hardware overhead that will likely prevent their
practical usage in the near-term future. Recently methods have been developed
to mitigate the effect of noise in shallow quantum circuits that are not
protected by error correction. Error mitigation methods require no additional
hardware resources but suffer from a bad asymptotic scaling and apply only to a
restricted class of quantum algorithms. In this work, we combine both
approaches and show how to implement encoded Clifford+$T$ circuits where
Clifford gates are protected from noise by error correction while errors
introduced by noisy encoded $T$-gates are mitigated using the quasi-probability
method. As a result, Clifford+$T$ circuits with a number of $T$-gates inversely
proportional to the physical noise rate can be implemented on small
error-corrected devices without magic state distillation. We argue that such
circuits can be out of reach for state-of-the-art classical simulation
algorithms.
