Source-linked AI summary
Mapping Quantum Circuits to IBM QX Architectures Using the Minimal Number of SWAP and H Operations
Robert Wille, Lukas Burgholzer, Alwin Zulehner
TL;DR
IBM QX architectures impose interaction constraints that make circuit mapping an optimization problem, while existing heuristic methods did not establish how close they were to the minimum number of added SWAP and H operations. The paper formulates mapping symbolically and solves it with Boolean satisfiability reasoning engines. It produces minimal mappings and finds that IBM’s heuristic solution exceeds the lower bound by more than 100% on average.
Problem
Existing mapping methods did not solve the NP-complete SWAP- and H-minimization problem exactly, leaving their distance from the optimum unclear.
Method
The paper formulates circuit mapping as a symbolic optimization problem and uses Boolean satisfiability solving to search possible mappings and added operations.
Results
The method maps circuits with a minimal number of SWAP and H operations, while IBM’s heuristic solution exceeds the lower bound by more than 100% on average.
Takeaways & Limitations
Exact mappings provide a basis for evaluating heuristic mapping quality, while restricted search can retain close-to-minimal solutions with improved solving performance.
Takeaways & Limitations
Exact solving is computationally expensive and is applicable only to small quantum circuits, while search-space restrictions may remove guarantees of minimality.
Abstract
from arXiv · showhide
The recent progress in the physical realization of quantum computers (the first publicly available ones--IBM's QX architectures--have been launched in 2017) has motivated research on automatic methods that aid users in running quantum circuits on them. Here, certain physical constraints given by the architectures which restrict the allowed interactions of the involved qubits have to be satisfied. Thus far, this has been addressed by inserting SWAP and H operations. However, it remains unknown whether existing methods add a minimum number of SWAP and H operations or, if not, how far they are away from that minimum--an NP-complete problem. In this work, we address this by formulating the mapping task as a symbolic optimization problem that is solved using reasoning engines like Boolean satisfiability solvers. By this, we do not only provide a method that maps quantum circuits to IBM's QX architectures with a minimal number of SWAP and H operations, but also show by experimental evaluation that the number of operations added by IBM's heuristic solution exceeds the lower bound by more than 100% on average. An implementation of the proposed methodology is publicly available at http://iic.jku.at/eda/research/ibm_qx_mapping.
1 INTRODUCTION
IBM’s publicly accessible QX processors motivated automatic circuit-mapping research because architecture-specific interaction constraints require added operations. Existing heuristic methods lacked exact optimality, prompting a symbolic approach that achieves minimal or close-to-minimal mappings and exposes substantial heuristic overhead.
- Motivation: IBM’s publicly available quantum processor, launched in 2017, motivated automatic methods for running circuits on QX architectures.The machines were accessible through cloud access and had attracted more than 100,000 users and 6.5 million experiments.
- Problem: Mapping logical qubits to physical qubits must satisfy coupling-map constraints that restrict which qubits may interact.Violations can be addressed by inserting SWAP and H operations, which increase circuit size and can harm execution fidelity.
- Gap: Existing methods used heuristics rather than exact minimization, leaving their distance from the optimum unclear.Exact methods are needed to evaluate the state of the art, even when optimal solutions are available only for small instances.
- Approach: The paper formulates mapping as a symbolic search over possible SWAP and H operations and uses Boolean satisfiability solvers to handle the search space.Performance optimizations can restrict the search space and produce close-to-minimal solutions faster, without always guaranteeing minimality.
- Result: IBM’s heuristic mapping solution exceeds the lower bound by more than 100% on average.The experimental evaluation compares heuristic results with lower bounds obtained through the proposed methodology.
2 BACKGROUND
Quantum circuits represent computations as sequences of single- and multi-qubit gates, while IBM QX architectures impose directed interaction constraints through coupling maps. Mapping therefore requires logical-to-physical assignments and may add SWAP or Hadamard operations to satisfy connectivity and CNOT direction requirements while controlling cost.
- Quantum Circuits: Quantum circuits encode computations as ordered sequences of single-qubit and controlled-not gates over logical qubits.Single-qubit gates are represented by unitary matrices, while CNOT gates specify control and target qubits.
- IBM QX Architectures: IBM QX architectures support universal single-qubit U gates and CNOT gates, but not every pair of physical qubits can interact.The decomposition into U and CNOT gates is assumed to have occurred before mapping constraints are handled.
- Coupling Maps: A directed coupling map specifies which physical qubit may control another physical qubit in a CNOT operation.An ordered pair in the coupling map represents an allowed control-to-target interaction.
- Mapping Operations: SWAP operations move logical qubits between physical locations when required interactions are unavailable.A SWAP exchanges the states of two physical qubits and is decomposed into elementary gates supported by the architecture.
- Mapping Operations: Four Hadamard operations can reverse a CNOT’s control and target direction, providing a cheaper remedy for one directional constraint.The cost model assigns seven added operations to a SWAP and four to a direction reversal, with lower operation count associated with higher fidelity.
3 DETERMINING A MINIMAL SOLUTION
The mapping problem is formulated symbolically to represent valid logical-to-physical assignments, gate-direction changes, and permutation choices across the circuit. A reasoning engine then searches this space while minimizing the associated SWAP and H costs.
- 3.1 Main Idea for Tackling the Complexity: The method targets minimal or close-to-minimal mappings of quantum circuits to IBM QX architectures despite the problem's NP-complete search space.It considers all SWAP and H applications that may influence circuit realization, while optional performance optimizations can sacrifice minimality for speed.
- 3.1 Main Idea for Tackling the Complexity: Boolean satisfiability reasoning engines are used to explore the symbolic mapping search space efficiently.The formulation uses satisfiability constraints together with an objective function so assignments can be valid and cost-minimal.
- 3.2 Symbolic Formulation of the Problem: Mapping variables x describe which physical qubit each logical qubit occupies before each circuit gate.The formulation represents logical qubits Q, physical qubits P, and the architecture's coupling map CM.
- 3.2 Symbolic Formulation of the Problem: The constraints enforce one-to-one logical-to-physical assignments and require every gate interaction to comply with the coupling map.The resulting symbolic formulation covers the entire search space and yields valid mappings when passed to a reasoning engine.
- 3.2 Symbolic Formulation of the Problem: Permutation variables y encode mapping changes before gates, while switching variables z encode reversed CNOT directions.SWAP operations realize permutations, and H operations permit control-target switching when the coupling map supports the opposite direction.
- 3.3 Minimizing the Cost: F = 4 is the minimum cost obtained for the illustrated IBM QX4 mapping.The resulting circuit realizes the original circuit on the specified architecture using the minimum required additional SWAP and H operations.
4 PERFORMANCE IMPROVEMENTS
Performance improvements reduce the search burden of exact mapping, but restricting possible permutations can sacrifice minimality for speed. The method also exploits smaller connected physical-qubit subsets to simplify instances.
- NP-complete mapping remains computationally expensive even when powerful reasoning engines determine minimal solutions.
- For n < m, solving mappings over subsets of n physical qubits reduces the exponential search space.The number of physical qubits considered contributes exponentially to search-space size.
- For a four-qubit circuit on five physical qubits, subset-based decomposition reduces one instance from 2100 to 280 possibilities.Checking all five subsets still substantially reduces the overall search space.
- Subsets containing isolated physical qubits can be discarded because no valid solution exists for them.Isolation can be checked in O(n) time before invoking the reasoning engine.
- Restricting the Possible Permutations: Restricting permutation points accelerates solving, but excessive restriction can produce solutions that are not minimal.Disjoint-qubit, odd-gate, and qubit-triangle strategies allow permutations only before selected gates or sequences.
5 EXPERIMENTAL RESULTS
Experiments on circuits mapped to IBM QX4 show that exact minimal mapping is expensive, while search-space reductions preserve or approach minimality with improved runtimes. Comparisons with Qiskit quantify substantial gaps between heuristic and minimum-cost mappings.
- Exact minimum-cost mapping is expensive, with solutions determined only for instances containing relatively few CNOT gates.This reflects the underlying NP-complete complexity.
- Subset selection significantly reduces runtime for three- and four-qubit benchmarks while preserving minimality.
- The disjoint-qubits strategy always achieves minimum cost on the evaluated benchmarks, whereas qubit triangle performs worst for minimality.All evaluated strategies nevertheless provide solutions close to minimum within acceptable runtime.
- Qiskit’s probabilistic mapper was run five times per benchmark, with the observed minimum reported for comparison.The comparison used Qiskit 0.4.15 and considered the actual mapping process.
6 CONCLUSIONS
The paper formulates quantum-circuit mapping to IBM QX architectures as an NP-complete optimization problem and solves it exactly with Boolean satisfiability. It also reports that IBM’s heuristic adds more than 100% above the lower bound on average.
- The proposed exact method uses a symbolic formulation and the Boolean satisfiability solver Z3 to determine minimal SWAP and H operations.
- The paper’s performance optimizations restrict the search space to obtain close-to-minimal solutions more quickly.
- More than 100% above the lower bound on average is the reported excess of IBM’s heuristic solution.
- The implementation is publicly available online.