



01688nas a2200133   4500008004100000245005300041210005200094260001500146520129100161100002301452700002301475700001901498856003701517       2021                        eng d00aSurface code compilation via edge-disjoint paths0 aSurface code compilation via edgedisjoint paths  c10/21/20213 a<p>We provide an efficient algorithm to compile quantum circuits for fault-tolerant execution. We target surface codes, which form a 2D grid of logical qubits with nearest-neighbor logical operations. Embedding an input circuit&#39;s qubits in surface codes can result in long-range two-qubit operations across the grid. We show how to prepare many long-range Bell pairs on qubits connected by edge-disjoint paths of ancillas in constant depth which can be used to perform these long-range operations. This forms one core part of our Edge-Disjoint Paths Compilation (EDPC) algorithm, by easily performing parallel long-range Clifford operations in constant depth. It also allows us to establish a connection between surface code compilation and several well-studied edge-disjoint paths problems. Similar techniques allow us to perform non-Clifford single-qubit rotations far from magic state distillation factories. In this case, we can easily find the maximum set of paths by a max-flow reduction, which forms the other major part of our EDPC algorithm. We compare EDPC to other compilation approaches including a SWAP-based algorithm, and find significantly improved performance for circuits built from parallel CNOTs, and for circuits which implement the multi-controlled X gate.</p>1 aBeverland, Michael1 aKliuchnikov, Vadym1 aSchoute, Eddie  uhttps://arxiv.org/abs/2110.11493