דלג לתוכן הראשי

פותר האופטימיזציה: פונקציית Qiskit מאת Q-CTRL Fire Opal

הערה

פונקציות Qiskit הן תכונה ניסיונית הזמינה רק למשתמשי IBM Quantum® Premium Plan, Flex Plan, ו-On-Prem (דרך IBM Quantum Platform API). הן בסטטוס הפצה בתצוגה מקדימה ועשויות להשתנות.

סקירה כללית​

עם Fire Opal Optimization Solver, תוכל לפתור בעיות אופטימיזציה בקנה-מידה שימושי על חומרה קוונטית מבלי שתידרש מומחיות קוונטית. פשוט הזן את הגדרת הבעיה ברמה גבוהה, והפותר ידאג לכל השאר. כל תהליך העבודה מודע לרעש ומנצל את ניהול הביצועים של Fire Opal מאחורי הקלעים. הפותר מספק באופן עקבי פתרונות מדויקים לבעיות מאתגרות קלאסית, אפילו בקנה-מידה מלא של המכשיר על ה-QPU הגדולים ביותר של IBM®.

הפותר גמיש וניתן להשתמש בו לפתרון בעיות אופטימיזציה קומבינטורית המוגדרות כפונקציות מטרה או כגרפים שרירותיים. אין צורך למפות בעיות לטופולוגיה של המכשיר. ניתן לפתור בעיות גם ללא אילוצים וגם עם אילוצים, כל עוד ניתן לנסח את האילוצים כמונחי עונשין. הדוגמאות הכלולות במדריך זה מדגימות כיצד לפתור בעיית אופטימיזציה ללא אילוצים ועם אילוצים בקנה-מידה שימושי, תוך שימוש בסוגי קלט שונים של הפותר. הדוגמה הראשונה כוללת בעיית Max-Cut המוגדרת על גרף בעל 156 צמתים ו-3-Regular, בעוד הדוגמה השנייה מתמודדת עם בעיית Minimum Vertex Cover בעלת 50 צמתים המוגדרת על ידי פונקציית עלות.

כדי לקבל גישה ל-Optimization Solver, צור קשר עם Q-CTRL.

תיאור הפונקציה​

הפותר מבצע אופטימיזציה מלאה ואוטומציה של כל האלגוריתם, החל מדיכוי שגיאות ברמת החומרה ועד מיפוי בעיות יעיל ואופטימיזציה קלאסית בלולאה סגורה. מאחורי הקלעים, הצינור של הפותר מצמצם שגיאות בכל שלב, ומאפשר את הביצועים המשופרים הנדרשים לסקאלה משמעותית. תהליך העבודה הבסיסי מבוסס על Quantum Approximate Optimization Algorithm (QAOA), שהוא אלגוריתם היברידי קוונטי-קלאסי. לסיכום מפורט של תהליך העבודה המלא של Optimization Solver, עיין במאמר המפורסם.

ויזואליזציה של תהליך העבודה של Optimization Solver

כדי לפתור בעיה גנרית עם Optimization Solver:

  1. הגדר את הבעיה שלך כפונקציית מטרה, גרף, או שרשרת ספין SparsePauliOp.
  2. התחבר לפונקציה דרך Qiskit Functions Catalog.
  3. הרץ את הבעיה עם הפותר וקבל תוצאות.

קלטים ופלטים​

קלטים​

שםסוגתיאורחובהברירת מחדלדוגמה
problemstr or SparsePauliOpאחד מהייצוגים המפורטים תחת "פורמטי בעיה מקובלים"כןN/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_typestrשם מחלקת הבעיה; בשימוש רק להגדרות בעיית גרף ושרשרת ספין, המוגבלות ל-"maxcut" או "spin_chain"; לא נדרש להגדרות בעיית פונקציית מטרה שרירותיתלאNone"maxcut"
backend_namestrשם ה-Backend לשימושלאה-Backend הפחות עמוס שיש לך גישה אליו"ibm_fez"
optionsdictאפשרויות קלט, כולל הבאות: (אופציונלי) session_id: str; התנהגות ברירת המחדל יוצרת Session חדשלאNone{"session_id": "cw2q70c79ws0008z6g4g"}

