نموذج الاستعلام في الحوسبة

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

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

النقطة الأساسية هي أن المدخلات تُقدَّم إلى الحساب، عادةً في شكل سلسلة ثنائية، دون إخفاء أي جزء منها.

وصف النموذج

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

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

سنعمل حصرًا مع السلاسل الثنائية في هذا الدرس، خلافًا للسلاسل التي تحتوي رموزًا مختلفة، لذا فلنكتب $\Sigma = \{0,1\}$ من الآن فصاعدًا للإشارة إلى الأبجدية الثنائية بشكل مريح. سنفكر في مسائل حسابية مختلفة، مع بعض الأمثلة البسيطة الموصوفة قريبًا، لكن في جميعها ستكون المدخلات ممثَّلة بدالة تأخذ الشكل:

$$f:\Sigma^n \rightarrow \Sigma^m$$

لعددين صحيحين موجبين $n$ و$m$. بطبيعة الحال، يمكننا اختيار اسم مختلف بدلًا من $f$، لكننا سنلتزم بـ$f$ طوال الدرس.

أن يُجري حساب استعلامًا يعني اختيار سلسلة $x \in \Sigma^n$ ما، ثم إتاحة السلسلة $f(x)\in\Sigma^m$ للحساب من قِبل الأوراكل. الطريقة الدقيقة التي يعمل بها هذا للخوارزميات الكمومية ستُناقَش قريبًا — نحتاج إلى التأكد من إمكانية تنفيذ ذلك بعملية كمومية وحدوية تتيح إجراء الاستعلامات في تراكب — لكن في الوقت الحالي يمكننا التفكير فيه بشكل حدسي على مستوى عالٍ.

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

أمثلة على مسائل الاستعلام

إليك بعض الأمثلة البسيطة على مسائل الاستعلام.

• OR. تأخذ دالة المدخلات الشكل $f:\Sigma^n \rightarrow \Sigma$ (إذًا $m=1$ لهذه المسألة). المهمة هي إخراج $1$ إذا وُجدت سلسلة $x\in\Sigma^n$ تجعل $f(x) = 1$، وإخراج $0$ إذا لم توجد مثل هذه السلسلة. إذا فكرنا في الدالة $f$ باعتبارها تمثيلًا لتسلسل من $2^n$ بت يتوفر لنا وصول عشوائي إليه، فالمسألة هي حساب OR لهذه البتات.

• التكافؤ (Parity). تأخذ دالة المدخلات مرة أخرى الشكل $f:\Sigma^n \rightarrow \Sigma$. المهمة هي تحديد ما إذا كان عدد السلاسل $x\in\Sigma^n$ التي تجعل $f(x) = 1$ زوجيًا أم فرديًا. بدقة، الإخراج المطلوب هو $0$ إذا كانت المجموعة $\{x\in\Sigma^n : f(x) = 1\}$ تضم عددًا زوجيًا من العناصر و$1$ إذا كانت تضم عددًا فرديًا. إذا فكرنا في الدالة $f$ باعتبارها تمثيلًا لتسلسل من $2^n$ بت يتوفر لنا وصول عشوائي إليه، فالمسألة هي حساب التكافؤ (أو XOR الشامل) لهذه البتات.

• الحد الأدنى (Minimum). تأخذ دالة المدخلات الشكل $f:\Sigma^n \rightarrow \Sigma^m$ لأي اختيارات من الأعداد الصحيحة الموجبة $n$ و$m$. الإخراج المطلوب هو السلسلة $y \in \{f(x) : x\in\Sigma^n\}$ التي تأتي أولًا في الترتيب المعجمي (أي الترتيب القاموسي) لـ$\Sigma^m$. إذا فكرنا في الدالة $f$ باعتبارها تمثيلًا لتسلسل من $2^n$ عدد صحيح مُشفَّر كسلاسل بطول $m$ بالنظام الثنائي يتوفر لنا وصول عشوائي إليه، فالمسألة هي حساب الحد الأدنى لهذه الأعداد.

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

