Comparing Quantum Annealer and Metaheuristic Methods to Solve the Steiner Tree Problem

Dieses Kapitel vertieft sich in den Vergleich von Quantenglühen und metaheuristischen Methoden zur Lösung des Steinerschen Baumproblems, einer anspruchsvollen kombinatorischen Optimierungsaufgabe. Die Studie untersucht die Leistung eines Quantenglühers (QA), insbesondere des D-WAVE Advantage QA, gegenüber klassischen Methoden wie simuliertem Glühen, genetischen Algorithmen und Bergsteigen. Das Kapitel stellt eine neue QUBO-Formulierung (Quadratic Unconstrained Binary Optimization) für das Steiner-Baumproblem vor, die mithilfe der AutoQUBO-Methode abgeleitet wurde und die die Konvertierung komplexer Optimierungsprobleme in das QUBO-Format vereinfacht. Die Ergebnisse deuten darauf hin, dass die QS zwar praktikable Lösungen liefern kann, aber ihre Leistung derzeit von hybriden und klassischen simulierten Glühlösern hinsichtlich Lösungsqualität und Laufzeit übertroffen wird. Die Studie beleuchtet Schlüsselfragen wie Qubitfehler und die Berechnungskosten geringfügiger Einbettungen, die die Effizienz der QS beeinflussen. Trotz dieser Herausforderungen zeigt die QA vielversprechende Ansätze für zukünftige Fortschritte im Quantencomputerbereich. Das Kapitel behandelt auch das Potenzial von Hybridglühern, die sich als ebenso effektiv wie klassische Methoden und schneller erweisen und eine praktische Lösung bieten, während die Quantenmethoden reifen. Die Analyse liefert einen detaillierten Vergleich von Löserlaufzeiten, Lösbarkeit und Qualität und bietet damit wertvolle Erkenntnisse für Fachleute im Bereich Optimierung und Quantencomputing.