Speichereffiziente Quanten-Optimierung für das Traveling Salesman Problem via binäre Kodierung von gültigen Lösungen

Speichereffiziente Quanten-Optimierung für das Traveling Salesman Problem via binäre Kodierung von gültigen Lösungen

Abstract:

Das Traveling Salesperson Problem (TSP) ist eine klassische kombinatorische Optimierungsaufgabe mit zahlreichen Anwendungen in Logistik, Planung und Terminbestimmung. Quantenalgorithmen, insbesondere der Quantum Approximate Optimization Algorithm (QAOA), haben bereits Potenzial gezeigt, um solche NP-schweren Probleme zu lösen und könnten gegenüber klassischen Methoden Vorteile bieten. Bestehende Quantenverfahren für das TSP verwenden üblicherweise eine One-Hot-Kodierung, die für ein TSP mit n Städten O(n^2) Qubits erfordert und constraintspezifische Mixer wie den XY-Mixer einsetzt, um im gültigen Zustandsraum zu bleiben. Diese Ansätze sind jedoch ressourcenintensiv und stoßen bei steigender Qubit-Zahl schnell an praktische Grenzen. In dieser Masterarbeit wird eine neue Kodierung für das TSP unter Nutzung von QAOA vorgestellt, bei der Permutationen in Binärform abgebildet werden und der Qubit-Bedarf so auf O(n log2 n) sinkt. Die größte Schwierigkeit dieser Binärkodierung liegt darin, dass kein einfacher constraintspezifischer Mixer verfügbar ist, um während der Optimierung die Gültigkeit der Zustände sicherzustellen. Zur Lösung dieses Problems wird eine effizient realisierbare unitäre Transformation entwickelt, die jedem binär kodierten Rundweg einen eindeutigen Index zuweist. Durch das Hinzufügen von O(log2(n!)) zusätzlichen Qubits, welche jede mögliche TSP-Permutation in faktorieller Basis repräsentieren, entsteht eine kanonische Isomorphie zwischen Permutationen und faktoriellel kodierten Zahlen. Dadurch kann in diesem zusätzlichen Qubit-Bereich ein einfacher X-Mixer oder ein Grover-Mixer verwendet werden, sodass sich der Optimierungsprozess automatisch auf gültige Zustände beschränkt und die Nebenbedingungen während der gesamten Optimierung eingehalten werden. Dies ermöglicht eine schnellere Konvergenz in Richtung der optimalen Lösung. In Rahmen dieser Masterarbeit werden es drei Varianten dieser Kodierung untersucht: (1) eine direkte unitäre Transformation mithilfe einer vorberechneten Lookup-Tabelle, (2) ein Verfahren auf Basis von Quantenarithmetik sowie (3) ein reines Index-Verfahren, bei dem sowohl Kosten- als auch Mixer-Hamiltonoperatoren in [log2(n!)] Qubits kodiert werden, was allerdings zu tieferen Schaltkreisen führt. Numerische Experimente mit kleinen Problemgrößen zeigen die Realisierbarkeit dieser Ansätze und unterstreichen die möglichen Vorteile des platzsparenden Kodierungsschemas für praktische Quantenoptimierungsaufgaben.

Autor/in:

Viktoria Patapovich

Betreuer:

Studentische Abschlussarbeit | Veröffentlicht Januar 2025 | Copyright © QAR-Lab
Anfragen zu dieser Arbeit an die Betreuer