مثال على مسألة بوعد:

• البحث المنفرد (Unique search). تأخذ دالة المدخلات الشكل $f:\Sigma^n \rightarrow \Sigma$، ونحن مَوعودون بوجود سلسلة واحدة بالضبط $z\in\Sigma^n$ تجعل $f(z) = 1$، وأن $f(x) = 0$ لجميع السلاسل $x\neq z$. المهمة هي إيجاد هذه السلسلة المنفردة $z$.

الأمثلة الأربعة الموصوفة للتو طبيعية، بمعنى أنها سهلة الوصف ويمكن تخيّل طيف واسع من المواقف أو السياقات التي قد تنشأ فيها.

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

بوابات الاستعلام

حين نصف الحسابات بالدوائر، تُجرى الاستعلامات بواسطة بوابات خاصة تُسمى بوابات الاستعلام.

أبسط طريقة لتعريف بوابات الاستعلام للدوائر البولية الكلاسيكية هي السماح لها بحساب دالة المدخلات $f$ مباشرة، كما يوضح الشكل التالي.

حين تُبنى دائرة بولية لمسألة استعلام، يُوصَل إلى دالة المدخلات $f$ من خلال هذه البوابات، وعدد الاستعلامات التي تُجريها الدائرة هو ببساطة عدد بوابات الاستعلام الظاهرة فيها. تُهيَّأ أسلاك الإدخال للدائرة البولية نفسها بقيم ثابتة، ينبغي اعتبارها جزءًا من الخوارزمية (وليس مدخلات للمسألة).

مثلًا، إليك دائرة بولية مع بوابات استعلام كلاسيكية تحل مسألة التكافؤ الموصوفة أعلاه لدالة من الشكل $f:\Sigma\rightarrow\Sigma$:

تُجري هذه الخوارزمية استعلامين لأن هناك بوابتي استعلام. طريقة عملها هي استعلام الدالة $f$ على الإدخالين المحتملين $0$ و$1$، ثم تُدخَل النتائج في دائرة بولية تحسب XOR. (ظهرت هذه الدائرة تحديدًا كمثال لدائرة بولية في درس الدوائر الكمومية من دورة أساسيات المعلومات الكمومية.)

أما بالنسبة للدوائر الكمومية، لا يصلح هذا التعريف لبوابات الاستعلام لأن هذه البوابات ستكون غير وحدوية لبعض اختيارات الدالة $f$. لذا، ما نفعله بدلًا من ذلك هو تعريف بوابات استعلام وحدوية تعمل كما يوضح هذا الشكل على حالات الأساس القياسية:

هنا، افتراضنا أن $x\in\Sigma^n$ و$y\in\Sigma^m$ سلسلتان اعتباطيتان. الرمز $y\oplus f(x)$ يشير إلى XOR البتي لسلسلتين، بطول $m$ في هذه الحالة. مثلًا، $001 \oplus 101 = 100$.

بتعبير حدسي، ما تفعله البوابة $U_f$ (لأي دالة $f$ مختارة) هو إعادة إخراج سلسلة الإدخال العلوية $x$ وإجراء XOR لقيمة الدالة $f(x)$ على سلسلة الإدخال السفلية $y$، وهي عملية وحدوية لكل اختيار من الدالة $f$. في الواقع، هي عملية حتمية وهي معكوسها الخاص. هذا يعني أن $U_f$ كمصفوفة هي دائمًا مصفوفة تبديل، أي مصفوفة فيها $1$ واحد في كل صف وكل عمود، وصفر في كل المدخلات الأخرى. تطبيق مصفوفة تبديل على متجه يُعيد ترتيب مدخلات المتجه فحسب (ومن هنا اسم مصفوفة التبديل)، وبالتالي لا يغير قاعدة المتجه الإقليدية — كاشفًا أن مصفوفات التبديل وحدوية دائمًا.

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

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