Transversal Algorithmic Fault Tolerance for Low-Overhead Quantum Computing | Quantum Colloquium

Fast, reliable logical operations are essential for the realization of useful quantum computers. By redundantly encoding logical qubits into many physical qubits and using syndrome measurements to detect and subsequently correct errors, one can achieve very low logical error rates. However, for many practical quantum error correcting (QEC) codes such as the surface code, it is generally believed that due to syndrome extraction errors, multiple extraction rounds---on the order of the code distance d---are required for fault-tolerant computation, particularly considering fault-tolerant state preparation. Here, we show that contrary to this common belief, fault-tolerant logical operations can be performed with constant time overhead for a broad class of QEC codes, including the surface code with magic state inputs and feed-forward operations, to achieve ``transversal algorithmic fault tolerance". Through the combination of transversal operations and novel strategies for correlated decoding, despite only having access to partial syndrome information, we prove that the deviation from the ideal measurement result distribution can be made exponentially small in the code distance, even if the instantaneous quantum state cannot be made close to a logical codeword. We supplement this proof with circuit-level simulations in a range of relevant settings, demonstrating the fault tolerance and competitive performance of our approach. Our work sheds new light on the theory of quantum fault tolerance, potentially reducing the space-time cost of practical fault-tolerant quantum computation by over an order of magnitude.