Comparison of Exponentially Decreasing Vs. Polynomially Decreasing Objective Functions for Making Quantum Circuits Nearest Neighbour Compliant

Many proposed architectures for quantum computing involve arranging qubits in a lattice, and then using swap gates to move the quantum states between qubits to enable any pair of qubits to interact with each other. Since swap gates perform no useful computation, they can be viewed as an overhead whose number should be minimised in efficient quantum programs. The location of the swap gates in a quantum circuit are chosen by minimising an objective function characterising the structure of the quantum circuit. Those which currently offer the lowest swap cost reduce the significance of each gate to the objective function relative to its position in the circuit. The criterion that describes how quickly the significance must decrease. In this paper, we show that to satisfy this criterion, it is necessary and sufficient for the decay to be exponential. However, when applying this new objective function, there is no significant improvement over the old function, with most of the benchmark circuits having less than 5% improvement. Only three circuits had more than 10% improvement in swap cost, and these circuits were all less than 100 gates long. The three longest circuits in the benchmark suite had less than 1% change in swap cost. There is also a significant penalty in run time, in one case reaching 265.48%.