آلة تورينج الكمومية

آلة تورينج الكمومية ( QTM ) أو الحاسوب الكمومي الشامل هي آلة مجردة تُستخدم لنمذجة تأثيرات الحاسوب الكمومي . وهي توفر نموذجًا بسيطًا يجسد كل قوة الحوسبة الكمومية، أي أنه يمكن التعبير عن أي خوارزمية كمومية رسميًا كآلة تورينج كمومية محددة. ومع ذلك، فإن الدائرة الكمومية المكافئة حسابيًا هي النموذج الأكثر شيوعًا. ^{[ 1 ] [ 2 ] : 2}

يمكن ربط آلات تورينغ الكمومية بآلات تورينغ الكلاسيكية والاحتمالية ضمن إطار عمل قائم على مصفوفات الانتقال . أي أنه يمكن تحديد مصفوفة يكون حاصل ضربها مع مصفوفة تمثل آلة كلاسيكية أو احتمالية هو مصفوفة الاحتمال الكمومي التي تمثل الآلة الكمومية. وقد أثبت ذلك لانس فورتناو . ^{[ 3 ]}

إحدى طرق فهم آلة تورينج الكمومية (QTM) هي أنها تعمم آلة تورينج الكلاسيكية (TM) بنفس الطريقة التي تعمم بها آلة الأوتوماتون الكمومية المحدودة (QFA) آلة الأوتوماتون الحتمية المحدودة (DFA). في جوهرها، تُستبدل الحالات الداخلية لآلة تورينج الكلاسيكية بحالات نقية أو مختلطة في فضاء هيلبرت ؛ وتُستبدل دالة الانتقال بمجموعة من المصفوفات الوحدوية التي تُسقط فضاء هيلبرت على نفسه. ^{[ 4 ]}

أي أن آلة تورينج الكلاسيكية تُوصف بسبعة عناصر .${\displaystyle M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle }$. راجع التعريف الرسمي لآلة تورينج للحصول على فهم أكثر تعمقًا لكل عنصر من عناصر هذه المجموعة.

بالنسبة لآلة تورينج الكمومية ذات الأشرطة الثلاثة (شريط واحد يحمل المدخلات، وشريط ثانٍ يحمل نتائج الحسابات الوسيطة، وشريط ثالث يحمل المخرجات):

• مجموعة الحالات${\displaystyle Q}$يتم استبدالها بمساحة هيلبرت .
• رموز الأبجدية الشريطية${\displaystyle \Gamma }$وبالمثل يتم استبدالها بفضاء هيلبرت (عادةً ما يكون فضاء هيلبرت مختلفًا عن مجموعة الحالات).
• الرمز الفارغ${\displaystyle b\in \Gamma }$هو عنصر من عناصر فضاء هيلبرت.
• رموز الإدخال والإخراج${\displaystyle \Sigma }$عادة ما يتم اعتبارها مجموعة منفصلة، ​​كما هو الحال في النظام الكلاسيكي؛ وبالتالي، لا يلزم أن يكون المدخل أو المخرج لآلة الكم نظامًا كميًا بحد ذاته.
• دالة الانتقال${\displaystyle \delta$ :\Sigma \times Q\otimes \Gamma \to \Sigma \times Q\otimes \Gamma \times \{L,R\}} هو تعميم لشبه الأوتوماتون، ويُفهم على أنه مجموعة من المصفوفات الوحدوية التي هي تشاكلات ذاتية لفضاء هيلبرت.${\displaystyle Q}$.
• الحالة الأولية${\displaystyle q_{0}\in Q}$قد تكون حالة مختلطة أو حالة نقية .
• المجموعة${\displaystyle F}$فضاء هيلبرت هو فضاء فرعي خطي من الحالات النهائية أو المقبولة${\displaystyle Q}$.

ما سبق ليس سوى رسم تخطيطي لآلة تورينج الكمومية، وليس تعريفها الرسمي، إذ يترك العديد من التفاصيل المهمة غامضة: على سبيل المثال، عدد مرات إجراء القياس ؛ انظر، على سبيل المثال، الفرق بين آلة تورينج الكمومية ذات القياس الواحد وآلة تورينج الكمومية ذات القياسات المتعددة. تؤثر مسألة القياس هذه على طريقة تعريف عمليات الكتابة إلى شريط الإخراج.

في عامي 1980 و1982، نشر الفيزيائي بول بينيوف مقالتين ^{[ 5 ] [ 6 ]} وصفتا لأول مرة نموذجًا ميكانيكيًا كميًا لآلات تورينج . وفي عام 1985، طوّر الفيزيائي ديفيد دويتش من جامعة أكسفورد فكرة الحواسيب الكمومية، مقترحًا أن البوابات الكمومية يمكن أن تعمل بطريقة مشابهة لبوابات المنطق الثنائي في الحوسبة الرقمية التقليدية . ^{[ 4 ]}

قام كل من إيرياما وأوهيا وفولوفيتش بتطوير نموذج لآلة تورينغ الكمومية الخطية (LQTM). وهي تعميم لآلة تورينغ الكمومية الكلاسيكية، تتميز بحالات مختلطة وتسمح بوظائف انتقال غير قابلة للانعكاس. وهذا يتيح تمثيل القياسات الكمومية دون نتائج كلاسيكية. ^{[ 7 ]}

تم تعريف آلة تورينج الكمومية مع الاختيار اللاحق بواسطة سكوت آرونسون ، الذي أظهر أن فئة الوقت متعدد الحدود على مثل هذه الآلة ( PostBQP ) تساوي فئة التعقيد الكلاسيكية PP . ^{[ 8 ]}

• محاكي الكم § حل مسائل الفيزياء

• مولينا، أبيل؛ واتروس، جون (2018). "إعادة النظر في محاكاة آلات تورينج الكمومية بواسطة الدوائر الكمومية" . وقائع الجمعية الملكية أ: العلوم الرياضية والفيزيائية والهندسية . 475 (2226). arXiv : 1808.01701 . doi : 10.1098/rspa.2018.0767 . PMC 6598068. PMID 31293355 .  
• إيرياما، ساتوشي؛ أوهيا، ماسانوري؛ فولوفيتش، إيغور (2004). "آلة تورينغ الكمومية المعممة وتطبيقها على خوارزمية الفوضى SAT". arXiv : quant-ph/0405191 .
• دويتش، د. (1985). "نظرية الكم، ومبدأ تشرش-تورينغ، والحاسوب الكمي الشامل". وقائع الجمعية الملكية في لندن. السلسلة أ، العلوم الرياضية والفيزيائية . 400 (1818): 97-117 . Bibcode : 1985RSPSA.400...97D . CiteSeerX 10.1.1.41.2382 . doi : 10.1098 / rspa.1985.0070 . JSTOR 2397601. S2CID 1438116 .   

• الحاسوب الكمومي – التاريخ