Answering Counting Queries with Differential Privacy on a Quantum Computer

إليك ملخص تقني مفصل للورقة البحثية بعنوان "الإجابة على استعلامات العد مع الخصوصية التفاضلية على حاسوب كمي" من تأليف موخيرجي، وأسغار، وبرينين.

1. بيان المشكلة

تتناول الورقة البحثية تحدي إجراء تحليل إحصائي على مجموعات البيانات الحساسة المخزنة بتنسيق مشفر كمياً مع ضمان الخصوصية التفاضلية (Differential Privacy - DP).

• السياق: يقوم عميل ($C$) برفع مجموعة بيانات إلى خادم كمي ($S$)، والذي يقوم بدوره بالإجابة على استعلامات لمحلل طرف ثالث ($T$). يتم تشفير مجموعة البيانات كحالة كمية (تحديداً التشفير بالأساس - basis encoding).
• الهدف: الإجابة على استعلامات العد (مثل: "كم عدد الأشخاص الذين تزيد أعمارهم عن 25 عاماً ويحملون شهادة جامعية؟") دون المساس بخصوصية الأفراد.
• الدوافع:
  1. تضخيم الخصوصية (Privacy Amplification): تشير الأعمال الحديثة إلى أن التشفير الكمي يعزز الخصوصية بطبيعته بسبب عشوائية القياسات الكمية، مما قد يوفر ضمانات أقوى من الآليات الكلاسيكية.
  2. الاستعانة بمصادر خارجية بكفاءة (Efficient Outsourcing): باستخدام الحشوة الكمية أحادية الزمن (Quantum One-Time Pad - QOTP)، يمكن للعميل تشفير مجموعة البيانات. ويمكن للخادم بعد ذلك إجراء عمليات حسابية بشكل متماثل (بشكل أعمى/homomorphically) دون معرفة البيانات، بشرط أن تكون العمليات متوافقة مع التشفير (بوابات Pauli أو Clifford).
• التحدي المحدد: بينما توجد آليات خصوصية تفاضلية كمية عامة، إلا أنها غالباً ما تضيف ضوضاء مفرطة. يهدف المؤلفون إلى اشتقاق حدود خصوصية أكثر إحكاماً خصيصاً لاستعلامات العد من خلال استغلال بنية السعة الكمية (amplitude) والحساسية المحددة لهذه الاستعلامات.

2. المنهجية

يقترح المؤلفون آليتين متميزتين لتقدير الإجابة على استعلام عد $q(D)$ لمجموعة بيانات مشفرة كمياً $|\phi_D\rangle = \frac{1}{\sqrt{n}}\sum |x_i\rangle$.

أ. التشفير الكمي وتفكيك الاستعلام

استعلام العد $q$ هو دالة بولية (Boolean function) تربط الصفوف بالمجموعة $\{0, 1\}$. يمكن تفكيك الحالة الكمية $|\phi_D\rangle$ إلى فضاءين فرعيين متعامدين:

• الفضاء الفرعي "الجيد" ($|\phi_G\rangle$): يشمل الصفوف حيث $q(x)=1$.
• الفضاء الفرعي "السيئ" ($|\phi_B\rangle$): يشمل الصفوف حيث $q(x)=0$.
  تصبح الحالة $|\phi_D\rangle = \sqrt{\alpha}|\phi_G\rangle + \sqrt{1-\alpha}|\phi_B\rangle$، حيث $\alpha = q(D)/n$ هو الإجابة الموحدة للاستعلام. الهدف هو تقدير $\alpha$.

ب. الآلية 1: القياس المباشر (العينات المتكررة)

تتضمن هذه الطريقة قياس الكيوبت المساعد (ancilla qubit) -الذي يشير إلى نتيجة الاستعلام- في القاعدة الحسابية $t$ من المرات.

