حل مشكلة ‘البائع المتجول’ من خلال الحوسبة الكمومية

مشكلة خوارزمية كلاسيكية في مجال علوم الحاسوب تُعرف بمشكلة البائع المتجول (TSP) هي مثال رئيسي على مشكلة تحسين تركيبي.

ما هو TSP بالضبط؟ هذا الكلاسيكي الرياضي يتضمن العثور على أقصر مسار ممكن لزيارة N عدد من المدن مرة واحدة بالضبط قبل العودة إلى المدينة الأصلية. ومع ذلك، كلما زاد عدد المدن، زادت المسارات الممكنة ووقت الحساب لإيجاد الحل الأمثل. بينما يمكن حل هذه المشكلة باستخدام طرق تقريبية، قد توفر الحواسيب الكمومية حلولًا أفضل بكثير وأكثر سرعة.

هذا هو بالضبط ما أظهره الفيزيائي النظري فريق البروفيسور د. جينس إيسيرت: أن مثل هذه المشاكل يمكن حلها بشكل أفضل وأسرع باستخدام الحواسيب الكمومية.

تستخدم الحوسبة الكمومية الأجهزة والخوارزميات التي تستغل ميكانيكا الكم لحل مشاكل معقدة تتجاوز قدرة الحواسيب التقليدية، بما في ذلك الحواسيب الفائقة. على الرغم من قوتها، فإن الحواسيب الفائقة — الحواسيب الكلاسيكية الضخمة التي تحتوي على آلاف نوى CPU وGPU — محدودة بفضل اعتمادها على تكنولوجيا الترانزستور من القرن العشرين عند حل مشاكل ذات تعقيد عالٍ.

هنا يأتي دور الفيزياء الكمومية. على عكس الحواسيب الكلاسيكية التي تشفر المعلومات في بتات ثنائية (0 و 1)، تستخدم الحواسيب الكمومية البتات الكمومية أو الكيوبتات لتشغيل خوارزميات كمومية متعددة الأبعاد.

علاوة على ذلك، على عكس الحواسيب التقليدية التي تستخدم مراوح للتبريد، تحتاج الحواسيب الكمومية إلى الحفاظ على معالجاتها الكمومية في درجات حرارة منخفضة جدًا للحفاظ على حالاتهم الكمومية. يتم ذلك عبر سوائل فائقة البرودة.

الموصلات الفائقة هي مواد تُظهر تأثيرًا ميكانيكيًا كموميًا حاسمًا، يسمح للإلكترونات بالتحرك عبرها دون مقاومة. عندما تمر الإلكترونات عبرها، تتزاوج لحمل شحنة عبر الحواجز. عندما يتم وضع موصلين فائقين على جانبي عازل، يتشكل وصلة جوزيفسون، التي تُستخدم لتوصيل الكيوبتات الفائقة.

الكيوبت مفيد في المهمة المهمة المتمثلة في وضع معلوماته الكمومية في حالة تراكب، وهي مزيج من التكوينات الممكنة للكيوبت. مجموعات الكيوبتات في حالة التراكب قادرة على إنشاء مساحات حسابية معقدة متعددة الأبعاد حيث يمكن تمثيل المشكلات المعقدة.

هنا، من خلال تشابك كيوبتين، يمكن أن تؤثر التغييرات في أحدهما مباشرة على الآخر، بينما عندما تُوضع هذه الكيوبتات المتشابكة في حالة تراكب، نحصل على العديد من الاحتمالات. يعمل الحساب على الحاسوب الكمومي عن طريق إعداد تراكب لجميع الحالات الحسابية الممكنة، ومن خلال التداخل تُعثر على الحلول.

بالطبع، بناء حاسوب كمومي يحتوي على عدد كبير من الكيوبتات هو إجراء معقد جدًا، رغم أن عدة طرق تُستكشف فيما يمكن لهذه الحواسيب إنجازه.

وفقًا لإيسيرت، الذي يقود مجموعة بحثية مشتركة في مركز هيلموتز-زنترم برلين (HZB)، مركز أبحاث مواد الطاقة، والجامعة العامة الحرة في برلين:

