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

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

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