Applications de l'informatique quantique - Optimisation

Les problèmes d'optimisation se retrouvent dans de nombreux secteurs d'activité. En voici quelques exemples :

• Optimisation du portefeuille. Un gestionnaire de fonds dispose d'une certaine somme d'argent à investir. Quelle est l'allocation optimale de ces fonds ?
• Optimisation des itinéraires. Un camion FedEx doit livrer 50 colis. Quel est l'itinéraire optimal pour livrer les colis ?
• Sécurité dans les aéroports. Un aéroport souhaite installer des caméras de sécurité pour surveiller tous les coins de l'aéroport. Quelle est la disposition optimale des caméras pour atteindre cet objectif ?

Chaque optimisation s'accompagne d'une définition de ce qui constitue une solution optimale et d'un ensemble de contraintes. Examinons la solution optimale et certaines contraintes possibles pour chaque exemple :

Optimisation du portefeuille. Le gestionnaire de fonds peut chercher à obtenir le rendement le plus élevé avec le risque le plus faible. La contrainte peut être, par exemple, de ne pas investir plus de 5 % du portefeuille dans un seul actif.

Optimisation de l'itinéraire :le camion FedEx peut vouloir effectuer ses livraisons en un minimum de temps. D'autres définitions de la solution optimale, au lieu du temps de livraison le plus court, pourraient être l'itinéraire le moins coûteux, en tenant compte des frais de carburant et de péage, ou l'itinéraire qui génère l'empreinte carbone la plus faible. La contrainte pourrait être de ne pas emprunter certaines routes résidentielles avant 8 heures du matin.

Sécurité de l'aéroport. L'aéroport peut souhaiter couvrir tous les couloirs avec le plus petit nombre de caméras. Une contrainte pourrait être qu'il doit y avoir au moins une caméra dans chaque hall.

Il est facile de voir comment les problèmes d'optimisation peuvent devenir exceptionnellement complexes. Le camion FedEx avec 50 arrêts a environ 30 vigintillions
(soit 3 x 10^64) options possibles. Même si l'optimisation peut être réalisée dans un délai raisonnable, il peut être nécessaire de la refaire à tout moment : Il y a un embouteillage important sur l'itinéraire, le prix d'un bien a baissé, ce qui le rend plus intéressant à l'achat, etc.

Mais lorsque les problèmes sont difficiles, leur résolution peut s'avérer très payante. Une entreprise de logistique qui économise 15 % sur les coûts de carburant grâce à l'optimisation des itinéraires peut augmenter ses bénéfices ou accroître sa part de marché. Un portefeuille optimal est bénéfique pour le client, le gestionnaire de portefeuille et son employeur.

La difficulté de résoudre ces problèmes et le gain que représente l'obtention des meilleures réponses sont les principales raisons pour lesquelles les entreprises envisagent l'informatique quantique. Pour replacer cette question dans un contexte financier, le Boston Consulting Group a récemment estimé que la résolution des problèmes d'optimisation à l'aide d'ordinateurs quantiques pouvait générer une valeur comprise entre 110 et 210 milliards de dollars.

Voici ce que cela donne avec Classiq :

Prenons le problème de la sécurité dans les aéroports. Ce type de problème est connu sous le nom de "max vertex cover". 

L'utilisateur spécifie la configuration ou le plan de l'aéroport et le nombre de caméras qu'il souhaite utiliser, et le moteur de synthèse de Classiq établit les mathématiques du problème. 

En termes techniques, l'utilisateur fournit un graphe d'arêtes pondérées et la taille de la couverture des sommets. Classiq fournit une fonction qui définit le problème, les contraintes et la solution. Le problème est ensuite résolu à l'aide de QAOA (Quantum Approximate Optimization Algorithm). Il s'agit d'un algorithme hybride - une partie quantique (fonction de coût quantique codant la solution ou la valeur d'espérance que nous voulons optimiser, une fonction de mélangeur quantique pour explorer chaque solution possible, un ansatz quantique ou un état initial paramétré), et une partie d'optimisation classique (dans notre cas, nous utilisons le package Pyomo ).

Ici, nous spécifions un graphique en étoile avec trois nœuds extérieurs, comme illustré ci-dessous. Par souci de commodité, nous avons attribué un numéro à chaque nœud. Si nous n'avons qu'une seule caméra, quelle position couvrirait toutes les zones de l'aéroport ?

import networkx comme nx
import pyomo.core sous 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)

    return model


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(result)

‍

Une fois le circuit généré, un circuit interactif apparaît dans une nouvelle fenêtre. La structure du circuit est clairement visible et nous pouvons approfondir n'importe quelle partie du circuit en cliquant sur l'icône plus dans le coin supérieur gauche.

Lorsque nous exécutons ce circuit avec le QAOA et que nous imprimons les résultats, nous obtenons la solution suivante (choisie parce que l'algorithme cherche à minimiser la fonction "coût").

La liste correspond aux emplacements potentiels de la caméra, de sorte que la position 0, le nœud central, devrait être dotée d'une caméra.

‍

Intéressé à voir ce que la plateforme Classiq peut apporter à votre organisation ? Contactez-nous pour planifier une démonstration

‍