  The overhead cost of performing universal fault-tolerant quantum computation
for large scale quantum algorithms is very high. Despite several attempts at
alternative schemes, magic state distillation remains one of the most efficient
schemes for simulating non-Clifford gates in a fault-tolerant way. However,
since magic state distillation circuits are not fault-tolerant, all Clifford
operations must be encoded in a large distance code in order to have comparable
failure rates with the magic states being distilled. In this work, we introduce
a new concept which we call redundant ancilla encoding. The latter combined
with flag qubits allows for circuits to both measure stabilizer generators of
some code, while also being able to measure global operators to
fault-tolerantly prepare magic states, all using nearest neighbor interactions.
In particular, we apply such schemes to a planar architecture of the triangular
color code family. In addition to our scheme being suitable for experimental
implementations, we show that for physical error rates near $10^{-4}$ and under
a full circuit-level noise model, our scheme can produce magic states using an
order of magnitude fewer qubits and space-time overhead compared to the most
competitive magic state distillation schemes. Further, we can take advantage of
the fault-tolerance of our circuits to produce magic states with very low
logical failure rates using encoded Clifford gates with noise rates comparable
to the magic states being injected. Thus, stabilizer operations are not
required to be encoded in a very large distance code. Consequently, we believe
our scheme to be suitable for implementing fault-tolerant universal quantum
computation with hardware currently under development.
