مقارنة بين تقنيات تقريب الهايبر بلين لقطع ماكس وخوارزمية التقدير الكمي التقريبية على بعض عائلات الرسوم العادية

يوجد اهتمام كبير في إيجاد حالات تحدي لمشاكل NP-hard، من منظور إظهار المزايا الكمية. نظرًا لحدود أجهزة NISQ القريبة المدى، فإنه من المفيد أيضًا أن تكون هذه الحالات صغيرة. في هذا العمل، نحدد عائلتين من الرسوم (|V|<1000) والتي تحقق فيها خوارزمية غومانس-ويليامسون لتقدير قطع ماكس تقريبًا يصل إلى 0.912 كحد أقصى. كما نوضح أن خوارزمية كوانتوم، وهي خوارزمية التقدير الكمي التقريبية (عمق p=1)، تحقق تقريبًا يبلغ 0.592 على حالات كارلوف في الحد (n)، وفي أفضل الأحوال تحقق تقريبًا يبلغ 0.894 على عائلة من الرسوم المنتظمة بقوة. نستكشف أيضًا بناء حالات تحدي بشكل حسابي من خلال إضطراب أوزان الحواف، وهو ما قد يكون له اهتمام مستقل، ونتضمن هذه الحالات في مستودع CI-QuBe على GitHub.