Planning Qubit Movements in Fully Connected Star Graphs

Abstract

Building a working quantum computer brings many challenges to overcome. For quanum processors, promising qubits seem to be NV-centres in diamond. Such processor is divided into processing units (PUs), each comprising an NV-centre with several carbon spin qubits, and they are interconnected with each other by optical links. The qubits within a PU can be modelled as nodes in a star graph and the optical connections as connections between the centres of the star graphs, such that the centres with their interconnections form a complete graph. We call the overall graph a fully connected star graph. In order to execute a quantum circuit, multiple pairs of qubits should be brought together in PUs at different times, which requires planning. Sorting the qubits is done via swaps. A swap within a PU can be performed easily, however, swapping between different PUs is done by teleportation, which is much more costly. Therefore, we neglect the costs of swaps within PUs. Parallellisation of swaps between PUs is done in a step. The less steps are used, the faster the quantum circuit is executed. In practice, as we are interested in fast computations, we often want to minimize the number of steps. The following problem is addressed. Given a current distribution of the qubits over the nodes in the fully connected star graph, and given a wanted, permuted distribution, minimize the number of swaps and/or steps to route the qubits from the current to the wanted distribution. At the moment, no efficient algorithm exists to sort the qubits especially in fully connected star graphs. Efficient solutions are presented in the form of algorithms. It is shown that qubit moves in fully connected star graphs can be scheduled efficiently, such that the number of moves is minimized. Guide lines are given to minimize the execution time too.