Magic-state encoder and magic teleportation: Efficient fault-tolerant non-Clifford gates with concatenated quantum codes

In fault-tolerant quantum computation, Clifford operations, e.g., controlled-NOT gates, can be efficiently implemented in a fault-tolerant manner. However, non-Clifford gates such as the $T$ gate $\pi/8$ rotation) and the Toffoli gate are difficult to implement efficiently. A standard approach to non-Clifford gates is ``magic state distillation,'' which can provide high-fidelity magic states using more low-fidelity magic states. Thus, reliable non-Clifford gates can be performed with the high-fidelity magic states and reliable Clifford operations. However, the resource overhead for magic state distillation is much larger than those for Clifford gates. To solve this problem, here we propose a new approach: magic-state encoder. This can be applied to concatenated quantum codes with a property that Hadamard gates can be implemented transversally. The magic-state encoder encodes (not distills) a high-fidelity level-$(l+1)$ encoded magic state with low-fidelity level-$l$ encoded magic states. As a result, non-Clifford gates (here we focus on the $T$ gate) can be performed with an overhead comparable to Clifford gates. By performing the $T$ gate by teleportation with an entangled state generated with a magic state, which we call ``magic teleportation,'' further improvement is possible.