QAOA: Optimierungsalgorithmus fĂĽrs Quantencomputing in der Praxis
Mit dem Quantum Approximation Optimization Algorithm lassen sich Quantencomputer fĂĽr viele kombinatorische Probleme einsetzen, etwa fĂĽr den maximalen Schnitt.
- Armin Berberovic
Optimierungsalgorithmen finden sich vielerorts: In der Luftfahrt plant man mit ihnen Flugrouten, das Finanzwesen verbessert mit ihnen das Portfoliomanagement und die Pharmaindustrie beschleunigt mit ihnen den Entwicklungsprozess neuer Medikamente. Sie sind das RĂĽckgrat vieler Industriezweige, und an ihrer Weiterentwicklung wird eifrig geforscht.
Ein vielversprechendes Kapitel der Forschung beginnt dort, wo Optimierungsalgorithmen auf Quantencomputer treffen. Die Hoffnung: Durch diese Verbindung lassen sich komplexe Optimierungsprobleme schneller lösen als mit klassischen Verfahren. Dafür sind jedoch neue Algorithmen erforderlich.
- Der Quantum Approximation Optimization Algorithm kombiniert Quantencomputer mit klassischen Maschinen.
- QAOA lässt sich für eine Vielzahl kombinatorischer Optimierungsprobleme wie das des maximalen Schnitts einsetzen.
- Der Algorithmus nutzt unterschiedliche Quantengatter und nähert sich iterativ einer optimalen Lösung an.
Ein Algorithmus, bei dem Quantencomputer einen Geschwindigkeitsvorteil versprechen, ist der Quantum Approximation Optimization Algorithm (QAOA). Er ist aus zweierlei Gründen interessant: Zum einen lässt sich mit QAOA eine Vielzahl praxisrelevanter Optimierungsprobleme lösen, darunter Klassiker wie das Problem des Handlungsreisenden, das Rucksackproblem oder die Suche nach dem maximalen Schnitt (MaxCut). Außerdem ist QAOA hervorragend für heutige Quantencomputer geeignet, da es sich um einen hybriden Algorithmus handelt, das heißt, er rechnet sowohl auf klassischen als auch auf Quantencomputern.
Das war die Leseprobe unseres heise-Plus-Artikels "QAOA: Optimierungsalgorithmus fürs Quantencomputing in der Praxis". Mit einem heise-Plus-Abo können Sie den ganzen Artikel lesen.