“هناك الكثير من الأساطير حوله، وأحيانًا بعض الضجيج والضخامة. ومع ذلك، لقد تناولنا المسألة بدقة، باستخدام الأساليب الرياضية، وقدمنا نتائج قوية في هذا الموضوع. قبل كل شيء، أوضحنا بأي معنى يمكن أن تكون هناك أي مزايا على الإطلاق.”

مشكلة البائع المتجول الحرجة

كمشكلة تحسين، تُعد مشكلة البائع المتجول ذات أهمية اقتصادية كبيرة في صناعة اللوجستيات وسلسلة الإمداد. إنها تندرج ضمن الفئة الأوسع لمشكلات التحسين التركيبي، التي تشمل أيضًا جدولة الوظائف، تخصيص الموارد، تحسين المحافظ، وحتى طي البروتين، كلها حاسمة لمختلف القطاعات.

نظرًا للأهمية الاجتماعية والاقتصادية لهذه المشكلات، فقد كانت موضوعًا لأبحاث مكثفة. وبالتالي، فإن العثور على إجابة لمشكلات مثل أكثر سلاسل الإمداد كفاءة وأرخص مسار توصيل له تأثير إيجابي على حياتنا اليومية.

ومع ذلك، فإن تحسين مسارات التوصيل لعدة وجهات مع مراعاة قيود مختلفة مثل ازدحام المرور، ارتفاع تكاليف التشغيل، تغييرات المسار المفاجئة، المواعيد التجارية الأخيرة، وطلبات العملاء يجعل مشكلة البائع المتجول أكثر تحديًا للحل. على الرغم من هذه التحديات، فإن حل مشكلة البائع المتجول أمر حاسم لتوصيل البضائع بكفاءة، مما يضمن نموذج عمل قابل للحياة.

هناك العديد من الفوائد لحل هذه المشكلة، بما في ذلك تقليل المسافة والساعات المقطوعة وتوفير استهلاك الوقود. يمكن أن يساعد تقليل المسافة المقطوعة في خفض البصمة الكربونية بشكل كبير، مما يترجم إلى جودة هواء أفضل، إبطاء تغير المناخ، ونمو اقتصادي. علاوة على ذلك، يمكن أن يساعد حل مشكلة البائع المتجول في توصيل البضائع في الوقت المحدد والاجتماعات مع العملاء في الوقت المناسب، مما يعزز تجربة العملاء وأعمال الخدمات الميدانية.

كما رأينا، لا يساعد حل المشكلة الشركات فحسب، بل تتسرب هذه الفوائد إلى العملاء أيضًا، مما يثري التجربة للجميع.

يمكن استخدام العديد من الطرق لحل مشكلة البائع المتجول. إحدى هذه الطرق هي نهج “القوة الغاشمة” (Brute-Force)، الذي يحسب جميع التباديل الممكنة للعثور على أقصر مسار. في طريقة الفروع والحدود (branch-and-bound)، يتم تقسيم المشكلة إلى عدة سلاسل من المشكلات الفرعية، حيث يؤثر حل كل مرحلة على الحل الذي يُعثر عليه في المراحل اللاحقة.

في البرمجة الديناميكية، يركز الاهتمام على تجنب الحسابات المتكررة. أما خوارزمية أقرب جار (Nearest Neighbor)، فهي خوارزمية تقريبية تبدأ بالموقع الابتدائي ثم تتوقف عند الأقرب. بمجرد تغطية جميع المدن، تعود إلى نقطة الانطلاق. رغم أنها عملية وسريعة نسبيًا، قد لا توفر دائمًا مسارًا فعالًا.

مع تقدم التكنولوجيا، يمكن تنفيذ تخطيط المسارات وتحسينها بشكل أكثر فعالية. يمكن للذكاء الاصطناعي (AI) على وجه الخصوص أن يساعد في حل المشكلة من خلال تحليل كمية هائلة من البيانات بسرعة لمساعدة العديد من الشركات الحديثة في اتخاذ قرارات تشغيلية واستراتيجية.

