Pseudoentanglement in constant depth: How trivial states can have non-trivial entanglement structure

ملخص تقني: التشابك الزائف في العمق الثابت

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

هناك سؤال مفتوح حاسم يتعلق بالعلاقة بين التشابك الزائف والعشوائية الزائفة (Pseudorandomness). فبينما تتطلب الحالات العشوائية الزائفة (PRSs) واليونيتريات العشوائية الزائفة (PRUs) أن يكون دائرة التحضير مخفية (أو أن يكون عمق الدائرة كافياً لمنع التعلم الفعال)، تشير النتائج الحديثة إلى أن الدوائر الكمومية ذات العمق الثابت وعدد المداخل المحدود ($QNC^0$) يمكن تعلمها بكفاءة من خلال عينات متعددة الحدود. هذا القابلية للتعلم تستبعد وجود حالات عشوائية زائفة في $QNC^0$. ومع ذلك، لا يزال من غير الواضح ما إذا كان يمكن تحضير حالات متشابكة زائفاً بواسطة مثل هذه الدوائر الضحلة والمحلية هندسياً. تحديداً، هل يمكن للحالات "التافهة" (تلك التي يمكن تحضيرها بدوائر ذات عمق ثابت) أن تظهر هياكل تشابك يصعب تقديرها حوسبياً؟

المنهجية
تبني الورقة البحثية عائلة من الدوائر الكمومية ذات العمق الثابت والمحلية في البعد الثاني (2D-local) والتي تنتج حالات متشابكة زائفاً. يعتمد البناء على ثلاثة مكونات تقنية رئيسية:

1. الافتراض التشفيري: صعوبة مشكلة تعلم التكافؤ مع الضجيج الكثيف-الخفيف (Dense-Sparse Learning Parity with Noise)، والتي قدمها Dao وJain [DJ25]. يوفر هذا الافتراض زوجاً من الخرائط الخطية، $F_{low}$ و $F_{high}$، وهما غير قابلتين للتمييز حوسبياً ولكن لديهما خصائص إنتروبيا مختلفة على المدخلات الخفيفة (sparse). وتحديداً، $F_{high}$ هي دالة متباينة (injective) على المدخلات الخفيفة (مما ينتج إنتروبيا عالية)، بينما $F_{low}$ هي دالة متعددة لواحد (many-to-one) (مما ينتج إنتروبيا منخفضة).
2. الترميز العشوائي ذو المداخل المحدودة: المساهمة التقنية الجوهرية هي ترميز عشوائي مثالي جديد للخرائط الخطية الكثيفة $x \mapsto Mx$. بخلاف عمليات الترميز السابقة التي تطلبت بوابات مخرجات غير محدودة (unbounded fan-out)، يستخدم هذا البناء فقط بوابات ذات مداخل ومخرجات محدودة (تحديداً، مدخل/مخرج $\le 3$).
   • يُدخل الترميز أقنعة عشوائية موحدة $r$ و $s$.
   • يُنتج بتات $w$ و $z$ بحيث يمكن لمفكك شفرة حتمي استعادة $Mx$.
   • والأهم من ذلك، أن إنتروبيا المخرجات المرمزة تساوي تماماً $H(Mx)$ مضافاً إليها حد ثابت يعتمد على القناع ومستقل عن المصفوفة $M$. وهذا يحافظ على فجوة الإنتروبيا بين فرعي الخريطة الخطية "المنخفض" و"العالي".
   • يتم تنفيذ الترميز عبر شبكة ثنائية الأبعاد من البلاكيتات (plaquettes) ذات الحجم الثابت باستخدام بوابات CNOT ذات الجيران الأقرب فقط، مما يضمن أن الدائرة محلية في البعد الثاني وذات عمق ثابت.
3. تحضير الحالة: يقوم المؤلفون بتحضير تراكب متماسك لبتات المدخلات (المأخوذة من توزيع Bernoulli خفيف) والأقنعة العشوائية. ثم يطبقون دائرة الترميز العشوائي بشكل متماسك. يؤدي تتبع سجلات المدخلات والقناع يترك مصفوفة كثافة قطرية على سجلات المخرجات، حيث تساوي إنتروبيا شانون لترميز الخريطة العشوائية. وبسبب خاصية الحفاظ على الإنتروبيا، تعكس إنتروبيا التشابك عبر القطع (cut) بين المدخل والمخرج فجوة الإنتروبيا للخرائط الخطية الأساسية.

