Nearest Neigbor Compliance

Abstract

Over the course of the last decade, an interest has emerged in nearest neighbor constraints for quantum circuit design. The challenge herein is to bothminimize the running time of a circuit and tomodify it such that quantum gates only act on adjacent qubits while leaving the desired computational operation intact. These modifications involve the insertion of SWAP gates, which introduces computational overhead. Several exact and heuristic methods have been developed to determine the minimal number of required SWAP gates. Until now, the model sizes of exact methods scale superexponentionally in the number of qubits of the quantum circuit. The main research goal of this project was to develop an integer linear program that instead scales polynomially both in the number of qubits and the number of quantum gates in the quantumcircuit.
7
First, qubits located on a linear array were considered. The resulting integer linear program proposed requires O(n^2 m) variables and constraints, where n denotes the number of qubits and m denotes the number of quantum gates of the quantum circuit under consideration. Second, qubits located on a two- or threedimensional grid were considered. The programs both require O(n4m) variables and O(n^3 m) constraints. Subsequently we prove that, for a fixed quantum circuit, the optimal objective value of the one-dimensional problem is an upper bound for the optimal objective value of the corresponding two- and three-dimensional problems. Using CPLEX’s Branch & Bound method, 131 benchmark instances of various circuit sizes were evaluated. The largest of which contained either eighteen qubits and sixteen quantum gates, or five qubits and 112 quantumgates.

Furthermore, we identify problems on the interface of nearest neighbor compliant quantum circuit design and distributed quantum computing. Integer linear program formulations are provided for these additional problems.