Sven Jandura
I found out about the Qiskit Developer Challenge in early April by browsing the IBM-Q Forum. By that time, I had been using Qiskit occasionally for a couple of month to execute a few simple quantum circuits on real quantum computers, mainly because this is pretty cool. The challenge asked to improve the current Qiskit compiler. I never looked at or cared about the compiler before, so I thought this was a good way to gain some insight.
The job of the compiler is twofold: Given a particular quantum circuit, it optimizes it in some way, in this case minimize the number of CNOT-gates used. But, even more importantly, it modifies the circuit in a way, that it can be executed by a quantum computer with a particular topology (The topology tells you between which qubits a CNOT-gate can be performed on a particular device). To do this, SWAP-gates are performed to swap qubits around, until the two qubits the CNOT should be performed on, are connected in the topology of the device. Since each SWAP-gate requires three CNOTs, I decided that the best way of improving the compiler is to focus on improving which qubits are swapped when.
I implemented the following algorithm to swap the qubits: Let a mapping be a table which tells us which qubit in the circuit we want to implement (logical qubits) corresponds to which qubit on the actual device (physical qubits). Whether or not a CNOT between two logical qubits can be performed only depends on the mapping. The mapping can be changed by performing SWAP-gates. Let the distance between two logical qubits be the length of the shortest path connecting them in the topology.
Now given a mapping and a list of the few next upcoming CNOTs that should be performed on the logical qubits, we first find the four most promising swaps. These are the swaps which minimize the total distance between all qubits in the upcoming CNOTs. For each swap, we calculate the new mapping. We count how many CNOTs can be executed with the new mapping and remove them from the list. Then for each new mapping we again find the four most promising swaps, calculate the new mappings, and continue until we have reached a depth of four mappings. From the 4⁴=256 final mappings we choose the one that allowed for the most CNOTs to be executed and execute the fist swap on the path to this mapping. Then we start the whole algorithm again, until the circuit is completed.
The algorithm is best illustrated with an example. Assume we have six qubits and the topology shown in Fig. 1. The action of the algorithm is shown in Fig. 2, the colored circles correspond to logical qubits. The black lines connect logical qubits, between which a CNOT should be executed. For the sake of simplicity only two swaps are investigated at each stage.
The initial mapping has a total distance of 7, because the distance between red and magenta and between blue and cyan is 2 each, and the distance between green and yellow is 3. If we swap green and blue, the total distance decreases by 2. If we swap blue and magenta, it decreases by 1. These are the two most promising swaps. We then calculate the mappings after the swaps have been applied (second line in Fig. 2) and remove all CNOTS that can be executed (third line). This process is then repeated with the new mappings. In the end, we were able to execute three CNOTs in the very left path. Because this is the best we could achieve, we choose to swap blue and green.
I was able to decrease the number of CNOTs on the test circuits by about 15%. At the same time, I achieved a speedup of approximately 38%, both compared to the original Qiskit compiler. I measured this for random circuits with 5, 16 and 20 qubits on different topologies.
In mid July I found out that IBM had selected my submission as the second prize winner of the Qiskit Developer Challenge. I am very honored that the judges appreciated my work like that. For me, it is super exciting to learn and understand about the field of quantum computation, which might change our world in a lot of different areas in the future.
