A SAT approach to the initial mapping problem in SWAP gate insertion for commuting gates

Abstract

Most quantum circuits require SWAP gate insertion to run on quantum hardware with limited qubit connectivity. A promising SWAP gate insertion method for blocks of commuting two-qubit gates is a predetermined swap strategy which applies layers of SWAP gates simultaneously executable on the coupling map. A good initial mapping for the swap strategy reduces the number of required swap gates. However, even when a circuit consists of commuting gates, e.g., as in the Quantum Approximate Optimization Algorithm (QAOA) or trotterized simulations of Ising Hamiltonians, finding a good initial mapping is a hard problem. We present a SAT-based approach to find good initial mappings for circuits with commuting gates transpiled to the hardware with swap strategies. Our method achieves a 65% reduction in gate count for random three-regular graphs with 500 nodes. In addition, we present a heuristic approach that combines the SAT formulation with a clustering algorithm to reduce large problems to a manageable size. This approach reduces the number of swap layers by 25% compared to both a trivial and random initial mapping for a random three-regular graph with 1000 nodes. Good initial mappings will therefore enable the study of quantum algorithms, such as QAOA and Ising Hamiltonian simulation applied to sparse problems, on noisy quantum hardware with several hundreds of qubits.

7 pages

References in corpus (7)

• Charge insensitive qubit design derived from the Cooper pair box
• A Quantum Approximate Optimization Algorithm
• t$|$ket$⟩$ : A Retargetable Compiler for NISQ Devices
• Quantum Circuit Placement
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• Well-conditioned multi-product formulas for hardware-friendly Hamiltonian simulation
• Formal Constraint-based Compilation for Noisy Intermediate-Scale Quantum Systems

Cited by in corpus (9)

• Large-scale quantum approximate optimization on non-planar graphs with machine learning noise mitigation
• Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer
• Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping
• Hardware-Efficient Preparation of Graph States on Near-Term Quantum Computers
• Optimization via Quantum Preconditioning
• Q-fid: Quantum Circuit Fidelity Improvement with LSTM Networks
• Q-gen: A Parameterized Quantum Circuit Generator
• Approximate Quadratization of High-Order Hamiltonians for Combinatorial Quantum Optimization
• Constrained Quantum Optimization via Iterative Warm-Start XY-Mixers