Surface codes are widely considered to be one of the most promising methods for achieving fault-tolerant quantum computation on noisy intermediate-scale quantum (NISQ) computers. One of the computational challenges involved is in transpiling the logical circuit to a form that is compatible with the physical hardware that has limited qubit connectivity. In particular, the goal is to first determine a mapping from the logical qubits in the input circuit to the surface code topology, and then route them via Bell pairs, in a manner that minimizes the total execution time. We refer to this problem as the surface code logical qubit mapping and routing problem. In this work, we formulate the mapping problem as a mixed integer program (MIP) and implement an edge-disjoint path algorithm for routing. In order to handle circuits with a larger number of qubits, we introduce a divide-and-conquer (DC) strategy for scalable mapping. We evaluate our MIP-based mapping approach against structural and random mapping baselines, demonstrating improved performance on both large-scale synthetic circuits and circuits from existing quantum algorithms.
Surface codes are widely considered to be one of the most promising methods for achieving fault-tolerant quantum computation on noisy intermediate-scale quantum (NISQ) computers. One of the computational challenges involved is in transpiling the logical circuit to a form that is compatible with the physical hardware that has limited qubit connectivity. In particular, the goal is to first determine a mapping from the logical qubits in the input circuit to the surface code topology, and then route them via Bell pairs, in a manner that minimizes the total execution time. We refer to this problem as the surface code logical qubit mapping and routing problem. In this work, we formulate the mapping problem as a mixed integer program (MIP) and implement an edge-disjoint path algorithm for routing. In order to handle circuits with a larger number of qubits, we introduce a divide-and-conquer (DC) strategy for scalable mapping. We evaluate our MIP-based mapping approach against structural and random mapping baselines, demonstrating improved performance on both large-scale synthetic circuits and circuits from existing quantum algorithms.
We provide an efficient algorithm to compile quantum circuits for fault-tolerant execution.We target surface codes, which form a two-dimensional 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 ancillae in constant depth that can be used to perform these long-range operations.This forms one core part of our edge-disjoint path 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 path 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 SWAP gates 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 controlled-NOT (CNOT) gates, and for circuits that implement the multicontrolled X gate C k NOT.
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 (1) mapping circuit qubits to the device qubits and (2) 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.
Facilitating the ability to achieve logical qubit error rates below physical qubit error rates, error correction is anticipated to play an important role in scaling quantum computers. While many algorithms require millions of physical qubits to be executed with error correction, current superconducting qubit systems contain only hundreds of physical qubits. One of the most promising codes on the superconducting qubit platform is the surface code, requiring a realistically attainable error threshold and the ability to perform universal fault-tolerant quantum computing with local operations via lattice surgery and magic state injection. Surface code architectures easily generalize to single-chip planar layouts, however space and control hardware constraints point to limits on the number of qubits that can fit on one chip. Additionally, the planar routing on single-chip architectures leads to serialization of commuting gates and strain on classical decoding caused by large ancilla patches. A distributed multi-chip architecture utilizing the surface code can potentially solve these problems if one can optimize inter-chip gates, manage collisions in networking between chips, and minimize routing hardware costs. We propose QuIRC, a superconducting Quantum Interface Routing Card for Lattice Surgery between surface code modules inside of a single dilution refrigerator. QuIRC improves scaling by allowing connection of many modules, increases ancilla connectivity of surface code lattices, and offers improved transpilation of Pauli-based surface code circuits. QuIRC employs in-situ Entangled Pair (EP) generation protocols for communication. We explore potential topological layouts of QuIRC based on superconducting hardware fabrication constraints, and demonstrate reductions in ancilla patch size by up to 77.8%, and in layer transpilation size by 51.9% when compared to the single-chip case.
Large-scale fault-tolerant quantum computation requires compiling logical circuits into physical operations tailored to a given architecture. Prior work addressing this challenge has mostly focused on the surface code and lattice surgery schemes. In this work, we broaden the scope by considering lattice surgery compilation for topological codes beyond the surface code. We begin by defining a code substrate-a blueprint for implementing topological codes and lattice surgery. We then abstract from the microscopic details and rephrase the compilation task as a mapping and routing problem on a macroscopic routing graph, potentially subject to substrate-specific constraints. We explore specific substrates and codes, including the color code and the folded surface code, providing detailed microscopic constructions. For the color code, we present numerical simulations analyzing how design choices at the microscopic and macroscopic levels affect the depth of compiled logical CNOT + T circuits. An opensource code is available on GitHub https://github.com/cda-tum/mqt-qecc.
Early demonstrations of fault tolerant quantum systems have paved the way for logical-level compilation. For fault-tolerant applications to succeed, execution must finish with a low total program error rate (i.e., a low program failure rate). In this work, we study a promising candidate for future fault-tolerant architectures with low spatial overhead: the Gross code. Compilation for the Gross code entails compiling to Pauli Based Computation and then reducing the rotations and measurements to the Bicycle ISA. Depending on the configuration of modules and the placement of code modules on hardware, one can reduce the amount of resulting Bicycle instructions to produce a lower overall error rate.
We find that NISQ-based, and existing FTQC mappers are insufficient for mapping logical qubits on Gross code architectures because 1. they do not account for the two-level nature of the logical qubit mapping problem, which separates into code modules with distinct measurements, and 2. they naively account only for length two interactions, whereas Pauli-Products are up to length n, where n is the number of logical qubits in the circuit. For these reasons, we introduce a two-stage pipeline that first uses hypergraph partitioning to create in-module clusters, and then executes a priority-based algorithm to efficiently assign clusters onto hardware. We find that our mapping policy reduces the error contribution from inter-module measurements, the largest source of error in the Gross Code, by up to ∼36% in the best case, with an average reduction of ∼13%. On average, we reduce the failure rates from inter-module measurements by ∼22% with localized factory availability, and by ∼17% on grid architectures, allowing hardware developers to be less constrained in developing scalable fault tolerant systems due to software driven reductions in program failure rates.
Silicon spin qubits have emerged as a promising qubit technology due to their favorable scaling and fabrication properties. However, efficiently compiling quantum circuits onto spin qubit platforms remains challenging, particularly when accounting for hardware constraints and the high sensitivity to static defects. Existing compilation approaches for spin qubits either largely ignore error correction, despite its critical role for large-scale quantum computation, or focus on low-level schedule constructions, missing a high-level compilation and routing for logical, error-corrected algorithms. To address this gap, we introduce a compilation framework for spin qubits based on the recent snakes on a plane model, which utilizes a 2D surface code and qubit teleportation to mitigate errors. Building on this model, we propose shortest-path and rotation-based algorithms as two novel classes of qubit-routing techniques, along with additional defect-handling and initial-mapping strategies. We evaluate both algorithms across diverse architectural settings and problem sizes, demonstrating that shortest-path methods excel in sparse, low-defect scenarios, while rotation-based approaches perform better in high-density environments. An open-source implementation of our framework is publicly available on GitHub as part of the Munich Quantum Toolkit (MQT) at https://github.com/munich-quantum-toolkit/spin-qubit-routing.