Kathleen Chang

It is a major challenge to perform addressable logical operations on constant-rate quantum LDPC (qLDPC) codes. Indeed, the overhead of targeting specific logical qubits represents a crucial bottleneck in many quantum fault-tolerance schemes. We introduce a protocol for performing fully addressable logical $CNOT$ or Hadamard gates with constant quantum space-time overhead, on a family of constant-rate and polynomial-distance qLDPC codes. Specifically, our gadgets perform Hadamard on any chosen logical qubit within a code block, and $CNOT$ between any pair of logical qubits, either within a block or across blocks. We also construct constant-overhead gadgets for highly parallel logical operations, including a large class of permutations of logical qubits. Prior protocols for such operations required polynomial space-time overhead with respect to the distance, or else relied on codes with certain symmetries that lack known asymptotic constructions. Our codes are given by tensor (i.e. hypergraph) products of classical codes constructed from lossless expander graphs. To address individual logical qubits, we develop a constant-overhead code-switching procedure between 2- and 3-dimensional product codes, which generalizes Bombin’s dimensional jump (arXiv:1412.5079). We provide rigorous fault-tolerance proofs for our gadgets, and specifically prove a constant threshold under locally stochastic noise. Along the way, we develop a small-set flip decoder for high-dimensional product codes from lossless expanders. Our techniques yield additional interesting consequences, such as single-shot state preparation of 2-dimensional product codes with constant space-time overhead.