Aller au contenu principal

Optimization Solver : une fonction Qiskit de Q-CTRL Fire Opal

remarque

Les fonctions Qiskit sont une fonctionnalité expérimentale réservée aux utilisateurs des plans IBM Quantum® Premium, Flex et On-Prem (via l'API IBM Quantum Platform). Elles sont en version préliminaire et susceptibles d'évoluer.

Vue d'ensemble​

Avec le Fire Opal Optimization Solver, tu peux résoudre des problèmes d'optimisation à l'échelle utilitaire sur du matériel quantique, sans avoir besoin d'expertise en informatique quantique. Il suffit de fournir la définition du problème de haut niveau — le Solver s'occupe du reste. L'ensemble du flux de travail est sensible au bruit et exploite la gestion des performances Fire Opal en arrière-plan. Le Solver fournit de manière constante des solutions précises à des problèmes difficiles à résoudre classiquement, même à l'échelle complète d'un appareil sur les plus grands QPU IBM®.

Le Solver est flexible et peut être utilisé pour résoudre des problèmes d'optimisation combinatoire définis comme des fonctions objectif ou des graphes arbitraires. Les problèmes n'ont pas à être mappés à la topologie de l'appareil. Les problèmes non contraints et contraints sont résolubles, à condition que les contraintes puissent être formulées comme des termes de pénalité. Les exemples de ce guide montrent comment résoudre un problème d'optimisation non contraint et un problème contraint à l'échelle utilitaire en utilisant différents types d'entrées du Solver. Le premier exemple porte sur un problème Max-Cut défini sur un graphe 3-régulier à 156 nœuds, tandis que le second aborde un problème de couverture minimale de sommets (Minimum Vertex Cover) à 50 nœuds défini par une fonction de coût.

Pour accéder à l'Optimization Solver, contacte Q-CTRL.

Description de la fonction​

Le Solver optimise et automatise entièrement l'algorithme, depuis la suppression des erreurs au niveau matériel jusqu'au mappage efficace du problème et à l'optimisation classique en boucle fermée. En coulisses, le pipeline du Solver réduit les erreurs à chaque étape, permettant d'atteindre les performances nécessaires pour monter en charge de façon significative. Le flux de travail sous-jacent s'inspire de l'algorithme QAOA (Quantum Approximate Optimization Algorithm), un algorithme hybride quantique-classique. Pour un résumé détaillé du flux de travail complet de l'Optimization Solver, consulte le manuscrit publié.

Visualisation du flux de travail de l'Optimization Solver

Pour résoudre un problème générique avec l'Optimization Solver :

  1. Définis ton problème sous forme de fonction objectif, de graphe ou de chaîne de spin SparsePauliOp.
  2. Connecte-toi à la fonction via le catalogue de fonctions Qiskit.
  3. Lance le problème avec le Solver et récupère les résultats.

Entrées et sorties​

Entrées​

NomTypeDescriptionRequisDéfautExemple
problemstr ou SparsePauliOpL'une des représentations listées sous « Formats de problèmes acceptés »OuiN/APoly(2.0*n[0]*n[1] + 2.0*n[0]*n[2] - 3.13520241298341*n[0] + 2.0*n[1]*n[2] - 3.14469748506794*n[1] - 3.18897660121566*n[2] + 6.0, n[0], n[1], n[2], domain='RR')
problem_typestrNom de la classe du problème ; utilisé uniquement pour les définitions de graphes et de chaînes de spin, limitées à « maxcut » ou « spin_chain » ; non requis pour les fonctions objectif arbitrairesNonNone"maxcut"
backend_namestrNom du backend à utiliserNonLe backend le moins occupé auquel ton instance a accès"ibm_fez"
optionsdictOptions d'entrée, dont : (Optionnel) session_id : str ; par défaut, crée une nouvelle sessionNonNone{"session_id": "cw2q70c79ws0008z6g4g"}

Formats de problèmes acceptés :

  • Représentation polynomiale d'une fonction objectif. Idéalement créée en Python à partir d'un objet SymPy Poly existant et mise en chaîne avec sympy.srepr.
  • Représentation par graphe d'un type de problème spécifique. Le graphe doit être créé avec la bibliothèque networkx en Python, puis converti en chaîne via la fonction networkx [nx.readwrite.json_graph.adjacency_data](http://nx.readwrite.json_graph.adjacency_data.).
  • Représentation en chaîne de spin d'un problème spécifique. La chaîne de spin doit être représentée sous la forme d'un objet SparsePauliOp ; consulte la documentation pour plus de détails.

Backends pris en charge : Exécute le code suivant pour voir la liste des backends actuellement pris en charge. Si ton appareil n'est pas listé, contacte Q-CTRL pour en demander la prise en charge.

# Added by doQumentation — required packages for this notebook
!pip install -q networkx numpy qiskit-ibm-catalog qiskit-ibm-runtime sympy
from qiskit_ibm_runtime import QiskitRuntimeService

service = QiskitRuntimeService()

service.backends()
[<IBMBackend('ibm_fez')>,
 <IBMBackend('ibm_brisbane')>,
 <IBMBackend('ibm_pittsburgh')>,
 <IBMBackend('ibm_kingston')>,
 <IBMBackend('ibm_torino')>,
 <IBMBackend('ibm_marrakesh')>]

Options :

NomTypeDescriptionDéfaut
session_idstrIdentifiant d'une session Qiskit Runtime existante"cw4r3je6f0t010870y3g"
job_tagslist[str]Liste d'étiquettes de tâches[]

Sorties​

NomTypeDescriptionExemple
resultdict[str, Any]Solution et métadonnées listées sous « Contenu du dictionnaire de résultats »{'solution_bitstring_cost': 3.0, 'final_bitstring_distribution': {'000001': 100, '000011': 2}, 'iteration_count': 3, 'solution_bitstring': '000001', 'variables_to_bitstring_index_map': {n[1]': 5, 'n[2]': 4, 'n[3]': 3, 'n[4]': 2, 'n[5]': 1}, 'best_parameters': [0.19628831763697097, -1.047052334523102], 'warnings': []}

Contenu du dictionnaire de résultats :

NomTypeDescription
solution_bitstring_costfloatLe meilleur coût minimum sur toutes les itérations
final_bitstring_distributionCountsDictLe dictionnaire de comptage de chaînes de bits associé au coût minimum
solution_bitstringstrLa chaîne de bits avec le meilleur coût dans la distribution finale
iteration_countintLe nombre total d'itérations QAOA effectuées par le Solver
variables_to_bitstring_index_mapfloatLa correspondance entre les variables et le bit équivalent dans la chaîne de bits
best_parameterslist[float]Les paramètres bêta et gamma optimisés sur toutes les itérations
warningslist[str]Les avertissements produits lors de la compilation ou de l'exécution de QAOA (par défaut None)

Benchmarks​

Les résultats de benchmarking publiés montrent que le Solver résout avec succès des problèmes dépassant 120 qubits, surpassant même des résultats précédemment publiés sur des recuits quantiques et des appareils à ions piégés. Les métriques de benchmark suivantes donnent une indication approximative de la précision et de la mise à l'échelle des types de problèmes, sur la base de quelques exemples. Les métriques réelles peuvent varier selon les caractéristiques du problème, comme le nombre de termes dans la fonction objectif (densité) et leur localité, le nombre de variables et l'ordre polynomial.

Le « Nombre de qubits » indiqué n'est pas une limite absolue, mais représente des seuils approximatifs en dessous desquels tu peux t'attendre à une précision de solution extrêmement constante. Des tailles de problèmes plus importantes ont été résolues avec succès, et les tests au-delà de ces limites sont encouragés.

La connectivité arbitraire entre qubits est prise en charge pour tous les types de problèmes.

Type de problèmeNombre de qubitsExemplePrécisionTemps total (s)Utilisation du runtime (s)Nombre d'itérations
Problèmes quadratiques faiblement connectés156Max-Cut 3-régulier100 %176429316
Optimisation binaire d'ordre supérieur156Modèle de verre de spin d'Ising100 %146127216
Problèmes quadratiques densément connectés50Max-Cut entièrement connecté100 %175826812
Problème contraint avec termes de pénalité50Couverture minimale de sommets pondérée avec 8 % de densité d'arêtes100 %107421510

Premiers pas​

Commence par t'authentifier avec ta clé API IBM Quantum. Sélectionne ensuite la fonction Qiskit comme suit. (Cet extrait suppose que tu as déjà enregistré ton compte dans ton environnement local.)

from qiskit_ibm_catalog import QiskitFunctionsCatalog

catalog = QiskitFunctionsCatalog(channel="ibm_quantum_platform")

# Access Function
solver = catalog.load("q-ctrl/optimization-solver")

Exemple : optimisation non contrainte​

Lance le problème de coupe maximale (Max-Cut). L'exemple suivant illustre les capacités du Solver sur un problème Max-Cut avec un graphe non pondéré 3-régulier à 156 nœuds, mais tu peux aussi résoudre des problèmes de graphes pondérés. En plus de qiskit-ibm-catalog, tu utiliseras également les packages suivants pour cet exemple : networkx et numpy. Tu peux les installer en décommentant la cellule suivante si tu exécutes cet exemple dans un notebook avec le noyau IPython.

# %pip install networkx numpy

1. Définir le problème​

Tu peux lancer un problème Max-Cut en définissant un problème de graphe et en spécifiant problem_type='maxcut'.

import networkx as nx
import numpy as np

# Generate a random graph with 156 nodes
maxcut_graph = nx.random_regular_graph(d=3, n=156, seed=8)
# Optionally, visualize the graph
nx.draw_networkx(
    maxcut_graph, nx.kamada_kawai_layout(maxcut_graph), node_size=100
)

Sortie de la cellule de code précédente

Le Solver accepte une chaîne de caractères comme entrée pour la définition du problème.

# Convert graph to string
problem_as_str = nx.readwrite.json_graph.adjacency_data(maxcut_graph)

2. Lancer le problème​

Lorsque tu utilises la méthode d'entrée par graphe, spécifie le type de problème.

# This cell is hidden from users
from qiskit_ibm_runtime import QiskitRuntimeService

service = QiskitRuntimeService()
backend_name = service.least_busy(n_qubits=156).name
# Solve the problem
maxcut_job = solver.run(
    problem=problem_as_str,
    problem_type="maxcut",
    backend_name=backend_name,  # E.g. "ibm_fez"
)

Vérifie le statut de ta charge de travail de fonction Qiskit ou récupère les résultats comme suit :

# Get job status
print(maxcut_job.status())
QUEUED

3. Récupérer le résultat​

Récupère la valeur de coupe optimale depuis le dictionnaire de résultats.

remarque
La correspondance des variables vers la chaîne de bits peut avoir changé. Le dictionnaire de sortie contient un sous-dictionnaire variables_to_bitstring_index_map qui permet de vérifier l'ordre.
# Poll for results
maxcut_result = maxcut_job.result()

# Take the absolute value of the solution since the cost function is minimized
qctrl_maxcut = abs(maxcut_result["solution_bitstring_cost"])

# Print the optimal cut value found by the Optimization Solver
print(f"Optimal cut value: {qctrl_maxcut}")
Optimal cut value: 209.0

Tu peux vérifier la précision du résultat en résolvant le problème classiquement avec des solveurs open-source comme PuLP si le graphe n'est pas densément connecté. Les problèmes à haute densité peuvent nécessiter des solveurs classiques avancés pour valider la solution.

Exemple : optimisation contrainte​

L'exemple Max-Cut précédent est un problème d'optimisation binaire quadratique non contraint classique. L'Optimization Solver de Q-CTRL peut être utilisé pour divers types de problèmes, y compris l'optimisation contrainte. Tu peux résoudre des types de problèmes arbitraires en fournissant la définition du problème sous forme de polynôme où les contraintes sont modélisées comme des termes de pénalité.

L'exemple suivant montre comment construire une fonction de coût pour un problème d'optimisation contraint, la couverture minimale de sommets (MVC). En plus des packages qiskit-ibm-catalog et qiskit, tu utiliseras également les packages suivants : numpy, networkx et sympy. Tu peux les installer en décommentant la cellule suivante si tu exécutes cet exemple dans un notebook avec le noyau IPython.

# %pip install numpy networkx sympy

1. Définir le problème​

Définis un problème MVC aléatoire en générant un graphe avec des nœuds pondérés aléatoirement.

import networkx as nx
from sympy import symbols, Poly, srepr

# To change the weights, change the seed to any integer.
rng_seed = 18
_rng = np.random.default_rng(rng_seed)
node_count = 50
edge_probability = 0.08
mvc_graph = nx.erdos_renyi_graph(
    node_count, edge_probability, seed=rng_seed, directed=False
)

# add node weights
for i in mvc_graph.nodes:
    mvc_graph.add_node(i, weight=_rng.random())

# Optionally, visualize the graph
nx.draw_networkx(mvc_graph, nx.kamada_kawai_layout(mvc_graph), node_size=200)

Sortie de la cellule de code précédente

Un modèle d'optimisation standard pour le MVC pondéré peut être formulé comme suit. D'abord, une pénalité doit être ajoutée pour tout cas où une arête n'est pas connectée à un sommet du sous-ensemble. Soit donc ni=1n_i = 1 si le sommet ii est dans la couverture (c'est-à-dire dans le sous-ensemble) et ni=0n_i = 0 sinon. L'objectif est de minimiser le nombre total de sommets dans le sous-ensemble, ce qui peut être représenté par la fonction suivante :

Minimizey=∑i∈Vωini\textbf{Minimize}\qquad y = \sum_{i\in V} \omega_i n_i

# Construct the cost function.
variables = symbols([f"n[{i}]" for i in range(node_count)])
cost_function = Poly(0, variables)

for i in mvc_graph.nodes():
    weight = mvc_graph.nodes[i].get("weight", 0)
    cost_function += variables[i] * weight

Désormais, chaque arête du graphe doit inclure au moins un point d'extrémité de la couverture, ce qui peut s'exprimer par l'inégalité :

ni+nj≥1 for all (i,j)∈En_i + n_j \ge 1 \texttt{ for all } (i,j)\in E

Tout cas où une arête n'est pas connectée au sommet de la couverture doit être pénalisé. Cela peut être représenté dans la fonction de coût en ajoutant une pénalité de la forme P(1−ni−nj+ninj)P(1-n_i-n_j+n_i n_j) où PP est une constante de pénalité positive. Ainsi, une alternative non contrainte à l'inégalité contrainte pour le MVC pondéré est :

Minimizey=∑i∈Vωini+P(∑(i,j)∈E(1−ni−nj+ninj))\textbf{Minimize}\qquad y = \sum_{i\in V}\omega_i n_i + P(\sum_{(i,j)\in E}(1 - n_i - n_j + n_i n_j))

# Add penalty term.
penalty_constant = 2
for i, j in mvc_graph.edges():
    cost_function += penalty_constant * (
        1 - variables[i] - variables[j] + variables[i] * variables[j]
    )

2. Lancer le problème​

# Solve the problem
mvc_job = solver.run(
    problem=srepr(cost_function),
    backend_name=backend_name,  # E.g. "ibm_fez"
)

Vérifie le statut de ta charge de travail de fonction Qiskit ou récupère les résultats comme suit :

print(mvc_job.status())

3. Obtenir le résultat​

Récupère la solution et analyse les résultats. Ce problème ayant des nœuds pondérés, la solution ne correspond pas simplement au nombre minimal de nœuds couverts. Le coût de la solution représente plutôt la somme des poids des sommets inclus dans la couverture de sommets. Il représente le « coût » ou le « poids » total de la couverture de toutes les arêtes du graphe avec les sommets sélectionnés.

mvc_result = mvc_job.result()
qctrl_cost = mvc_result["solution_bitstring_cost"]

# Print results
print(f"Solution cost: {qctrl_cost}")
Solution cost: 10.248198273708624

Support​

Pour toute question ou problème, contacte Q-CTRL.

Prochaines étapes​

Recommandations