ماشین تورینگ کوانتومی

یک ماشین تورینگ کوانتومی (به انگلیسی: quantum Turing machine) (مخفف انگلیسی: QTM) که به آن ماشین تورینگ جهانی نیز می‌گویند یک ماشین انتزاعی است که برای مدل کردن تأثیرات یک کامپیوتر کوانتومی استفاده می‌شود. این ماشین یک مدل بسیار ساده را ارائه می‌کند که قدرت محاسبات کوانتومی را نشان می‌دهد. هر الگوریتم کوانتومی می‌تواند به صورت رسمی توسط یک ماشین تورینگ کوانتومی بیان شود. این نوع ماشین تورینگ نخستین بار توسط دانشمند فیزیکدان دانشگاه اکسفورد David Deutsch در سال ۱۹۸۵ ارائه شد. وی پیشنهاد کرد که گیت‌های کوانتومی می‌توانند همانند گیت‌های منطقی دودویی کلاسیک عمل کنند. معمولاً ماشین‌های تورینگ کوانتومی برای آنالیز کردن محاسبات کوانتومی مورد استفاده قرار نمی‌گیرند و معمولاً از مدل مدارات کوانتومی که مدل‌های رایج تری هستند استفاده می‌شود و این مدل‌ها با یکدیگر معادل هستند. ماشین‌های تورینگ کوانتومی می‌توانند توسط ماتریس‌های انتقال با ماشین تورینگ‌های احتمالی کلاسیک معادل شوند.

Iriyama، Ohya و Volovich مدل دیگری از ماشین تورینگ کوانتومی را تحت عنوان ماشین تورینگ کوانتومی خطی (LQTM) ارائه دادند. این نوع ماشین تورینگ حالتی کلی از ماشین‌های تورینگ کوانتومی کلاسیک هستند که توابع انتقال غیرقابل برگشت را مدل می‌کنند. این مسئله باعث می‌شود که بتوان اندازه‌گیری‌های کوانتومی را بدون نتیجه خروجی کلاسیک بیان کرد.

منابع

↑ Deutsch, David (July 1985). "Quantum theory, the Church-Turing principle and the universal quantum computer" (PDF). Proceedings of the Royal Society of London; Series A, Mathematical and Physical Sciences. 400 (1818): pp. 97–117. Bibcode:1985RSPSA.400...97D. doi:10.1098/rspa.1985.0070. Archived from the original (PDF) on 23 November 2008. Retrieved 27 June 2012.
↑ اندرو یائو (1993). "Quantum circuit complexity". Proceedings of the 34th Annual Symposium on Foundations of Computer Science. pp. 352–361.
↑ Lance Fortnow (2003). "One Complexity Theorist's View of Quantum Computing". Theoretical Computer Science. 292 (3): 597–610. doi:10.1016/S0304-3975(01)00377-2.
↑ Simon Perdrix; Philippe Jorrand (2007-04-04). "Classically-Controlled Quantum Computation". Math. Struct. In Comp. Science. 16 (4): 601–620. arXiv:quant-ph/0407008. doi:10.1017/S096012950600538X. also Simon Perdrix and Philippe Jorrand (2006). "Classically-Controlled Quantum Computation" (PDF). Math. Struct. In Comp. Science. 16 (4): 601–620. doi:10.1017/S096012950600538X.

[Deutsch1985-1] Deutsch, David (July 1985). "Quantum theory, the Church-Turing principle and the universal quantum computer" (PDF). Proceedings of the Royal Society of London; Series A, Mathematical and Physical Sciences. 400 (1818): pp. 97–117. Bibcode:1985RSPSA.400...97D. doi:10.1098/rspa.1985.0070. Archived from the original (PDF) on 23 November 2008. Retrieved 27 June 2012.

[equivalence-2] اندرو یائو (1993). "Quantum circuit complexity". Proceedings of the 34th Annual Symposium on Foundations of Computer Science. pp. 352–361.

[transition-3] Lance Fortnow (2003). "One Complexity Theorist's View of Quantum Computing". Theoretical Computer Science. 292 (3): 597–610. doi:10.1016/S0304-3975(01)00377-2.

[4] Simon Perdrix; Philippe Jorrand (2007-04-04). "Classically-Controlled Quantum Computation". Math. Struct. In Comp. Science. 16 (4): 601–620. arXiv:quant-ph/0407008. doi:10.1017/S096012950600538X. also Simon Perdrix and Philippe Jorrand (2006). "Classically-Controlled Quantum Computation" (PDF). Math. Struct. In Comp. Science. 16 (4): 601–620. doi:10.1017/S096012950600538X.