يتم أيضًا دراسة الحواسيب الكمومية لحل المشكلة؛ لأنها تقدم تسارعات حسابية كبيرة مقارنة بالحواسيب الكلاسيكية. لقد اقتُرح منذ زمن طويل أن هذه الحواسيب قد تساعد فعليًا في تحسين التقريبات لهذه المشكلات.

استخدام تقنيات الحوسبة الكمومية لحل مشكلة البائع المتجول

بينما تحظى الحوسبة الكمومية باهتمام هائل وتقدم نتائج واعدة لبعض المشكلات، لا يزال مدى هذه الميزة الكمومية غير مستكشف إلى حد كبير.

وبالتالي، قدمت الدراسة دليلًا بنائيًا كاملًا على أن الحواسيب الكمومية يمكنها بالفعل التفوق على الحواسيب التقليدية في العثور على تقريبات لمشكلات التحسين التركيبي.

استخدمت الدراسة الأخيرة، التي قادها إيسيرت وزميله جان-بيير سيفرت، فقط أساليب تحليلية لتقييم مدى قدرة حاسوب كمومي بكيوبتات على حل مشكلة البائع المتجول.

“نفترض ببساطة، بغض النظر عن التحقيق الفيزيائي، أن هناك عددًا كافيًا من الكيوبتات وننظر في إمكانيات إجراء عمليات حسابية بها”، وهو ما يكشف عن تشابه مع مشكلة شائعة في علم التشفير، أي تشفير البيانات، كما أوضح فنسنت أوليتزش، طالب دكتوراه في الجامعة التقنية ببرلين.

ثم استخدم الفريق خوارزمية شور، وهي خوارزمية كمومية، لإيجاد العوامل الأولية لعدد صحيح وحل فئة فرعية من هذه مشكلات التحسين. بذلك، لن ينفجر وقت الحوسبة مع زيادة عدد المدن. سيزداد فقط بصورة متعددة الحدود، أي بـ Nx حيث x ثابت. بهذه الطريقة، يكون الحل المستخرج أيضًا أفضل نوعيًا بكثير من ما يُستنتج من الحل التقريبي باستخدام الخوارزمية التقليدية.

باستخدام مفاهيم التشفير ونظرية التعلم الحاسوبي، تقدم الدراسة “دليلًا بنائيًا كاملًا على أن الحواسيب الكمومية تتمتع بميزة فوق متعددة الحدود على الحواسيب الكلاسيكية في تقريب مشكلات التحسين التركيبي.”

وأشارت الدراسة أيضًا إلى أن فريق البحث أحرز تقدمًا كبيرًا في السؤال المهم حول ما قد تقدمه الحواسيب الكمومية المحتملة في تقريب حلول مشكلات التحسين التركيبي، التي لها تأثيرات اجتماعية واقتصادية كبيرة.

تم تمويل الدراسة من قبل وحدة أبحاث أينشتاين، مركز برلين للرياضيات (MATH+ مجموعة التميز)، BMBF (Hybrid)، BMWK (EniQmA)، وادي كوانتم ميونيخ، وDFG. كما قدمت وزارة التعليم والبحث الفيدرالية في ألمانيا دعمًا ماليًا.

استكشاف إمكانات الحوسبة الكمومية

على الرغم من الإنجاز العظيم، لم تكن هذه المرة الأولى التي تُستخدم فيها الحوسبة الكمومية لحل مشكلة البائع المتجول. هناك العديد من الحالات التي يبحث فيها المتحمسون والباحثون عن حل المشكلة باستخدام الحوسبة الكمومية.

في ديسمبر 2022، اقترح ورقة خوارزمية كمومية لمشكلة البائع المتجول تعتمد على بحث غروفر التكيفي (GAS). ضمن إطار GAS، هناك صعوبتان أساسيتان — قد لا تكون الحلول قابلة للتنفيذ، وعدد الكيوبتات في الحواسيب الكمومية الحالية محدود جدًا ولا يمكنه تلبية المتطلبات الدنيا، مما يقيد تطبيق الخوارزميات الكمومية لمشكلات التحسين التركيبي.

