اتوماتای محدود کوانتومی

در محاسبات کوانتومی، اتوماتای محدود کوانتومی (quantum finite automata) یا (QFA) یا ماشین‌های حالت کوانتومی (quantum state machines)، حالتی کوانتومی از اتوماتای احتمالاتی یا یک فرایند تصمیم مارکوف می‌باشد.
انواع مختلفی از اتومات‌ها همانند measure-once و measure-many تعریف شده‌اند. در واقع اتوماتای محدود کوانتومی نمونه خاصی از اتوماتای محدود هندسی و اتوماتای محدود توپولوژیکی می‌باشد.
اتوماتا با پذیرش یک رشته به طول متناهی  از ها از یک الفبای ورودی  و اختصاص احتمال  به هر رشته کار خواهد کرد. این احتمال بیانگر قرارگیری احتمال اتوماتون در حالت پذیرش می‌باشد، اینکه رشته پذیرفته می‌شود یا خیر.
زبان‌های پذیرفته شده QFA نه زبان‌های معمول اتوماتای محدود تعیین پذیر هست و نه زبان تصادفی اتوماتای محدود احتمالاتی. در واقع مطالعه زبان‌های کوانتوم همواره بخش مناسبی برای تحقیقات علمی بوده‌است.

توضیحات اصلی

