Constraints on Quantum Circuits and getting around them
Physical quantum computers have many constraints that an idealized, theoretical model of a quantum computer often ignores. The limited connectivity between qubits is one such constraint. Only if qubits are connected can we perform a two-qubit gate between them. When they are not, we have to move the qubits to a place where we can execute the gate.
The recent Qiskit developer challenge asked developers to write software for transforming circuits to work around the connectivity constraint (my submission tied for second place). As it turns out this problem is hard. As we broke it down into various sub-problems we found ourselves face-to-face with many NP-hard problems (job scheduling, optimization, place & route-style problems).
The heart of the problem is deciding where to place qubits at different parts of the execution. We give various mapper subroutines that do exactly that. Equipped with the quantum computer architecture, mappers decide where to place qubits from a circuit description. With such a mapper, we can write a whole compiler for mapping circuits to architectures.
Mappers for Minimizing Circuit Size
The mapper needs to find a placement of qubits on the hardware such that — at least some part of— the input circuit can be executed. We simplify matters and only look at the set of gates that might be executed next (a set of disjoint gates). The architecture may, and probably will, prevent us from executing some of these gates. We comprise and find some “good” placement of qubits that can execute at least a subset of the gates. The specific mapper decides what is a good placement.
A simple mapper routine is to just make sure that the cheapest gate can be executed. Here, cheapest means with the least estimated movement. This mapper finds the cheapest movement of qubits such that that at least one gate can be executed.
Note that the simple mapper does not care about what is done to the remaining qubits. Instead, we modify it to also try to move the remaining qubits closer; we can save a few gates in overhead by moving qubits in parallel instead of sequentially. All gates need to be performed eventually, so the mapper tries to minimize the overhead by also moving some other qubits involved in gates closer to one another. When it finds savings, it does the movement. This mapper turns out to do reasonably well and is competitive with the mapper included with Qiskit. However, it can be quite slow, and it does not work so well for small random circuits (as used for the tests in this challenge).
In the end, we submitted a hybrid mapper. Qiskit’s mapper can fail to find a good placement of qubits, in which case it runs a fallback routine similar to repeating the simple mapper that we discussed. Instead of the fallback, we first try to use our second mapper to do better. If it finds savings, then we use it; otherwise, it is only as good as the simple mapper so we fall back to that. The resulting hybrid mapper fairly consistently performs better than Qiskit, both in time and overhead efficiency.
Conclusion
The Qiskit developer challenge forced us to take a good look at how well our software was doing in some respects. We had been looking at the depth of circuits and not the size. It turns out that these two can have very different optimization strategies. We are currently working on a scientific paper that will go into more depth and also discuss larger sized circuits. Furthermore, we are planning to release software tool so you can map your own quantum circuits onto various architectures.