وبالتالي، قامت الورقة بتحسين موصل اكتشاف الدورة الهاميلتونية (HCD)، الذي يمكنه إزالة الحلول غير العملية تلقائيًا أثناء تنفيذ الخوارزمية. كما صمموا استراتيجية “سجل المرسى” لتوفير استهلاك الكيوبتات، مع مراعاة متطلبات القابلية للعكس في الحوسبة الكمومية وتجاوز صعوبة عدم إمكانية كتابة أو تحرير الكيوبتات المستخدمة ببساطة. سمح ذلك للدراسة باستخدام 31 كيوبت فقط، وحقق الحل معدل نجاح قدره 86.71٪.

في عام 2019، كتب خبير الفيزياء المُعرّف ذاتيًا جوزيف كاميدج عن استخدام معالج كمومي بالتقليب، مما مكنه من حل مشكلة البائع المتجول لسبع مدن وله القدرة النظرية على حلها لتسع مدن بمجرد إزالة القيود التكنولوجية.

طريقة حوسبة جديدة، التبريد الكمومي (Quantum annealing)، أظهرت القدرة على حل مشكلات التحسين أسرع من التقنيات الكلاسيكية. نظريتها تشير إلى أن الكيوبتات ستحقق حالة طاقة منخفضة مثالية عندما تكون مبردة بشكل فائق.

ومع ذلك، في عام 2021، أظهرت دراسة ممولة من قبل Supply Chain Digital & Data Science، وجونسون آند جونسون أن جهاز التبريد الكمومي لا يمكنه التعامل إلا مع حجم مشكلة يصل إلى 8 عقد أو أقل، وأداؤه دون المستوى سواء من حيث الوقت أو الدقة مقارنةً بالحلال الكلاسيكي.

استخدام الحوسبة الكمومية لحل مشكلة البائع المتجول مستمر منذ فترة. قبل أكثر من عقدين، في عام 2001، بدأت دراسة البحث عن خوارزمية كمومية لحل المشكلة.

في الورقة، نظر باكلي هوبر من جامعة ألاباما في خوارزميات شروغروفر وشور. أشار إلى أن خوارزمية شروغروفر توفر تحسينًا بجذر تربيعي فقط، مما يعني أنها لا تستطيع جعل مشكلة غير قابلة للحل على الحاسوب الكلاسيكي قابلة للحل على الحاسوب الكمومي. أما خوارزمية شور، فقد لاحظ هوبر أنه، رغم أنها يمكن أن تحول مشكلة عامل أولي يُفترض أنها غير قابلة للحل إلى مشكلة قابلة للحل على الجهاز الكمومي، إلا أنها مناسبة فقط لنوع محدد جدًا من المشكلات.

بشكل عام، لم يجد هوبر “نتيجة مرضية لخوارزمية لحساب حلول تقريبية لمشكلة البائع المتجول”.

بعد بضع سنوات، قدم معهد مهندسي الكهرباء والإلكترونيات (IEEE) خوارزمية جديدة لحل المشكلة، مستوحاة من كل من الخوارزميات الجينية والحوسبة الكمومية. وجد IEEE أن النتائج المستخلصة من تطبيق الخوارزمية المقترحة على بعض حالات مشكلة البائع المتجول أفضل بكثير من تلك التي توفرها الخوارزميات الجينية القياسية.

انقر هنا لتتعرف على الحالة الحالية للحوسبة الكمومية.

الشركات التي تعمل مع الحوسبة الكمومية

الآن، دعونا نلقي نظرة على بعض الأسماء التي تعمل على البحث والتطوير في مجال الحوسبة الكمومية:

#1. IBM

شركة International Business Machines Corporation (IBM ) تشارك في مجموعة واسعة من القطاعات، بما في ذلك الذكاء الاصطناعي، خدمات السحابة، تكنولوجيا المعلومات، التمويل للعميل، والتمويل التجاري. كما تشارك العملاق التقني في الحوسبة الكمومية عبر منصة IBM Quantum، التي توفر وصولًا عامًا ومميزًا إلى خدمات الحوسبة الكمومية السحابية. تشمل هذه الخدمات مجموعة من معالجات IBM الكمومية النموذجية، ودروسًا حول الحوسبة الكمومية، وكتابًا تفاعليًا.

