A quadratic unconstrained binary optimization approach for qubit mapping

Abstract

Logische Bitoperationen sind die Grundbausteine von Computer Software. Hierbei werden Bits manipuliert, um verschiedene Aufgaben auszuführen, beispielsweise bitweise AND-, OR-, XOR- und NOT-Operationen. Dies ist der Quantensoftware sehr ähnlich. Hier werden sogenannte Quantum Gates - die Quantengegenstücke von klassischen Bitoperationen - zur Manipulation von Quantenbits, der kleinsten Einheit der Quanteninformation, verwendet.Die Zuordnung von logischen Qubits in einem Quantenprogramm zu den physischen Qubits eines Quantencomputers wird als Qubit-Mapping bezeichnet. Dieser Schritt ist Teil der Kompilierung eines Quantenprogramms und daher Vorraussetung für die Ausführbarkeit jedes Quantenprogramms auf einem Quantencomputer. Während dieses Mapping-Schritts werden zusätzliche Operationen in das Programm eingebaut, die für die Ausführbarkeit des Programms notwendig sind. Da Quantencomputer aktuell eine sehr begrenzte Rechenleistung haben, ist das Ziel so wenig zusätzliche Operationen wie möglich in das Quantenprogramm durch das Mapping einzubauen. Das Qubit-Mapping Problem beschreibt das Optimierungsproblem, welches diese notwendigen zusätzlichen Operationen minimiert.Es wird in dieser Arbeit eine neue Methode zur Lösung des Qubit-Mapping Problems vorgestellt, die auf quadratischer unbeschränkter binärer Optimierung und einem evolutionären Algorithmus basiert. Der Ansatz erzielt für eine Reihe von Quantenprogrammen signifikant bessere Lösungen zu aktuellen Mapping-Algorithmen.

Logical bit operations are an essential part of computer programming. They involve manipulating individual bits within binary numbers to perform various tasks, such as bitwise AND, OR, XOR, and NOT operations. This is very similar to quantum software, where quantum logic gates are the quantum counterparts of classical logical bit operations and are used to manipulate quantum bits, the quantum equivalent to a bit and thus, the unit of quantum information.In order to run a quantum software on a quantum computer, the logical qubits used in the program have to be assigned to the physical qubits on the hardware. The act of assigning logical qubits in a quantum program to physical qubits on a quantum computer is called qubit mapping. It is a vital part of a quantum program's compilation as it affects how well the program will run on a quantum computer. The qubit mapping problem is the corresponding mathematical problem that aims to minimize the changes to a quantum program needed in order to make it executable on a quantum computer. This is a crucial objective since current quantum devices have limited computing power, making it difficult to carry out long and complex computations. Improving the qubit mapping can thus significantly enhance the performance of quantum programs.Because of its great importance, the qubit mapping problem has been studied and approached in recent years with a wide range of different techniques. This work aligns itself among these techniques, however, presents a new strategy by using a type of optimization called quadratic unconstrained binary optimization in order to improve upon existing results. The evaluation showed, that within some of the relevant benchmarks, results from this approach are similar to or better than other existing algorithms.