פורמטי בעיה מקובלים:

  • ייצוג ביטוי פולינומיאלי של פונקציית מטרה. רצוי ליצור בפייתון עם אובייקט SymPy Poly קיים ולעצב לסטרינג באמצעות sympy.srepr.
  • ייצוג גרף של סוג בעיה ספציפי. יש ליצור את הגרף באמצעות ספריית networkx בפייתון, ולאחר מכן להמיר לסטרינג באמצעות פונקציית networkx [nx.readwrite.json_graph.adjacency_data](http://nx.readwrite.json_graph.adjacency_data.).
  • ייצוג שרשרת ספין של בעיה ספציפית. שרשרת הספין צריכה להיות מיוצגת כאובייקט SparsePauliOp; ראה את התיעוד לפרטים נוספים.

Backends נתמכים: הרץ את הקוד הבא כדי לראות את רשימת ה-Backends הנתמכים כרגע. אם המכשיר שלך אינו מפורט, פנה ל-Q-CTRL להוספת תמיכה.

# 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')>]

אפשרויות:

שםסוגתיאורברירת מחדל
session_idstrמזהה session קיים של Qiskit Runtime"cw4r3je6f0t010870y3g"
job_tagslist[str]רשימת תגי job[]

פלטים​

שםסוגתיאורדוגמה
resultdict[str, Any]פתרון ומטה-נתונים המפורטים תחת "תוכן מילון התוצאה"{'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': []}

תוכן מילון התוצאה:

שםסוגתיאור
solution_bitstring_costfloatהעלות המינימלית הטובה ביותר בכל האיטרציות
final_bitstring_distributionCountsDictמילון ספירות ה-bitstring המשויך לעלות המינימלית
solution_bitstringstrה-Bitstring עם העלות הטובה ביותר בהתפלגות הסופית
iteration_countintהמספר הכולל של איטרציות QAOA שבוצעו על ידי הפותר
variables_to_bitstring_index_mapfloatהמיפוי מהמשתנים לביט המקביל ב-bitstring
best_parameterslist[float]פרמטרי ה-beta וה-gamma המאורגנים בכל האיטרציות
warningslist[str]האזהרות שנוצרו בזמן קומפילציה או הרצת QAOA (ברירת מחדל None)

ביצועים השוואתיים​

תוצאות ביצועים השוואתיים מפורסמות מראות שהפותר פותר בהצלחה בעיות עם יותר מ-120 Qubits, ואף עולה על תוצאות שפורסמו בעבר על מכשירי quantum annealing ומלכודות יונים. מדדי הביצועים ההשוואתיים הבאים מספקים אינדיקציה גסה לדיוק וסקאלה של סוגי בעיות בהתבסס על מספר דוגמאות. המדדים בפועל עשויים להיות שונים בהתבסס על תכונות בעיה שונות, כגון מספר המונחים בפונקציית המטרה (צפיפות) והמקומיות שלהם, מספר המשתנים, וסדר הפולינום.

ה"מספר של Qubits" המצוין אינו מגבלה קשיחה אלא מייצג סף גס שבו תוכל לצפות לדיוק פתרון עקבי מאוד. גדלי בעיות גדולים יותר נפתרו בהצלחה, וניסוי מעבר למגבלות אלו מומלץ.

קישוריות Qubit שרירותית נתמכת בכל סוגי הבעיות.

סוג בעיהמספר Qubitsדוגמהדיוקזמן כולל (שניות)שימוש בזמן ריצה (שניות)מספר איטרציות
בעיות ריבועיות עם קישוריות דלילה1563-regular Max-Cut100%176429316
אופטימיזציה בינארית מסדר גבוה156מודל Ising spin-glass100%146127216
בעיות ריבועיות עם קישוריות צפופה50Max-Cut עם קישוריות מלאה100%175826812
בעיה עם אילוצים ומונחי עונשין50Weighted Minimum Vertex Cover עם צפיפות קשתות 8%100%107421510

תחילת העבודה​

ראשית, אמת את עצמך באמצעות מפתח ה-API של IBM Quantum. לאחר מכן, בחר את פונקציית Qiskit כדלקמן. (קטע זה מניח שכבר שמרת את חשבונך בסביבה המקומית שלך.)

from qiskit_ibm_catalog import QiskitFunctionsCatalog

catalog = QiskitFunctionsCatalog(channel="ibm_quantum_platform")

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

דוגמה: אופטימיזציה ללא אילוצים​

הרץ את בעיית החיתוך המקסימלי (Max-Cut). הדוגמה הבאה מדגימה את יכולות הפותר על בעיית Max-Cut של גרף לא-ממושקל 3-regular בעל 156 צמתים, אך תוכל גם לפתור בעיות גרף ממושקל. בנוסף ל-qiskit-ibm-catalog, תשתמש גם בחבילות הבאות להרצת דוגמה זו: networkx ו-numpy. תוכל להתקין חבילות אלו על ידי הסרת הסימון מהתא הבא אם אתה מריץ דוגמה זו ב-notebook באמצעות ה-kernel של IPython.

# %pip install networkx numpy

1. הגדר את הבעיה​

תוכל להריץ בעיית Max-Cut על ידי הגדרת בעיית גרף וציון 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
)

