2D Nearest Neighbor Optimization Method Based on Constrained Programming
Lin Zhou, Bing Beverly Guo, Changhai Lin · 2021
As quantum computing enters the era of NISQ (Noisy Intermediate-Scale Quantum), nearest neighbor constraint has become an urgent problem in qubits arrangement. In order to reduce the nearest neighbor cost, this paper proposes a 2D nearest neighbor constraint synthesis algorithm. First, in order to solve the initial arrangement problem, the nearest neighbor constraint problem is modeled as a constrained programming equation, and the optimal path method is selected to solve the optimal initial arrangement of the qubits; Then on the basis of the initial arrangement, we use a heuristic selection algorithm based on the directed acyclic graph to search for the optimal path to construct an external queue to select the optimal SWAP gate insertion method. Using a representative benchmark line for test comparison, compared with the classic algorithm, the average optimization rate of the algorithm proposed in this paper has increased by 24.1%.