A Survey of Qubit Routing Algorithms

Before applications actually run on quantum hardware, the design of the quantum application and its pre-processing take place in the classical environment. Transforming a quantum circuit into a form that is able to run on quantum hardware, known as transpilation, is a crucial process in performing quantum experiments. Routing is a particularly important and computationally expensive part of the transpilation process. The routing process can alter a circuit’s accuracy, execution time, quantum gate count, and depth. Several routing algorithms exist that aim to optimize some portion of the routing process. There are many variables to consider when choosing an optimal routing algorithm, such as routing time, circuit accuracy, gate count, circuit execution time, and more. Identifying what routing algorithm is best for a given quantum experiment based on various properties can allow researchers to make informed routing decisions, as well as optimize target aspects of their work. This thesis draws connections between the properties of circuits, hardware, and routing algorithms to identify when a specific routing algorithm will outperform the others.