Using reinforcement learning to achieve backend optimisation for quantum compilers
With the advent of the first generation of quantum computers (for example Google, Rigetti and IBM in the US; and OQC, Universal quantum and NQIT in the UK), attention has turned to compiling quantum algorithms to run on these machines. The emerging norm is a quantum compiler structure that is, in some important respects closely analogous to that of a classical compiler. In particular, the front-end, optimiser, back-end division has been retained, in which the quantum circuit (typically encoded in openQASM) plays the role of the intermediate representation (IR).
Just as in the classical case, the backend receives the IR which is in some sense optimised, but in a manner that is not specific to the target hardware. Specifically, quantum circuits consist of two-qubit gates, and implicitly assume complete connectivity - that is, any two pair of qubits can interact (gate together). This, however, contravenes physical constraints, which mean that there will be some limitation on the actual connectivity, for example the qubits may be laid out in a square grid, with each only able to interact with its four neighbours. It is possible to swap qubits, therefore general quantum algorithms can be executed on such machines, but with an execution time cost incurred by the insertion of these swaps. Therefore the role of the quantum compiler backend is to optimally map the IR (which is a quantum circuit assuming complete connectivity) to a target architecture with some known limited connectivity.
Typically ad-hoc and / or heuristic approaches have been taken to this quantum backend optimisation problem, however we have previously shown that it can be expressed as a reinforcement learning problem, with proof of principle results demonstrating the potential of this technique. The goal of this project is therefore to improve and extend this work.