المساهمات والنتائج الرئيسية

• النظرية 1.1 (التشابك الزائف في العمق الثابت): بافتراض عدم قدرة الخوارزميات الكمومية ذات الوقت متعدد الحدود (QPT) على حل مشكلة Dense-Sparse LPN، توجد توزيعة يمكن أخذ عينات منها بكفاءة لمجموعات من $(C_{low}, C_{high}, W)$، حيث $C_{low}$ و $C_{high}$ هما دائرتان محليتان في البعد الثاني وذات عمق ثابت. تمتلك الحالات الناتجة $|\psi_{low}\rangle$ و $|\psi_{high}\rangle$ فجوة إنتروبيا تشابك إضافية قدرها $\omega(\log n)$ عبر قطع ثابت $W$، ومع ذلك فإن أوصاف الدوائر غير قابلة للتمييز حوسبياً.

  • الأهمية: يثبت هذا أن التشابك الزائف ممكن في نظام $QNC^0$، بينما العشوائية الزائفة ليست كذلك. هذه الحالات هي حالات "مفتاح عام" (public-key) متشابكة زائفاً: دوائر تحضيرها عامة وضحلة، ومع ذلك فإن هيكل تشابكها مخفي.

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

• النظرية 1.3 (صعوبة الهاملتوني في البعد الثاني): من خلال دمج مساقط محلية مع دوائر التشابك الزائف، يبني المؤلفون عائلة من الهاملتونيات المحلية في البعد الثاني ذات فجوة طيفية ثابتة (الفجوة = 1). ترث الحالات الأرضية الفريدة لهذه الهاملتونيات فجوة التشابك، مما يجعل مهمة تعلم إنتروبيا التشابك عبر قطع ثابت أمراً صعباً حوسبياً كمومياً.

• النظرية 1.4 (صعوبة الهاملتوني في البعد الأول): باستخدام بناء حالة تاريخ Feynman–Kitaev المبطن في البعد الأول، يوسع المؤلفون النتيجة إلى هاملتونيات محلية في البعد الأول. تمتلك هذه الهاملتونيات فجوة طيفية عكسية متعددة الحدود. وتحتفظ الحالات الأرضية الفريدة بفجوة التشابك (مع فقدان إضافي صغير)، مما يثبت الصعوبة في الأنظمة أحادية البعد بناءً على افتراض كود مستند إلى التشفير بعد الكمي.

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

• الطبيعة "المفتاح العام": على عكس الحالات العشوائية الزائفة، التي تتطلب أن تكون دائرة التحضير سرية، يتم توليد هذه الحالات المتشابكة زائفاً بواسطة دوائر عامة. وهذا يسمح بصياغة نتائج الصعوبة في نموذج التعقيد الحوسبي (المدخل هو وصف كلاسيكي لدائرة أو هاملتوني) بدلاً من نموذج تعقيد العينات.
• الأمان بعد الكمي: تعتمد الصعوبة على Dense-Sparse LPN، وهو افتراض مستند إلى الكود يُعتقد أنه آمن ضد المهاجمين الكموميين، مما يميزها عن النتائج السابقة (مثل [BZZ24]) التي اعتمدت على تحليل العوامل (الذي يمكن حله كمومياً).
• القيود: يشير المؤلفون صراحة إلى القيود. "القطع المخفي" هو قطع ثابت وغير هندسي (يتم تحديده بواسطة بنية الدائرة وليس منطقة مكانية متصلة)، مما يعني أن النتيجة لا تعالج مباشرة القطوع الهندسية ذات الصلة بتمييز قانون المساحة مقابل قانون الحجم في الجاذبية الكمومية. بالإضافة إلى ذلك، فإن البناء محدد لإنتروبيا فون نيومان (شانون)؛ وتعميم النتيجة على إنتروبيا ريني (Rényi) الأخرى ليس مضموناً بالتحليل الحالي للدالة الخاسرة.

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