Mapping of quantum algorithms on a quantum chip

Abstract

Quantum algorithms can be described by quantum circuits which consist of quantum bits (qubits) and quantum gates. Such a circuit description assumes that any kind of interaction between qubits is possible. However, quantum chips have limited qubits connectivity only allowing, for instance, nearest-neighbor (NN) interactions. That means, qubits need to be placed in adjacent positions for performing a two-qubit gate. In this thesis, a routing algorithm is proposed where physical qubits or planar-based logical qubits are routed to obey this nearest neighbor constraint in a 2D qubit topology. This algorithm tries to minimize the circuit latency or communication overhead.

The proposed routing algorithm is based on a sliding window principle. Different paths, found by using an adapted breadth-first search algorithm, are evaluated based on the interleaving of the corresponding routing instructions, e.g., SWAP operations with previous instructions, and by looking at the disordering of future qubits. The path that will add the lowest number of cycles to the algorithm is then selected and efficiently inserted with the rest of the instructions. This process continues until all the instructions inside the quantum algorithm obey the nearest neighbor constraints.

The routing algorithm is tested for several real quantum algorithms taken from QLib and ScaffCC, as well as for random generated benchmarks. Taking different alternative paths into account and evaluating those paths for possible interleaving with previous instructions, always has a positive effect to minimize the number of added cycles. The results concerning the evaluation of the disordering of future qubits could have a positive or negative effect on the circuit latency depending on the quantum circuit.