راهی ساده و شهودی برای دریافت درکی صحیح از اتوماتای محدود کوانتومی وجود دارد که شروع آن از طریق تفسیر اتوماتای محدود تعیین پذیر (DFA) به کمک نظریه گراف امکان‌پذیر می‌شود. یک DFA را می‌توان یک گراف جهت دار، حالات را راس گراف و یال‌های جهت دار را انتقال دهنده‌های حالت در نظر گرفت. هر یال جهت دار با نماد ورودی ممکن برچسب‌گذاری می‌شود؛ بنابراین دادن یک نماد مشخص و حالت مشخص به یال‌های جهت دار قدم بعدی می‌باشد. یکی از راه‌های معرفی همچین گرافی به کمک ماتریس‌های مجاورت امکان‌پذیر است به این صورت که برای هر نماد ورودی یک ماتریس در نظر گرفته شود. در این مورد، لیست حالت‌های ممکن DFA به صورت یک بردار ستونی نوشته می‌شود. با دادن یک نماد ورودی ماتریس مجاورت نشان خواهد داد که چگونه دادن هر (سطر در بردار حالت) به حالت بعدی انتقال خواهد یافت. یک انتقال حالت با ضرب ماتریس‌ها صورت می‌گیرد.
هر عنصر ورودی، عامل انتقال متفاوتی می‌باشد بنابراین نیاز به یک ماتریس مجاورت متمایز برای هر نماد ورودی ممکن است. درایه‌های این ماتریس می‌بایست همگی صفر و یک باشند. برای هر ستون ماتریس فقط یک درایه ناصفر وجود دارد که این درایه نشان دهنده انتقال حالت منحصر به فرد بعدی می‌باشد. به‌طور مشابه، حالت سیستم، یک بردار ستونی است که فقط دارای یک درایه ناصفر می‌باشد که این درایه مطابق حالت فعلی سیستم است. فرض کنید  به عنوان مجموعه‌ای از نمادهای ورودی باشد. برای هر ،  را به عنوان ماتریس مجاورت داریم که نشان دهنده سیر تکامل DFA به حالت بعدی خودش هست؛ بنابراین مجموعه  به‌طور کامل انتقال حالت عملگر DFA را شرح می‌دهد. فرض کنید Q مجموعه حالت‌های ممکن از DFA باشد. اگر N حالت در Q وجود داشته باشد آنگاه هر ماتریس ،N با N-بعد خواهد بود. حالت شروع  مطابق یک بردار ستونی با یک ۱ در سطر q₀ام می‌باشد. حالت عمومیq وقتی است که یک بردار ستونی با یک ۱ در سطر qام باشد. با تخطی از نشانه‌گذاری معمول، فرض کنید q₀ و q دوبردار باشند. سپس، بعد از خواندن نمادهای ورودی  از نوار ورودی حالت DFA طبق  مشخص خواهد شد. انتقال حالت توسط ضرب ماتریس‌ها صورت می‌گیرد (مثلاً ضرب q₀ با ، یا غیره).
توضیحات بالا در مورد یک DFA، بر حسب بردارها و نگاشت‌های خطی، به طرز تقریباً بدیهی نیاز به عمومی‌سازی دارد که از طریق جایگزین کردن q با یک بردار عمومی و ماتریس‌های  با عملگرهای عمومی انجام می‌پذیرد. دانستن اینکه یک QFA چه می‌کند ضروریست: q را با یک دامنه احتمال و  را با ماتریس‌های واحد جایگزین می‌کند. به همین ترتیب عمومی‌سازی دیگری آشکار می‌گردد آنکه: بردار q در یک منیفلد قابل توزیع می‌شود؛ مجموعه ماتریس‌های انتقال در منیفلد اتومورفیزم می‌شود؛ در واقع یک اتوماتون محدود توپولوژیکی تعریف می‌کند.
قبل از رفتن به سراغ تعریف رسمی یک QFA لازم است به دو عمومی‌سازی مهم اشاره کرد. اولی اتوماتون محدود تعیین پذیر است. در این مورد بردار q توسط برداری که بیشتر از یک درایه آن ناصفر باشد جایگزین می‌شود. چنین برداری سپس عنصری از مجموعه توانی Q را معرفی می‌کند که در واقع تنها تابع مشخصه‌ای بر روی Q می‌باشد. همچنین ماتریس‌های انتقال حالت  به این صورت تعریف می‌شوند که هر ستون می‌تواند چندین عامل غیر صفر داشته باشد. بعد از هر کاربرد ، گرچه، هر بردار ستونی q می‌بایست دوباره نرمال شود آنگونه که تمامی درایه‌هایش صفر یا یک باشد. به‌طور مشابه، ماتریس‌ها می‌توانند به عنوان اتومورفیسم‌هایی از یک فضای همگن در نظر گرفته شوند که در واقع این یک اتوماتون محدود هندسی را تعریف می‌کند.
یک تئوری شناخته شده نشان می‌دهد که برای هر DFA، یک NFA مشابه وجود دارد و برعکس که دلالت دارد بر اینکه مجموعه زبان‌های DFA و NFA یکی هستند. این‌ها همان زبان‌های معمول هستند. در عمومی‌سازی QFA، مجموعه زبان‌ها متفاوت خواهد بود. توصیف این مجموعه یکی از قابل توجه‌ترین مشکلات تحیق دربارهٔ نظریه QFA است.
عمومی‌سازی بعدی بلافاصله این‌گونه آشکار می‌شود که از ماتریس Stochastic برا ماتریس‌های انتقال حالت و بردارهای احتمالی برای حالت استفاده شود که اتوماتون محدود احتمالاتی را می‌دهد. بدیهی است که به عنوان احتمال، درایه‌های این بردار می‌بایست اعداد طبیعی و مثبت، با مجموع ۱ باشد. ماتریس‌های احتمال باید داری این خصوصیت باشد برای همین نیز آن‌ها stochastic هستند. هر بردار حالت باید به عنوان یک سنقطه مشخص در سیملکس در نظر گرفته شود؛ بنابراین، این یک اتوماتون توپولوژیکی با سیمپلکس منیفلد و ماتریس‌های stochastic اتومورفیسم خطی از سیمپلکس بر روی خودش. چون هر انتقال الزاماً مستقل از قبلی است (با نادیده گرفتن فرق بین زبان‌های پذیرفته شده با نشده)،PFA الزاماً تبدیل به یک نوعی از زنجیره مارکوف می‌شود.
در مقابل، در یک QFA، منیفلد فضای تصویری مختلط (Complex projective space)  و ماتریس‌های انتقال ماتریس‌های واحد هستند. هر نقطه در  مربوط به یک کوانتوم-مکانیک احتمال amplitude یا حالت خاص می‌باشد. ماتریس‌های واحد را می‌توان به عنوان یک حاکم بر روند گذر زمان سیستم در نظر گرفت (یعنی در تصویر Schrödinger) از حالت خالص به حالت‌های تلفیقی مستقیماً این گونه بدست می‌آید که یک حالت تلفیقی توزیع احتمال measure-theoretic بر روی .
نکته قابل اندیشه در واقع توزیع‌های است که باعث تأثیر در منیقلد طی ورود یک زبان می‌شود. برای یک اتوماتون بهینه بودن برای شناخت یک زبان آن است که توزیع می‌بایست تا جایی که امکان دارد یکسان باشد.