في الآونة الأخيرة، صرّح علماء IBM أنهم على خطوة أخرى أقرب إلى تجاوز عقبة تفتح الإمكانات التحويلية للحواسيب الكمومية. لهذا، قدموا رمز تصحيح الأخطاء الكمومية الجديد، الذي يقولون إنه أكثر كفاءة بحوالي عشرة أضعاف مقارنة بالطرق السابقة.

في أواخر العام الماضي، أطلقت الشركة أيضًا الحاسوب الكمومي المسمى Condor، الذي يحتوي على 1,121 كيوبت فائق التوصيل مرتبة بنمط خلية العسل. كما كشفت IBM عن IBM Quantum System Two، أول حاسوب كمومي معياري لها ومعمارية حوسبة فائقة مركزة على الكم، والتي يمكن توسيعها وبالتالي يمكن ترقيتها بشرائح ستُطلق خلال السنوات الخمس المقبلة.

برأس مال سوقي يبلغ 175 مليار دولار، تُتداول أسهم IBM عند 190.86 دولار، بارتفاع 16.66٪ منذ بداية العام (YTD). سجلت IBM إيرادات (TTM) قدرها 61.86 مليار دولار مع ربحية السهم (EPS) (TTM) 8.03، نسبة السعر إلى الأرباح (P/E) (TTM) 23.76، والعائد على حقوق الملكية (ROE) (TTM) 33.36٪. تدفع الشركة عائد توزيعات قدره 3.48٪.

#2. D-Wave Systems

تُطوّر هذه الشركة المتخصصة في الحوسبة الكمومية وتقدّم الأنظمة والبرمجيات والخدمات ذات الصلة. تشمل منتجاتها The Leap و The Advantage، وتوفر تطبيقات كمومية للجدولة، اللوجستيات، اكتشاف الأدوية، عمليات التصنيع، والمزيد.

في وقت سابق من هذا الشهر، صرّحت D-Wave أن الأجهزة الكمومية يمكنها الآن حل المشكلات ذات التطبيقات الواقعية أسرع من أي حاسوب عادي. في وقت سابق من هذا العام، أعلنت الشركة عن حاسوب كمومي يحتوي على 1,200 كيوبت، 10,000 موصل، وزمن حل أسرع بـ 20 مرة في المشكلات الصعبة للتحسين.

تُتداول أسهم الشركة حاليًا عند 1.86 دولار، بارتفاع 138.6٪ منذ بداية العام (YTD)، برأس مال سوقي يبلغ 267 مليون دولار. سجلت مبيعات قدرها 8.247 مليون دولار (TTM)، ربحية سلبية (EPS) (TTM) -0.66، نسبة السعر إلى الأرباح (P/E) (TTM) -3.19، وأعلنت عن نمو يزيد عن 20٪ في المبيعات لكل من الربع الرابع ونتائج نهاية عام 2023، بينما ارتفعت الحجوزات بنسبة 34٪ و89٪ على التوالي.

ومن المثير للاهتمام، صرّح الرئيس التنفيذي للشركة، الدكتور آلان باراز، بأن زخم الشركة يعود إلى شراكتها الاستراتيجية متعددة السنوات مع Zapata AI، وإطلاق نموذج Advantage2 الذي يحتوي على أكثر من 1,200 كيوبت، ومشروعات مشتركة مع NEC أستراليا و Deloitte كندا، وتعيين كريستين نيلسن، وزيرة الأمن الداخلي السابقة، كعضوة في مجلس الإدارة.

الخاتمة

من المتوقع أن يصل سوق الحوسبة الكمومية إلى 6.5 مليار دولار في عام 2028، وإمكاناته لحل مشكلة البائع المتجول (TSP) لها تداعيات على عدة صناعات، مثل التصنيع، اللوجستيات، إدارة سلسلة الإمداد، التجارة الإلكترونية، النقل، والبحث. في النهاية، يمكن أن ينتج عن ذلك فوائد كبيرة، لا سيما تعزيز الإنتاجية، خفض النفقات، وتحفيز الابتكار عبر قطاعات متنوعة.

انقر هنا للحصول على قائمة بأفضل خمس شركات حوسبة كمومية.