لماذا تُكتب مسائل التحسين بصيغة نموذج إيزنغ؟
Why are optimization problems written as Ising models?
لأن هاملتونيان إيزنغ $\sum J_{ij}Z_iZ_j+\sum h_iZ_i$ قطري في الأساس الحسابي، فقيمه هي قيم دالة الكلفة، ويمكن تطبيقه ببوابات $R_{ZZ}$ و$R_Z$.
An Ising Hamiltonian ΣJ_ij Z_iZ_j + Σh_i Z_i is diagonal, its eigenvalues are the cost values, and it is implemented with RZZ and RZ gates.
كثير من مسائل التحسين التوافقي (القطع الأعظمي، تلوين الرسوم، الجدولة، حقيبة الظهر) يمكن كتابتها على صورة تقليل دالة تربيعية لمتغيرات ثنائية (QUBO)، وهذه تكافئ نموذج إيزنغ بالتعويض $z_i=(1-s_i)/2$ مع $s_i=\pm1$. جمع Lucas (2014) صياغات إيزنغ لكثير من مسائل NP.
الفائدة الكمّية: كل متغير يصبح كيوبتاً، و$s_i$ يصبح المؤثر $Z_i$، فيصبح الهاملتونيان قطرياً قيمه هي قيم الكلفة لكل سلسلة بتات. التطور $e^{-i\gamma H_C}$ يتفكك إلى بوابات $R_{ZZ}$ و$R_Z$، وهذا ما تستعمله QAOA والتلدين الكمّي.
مثال القطع الأعظمي: $C=\sum_{(i,j)}w_{ij}\frac{1-Z_iZ_j}{2}$. في مختبر التحسين يمكنك عرض الصيغة الإيزنغية لكل رسم والتحقق من أن قيمة القطع تساوي $(W-E)/2$ حيث $W$ مجموع الأوزان و$E$ طاقة إيزنغ.
موضوعات مرتبطة
المراجع
- Andrew Lucas (2014). Ising formulations of many NP problems. Frontiers in Physics 2:5 doi:10.3389/fphy.2014.00005
- Edward Farhi; Jeffrey Goldstone; Sam Gutmann (2014). A Quantum Approximate Optimization Algorithm. arXiv:1411.4028 doi:10.48550/arXiv.1411.4028
