Surface code compilation via edge-disjoint paths

Abstract

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'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 that 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 many 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 EDPC. EDPC has the best asymptotic worst-case performance guarantees on the circuit depth for compiling parallel operations when compared to related compilation methods based on swaps and network coding. EDPC also shows a quadratic depth improvement over sequential Pauli-based compilation for parallel rotations requiring magic resources. We implement EDPC and find significantly improved performance for circuits built from parallel cnots, and for circuits which implement the multi-controlled $X$ gate.

48 pages, 20 figures. Published version in PRX Quantum. Includes new comparison table, tightened Theorem 3.3/3.4, and source code

References in corpus (11)

• Surface codes: Towards practical large-scale quantum computation
• Quantum computing with nearest neighbor interactions and error rates over 1%
• Novel constructions for the fault-tolerant Toffoli gate
• Universal quantum computing with twist-free and temporally encoded lattice surgery
• Fault-Tolerant Postselected Quantum Computation: Schemes
• Optimized Surface Code Communication in Superconducting Quantum Computers
• Braiding by Majorana Tracking and Long-Range CNOT Gates with Color Codes
• Quantum computing by color-code lattice surgery
• Advantages and limitations of quantum routing
• Bounds on stabilizer measurement circuits and obstructions to local implementations of quantum LDPC codes
• Flexible layout of surface code computations using AutoCCZ states

Cited by in corpus (23)

• Efficient Long-Range Entanglement using Dynamic Circuits
• High-fidelity realization of the AKLT state on a NISQ-era quantum processor
• Toward a 2D Local Implementation of Quantum LDPC Codes
• A "thoughtful" Local Friendliness no-go theorem: a prospective experiment with new assumptions to suit
• A High Performance Compiler for Very Large Scale Surface Code Computations
• Looped Pipelines Enabling Effective 3D Qubit Lattices in a Strictly 2D Device
• Realistic Cost to Execute Practical Quantum Circuits using Direct Clifford+T Lattice Surgery Compilation
• Applications of Universal Parity Quantum Computation
• Quantum Routing with Teleportation
• TISCC: A Surface Code Compiler and Resource Estimator for Trapped-Ion Processors
• Hardware-Efficient Quantum Random Access Memory Design with a Native Gate Set on Superconducting Platforms
• Resource Analysis of Low-Overhead Transversal Architectures for Reconfigurable Atom Arrays
• Teleporting two-qubit entanglement across 19 qubits on a superconducting quantum computer
• Locality-aware Pauli-based computation for local magic state preparation
• LSQCA: Resource-Efficient Load/Store Architecture for Limited-Scale Fault-Tolerant Quantum Computing
• Feasibility of Logical Bell State Generation in Memory Assisted Quantum Networks
• Lattice Surgery Compilation Beyond the Surface Code
• Unified Architecture for Quantum Lookup Tables
• Type-Based Verification of Connectivity Constraints in Lattice Surgery
• Online Job Scheduler for Fault-tolerant Quantum Multiprogramming
• Dense packing of the surface code: code deformation procedures and hook-error-avoiding gate scheduling
• Managing Classical Processing Requirements for Quantum Error Correction
• RESCQ: Realtime Scheduling for Continuous Angle Quantum Error Correction Architectures