QAOA يدوياً لقطع المربع الأعظمي
QAOA by Hand for Max-Cut on the Square
بناء دائرة QAOA بعمق 1 من $R_{ZZ}$ و$R_X$، وبحث شبكي عن $(\gamma,\beta)$؛ أفضل $\langle C\rangle=3$ من الحل الأمثل 4.
طبقة الكلفة $e^{-i\gamma H_C}$ مع $H_C=\sum(1-Z_iZ_j)/2$ تساوي حتى طور كلي $\prod R_{ZZ}(-\gamma)$، وطبقة الخلط $\prod R_X(2\beta)$. نحسب $\langle C\rangle$ بدقة من متجه الحالة ثم نبحث على شبكة $41\times41$. النتيجة: $\gamma=3\pi/4$ و$\beta=3\pi/8$ و$\langle C\rangle=3$ (نسبة 0.75)، والحلان الأمثلان 0101 و1010 باحتمال نحو $0.266$ لكلٍّ منهما. يتطابق هذا مع محرك المختبر. QAOA هنا لا يتفوق على الحل الكلاسيكي البسيط لهذا الرسم الصغير.
المتطلبات: pip install qiskit numpy
الشيفرة
import numpy as np
from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector
edges = [(0, 1), (1, 2), (2, 3), (3, 0)]
n = 4
def cut_value(bits):
z = bits[::-1]
return sum(z[i] != z[j] for i, j in edges)
def qaoa_p1(gamma, beta):
qc = QuantumCircuit(n)
qc.h(range(n))
for i, j in edges:
qc.rzz(-gamma, i, j)
qc.rx(2 * beta, range(n))
return qc
def expected_cut(gamma, beta):
probs = Statevector.from_instruction(qaoa_p1(gamma, beta)).probabilities_dict()
return sum(p * cut_value(b) for b, p in probs.items())
grid = [(g, b) for g in np.linspace(0, np.pi, 41) for b in np.linspace(0, np.pi / 2, 41)]
g_best, b_best = max(grid, key=lambda gb: expected_cut(*gb))
print(f"gamma = {g_best:.4f}, beta = {b_best:.4f}")
print("<C> =", round(expected_cut(g_best, b_best), 4), "| optimum = 4")
probs = Statevector.from_instruction(qaoa_p1(g_best, b_best)).probabilities_dict()
top = sorted(probs.items(), key=lambda kv: -kv[1])[:4]
print([(str(b), round(float(p), 4), cut_value(b)) for b, p in top])
شرح الشيفرة سطراً بسطر
| السطر | الشرح |
|---|---|
| 1-3 | الاستيراد. |
| 5 | حواف المربع. |
| 6 | عدد العقد. |
| 9-11 | قيمة القطع لسلسلة بتات (معكوسة لتطابق فهرسة العقد). |
| 14 | دالة تبني دائرة QAOA بعمق 1. |
| 15-16 | تراكب منتظم. |
| 17-18 | طبقة الكلفة: RZZ(−γ) لكل حافة. |
| 19 | طبقة الخلط: RX(2β). |
| 20 | إرجاع الدائرة. |
| 23-25 | القطع المتوقع ⟨C⟩ من الاحتمالات الدقيقة. |
| 28 | شبكة قيم γ ∈ [0, π] وβ ∈ [0, π/2]. |
| 29 | أفضل نقطة على الشبكة. |
| 30-31 | طباعة المعاملات و⟨C⟩. |
| 32-33 | أعلى أربع سلاسل احتمالاً. |
| 34 | طباعتها مع قيم القطع. |
المخرجات (من تشغيل فعلي)
gamma = 2.3562, beta = 1.1781
<C> = 3.0 | optimum = 4
[('0101', 0.2656, 4), ('1010', 0.2656, 4), ('0110', 0.0781, 2), ('1001', 0.0781, 2)]
نُفّذ بـ Python 3.13.18 في 2026-11-20 08:14 UTC.
الناتج حتمي (بحث شبكي على احتمالات دقيقة).
المراجع
- Edward Farhi; Jeffrey Goldstone; Sam Gutmann (2014). A Quantum Approximate Optimization Algorithm. arXiv:1411.4028 doi:10.48550/arXiv.1411.4028
- Andrew Lucas (2014). Ising formulations of many NP problems. Frontiers in Physics 2:5 doi:10.3389/fphy.2014.00005
- IBM Quantum (2025). Qiskit SDK API documentation. IBM Quantum Documentation quantum.cloud.ibm.com
