An Integer Programming Model for the Optimal Qubit Allocation
Hyeonseok Choi, In-Chan Choi · Journal of Korean Institute of Industrial Engineers · 2021
A qubit allocation problem is to find an assignment of logical qubits in a quantum algorithm to the physical qubits of a quantum computing device. The physical qubits are often configured in a coupling map, which is a directed graph that represents communication relationship between adjacent physical qubits. A proper qubit allocation satisfies all logical qubit communication relationship in a quantum circuit by conforming to the coupling map restriction. To find the proper qubit allocation, we often need to change the quantum circuit by using a set of circuit transformations, which include reversal, bridge, and swap. Such a transformation results in the quantum circuit with newly added quantum gates and subsequenlty causes extra quantum errors. In this study, we propose an integer programming model that minimizes the sum of the quantum costs of the circuit transformation. In our model, all three circuit transformations are considered. Moreover, we present the results of the computational experiment in which our model is compared with heuristic procedures from previous studies.