اتوماتای متناهی کوانتومی
در محاسبات کوانتومی، اتوماتای متناهی کوانتومی (quantum finite automata) یا (QFA) یا ماشین‌های حالت کوانتومی (quantum state machines)، حالتی کوانتومی از اتوماتای احتمالاتی یا یک فرایند تصمیم مارکوف می‌باشد. انواع مختلفی از اتومات‌ها همانند measure-once و measure-many تعریف شده‌اند. در واقع اتوماتای متناهی کوانتومی نمونه خاصی از اتوماتای متناهی هندسی و اتوماتای متناهی توپولوژیکی می‌باشد.
اتوماتا با پذیرش یک رشته به طول متناهی formula_1 از formula_2ها از یک الفبای ورودی formula_3 و اختصاص احتمال formula_4 به هر رشته کار خواهد کرد. این احتمال بیانگر قرارگیری احتمال اتوماتون در حالت پذیرش می‌باشد، اینکه رشته پذیرفته می‌شود یا خیر.
زبان‌های پذیرفته شده QFA نه زبان‌های معمول اتوماتای متناهی قطعی هست و نه زبان تصادفی اتوماتای متناهی احتمالاتی. در واقع مطالعه زبان‌های کوانتوم همواره بخش مناسبی برای تحقیقات علمی بوده‌است.
راهی ساده و شهودی برای دریافت درکی صحیح از اتوماتای متناهی کوانتومی وجود دارد که شروع آن از طریق تفسیر اتوماتای متناهی قطعی (DFA) به کمک نظریه گراف امکان‌پذیر می‌شود. یک DFA را می‌توان یک گراف جهت دار، حالات را راس گراف و یال‌های جهت دار را انتقال دهنده‌های حالت در نظر گرفت. هر یال جهت دار با نماد ورودی ممکن برچسب‌گذاری می‌شود؛ بنابراین دادن یک نماد مشخص و حالت مشخص به یال‌های جهت دار قدم بعدی می‌باشد. یکی از راه‌های معرفی همچین گرافی به کمک ماتریس‌های مجاورت امکان‌پذیر است به این صورت که برای هر نماد ورودی یک ماتریس در نظر گرفته شود. در این مورد، لیست حالت‌های ممکن DFA به صورت یک بردار ستونی نوشته می‌شود. با دادن یک نماد ورودی ماتریس مجاورت نشان خواهد داد که چگونه دادن هر (سطر در بردار حالت) به حالت بعدی انتقال خواهد یافت. یک انتقال حالت با ضرب ماتریس‌ها صورت می‌گیرد.
هر عنصر ورودی، عامل انتقال متفاوتی می‌باشد بنابراین نیاز به یک ماتریس مجاورت متمایز برای هر نماد ورودی ممکن است. درایه‌های این ماتریس می‌بایست همگی صفر و یک باشند. برای هر ستون ماتریس فقط یک درایه ناصفر وجود دارد که این درایه نشان دهنده انتقال حالت منحصر به فرد بعدی می‌باشد. به‌طور مشابه، حالت سیستم، یک بردار ستونی است که فقط دارای یک درایه ناصفر می‌باشد که این درایه مطابق حالت فعلی سیستم است. فرض کنید formula_5 به عنوان مجموعه‌ای از نمادهای ورودی باشد. برای هر formula_6، formula_7 را به عنوان ماتریس مجاورت داریم که نشان دهنده سیر تکامل DFA به حالت بعدی خودش هست؛ بنابراین مجموعه formula_8 به‌طور کامل انتقال حالت عملگر DFA را شرح می‌دهد. فرض کنید "Q" مجموعه حالت‌های ممکن از DFA باشد. اگر "N" حالت در "Q" وجود داشته باشد آنگاه هر ماتریس formula_7،"N" با "N"-بعد خواهد بود. حالت شروع formula_10 مطابق یک بردار ستونی با یک ۱ در سطر "q"ام می‌باشد. حالت عمومی"q" وقتی است که یک بردار ستونی با یک ۱ در سطر "q"ام باشد. با تخطی از نشانه‌گذاری معمول، فرض کنید "q" و "q" دوبردار باشند. سپس، بعد از خواندن نمادهای ورودی formula_11 از نوار ورودی حالت DFA طبق formula_12 مشخص خواهد شد. انتقال حالت توسط ضرب ماتریس‌ها صورت می‌گیرد (مثلاً ضرب "q" با formula_7، یا غیره).
توضیحات بالا در مورد یک DFA، بر حسب بردارها و نگاشت‌های خطی، به طرز تقریباً بدیهی نیاز به عمومی‌سازی دارد که از طریق جایگزین کردن "q" با یک بردار عمومی و ماتریس‌های formula_14 با عملگرهای عمومی انجام می‌پذیرد. دانستن اینکه یک QFA چه می‌کند ضروریست: "q" را با یک دامنه احتمال و formula_14 را با ماتریس‌های واحد جایگزین می‌کند. به همین ترتیب عمومی‌سازی دیگری آشکار می‌گردد آنکه: بردار "q" در یک منیفلد قابل توزیع می‌شود؛ مجموعه ماتریس‌های انتقال در منیفلد اتومورفیزم می‌شود؛ در واقع یک اتوماتون متناهی توپولوژیکی تعریف می‌کند.
قبل از رفتن به سراغ تعریف رسمی یک QFA لازم است به دو عمومی‌سازی مهم اشاره کرد. اولی اتوماتون متناهی قطعی است. در این مورد بردار "q" توسط برداری که بیشتر از یک درایه آن ناصفر باشد جایگزین می‌شود. چنین برداری سپس عنصری از مجموعه توانی "Q" را معرفی می‌کند که در واقع تنها تابع مشخصه‌ای بر روی Q می‌باشد. همچنین ماتریس‌های انتقال حالت formula_14 به این صورت تعریف می‌شوند که هر ستون می‌تواند چندین عامل غیر صفر داشته باشد. بعد از هر کاربرد formula_14، گرچه، هر بردار ستونی "q" می‌بایست دوباره نرمال شود آنگونه که تمامی درایه‌هایش صفر یا یک باشد. به‌طور مشابه، ماتریس‌ها می‌توانند به عنوان اتومورفیسم‌هایی از یک فضای همگن در نظر گرفته شوند که در واقع این یک اتوماتون متناهی هندسی را تعریف می‌کند.
یک تئوری شناخته شده نشان می‌دهد که برای هر DFA، یک NFA مشابه وجود دارد و برعکس که دلالت دارد بر اینکه مجموعه زبان‌های DFA و NFA یکی هستند. این‌ها همان زبان‌های معمول هستند. در عمومی‌سازی QFA، مجموعه زبان‌ها متفاوت خواهد بود. توصیف این مجموعه یکی از قابل توجه‌ترین مشکلات تحیق دربارهٔ نظریه QFA است.
عمومی‌سازی بعدی بلافاصله این‌گونه آشکار می‌شود که از ماتریس Stochastic برا ماتریس‌های انتقال حالت و بردارهای احتمالی برای حالت استفاده شود که اتوماتون متناهی احتمالاتی را می‌دهد. بدیهی است که به عنوان احتمال، درایه‌های این بردار می‌بایست اعداد طبیعی و مثبت، با مجموع ۱ باشد. ماتریس‌های احتمال باید داری این خصوصیت باشد برای همین نیز آن‌ها stochastic هستند. هر بردار حالت باید به عنوان یک سنقطه مشخص در سیملکس در نظر گرفته شود؛ بنابراین، این یک اتوماتون توپولوژیکی با سیمپلکس منیفلد و ماتریس‌های stochastic اتومورفیسم خطی از سیمپلکس بر روی خودش. چون هر انتقال الزاماً مستقل از قبلی است (با نادیده گرفتن فرق بین زبان‌های پذیرفته شده با نشده)،PFA الزاماً تبدیل به یک نوعی از زنجیره مارکوف می‌شود.
در مقابل، در یک QFA، منیفلد فضای تصویری مختلط (Complex projective space) formula_18 و ماتریس‌های انتقال ماتریس‌های واحد هستند. هر نقطه در formula_18 مربوط به یک کوانتوم-مکانیک احتمال amplitude یا حالت خاص می‌باشد. ماتریس‌های واحد را می‌توان به عنوان یک حاکم بر روند گذر زمان سیستم در نظر گرفت (یعنی در تصویر Schrödinger) از حالت خالص به حالت‌های تلفیقی مستقیماً این گونه بدست می‌آید که یک حالت تلفیقی توزیع احتمال measure-theoretic بر روی formula_18.
نکته قابل اندیشه در واقع توزیع‌های است که باعث تأثیر در منیقلد طی ورود یک زبان می‌شود. برای یک اتوماتون بهینه بودن برای شناخت یک زبان آن است که توزیع می‌بایست تا جایی که امکان دارد یکسان باشد.
اتوماتای Measure-once توسط Moore و James P. Crutchfield معرفی شد که تعریف آن به شرح زیر است.
همانند یک اتوماتون متناهی معمولی، اتوماتون کوانتومی دارای formula_21حالت درونی امکان‌پذیر می‌باشد، که در این جا به صورت یک formula_21-حالت qubit formula_23 معرفی می‌شود. در واقع formula_21-حالت qubit formula_25 عنصری است از Complex projective space formula_21 بعدی همراه ضرب داخلی formula_27 که Fubini–Study metric می‌باشد.
انتقال‌های حالت، یا ماتریس‌های انتقال یا de Bruijn graphs توسط مجموعه‌ای formula_28 از ماتریس‌های واحدformula_7 با یک ماتریس واحد برای هر formula_6 معرفی می‌شود. به همین صورت با دادن formula_31 ماتریس واحد ذکر شده انتقال حالت اتوماتون را از حالت فعلی اش formula_23 به حالت بعدی formula_33:
سپس، سه تایی formula_35 بر گرفته از نیم اتوماتون را توصیف می‌کند.
حالت پذیرش اتوماتون را با دادن ماتریس Projection formula_36 داریم، که با دادن حالت کوانتومی formula_21-بعدی formula_23 برای احتمال formula_23 حالت پذیرش خواهد بود.
همچنین برای رشته متناهی formula_1 داریم: که در اینجا بردار formula_23 نمایانگر حالت شروع اتوماتون، حالت قبل از پذیرش رشته می‌باشد. رشته تهی formula_44 نیز به عنوان یک ماتریس واحد تلقی می‌گردد؛ بنابراین احتمال حالت شروع در یک حالت پذیرش شده‌است.
اتوماتون متناهی قطعی کلاسیک را با دادن جدول انتقال حالت زیر در نظر بگیرید
حالت کوانتومی برداریست با نشانه‌گذاری برا-کت با اعداد مختلط formula_47 بنابراین ماتریس‌های انتقال واحد و خواهند بود. برای formula_51 در حالت پذیرش ماتریس projection را داریم.
واضح است اگر حالت شروع حالت خالص formula_53 یا formula_54 باشد، نتیجه به راه‌اندازی یا اجرای ماشین دقیقاً با ماشین حالت قطعی متناهی کلاسیک برابر خواهد شد. به خصوص، زبان پذیرش شده‌ای برای این اتوماتون با احتمال یک در حالت شروع وجود دارد که آن نیز دقیقاً مانند زبان معمول برای DFA کلاسیک که با عبارت با قاعده مفروض است: حالت غیر کلاسیک زمانی رخ می‌دهد که جفت formula_56 و formula_57 غیر صفر باشند. رفتارهای دیگر زمانی رخ می‌دهد که ماتریس‌های formula_58 و formula_59 به اندازه کافی ساده نباشند. برای مثال به de Rham curve رجوع کنید.
اتوماتای Measure-many اولین بار توسط Kondacs و Watrous در سال ۱۹۹۷ معرفی شد. این اتوماتا شبیه چارچوب کلی Measure-once می‌باشد با این تفاوت که که به جای وجود یک پروجکشن در انتها وجود دارد یک پروجکشن یا اندازه‌گیری کوانتومی که بعد از خواندن هر حرف اعمال می‌شود. تعریف رسمی آن به شکل زیر است.
فضای هیلبرت formula_60 به سه زیرفضای متعامد تجزیه می‌شود
در واقع این زیر فضاهای متعامد معمولاً به عنوان مجموعه formula_62 از بردارهای پایه‌ای متعامد برای فضای هیلبرت formula_60 فرموله می‌شوند. این مجموعه از بردارهای پایه به زیر مجموعه‌های formula_64 و formula_65 تقسیم می‌شود. به‌طوری که
یک طول خطی از بردارهای پایه در مجموعه پذیرش است. فضای رد به‌طور مشابه تعریف می‌شود و فضای باقی‌مانده زیر فضای non-halting در نظر گرفته می‌شود. سه ماتریس تصویر formula_67، formula_68 و formula_69 را داریم که هر یک تصویر مربوط به زیر فضایش است:
تجزیه یک رشته ورودی به شکل زیر امکان‌پذیر است. فرض کنید که اتوماتون در حالت formula_23 باشد. بعد از خواندن یک حرف ورودی formula_31 اتوماتون در حالت
قرار می‌گیرد. در این زمان، سنجشی بر روی حالت formula_33 از طریق عملگرهای پروجکشن "P" در زمانی که تابع موجی اش به یکی از سه زیر فضای formula_75 یا formula_76 یا formula_77 فرو بریزد اعمال می‌شود. احتمال فرو ریزش به وسیله
برای زیر فضای پذیرش و به‌طور مشابه دو فضای دیگر تعیین می‌شود.
اگر تابع موجی به دو فضای پذیرش یا رد ریزش کند آنگاه پردازش بیشتر متوقف می‌شود. در غیر این صورت پردازش با خواندن حرف بعدی از ورودی ادامه می‌یابد. در واقع پردازش تا زمانی که تمام رشته خوانده یا ماشین متوقف شود ادامه دارد. اغلب نماد formula_79 و $ به عنوان نشان دهنده ابتدا و انتهای یک رشته به الفبا اضافه می‌شوند.
اتوماتون meaure-many اغلب توسط شش تایی formula_80 تعیین می‌شود. حالت شروع نیز به وسیله formula_81 و تبدیلات واحد با
تعیین می‌شود، به‌طوری که