DOI: https://doi.org/10.22331/q-2026-05-06-2097
تاريخ النشر: 2026-05-06
المؤلف: Gabriel Waite وآخرون
الموضوع الرئيسي: أنظمة الكم ذات الجسيمات المتعددة
نظرة عامة
في هذا البحث، يثبت المؤلفون أن مشكلة هاميلتونيان المحلي الثنائي على شبكة كيوبيت مربعة ثنائية الأبعاد هي StoqMA-complete. يتم تحقيق ذلك من خلال توسيع تقنيات بناء الدوائر المتناثرة مكانيًا التي تم تطويرها سابقًا بواسطة أوليفيرا وترهال، جنبًا إلى جنب مع الأدوات التداخلية التي قدمها برافوي وآخرون. تشمل المساهمات الرئيسية للدراسة إثبات أن دوائر StoqMA يمكن أن تكون متناثرة مكانيًا وأنه يمكن بناء أدوات تداخلية تحافظ على الخصائص الهندسية والهاميلتونية دون زيادة أبعاد الجسيمات.
تشير النتائج إلى أنه بينما تُعرف مشكلة هاميلتونيان المحلي العام بأنها QMA-complete على شبكة مربعة، لم يتم تصنيف التعقيد المحدد لمشكلة هاميلتونيان المحلي الثنائي كـ StoqMA-complete سابقًا. يوضح المؤلفون بنجاح أن تحديد طاقة الحالة الأساسية لهاميلتونيان محلي ثنائي على شبكة مربعة هو StoqMA-hard. يحققون ذلك من خلال استخدام تقنيات الأدوات التداخلية لتقليل الهاميلتونيان المحلي الثنائي العام إلى أشكال محلية ثنائية على الشبكة المربعة، موازينًا المنهجيات التي استخدمها أوليفيرا وترهال. علاوة على ذلك، تستكشف الدراسة حالة محددة من الهاميلتونيان الأديباتيكي المقترح من قبل بيامونتي ولove، مؤكدة على StoqMA-completeness الخاصة بها أيضًا.
مقدمة
تتناول مقدمة هذه الورقة البحثية التعقيد الحسابي المرتبط بتحديد طاقات الحالة الأساسية للهاميلتونيان المحلي، مشددة على أن مشكلة الهاميلتونيان المحلي هي QMA-complete، مما يطرح تحديات كبيرة لكل من الأساليب الكلاسيكية والكمومية. يركز المؤلفون على مشكلة هاميلتونيان المحلي الثنائي في سياق أنظمة كيوبيت على شبكة مربعة ثنائية الأبعاد. تعتبر الهاميلتونيانات الستوكواستية، التي تتميز بعناصر غير إيجابية خارج القطر في الأساس الحسابي، ذات صلة خاصة لأنها تخفف من مشكلة الإشارة التي تواجهها محاكيات مونت كارلو، مما يسمح بتطبيق هذه الأساليب بشكل فعال. تم تقديم فئة التعقيد StoqMA، التي تقع بين MA و QMA، لتلخيص التحديات المتعلقة بالعثور على طاقات الحالة الأساسية للهاميلتونيانات الستوكواستية، مع تكهنات ملحوظة بشأن احتوائها في MA تحت إجراءات تضخيم محددة.
تستند الورقة إلى أعمال سابقة لبرافوي وبيسن وترهال، الذين أثبتوا أن مشكلة هاميلتونيان المحلي الثنائي هي StoqMA-complete لـ \( k \geq 2 \). يهدف المؤلفون إلى المساهمة في هذا النقاش من خلال إثبات StoqMA-completeness لمشكلة هاميلتونيان المحلي الثنائي على الرسوم البيانية المتناثرة مكانيًا ومن ثم مشكلة هاميلتونيان المحلي الثنائي على الشبكات ثنائية الأبعاد. يشير مخطط الورقة إلى نهج منظم، يبدأ بالتعريفات الأساسية والمساهمات التقنية، تليه مراجعة للبناءات الضرورية وتقديم أدوات تداخلية جديدة ضرورية لتخفيضاتهم. تعد الأقسام النهائية باستكشاف هاميلتونيان باولي الستوكواستيكي الأب الذي هو StoqMA-complete، إلى جانب مجموعة متنوعة من الإثباتات التقنية في الملاحق.
مناقشة
في هذا القسم، يناقش المؤلفون الإطار الفني والنتائج المهمة المتعلقة بمشكلة هاميلتونيان المحلي الثنائي، وخاصة فئة تعقيدها StoqMA. يعرفون المفاهيم الأساسية مثل الهاميلتونيانات المحلية k، والهاميلتونيانات الستوكواستية، ودوائر التحقق، مؤكدين على أهمية الحفاظ على خاصية الستوكواستية في بنائهم. يثبت المؤلفون أن مشكلة هاميلتونيان المحلي الثنائي هي StoqMA-complete من خلال إظهار كيفية تحويل دوائر StoqMA بعيدة المدى إلى دوائر متناثرة مكانيًا مع الحفاظ على معايير الاكتمال والصحة. تتضمن هذه التحويلة استخدام شبكة Swap لتحويل التفاعلات بعيدة المدى إلى تفاعلات جارة، تليها خريطة إلى هيكل دائرة متناثرة مكانيًا.
يقدم المؤلفون أدوات تداخلية جديدة تحافظ على الستوكواستية وتسهّل التخفيض من رسم بياني متناثر مكانيًا إلى رسم بياني مسطح، مما يثبت في النهاية أن مشكلة هاميلتونيان المحلي الثنائي على شبكة مربعة ثنائية الأبعاد هي أيضًا StoqMA-complete. تبرز نتائجهم العلاقة المعقدة بين الهاميلتونيانات المحلية وفئات التعقيد، مما يعزز أهمية الهاميلتونيانات الستوكواستية في الأطر الحسابية الكمومية. تسهم النتائج في فهم أعمق للتعقيد الحسابي للأنظمة الكمومية ودور الستوكواستية في ديناميات الهاميلتونيان.
DOI: https://doi.org/10.22331/q-2026-05-06-2097
Publication Date: 2026-05-06
Author(s): Gabriel Waite et al.
Primary Topic: Quantum many-body systems
Overview
In this research, the authors establish that the 2-Local Stoquastic Hamiltonian problem on a two-dimensional square qubit lattice is StoqMA-complete. This is accomplished by extending the spatially sparse circuit construction techniques previously developed by Oliveira and Terhal, along with the perturbative gadgets introduced by Bravyi et al. The key contributions of the study include demonstrating that StoqMA circuits can be made spatially sparse and that geometrical, stoquastic-preserving perturbative gadgets can be constructed without increasing the particle dimension.
The findings indicate that while the general 2-Local Hamiltonian problem is known to be QMA-complete on a square lattice, the specific complexity of the 2-Local Stoquastic Hamiltonian had not been previously classified as StoqMA-complete. The authors successfully show that determining the ground-state energy of a 2-Local stoquastic Hamiltonian on a square lattice is StoqMA-hard. They achieve this by employing perturbative gadget techniques to reduce general 2-local stoquastic Hamiltonians to 2-local forms on the square lattice, paralleling the methodologies of Oliveira and Terhal. Furthermore, the study explores a specific case of adiabatic Hamiltonians proposed by Biamonte and Love, confirming its StoqMA-completeness as well.
Introduction
The introduction of this research paper addresses the computational complexity associated with determining ground-state energies of local Hamiltonians, highlighting that the Local Hamiltonian problem is QMA-complete, thus posing significant challenges for both classical and quantum computing approaches. The authors focus on the Local Stoquastic Hamiltonian problem within the context of 2D square-lattice qubit systems. Stoquastic Hamiltonians, characterized by non-positive off-diagonal elements in the computational basis, are particularly relevant as they mitigate the sign problem encountered in Monte Carlo simulations, allowing these methods to be applied effectively. The complexity class StoqMA, which lies between MA and QMA, is introduced to encapsulate the challenges of finding ground-state energies for stoquastic Hamiltonians, with notable conjectures regarding its containment in MA under specific amplification procedures.
The paper builds on previous work by Bravyi, Bessen, and Terhal, who established that the k-Local Stoquastic Hamiltonian problem is StoqMA-complete for \( k \geq 2 \). The authors aim to contribute to this discourse by proving the StoqMA-completeness of the 6-Local Stoquastic Hamiltonian problem on spatially sparse graphs and subsequently the 2-Local Stoquastic Hamiltonian problem on 2D lattices. The outline of the paper indicates a structured approach, beginning with foundational definitions and technical contributions, followed by a review of necessary constructions and the introduction of new perturbative gadgets essential for their reductions. The final sections promise to explore a parent stoquastic Pauli Hamiltonian that is StoqMA-complete, alongside various technical proofs in the appendices.
Discussion
In this section, the authors discuss the technical framework and significant findings related to the Local Stoquastic Hamiltonian problem, particularly its complexity class StoqMA. They define key concepts such as k-local Hamiltonians, stoquastic Hamiltonians, and verification circuits, emphasizing the importance of maintaining the stoquastic property in their constructions. The authors establish that the 6-Local Stoquastic Hamiltonian problem is StoqMA-complete by demonstrating how to transform long-range StoqMA circuits into spatially sparse circuits while preserving the completeness and soundness parameters. This transformation involves using a Swap network to convert long-range interactions into nearest-neighbor interactions, followed by a mapping to a spatially sparse circuit structure.
The authors introduce new perturbative gadgets that maintain stoquasticity and facilitate the reduction from a spatially sparse graph to a planar graph, ultimately proving that the 2-Local Stoquastic Hamiltonian problem on a 2D square lattice is also StoqMA-complete. Their results highlight the intricate relationship between local Hamiltonians and complexity classes, reinforcing the significance of stoquastic Hamiltonians in quantum computational frameworks. The findings contribute to a deeper understanding of the computational complexity of quantum systems and the role of stoquasticity in Hamiltonian dynamics.