Dependency-Aware Compilation for Surface Code Quantum Architectures

Practical applications of quantum computing depend on fault-tolerant devices with error correction. Today, the most promising approach is a class of error-correcting codes called surface codes. We study the problem of compiling quantum circuits for quantum computers implementing surface codes. Optimal or near-optimal compilation is critical for both efficiency and correctness. The compilation problem requires mapping circuit qubits to the device qubits and routing execution paths between interacting qubits. We solve this problem efficiently and near-optimally with a novel algorithm that exploits the dependency structure of circuit operations to formulate discrete optimization problems that can be approximated via simulated annealing, a classic and simple algorithm. Our extensive evaluation shows that our approach is powerful and flexible for compiling realistic workloads. For example: (1) in terms of solution quality, our approach matches or outperforms Autobraid, a state-of-the-art approach for a related problem, on 84% of benchmarks, with significant gains on dense circuits; including up to 31% cost improvement on Quantum Fourier Transform circuits; (2) in 69 circuits where we can compute an optimal solution using a satisfiability solver, our approach is within 25% of optimal for all but 5.