• العملية: يرسل العميل $t$ من النسخ المشفرة للحالة. يقوم الخادم بقياس الكيوبت المساعد، ويحصل على سلسلة من الأصفار والآحاد. المتوسط لهذه النتوات يقدر $\alpha$.
• تحليل الخصوصية:
  • يعيد المؤلفون تحليل خصوصية هذه العملية، موضحين أنها تعادل أخذ عينات عشوائية لـ $t$ من الصفوف من مجموعة البيانات وإرجاع متوسط نتائج الاستعلام على تلك الصفوف.
  • يثبتون أنه إذا لم يتم أخذ الصف الحساس كعينة (وهو ما يحدث باحتمالية عالية بالنسبة لـ $n$ كبيرة)، فإن المخرجات ستكون متطابقة لمجموعات البيانات المتجاورة، مما يوفر خصوصية نقية دون إضافة ضوضاء.
  • إذا تم أخذ الصف الحساس كعينة $j$ من المرات، فإن الحساسية تكون $j/t$.
  • النتيجة: يشتقون طيفاً من ضمانات $(\epsilon, \delta)$-DP. والأهم من ذلك، أنه بالنسبة لـ $k=0$ (عدم إضافة ضوضاء صريحة)، فإن الآلية تحقق $(0, \delta_0)$-DP. وبالنسبة لـ $k \ge 1$، فإن إضافة ضوضاء لابلاس (Laplace noise) بمقياس $k/(t\epsilon)$ تعطي $\epsilon$ أقل بكثير من الحدود العامة المعروفة سابقاً.

ج. الآلية 2: تقدير السعة (تقدير الطور - Phase Estimation)

تستخدم هذه الطريقة خوارزمية تقدير السعة لـ Brassard وآخرون لتقدير $\alpha$ مع تسريع تربيعي ($O(1/\Delta)$ مقابل $O(1/\Delta^2)$ للقياس المباشر).

• العملية: تستخدم الخوارزمية مؤثر وحدة (unitary operator) $Q$ (شبيه بـ Grover) لتدوير الحالة في الفضاء ثنائي الأبعاد الذي يشغله $|\phi_G\rangle$ و $|\phi_B\rangle$. زاوية الدوران هي $2\theta_\alpha$، حيث $\sin^2(\theta_\alpha) = \alpha$.
• اشتقاق الحساسية العالمية:
  • يشتق المؤلفون الحساسية العالمية للزاوية $\theta_\alpha$. بما أن حساسية العد $\alpha$ هي $1/n$، فإنهم يحللون الدالة $f(\theta) = \sin^2(\theta)$.
  • يثبتون أن أقصى تغير في الزاوية $\Delta \theta$ ناتج عن تغير قدره $1/n$ في $\alpha$ هو $\sin^{-1}(1/\sqrt{n})$. هذا هو الحد الضيق المستخدم لمعايرة الضوضاء.
• تنفيذ الخصوصية:
  • بدلاً من إضافة الضوضاء إلى القياس النهائي، يقومون بإدخال مؤثر وحدة $U_\eta$ يضيف إزاحة طور عشوائية $\eta$ إلى القيم الذاتية للمؤثر $Q$.
  • يتم أخذ $\eta$ من توزيع لابلاس بمقياس يتناسب مع حساسية الزاوية المشتقة: $\text{Lap}(\sin^{-1}(1/\sqrt{n})/\epsilon)$.
  • يتم تطبيق هذه الضوضاء قبل قياس تقدير الطور، مما يضمن أن المخرجات تحقق الخصوصية التفاضلية.

د. التعامل مع الضوضاء المتأصلة (قنوات إزالة الاستقطاب - Depolarizing Channels)

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

• يوضح المؤلفون أن ضوضاء إزالة الاستقطاب المطبقة بعد مؤثرات الوحدة تعمل كمضخم إضافي للخصوصية.
• باستخدام نظرية التركيب (composition theorem)، يجمعون بين ضوضاء لابلاس الصريحة والضوضاء الضمنية من قناة إزالة الاستقطاب لتوفير ميزانية خصوصية إجمالية $(\epsilon_{total}, \delta)$.

هـ. الحوسبة العمياء (التشفير المتماثل - Homomorphic Encryption)

للسماح للخادم بإجراء الحسابات دون رؤية البيانات:

• يتم تشفير مجموعة البيانات باستخدام الحشوة الكمية أحادية الزمن (QOTP) ($X^a Z^b$).
• يتم تنفيذ دوائر الاستعلام (المكونة من بوابات CNOT، Toffoli، إلخ) بشكل متماثل.
• القيد: بينما يمكن تطبيق بوابات Pauli و Clifford مع تحديثات بسيطة للمفاتيح، فإن البوابات غير الـ Clifford (مثل بوابة $T$ المطلوبة لبوابة Toffoli) تتطلب "حالات سحرية" (magic states) وتفاعلاً من العميل لتحديث المفاتيح. يشير المؤلفون إلى أنه بالنسبة لاستعلامات السمات الفردية البسيطة على البيانات الثنائية، يمكن تنفيذ دوائر مكونة من بوابات Clifford فقط، مما يتيح حساباً أعمى بالكامل وغير تفاعلي.

