Magic Gate Teleportation: Structure, Useful Resource States, and Simpler Feedforward

Quantum gate teleportation is a key technique in fault-tolerant quantum computation that uses resource states to implement logical gates. Here, we develop a theory of magic gate teleportation (MGT), a form of quantum gate teleportation that uses non-stabilizer resource states to implement non-Clifford unitary gates on arbitrary input states without revealing information about those states. This setting is motivated by the canonical approach to implementing logical non-Clifford gates in fault-tolerant quantum computation. We uncover a hidden structure within MGT---after backpropagating the Pauli measurements, MGT protocols can be viewed as encoding the input state into a stabilizer code heralded by the measurement outcomes, followed by a logical non-Clifford gate. Using this structure, we construct MGT protocols for any resource state obtained by applying commuting Pauli rotations to a stabilizer state, and provide an efficient algorithm for synthesizing their circuit implementations. Conversely, we prove that directly useful single-qubit resource states are necessarily Clifford-equivalent to diagonal states, and establish the same constraint for multi-qubit resource states used in a broad class of MGT protocols. In particular, the output state distilled from the [![5, 1, 3]!] protocol is not directly useful for any MGT protocols, though it can be probabilistically converted into directly useful states. Finally, we identify conditions under which the feedforward operators can be implemented by Pauli operators, shedding light on the paradigm of algorithmic fault tolerance and simplifying the feedforward operations needed for quantum computing.