![Error-Correcting Codes: Theory and Practice Logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-05/Quantum%20Algorithms%2C%20Complexity%2C%20and%20Fault%20Tolerance.jpg?h=49a0d866&itok=FUjtT9Ai)
Abstract
We propose a new scheme for transforming a general quantum circuit into a geometrically local quantum circuit with polynomial qubit overhead and constant circuit depth overhead.We show that our scheme preserves fault-tolerance of the input quantum circuit under local stochastic noise. As a corollary, we show that our scheme can be used as a black box to transform any fault-tolerance construction involving non-local operations into one which only involves geometrically local operations. More generally, our transformation dispenses with the need for considering the locality of operations when designing schemes for fault-tolerant quantum information processing. Applied to recent fault-tolerance constructions, this gives a fault-tolerance threshold theorem for universal quantum computations with local operations, a polynomial qubit overhead and a quasi-polylogarithmic depth overhead. A key element for our construction is a parallel repetition theorem for fault-tolerant long-range entanglement generation.