Quantum Approximate Optimization Algorithm

Der Quantum Approximate Optimization Algorithm (QAOA) ist ein hybrider Quanten-klassischer Algorithmus, der entwickelt wurde, um approximative Lösungen für kombinatorische Optimierungsprobleme zu finden. Er eignet sich besonders gut für Probleme, die als Minimierung einer Kostenfunktion über eine diskrete Menge von Variablen formuliert werden können, wie das Max-Cut-Problem oder das Traveling Salesperson Problem. QAOA arbeitet in Schichten und wechselt zwischen der Anwendung eines 'problem Hamiltonian' (der die Kostenfunktion kodiert) und eines 'mixer Hamiltonian' (der die Erkundung des Lösungsraums ermöglicht). Die Parameter, die die Dauer oder Stärke dieser Hamiltonian-Anwendungen steuern, sind klassische Variablen, die iterativ optimiert werden. Ein klassischer Computer wird verwendet, um den Quantenzustand vorzubereiten, die Quantenschaltung für einen gegebenen Satz von Parametern auszuführen, den resultierenden Zustand zu messen, um den Wert der Kostenfunktion abzuschätzen, und dann die Parameter mithilfe einer klassischen Optimierungsroutine (z. B. Gradientenabstieg) zu aktualisieren. Dieser Prozess wiederholt sich, bis die Parameter konvergieren und eine approximative Lösung liefern. QAOA gilt als Near-Term Quantum Algorithm, was bedeutet, dass er für den Einsatz auf aktuellen oder zukünftigen Noisy Intermediate-Scale Quantum (NISQ) Geräten konzipiert ist. Seine Effektivität hängt von der Tiefe der Schaltung (Anzahl der Schichten) und der Qualität des klassischen Optimierers ab.