TL;DR
This paper presents a novel integer programming (IP) formulation to solve the qubit assignment and routing problem for quantum computers. By modeling the problem as an IP, the authors can optimize for circuit fidelity, depth, and crosstalk simultaneously, leading to significantly improved circuit performance compared to existing methods like Qiskit's SABRE transpiler.
What Problem Does This Paper Address?
Quantum computers, especially those based on superconducting qubits, have limitations in terms of qubit connectivity and are susceptible to noise. Implementing a logical quantum circuit on such hardware requires mapping logical qubits to physical qubits and ensuring gates are executed in the correct order. This "qubit assignment and routing" problem is crucial for achieving high-fidelity quantum computations. Existing methods often rely on heuristics, which may not yield optimal solutions. The authors aim to provide an exact, flexible, and general method for this problem that can optimize for multiple performance metrics.
Methods
The core of this paper is a novel integer linear programming (ILP) formulation. This formulation models the qubit assignment and routing problem as a network flow problem with binary variables. Key aspects of their approach include:
- Unified Formulation: It simultaneously considers qubit allocation (initial placement) and routing (movement of qubits via SWAP gates).
- Hardware-Agnostic: The model can handle arbitrary hardware topologies, represented as graphs.
- Cost Functions: The authors define three objective functions that can be optimized:
- Error Rate: A proxy for circuit fidelity, considering gate fidelities and the number of CNOTs used.
- Circuit Depth: Minimizing the number of sequential gate layers.
- Crosstalk: Minimizing the simultaneous use of specific pairs of hardware edges.
- SWAP Gate Handling: The formulation explicitly accounts for the cost of SWAP gates, distinguishing between SWAPs that can be merged with existing gates and those that require additional operations.
- Linearization: Non-linear constraints (like those involving products of binary variables) are linearized using McCormick inequalities to be compatible with standard ILP solvers.
Datasets
The paper evaluates its method on:
- Synthetic Data: Quantum Volume (QV) circuits of sizes 6 and 8 qubits. QV circuits are designed to stress the capabilities of noisy quantum computers by requiring all-to-all connectivity.
- Toy Hamiltonian Evolution Circuits: A set of Clifford circuits from a previous study [7], used to demonstrate the method's applicability beyond QV circuits and on various topologies.
Key Insights and Ideas
- Simultaneous Optimization is Possible: For error rate and depth, the authors found that these objectives can be optimized simultaneously without significant trade-offs, at least for the tested circuit sizes and topologies. This is a significant finding, suggesting that a weighted combination of these objectives can effectively drive improvements.
- Routing is More Critical than Layout: Experimental results indicate that optimizing qubit routing has a more substantial impact on final circuit fidelity than optimizing the initial qubit assignment alone.
- Crosstalk vs. Fidelity Trade-off: Minimizing crosstalk is in conflict with optimizing for error rate and depth, requiring careful consideration of priorities.
- IP Outperforms Heuristics: The proposed IP formulation, even when used heuristically for larger circuits, consistently outperforms Qiskit's SABRE transpiler in terms of CNOT count, circuit duration, and ultimately, measured heavy output probability (HOP).
- SWAP Merging Matters: The ability to merge SWAP gates with adjacent two-qubit gates, as modeled in their formulation, is crucial for reducing circuit complexity.
Key Results
- CNOT Count Reduction: The IP formulation reduces the CNOT count by approximately 10% compared to SABRE on average across different topologies and circuit sizes. For Hamiltonian evolution circuits, this reduction was around 11%.
- Duration Reduction: Circuit duration is reduced by approximately 21% on average compared to SABRE.
- Improved Heavy Output Probability (HOP): Circuits compiled using the IP method showed higher HOP on actual hardware, indicating better fidelity. For 6-qubit QV circuits on a line topology, BIP achieved a HOP of 0.6771 ± 0.0022, compared to SABRE's 0.6506 ± 0.0030.
- Heuristic Performance: Even when used as a heuristic for 8-qubit circuits (due to computational limitations for exact solutions), the IP approach significantly reduced CNOT count (by ~14% on average) and duration (by ~25% on average) compared to SABRE.
Limitations and Future Work
- Scalability: The primary limitation is the computational cost of solving the ILP to proven optimality. For larger circuits (e.g., 8-qubit QV circuits), the authors resort to using CPLEX as a heuristic, limiting CPU time. This makes the exact ILP formulation unsuitable for very large-scale problems in its current form.
- Objective Function Proxies: While the chosen objective functions (error rate proxy, depth) correlate well with HOP, they are not perfect predictors. The authors suggest that using experimentally measured per-gate error rates could improve this correlation, but this adds computational overhead.
- Future Work: The authors suggest exploring more accurate characterizations of crosstalk and developing mathematical optimization heuristics that can tackle larger circuits more efficiently. They also highlight the need for further investigation into the trade-offs between different objective functions for specific applications.
Summary updated