3. المساهمات الرئيسية

1. تحليل خصوصية منقح للقياس المباشر: يثبت المؤلفون أنه بالنسبة لاستعلامات العد، توفر آلية القياس المباشر تضخيماً للخصوصية. ويظهرون أننا نحتاج إلى ضوضاء أقل مما اقترحته حدود الخصوصية الكمية العامة سابقاً، وفي بعض النطاقات ($k=0$)، تحقق الآلية الخصوصية التفاضلية ببساطة من خلال عشوائية العينات الكمية.
2. حساسية عالمية ضيقة لتقدير السعة: يشتقون حداً علوياً دقيقاً للتغير في زاوية الطور ($\sin^{-1}(1/\sqrt{n})$) الناتج عن تغيير نقطة بيانات واحدة. وهذا يسمح بمعايرة ضوضاء أكثر إحكاماً بكثير من استخدام حساسية السعة الخام.
3. تقدير السعة ذو الخصوصية التفاضلية: يقترحون طريقة جديدة لجعل خوارزمية تقدير السعة ذات خصوصية تفاضلية عن طريق حقن الضوضاء في طور القيم الذاتية لمؤثر Grover، بدلاً من المخرج النهائي.
4. دمج الضوضاء المتأصلة: يوضحون كيفية احتساب ضوضاء إزالة الاستقطاب الطبيعية لأجهزة الكم الكمي للمساهمة في تقليل كمية الضوضاء الصريحة المطلوبة.
5. إطار الحوسبة العمياء: يضعون خارطة طريق لكيفية الاستعانة بمصادر خارجية لهذه الآليات لخادم كمي باستخدام QOTP، مع تحليل المقايضات بين تعقيد الاستعلام والحاجة إلى تفاعل العميل (الحالات السحرية).

4. النتائج

• القياس المباشر: بالنسبة لمجموعة بيانات بحجم $n=10^6$ و $t=10^3$ من القياسات، تحقق الآلية $\epsilon \approx 0.0006$ (مع $k=2$) أو خصوصية نقية ($\epsilon=0$) مع $\delta$ صغير إذا لم يتم إضافة ضوضاء. يعد هذا تحسناً كبيراً مقارنة بالحد العام المستمد من العمل السابق [3].
• تقدير السعة: الحساسية المشتقة $\sin^{-1}(1/\sqrt{n})$ أصغر بكثير من حساسية السعة نفسها بالنسبة لـ $n$ كبيرة، مما يسمح باستعلامات أكثر دقة مع نفس ميزانية الخصوصية.
• الكفاءة: توفر طريقة تقدير السعة تسريعاً تربيعياً في تعقيد الاستعلام مقارنة بالقياس المباشر، رغم أنها تتطلب أجهزة كم كمية مصححة للأخطاء (وليس أجهزة NISQ).

5. الأهمية

• التقدم النظري: تجسر الورقة البحثية الفجوة بين الخصوصية التفاضلية الكلاسيكية والحوسبة الكمية من خلال تقديم حدود محكمة ومحددة لأكثر فئات الاستعلامات شيوعاً (العد/المحمول). وهي تتحدى الافتراض بأن الخصوصية التفاضلية الكمية تتطلب دائماً ضوضاء ثقيلة، وتظهر أن ميكانيكا الكم يمكن أن تضخم الخصوصية بشكل طبيعي.
• الآثار العملية: تشير النتائج إلى أن الخوادم الكمية يمكن أن توفر رؤى إحصائية دقيقة للغاية على البيانات الحساسة بتكاليف خصوصية أقل من الخوادم الكلاسيكية، بشرط أن تدعم الأجهزة الخوارزميات اللازمة.
• أمن الاستعانة بمصادر خارجية: يوفر النقاش حول QOTP والتقييم المتماثل خارطة طريق للتحليل الكمي الأعمى والآمن للبيانات، وهي خطوة حاسمة نحو الحوسبة الكمية السحابية العملية للمجالات الحساسة مثل الرعاية الصحية أو بيانات التعداد السكاني.
• الوعي بالأجهزة: من خلال مراعاة ضوضاء إزالة الاستقطاب، يقر العمل بالواقع الفعلي لأجهزة الكم الكمية القريبة من المثالية (NISQ)، مما يوفر إطاراً حيث تساهم عيوب الأجهزة في تعزيز الأمن بدلاً من مجرد إضعاف الأداء.