פלט תא הקוד הקודם

הפותר מקבל סטרינג כקלט להגדרת הבעיה.

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

2. הרץ את הבעיה​

בעת שימוש בשיטת קלט מבוססת גרף, ציין את סוג הבעיה.

# 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"
)

בדוק את הסטטוס של עומס העבודה של פונקציית Qiskit שלך או קבל תוצאות כדלקמן:

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

3. קבל את התוצאה​

קבל את ערך החיתוך האופטימלי ממילון התוצאות.

הערה
המיפוי של המשתנים ל-bitstring עשוי להשתנות. מילון הפלט מכיל תת-מילון variables_to_bitstring_index_map, אשר עוזר לאמת את הסדר.
# 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

תוכל לאמת את דיוק התוצאה על ידי פתרון הבעיה קלאסית עם פותרים בקוד פתוח כמו PuLP אם הגרף אינו מחובר בצפיפות. בעיות עם צפיפות גבוהה עשויות לדרוש פותרים קלאסיים מתקדמים כדי לאמת את הפתרון.

דוגמה: אופטימיזציה עם אילוצים​

דוגמת Max-Cut הקודמת היא בעיית אופטימיזציה בינארית ריבועית ללא אילוצים נפוצה. Optimization Solver של Q-CTRL יכול לשמש לסוגי בעיות שונים, כולל אופטימיזציה עם אילוצים. תוכל לפתור סוגי בעיות שרירותיים על ידי הזנת הגדרת הבעיה המיוצגת כפולינום שבו אילוצים מדוגמים כמונחי עונשין.

הדוגמה הבאה מדגימה כיצד לבנות פונקציית עלות עבור בעיית אופטימיזציה עם אילוצים, כיסוי קודקוד מינימלי (MVC). בנוסף לחבילות qiskit-ibm-catalog ו-qiskit, תשתמש גם בחבילות הבאות להרצת דוגמה זו: numpy, networkx, ו-sympy. תוכל להתקין חבילות אלו על ידי הסרת הסימון מהתא הבא אם אתה מריץ דוגמה זו ב-notebook באמצעות ה-kernel של IPython.

# %pip install numpy networkx sympy

1. הגדר את הבעיה​

הגדר בעיית MVC אקראית על ידי יצירת גרף עם צמתים בעלי משקל אקראי.

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)

פלט תא הקוד הקודם

ניתן לנסח מודל אופטימיזציה סטנדרטי ל-MVC ממושקל כדלקמן. ראשית, יש להוסיף עונש עבור כל מקרה שבו קשת אינה מחוברת לקודקוד בתת-הקבוצה. לכן, נגדיר ni=1n_i = 1 אם קודקוד ii נמצא בכיסוי (כלומר, בתת-הקבוצה) ו-ni=0n_i = 0 אחרת. שנית, המטרה היא למזער את המספר הכולל של הקודקודים בתת-הקבוצה, אשר ניתן לייצג באמצעות הפונקציה הבאה:

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

כעת כל קשת בגרף צריכה לכלול לפחות נקודת קצה אחת מהכיסוי, אשר ניתן לבטא כאי-שוויון:

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

כל מקרה שבו קשת אינה מחוברת לקודקוד הכיסוי חייב לקבל עונש. ניתן לייצג זאת בפונקציית העלות על ידי הוספת עונש בצורה P(1−ni−nj+ninj)P(1-n_i-n_j+n_i n_j) כאשר PP הוא קבוע עונשין חיובי. לפיכך, חלופה ללא אילוצים לאי-השוויון עם אילוצים ל-MVC ממושקל היא:

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. הרץ את הבעיה​

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

בדוק את הסטטוס של עומס העבודה של פונקציית Qiskit שלך או קבל תוצאות כדלקמן:

print(mvc_job.status())

3. קבל את התוצאה​

קבל את הפתרון ונתח את התוצאות. מאחר שלבעיה זו יש צמתים ממושקלים, הפתרון אינו פשוט המספר המינימלי של הצמתים המכוסים. במקום זאת, עלות הפתרון מייצגת את סכום המשקלות של הקודקודים הנכללים בכיסוי הקודקוד. היא מייצגת את "העלות" או "המשקל" הכולל של כיסוי כל הקשתות בגרף באמצעות הקודקודים שנבחרו.

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

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

קבלת תמיכה​

לכל שאלה או בעיה, פנה ל-Q-CTRL.

הצעדים הבאים​

המלצות