The synthesis of nearest neighbour compliant quantum circuits

When using heuristics, there is a trade-off between the run-time and the performance.<br><br>The run-time/performance trade-off was investigated for a variety of functions which determine how important each gate should be based on its position in the circuit, and it was found that while the quadratic decreasing weight function from the literature had the lowest swap cost, the previously unstudied linear decreasing weight function was faster.

Averaged over a number of large random circuits, the relative run-time improvement of the linear function compared to the quadratic outweighs the increase in swap cost.<br><br>To reduce the time taken to find an initial placement, a method of random sampling was proposed. The distribution of the swap costs for random circuits was modelled as a normal distribution to approximate how many random placements need to be inspected in order to find one within a certain distance of the optimum.

It was experimentally observed that when taking a random sample of 100 placements, the best placement in the sample was below the predicted 10th percentile of all placements 96.85% of the time, averaged over physical qubit arrays with between 10 and 16 qubits in varying arrangements.<br><br>A method for an offline estimation of the number of gates that should be considered when choosing the placement and swap gates was proposed.

This speeds up the compilation process by ensuring the swap insertion pass only needs to be performed once per circuit, with negligible difference in swap cost.<br><br>When generating a circuit whose only purpose is to move the logical qubits from one layout to another, the A* algorithm is guaranteed to find the smallest circuit. The time complexity of A* depends on the quality of the heuristic, and this thesis proposes a new heuristic which significantly outperforms the previous heuristic, and in some circumstances is shown to behave optimally.<br><br>The swap insertion pass of a circuit can be parallelised by splitting it up into subcircuits, however doing so will affect the swap cost.

This thesis calculates the relationship between the number of subcircuits and the swap cost, which brings the estimation of the optimal number of subcircuits offline. This speeds up the compilation of a circuit compared to methods which try multiple different numbers of subcircuits in order to choose the best.