حدود الحوسبة الكمومية : ستكون أجهزة الكمبيوتر الكمومية جيدة بشكل لا يصدق في إنجاز مهام معينة. ولكن لحل معظم المشكلات ، لن يكون أداءهم أفضل قليلاً من أجهزة الكمبيوتر الحالية. الكمبيوتر النهائي ليس للغد!
“مهندسون من ماركة Haggar للملابس الجاهزة يطورون” بنطلون كوانتوم “، عنوان الجريدة الأمريكية الأسبوعية الساخرة The Onion في يونيو 2001. “من خلال استغلال الازدواجية الغريبة لبانتالون شرودنجر ، أوضح المقال ، أن هذه السراويل غير التقليدية ستشكل في نفس الوقت ملابس غير رسمية وفساتين سهرة.” سخر The Onion بلا شك من العديد من المقالات التي تهتم بالحوسبة الكمومية التي كانت شائعة في الصحافة العلمية الشعبية على مدى السنوات العشر الماضية.
هناك ادعاء متكرر ولكنه خاطئ وهو أن أجهزة الكمبيوتر الكمومية يمكنها نظريًا التغلب على مجموعة من المشكلات الصعبة بشكل خاص ، ما يسمى بمشكلات np-Complete – والتي سنعود إليها – والتي حتى أقوى أجهزة الكمبيوتر الموجودة تفشل في حلها عمليًا. – وقت معقول. سر هذه العروض: بنية قادرة على التعامل مع جميع الاستجابات الممكنة في وقت واحد.
جدول المحتويات
إذا أردنا تطوير جهاز كمبيوتر قادر على حل مشكلة np كاملة بنقرة واحدة ،
إذا أردنا تطوير جهاز كمبيوتر قادر على حل مشكلة np كاملة بنقرة واحدة ، فإن العديد من جوانب مجتمعنا ستنقلب رأسًا على عقب. يمكن لمثل هذه الآلة تحديد أي هيكل مخفي في بيانات سوق الأوراق المالية أو سجلات الطقس أو نشاط الدماغ ، دون حتى هذه الحسابات الروتينية التي تتطلب فهمًا عميقًا للمشكلة. سيجعل هذا الكمبيوتر السحري أيضًا من الممكن أتمتة الإبداع الرياضي. من المحتمل أن يحل تخمينات عمرها قرن من الزمان مثل فرضية Goldbach أو Riemann ، واستكشاف جميع البراهين أو الدحض الممكنة التي تحتوي على رقم معين – مليار على سبيل المثال – من الرموز.
إقرأ أيضا:من هي أجاثا كريستي ؟إذا توقع المرء مثل هذه المآثر من أجهزة الكمبيوتر الكمومية ، فهناك فرصة ضئيلة للعثور عليها في السوق قبل مولدات الدفع الملتوية في الزمكان أو الدروع المضادة للجاذبية ، أي في المستقبل البعيد والافتراضي. ومع ذلك ، إذا كان الضجيج حول أجهزة الكمبيوتر الكمومية مبالغًا فيه ، فسيكون من المبالغة أيضًا إبعاد الحوسبة الكمومية إلى خزانة الخيال العلمي. من البناء أكثر أن نحاول تحديد حدود أجهزة الكمبيوتر الكمومية ، وما الذي يمكننا فعله بالفعل إذا تم تطويرها.
حدود الحوسبة الكمومية : تم اقتراح فكرة الحوسبة الكمومية منذ 26 عامًا
تم اقتراح فكرة الحوسبة الكمومية منذ 26 عامًا من قبل الفيزيائي الأمريكي ريتشارد فاينمان. منذ ذلك الحين ، استكشف علماء الكمبيوتر إمكانياتها وفهموا إلى حد كبير أي فئات من المشاكل ستكون أجهزة الكمبيوتر الكمومية فعالة وأيها لن يقدموا مزايا أخرى. في الحالة الحالية لفهمنا ، ستسمح أجهزة الكمبيوتر الكمومية بإحراز تقدم مذهل في بعض المشكلات المحددة ، على سبيل المثال لكسر رموز التشفير المستخدمة في المعاملات على الإنترنت. من ناحية أخرى ، بالنسبة لمشاكل أخرى مثل لعبة الشطرنج ، وتخطيط الرحلات الجوية أو العرض الآلي للنظريات الرياضية ،
لاحظ أن هذه القيود مستقلة عن الصعوبات العملية الكامنة في تطوير الكمبيوتر الكمي ، مثل فك الترابط (فقدان الطابع الكمي لنظام ما من خلال التفاعل مع بيئته). ستظل القيود المفروضة على ما يمكن برمجته رياضياً على جهاز كمبيوتر كمي سارية حتى لو تغلب الفيزيائيون على مشكلة فك الترابط.
إقرأ أيضا:اسهل طريقة لتخفيف الوزنلماذا يمثل الكمبيوتر الكمومي تقدمًا في حل بعض المشكلات دون غيرها؟
لماذا يمثل الكمبيوتر الكمومي تقدمًا في حل بعض المشكلات دون غيرها؟ أليس الكمبيوتر الأسرع أسرع في كل الأحوال؟ الجواب لا. لفهم ذلك ، يجب علينا أولاً أن ننظر إلى مفهوم التعقيد في علوم الكمبيوتر. بالنسبة لمتخصصي تكنولوجيا المعلومات ، فإن الجانب الحاسم للمشكلة هو المعدل الذي يزداد فيه الوقت اللازم لحل هذه المشكلة مع زيادة حجم البيانات. يتم قياس الوقت بأعداد الخطوات الأولية للحساب التي تستغرقها الخوارزمية للوصول إلى حل.
على سبيل المثال ، باستخدام الطريقة الكلاسيكية التي تم تعلمها في المدرسة الابتدائية ، فإن الوقت المستغرق لمضاعفة رقم مكون من رقم واحد في عدد آخر يزيد بمقدار n 2 ، وهو عدد الأرقام المربعة: إذا استغرق الأمر دقيقة لضرب رقمين مكونين من ثلاثة أرقام ، سوف يستغرق الأمر أربع دقائق لضرب رقمين من ستة أرقام. يُقال إن مثل هذا التطور لوقت الحساب متعدد الحدود ، حيث يتم قياس معدل الزيادة بواسطة قوى n.
حدود الحوسبة الكمومية : الكأس: وقت الحوسبة الذي ينمو بشكل متعدد الحدود
من ناحية أخرى ، بالنسبة للعملية العكسية التي تتكون من تحليل عدد صحيح إلى أعداد أولية ، على سبيل المثال 105 = 3 × 5 × 7 ، تتطلب الطرق الأكثر فاعلية المعروفة وقتًا يزيد أضعافًا مضاعفة مع عدد أرقام الرقم المطلوب (بتعبير أدق ، مثل 2 أس n1 / 3). وبالتالي ، فإن التحليل إلى عوامل بطبيعته أصعب من الضرب. بالنسبة للأرقام التي تحتوي على ألف رقم ، يصبح الفرق في وقت الحساب بين هاتين العمليتين أكبر بكثير من الاختلاف بين قدرات كمبيوتر Commodore في أوائل الثمانينيات وتلك الخاصة بالحاسوب العملاق الحديث.
إقرأ أيضا:لماذا الشبكات الاجتماعية مهمة؟المشاكل التي يمكن حلها في وقت معقول حتى بالنسبة لـ n الكبيرة هي تلك التي توجد فيها خوارزمية يزيد وقت حسابها بطريقة متعددة الحدود ، أي كقوة ثابتة لـ n. يقال إن مثل هذه الخوارزمية فعالة ، والمشكلات التي يمكن حلها بواسطة خوارزمية فعالة تشكل فئة مشاكل التعقيد p (p تعني “وقت متعدد الحدود”).
بعض المشكلات
بعض المشكلات من النوع p ، مثل مشكلة اتصال الرسم البياني (بالنظر إلى خريطة الطريق ، هل من الممكن الوصول إلى كل مدينة من أي مدينة أخرى؟) ، هل من السهل حلها. ومع ذلك ، ليس كل منهم لديهم حل فعال واضح. هذا هو الحال مع اختبار البدائية (بالنظر إلى عدد صحيح ، هل هو أولي أم مركب؟) أو مشكلة المطابقة (بالنظر إلى قائمة الرجال والنساء المستعدين للزواج فلانًا ، هل من الممكن تعيين موافقة الزوج على الجميع؟).
المشكلات الأخرى التي تكون صياغتها غير ضارة للغاية ، تبين أنها أكثر تعقيدًا بكثير. هذه على سبيل المثال مشاكل التخزين (كيفية تخزين مجموعة من الصناديق بأحجام مختلفة في صندوق السيارة) ، 3 ألوان (تحديد ما إذا كان من الممكن تلوين جميع البلدان على الخريطة بثلاثة ألوان في تلك الدولتين المتجاورتين لا تكون أبدًا من نفس اللون) ، أو بائع متجول (ارسم دائرة الحد الأدنى للطول التي تزور جميع مدن المنطقة مرة واحدة فقط). على الرغم من أن لدينا خوارزميات أقل سوءًا لهذه المشكلات من تلك التي تتمثل في تجربة جميع الاحتمالات ، إلا أننا لا نعرف أي طرق أكثر فاعلية بشكل أساسي: يزداد وقت حساب أفضل الخوارزميات المعروفة بشكل كبير مع حجم بيانات المشكلة. .
حدود الحوسبة الكمومية : سؤال مليون دولار
حدود الحوسبة الكمومية : سؤال مليون دولار
المشكلات الثلاث التي ذكرناها للتو لها خاصية مثيرة جدًا للاهتمام: .إنها إصدارات مختلفة من المشكلة “نفسها” ، بمعنى أن وجود خوارزمية فعالة لأحدها يعني وجود خوارزميات فعالة لأحدها. كوك من جامعة تورنتو ، وريتشارد كارب من جامعة كاليفورنيا في بيركلي ، وليونيد ليفين ، الذي يعمل حاليًا في جامعة بوسطن ، إلى هذا الاستنتاج في .السبعينيات ، حيث طوروا نظرية الاكتمال
np تعني “وقت كثير الحدود غير القطعي”. مشاكل الفئة np هي تلك التي يمكن التحقق من حل مقترح لها في زمن كثير الحدود. قد يكون من الصعب تحديد الحل نفسه. على سبيل المثال ، قد يستغرق العثور .على طريق يزور كل مدينة مرة واحدة فقط في بلد به آلاف المدن والطرق سنوات ؛ ولكن إذا قدم شخص ما طريقًا ، فمن السهل. التحقق مما إذا كان اقتراحه حلاً.
تجمع فئة np معًا عددًا كبيرًا من المشكلات ذات الأهمية العملية. لاحظ أن كل مسائل p هي مسائل من باب أولى ، أو بعبارة أخرى ، الصنف p موجود في الصنف np. في الواقع ، إذا تمكنا من حل مشكلة بسرعة ، فيمكننا أيضًا التحقق من الحل بسرعة.
لقد أبرز كل من S. Cook و R. Karp و L. إذا وجدنا خوارزمية فعالة لأحدهم ، فيمكننا تكييفها لحل جميع مشاكل np الأخرى. مشاكل الترتيب والتلوين والباعة المتجولين المذكورة أعلاه هي نماذج أولية لمشاكل np-Complete. تعد مشكلات np-Complete هي الأصعب بطبيعتها.
وجود خوارزمية فعالة
إن وجود خوارزمية فعالة لمشكلة np-complete يعني أن جميع مشاكل np ، .بما في ذلك مشاكل np-complete ، هي في الواقع مشاكل p. تتلخص كل هذه المشكلات في المشكلات التي يمكن حلها في زمن كثير الحدود.
هل توجد مثل هذه الخوارزمية؟ بمعنى آخر ، هل p = np؟ إنه سؤال مليون دولار حرفيًا ، منذ أن اختاره معهد كلاي للرياضيات ، كامبريدج (الولايات المتحدة) ، في عام 2000 من بين “أسئلة الألفية” السبعة ، التي تم تحديد حلها. بسعر مليون دولار.
منذ ما يقرب من نصف قرن منذ طرح هذا السؤال ، لم يجد أحد خوارزمية فعالة لمشكلة كاملة np. لذلك فإن جميع علماء الكمبيوتر مقتنعون الآن تقريبًا بأن هذه العملية ، حتى لو لم يكن أحد قادرًا على .فهم السبب أو إثبات ذلك.
حدود الحوسبة الكمومية : لا يزال هناك أمل واحد فقط لحل مشاكل np الكاملة
حدود الحوسبة الكمومية : لا يزال هناك أمل واحد فقط لحل مشاكل np الكاملة
لنفترض أن أرستها ص فاي. لا يزال هناك أمل واحد فقط لحل مشاكل np الكاملة في وقت معقول (أي متعدد الحدود): لتوسيع مفهوم الكمبيوتر والخوارزمية. للوهلة الأولى ، يبدو أن الإمكانيات التي توفرها ميكانيكا الكم تلبي هذا الهدف تمامًا. تجعل قوانين الكم من الممكن تخزين ومعالجة كمية كبيرة من المعلومات من خلال الاعتماد على. الحالات (الكمية) لعدد صغير من الجسيمات. لنأخذ على سبيل المثال 1000 جسيم يكون دورانها ، عند قياسه ، إما “لأعلى” أو “لأسفل”. الدوران ، أو الزخم الزاوي الجوهري ، هو خاصية كمومية للجسيمات ، لكن معناها الدقيق غير ذي صلة هنا. ما يهم هو في ميكانيكا الكم ، تتميز .حالة هذه المجموعة من الجسيمات بـ “السعات” ، وهي أرقام مركبة مرتبطة باحتمال أن تكون الجسيمات في مثل هذه الحالة أو تلك .
على سبيل المثال ، يرتبط أحد السعة. بإمكانية قياس جميع الجسيمات بدوران “مرتفع”. ، والآخر بالتكوين حيث يكون للأول 500 دوران “مرتفع” بينما يكون للـ 500 الآخر دوران “منخفض”. متتالي. هناك 21000 تكوين محتمل ، أو حوالي 10300 (أكثر من عدد الذرات في الكون المرئي) ، ولكل منها اتساع. الحالة الكمومية لـ 1000 جسيم هي عمومًا تراكب لهذه الحالات الجماعية الأساسية البالغ عددها 10300 ؛السعات المقابلة.
