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

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

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

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

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

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

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

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

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

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

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

وفقا لأيسرت ، الذي يقود مجموعة بحثية مشتركة في Helmholtz-Zentrum Berlin (HZB) ، مركز أبحاث المواد الطاقوية ، والجامعة البحثية العامة Freie Universität Berlin:

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

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

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

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

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

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

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

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

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

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

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

استخدام تقنيات الحوسبة الكمومية لحل TSP

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ومع ذلك ، في 2021 ، وجدت دراسة تمولها سلسلة التوريد الرقمية وعلوم البيانات ، وجونسون آند جونسون ، أن جهاز التبريد الكمومي يمكنه فقط التعامل مع حجم مشكلة 8 عقد أو أقل ، وأداؤه ضعيف من حيث الوقت والدقة مقارنة بالحل الكلاسيكي.

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

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

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

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

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

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

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

#1. IBM

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

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

في نهاية العام الماضي ، أطلقت الشركة كمبيوتر كمومي يسمى Condor ، مع 1,121 qubit فائق التوصيل يتم ترتيبها في نمط سداسي. كما كشفت شركة آي بي إم النقاب عن نظام IBM Quantum System Two ، وهو كمبيوتر كمومي قابل للتحديث وعمارة حوسبة كمومية ، وهو قابل للتحديث مع الشريحة التي سيتم إطلاقها في течение الخمس سنوات القادمة.

مع قيمة سوقية تبلغ 175 مليار دولار ، تُباع أسهم شركة آي بي إم عند 190.86 دولار ، بزيادة 16.66٪ منذ بداية العام. سجلت شركة آي بي إم إيرادات (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 qubit و 10,000 coupler ، وسرعة حل المشكلات الصعبة للتحسين 20 مرة أسرع.

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

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

الخلاصة

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

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