1. خوارزمية شور (Shor's Algorithm) وأهميتها [0]

thumbnail

1.1. مقدمة وأهداف الخوارزمية [0]

  1. خوارزمية شور هي الخوارزمية الكمومية الأكثر أهمية وشيوعًا. [0]
  2. تسمح هذه الخوارزمية بإيجاد العوامل الأولية لعدد كبير . [1]
    1. إذا كان (حيث و أوليان)، فإن الخوارزمية تجد و . [1]
  3. هذه القدرة هي العمود الفقري لتشفير RSA واسع الاستخدام. [2]
    1. استخدام خوارزمية شور سيسمح بكسر تشفير RSA. [2]
    2. هذا لن يحدث قريبًا ويتطلب حاسوبًا كموميًا متسامحًا مع الأخطاء. [3]
    3. يتطلب الحاسوب الكمومي ملايين من الكيوبتات المنطقية. [3]
  4. تستخدم الخوارزمية كلًا من الحواسيب الكلاسيكية والكمومية لخطوات مختلفة. [4]
  5. الخطوة الكلاسيكية الأولى: اختيار عدد بين 1 و . [5]
    1. يجب أن يكون القاسم المشترك الأكبر (GCD) لـ و هو 1. [5]
    2. هذا يعني أن و لا يشتركان في عوامل مشتركة. [5]
  6. الخطوة التالية هي الخطوة الكمومية، ولكن يجب مراجعة نظرية الأعداد أولًا. [6]
  7. الحساب المعياري (Modular Arithmetic): يقال أن يطابق معيار . [7]
    1. هذا يعني أن باقي قسمة على هو . [7]
    2. مثال: 3 يطابق 1 معيار 2، لأن باقي قسمة 3 على 2 هو 1. [8]
  8. يمكن اختزال مشكلة التحليل إلى إيجاد فترة الأسس المعيارية. [9]
    1. الأسس المعيارية هي أخذ قوى عدد ما معيار عدد آخر. [10]
    2. مثال: عند أخذ قوى متزايدة لعدد (مثل 2) معيار ، نحصل على نمط متكرر. [11]
    3. الفترة $R$ هي طول هذا التسلسل المتكرر. [12]
    4. في المثال المذكور، الفترة تساوي 6. [13]
    5. تبدأ جميع التسلسلات بـ يطابق 1 معيار . [14]
    6. يجب زيادة القوة حتى العودة إلى 1. [14]
  9. إذا تمكنا من إيجاد الفترة ، يمكن استخدام نظرية الأعداد لإيجاد العوامل الأولية. [15]
    1. إذا كان واختير بحيث . [16]
    2. إذا وجدنا تقريبًا جيدًا لـ (فترة ). [17]
    3. فإن و لديهما فرصة جيدة لاحتواء عوامل . [17]

1.2. الخطوة الكمومية: إيجاد الفترة باستخدام تقدير الطور الكمومي [18]

  1. الخطوات التالية توضح كيفية إيجاد فترة الأسس المعيارية . [18]
  2. نحتاج إلى بوابة التي تحول الحالة إلى الحالة . [19]
  3. تطبيق هذه البوابة عدة مرات على الحالة يعطي قوى معيار . [20]
    1. كيفية بناء هذه البوابة خارج نطاق هذا المساق. [21]
  4. تحليل المتجهات الذاتية (Eigenvectors): [22]
    1. النظر في حالة معينة (لم يتم تحديدها صراحة). [22]
    2. تطبيق البوابة على هذه الحالة يعطي حالة جديدة. [23]
    3. يمكن تغيير إلى لأن كلاهما يساوي 1. [24]
    4. بضرب الطرف الأيمن في 1 (باستخدام )، نحصل على حالة معينة. [25]
    5. يمكن تغيير إلى لأن كلاهما يساوي 1. [26]
    6. تصبح الحالة بأكملها هي حالة . [27]
    7. هذا يعني أن الحالة هي متجه ذاتي (Eigenvector) للبوابة . [28]
    8. القيمة الذاتية (Eigenvalue) المقابلة هي . [28]
  5. إذا تمكنا من بناء الحالة ، يمكن استخدام خوارزمية تقدير الطور الكمومي (Quantum Phase Estimation - QPE). [29]
    1. تستخدم QPE للحصول على قيمة . [29]
  6. بناء حالة التراكب: [30]
    1. من الأسهل بكثير بناء التراكب المتساوي لجميع حالات . [30]
    2. هذا التراكب المتساوي يصبح الحالة . [30]
    3. يمكن بناء الحالة بتطبيق بوابة Hadamard على الكيوبت الأيمن في سجل من الأصفار. [32]
    4. بناء الحالة ينشئ فعليًا الحالة: . [33]
  7. تطبيق QPE: [34]
    1. الدائرة المستخدمة هي ببساطة دائرة تقدير الطور الكمومي. [34]
    2. نعلم أن هو متجه ذاتي للبوابة . [36]
    3. نستخدم هذا لتقدير القيمة الذاتية . [37]
    4. هو عدد صحيح من 0 إلى . [37]
    5. المتجه الذاتي هو تراكب لجميع حالات . [38]
    6. عند قياس الكيوبتات، نحصل على القيمة الذاتية لواحدة من حالات . [39]
    7. هذا يعني أننا سنحصل على قيمة لـ واحدة من 0 إلى . [39]
    8. إذا كانت القيمة الذاتية المقاسة هي صفر ()، يجب تكرار الدائرة. [40]
    9. الهدف هو الحصول على قيمة ذاتية غير صفرية. [40]
  8. بعد الخطوة الكمومية، نحصل على عدد عشري يساوي . [41]

1.3. الخطوة الكلاسيكية الثانية: استخدام الكسور المستمرة لاستخلاص [42]

  1. يتم تقدير قيم و باستخدام تقنية تسمى الكسور المستمرة (Continued fractions). [42]
    1. مثال على الكسر المستمر للعدد العشري 0.312. [42]
  2. عملية الكسور المستمرة: [43]
    1. نبدأ بكتابة العدد ككسر. [43]
    2. ثم نقلب الكسر. [43]
    3. نستمر في هذه العملية حتى يصبح البسط هو العدد 1. [44]
  3. يمكن تقريب قيمة العدد العشري بكسر عن طريق تقريب الكسر المستمر. [45]
    1. يوضح النص أول ثلاثة تقريبات للعدد العشري 0.312. [46]
  4. لتقريب ، نجد تقريبًا يكون فيه المقام أقل من . [47]
    1. يجب أن تكون الفترة أقل من . [47]
  5. إذا كانت فردية، يجب تكرار الخوارزمية للحصول على قيمة جديدة لـ . [48]
  6. إيجاد العوامل: [49]
    1. بعد الحصول على قيمة لـ ، يمكن استخدامها لإيجاد عوامل . [49]
    2. نعلم أن يطابق 1 معيار . [50]
    3. هذا يعني أن يطابق 0 معيار . [50]
    4. بالتالي، له عامل (لأن الباقي صفر عند القسمة على ). [51]
    5. بتحليل باستخدام فرق مربعين، نحصل على . [52]
    6. بحساب و باستخدام تقريب . [53]
    7. هناك فرصة جيدة لأن يكون أحدهما أو كلاهما أحد عوامل . [53]
    8. هذا يسمح بإيجاد و . [54]

1.4. مثال عملي: تحليل العدد 15 [55]

  1. مثال سريع مع يساوي 15، حيث و . [55]
  2. الخطوة 1 (كلاسيكية): اختيار أولي نسبيًا مع 15. [56]
    1. نختار يساوي 7. [57]
  3. الخطوة 2 (كمومية): استخدام الجزء الكمومي لإيجاد الفترة . [58]
    1. يجب إيجاد بحيث يطابق 1 معيار 15. [59]
    2. باستخدام الخوارزمية، نجد أن تساوي 4. [60]
  4. الخطوة 3 (كلاسيكية): حساب القاسم المشترك الأكبر (GCD). [61]
    1. نحسب و . [61]
  5. النتائج: [62]
    1. الأول يصبح . [62]
    2. الثاني يصبح . [62]
    3. هو 3. [63]
    4. هو 5. [63]
    5. تم إيجاد عوامل 15 (3 و 5) باستخدام خوارزمية شور. [64]