Quantencomputing-Anwendungen - Optimierung

Optimierungsprobleme gibt es in zahlreichen Branchen. Hier sind nur einige Beispiele:

• Optimierung des Portfolios. Ein Vermögensverwalter hat einen bestimmten Geldbetrag zu investieren. Wie sieht die optimale Aufteilung dieser Mittel aus?
• Optimierung der Route. Ein FedEx-LKW muss 50 Pakete ausliefern. Was ist die optimale Route für die Zustellung der Pakete?
• Sicherheit am Flughafen. Ein Flughafen möchte Sicherheitskameras installieren, um alle Ecken des Flughafens zu überwachen. Wie sieht die optimale Anordnung der Kameras aus, um dies zu erreichen?

Für jede Optimierung gibt es eine Definition, was eine optimale Lösung ist, und eine Reihe von Beschränkungen. Lassen Sie uns die optimale Lösung und einige mögliche Beschränkungen für jedes Beispiel untersuchen:

Portfolio-Optimierung. Der Vermögensverwalter könnte die höchste Rendite mit dem geringsten Risiko anstreben. Die Beschränkung könnte beispielsweise darin bestehen, nicht mehr als 5 % des Portfolios in einen einzelnen Vermögenswert zu investieren.

Routenoptimierung:Der FedEx-LKW möchte die Lieferungen in möglichst kurzer Zeit erledigen. Eine alternative Definition der optimalen Lösung könnte anstelle der kürzesten Lieferzeit die kostengünstigste Route unter Berücksichtigung von Kraftstoff- und Mautgebühren oder die Route mit der geringsten CO2-Bilanz sein. Die Einschränkung könnte darin bestehen, bestimmte Wohnstraßen nicht vor 8 Uhr morgens zu befahren.

Flughafensicherheit. Der Flughafen möchte vielleicht alle Korridore mit einer möglichst geringen Anzahl von Kameras abdecken. Eine Einschränkung könnte sein, dass in jeder Halle mindestens eine Kamera vorhanden sein muss.

Es ist leicht zu erkennen, wie Optimierungsprobleme außergewöhnlich komplex werden können. Der FedEx-LKW mit 50 Haltestellen hat etwa 30 Vigintillionen
(das sind 3 x 10^64) mögliche Optionen. Selbst wenn die Optimierung in einer angemessenen Zeit abgeschlossen werden kann, muss sie möglicherweise in einem Augenblick neu durchgeführt werden: Es gibt einen größeren Stau auf der Strecke, der Preis eines Wirtschaftsguts ist gesunken, so dass es attraktiver geworden ist, es zu kaufen, usw.

Aber wenn die Probleme schwierig sind, kann ihre Lösung eine große Belohnung sein. Ein Logistikunternehmen, das durch eine optimierte Streckenführung 15 % der Treibstoffkosten einspart, kann seine Gewinne steigern oder seinen Marktanteil vergrößern. Ein optimales Portfolio ist gut für den Kunden, den Portfoliomanager und seinen Arbeitgeber.

Die Schwierigkeit, diese Probleme zu lösen, und der Gewinn, der sich aus den besten Antworten ergibt, sind die Hauptgründe dafür, dass Unternehmen Quantencomputer in Betracht ziehen. Um dies in einen finanziellen Kontext zu stellen, schätzte die Boston Consulting Group kürzlich, dass durch die Lösung von Optimierungsproblemen mit Hilfe von Quantencomputern ein Wert von 110 bis 210 Mrd. USD freigesetzt werden kann.

So sieht es mit Classiq aus:

Nehmen wir das Problem der Flughafensicherheit. Diese Art von Problem ist als "Max Vertex Cover"-Problem bekannt. 

Der Benutzer gibt die Konfiguration oder den Grundriss des Flughafens und die Anzahl der Kameras an, die er verwenden möchte, und die Classiq-Synthese-Engine stellt die mathematische Lösung des Problems auf. 

Technisch ausgedrückt, gibt der Benutzer einen gewichteten Kantengraphen und die Größe der Scheitelpunktabdeckung an. Classiq liefert eine Funktion, die das Problem, die Einschränkungen und die Lösung definiert. Das Problem wird dann mit QAOA (Quantum Approximate Optimization Algorithm) gelöst. Dabei handelt es sich um einen hybriden Algorithmus mit einem Quantenanteil (Quantenkostenfunktion, die die Lösung oder den Erwartungswert kodiert, den wir optimieren wollen, eine Quantenmischfunktion, um jede mögliche Lösung zu untersuchen, einen Quantenansatz oder einen parametrisierten Anfangszustand) und einem klassischen Optimierungsteil (in unserem Fall verwenden wir das Pyomo-Paket ).

Hier geben wir ein Sterndiagramm mit drei äußeren Knoten an, wie unten abgebildet. Der Einfachheit halber haben wir jeden Knoten mit einer Nummer versehen. Wenn wir nur eine Kamera haben, welche Position würde alle Bereiche des Flughafens abdecken?

import networkx as nx
import pyomo.core as pyo
from classiq import combinatorial_optimization
from classiq_interface.combinatorial_optimization.preferences import QAOAPreferences
from classiq_interface.combinatorial_optimization.solver_types import QSolver


def mvc(graph: nx.Graph, k: int) -> pyo.ConcreteModel:
    model = pyo.ConcreteModel()
    model.x = pyo.Var(graph.nodes, domain=pyo.Binary)
    model.amount_constraint = pyo.Constraint(expr=sum(model.x.values()) == k)

    def obj_expression(model):
        return sum((1 - model.x[i]) * (1 - model.x[j]) for i, j in graph.edges)

    model.cost = pyo.Objective(rule=obj_expression, sense=pyo.minimize)

    Modell zurückgeben


G = nx.star_graph(3)
mvc_model = mvc(G, 1)

qaoaP = QAOAPreferences(qsolver=QSolver.QAOAMixer)
mvc_problem = combinatorial_optimization.CombinatorialOptimization(model=mvc_model,
                                                                   qaoa_preferences=qaoaP)
qc = mvc_problem.generate()
qc.show_interactive()

open("MVC_interactive_circuit.html", "w").write(qc.interactive_html)

result = mvc_problem.solve()
print(ergebnis)

‍

Sobald wir die Schaltung erstellt haben, wird eine interaktive Schaltung in einem neuen Fenster angezeigt. Die Struktur des Schaltkreises ist klar zu erkennen, und wir können in jeden Teil des Schaltkreises tiefer eintauchen, indem wir auf das Plus-Symbol in der oberen linken Ecke klicken.

Wenn wir diese Schaltung mit dem QAOA ausführen und die Ergebnisse ausdrucken, erhalten wir diese Lösung (die gewählt wurde, weil der Algorithmus auf die Minimierung der "Kostenfunktion" hinarbeitet).

Die Liste entspricht den potenziellen Kamerastandorten, so dass Position 0, der mittlere Knoten, eine Kamera haben sollte.

‍

Möchten Sie sehen, was die Classiq-Plattform für Ihr Unternehmen leisten kann? Kontaktieren Sie uns, um eine Demo zu vereinbaren

‍