موضوع مقاله: اتوماتای متناهی کوانتومی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # اتوماتای متناهی کوانتومی | مقدمه: در واقع اتوماتای متناهی کوانتومی نمونه خاصی از اتوماتای متناهی هندسی و اتوماتای متناهی توپولوژیکی می‌باشد. | ## بخش 1: اتوماتای متناهی کوانتومی | اتوماتا با پذیرش یک رشته به طول متناهی از ها از یک الفبای ورودی و اختصاص احتمال به هر رشته کار خواهد کرد. این احتمال بیانگر قرارگیری احتمال اتوماتون در حالت پذیرش می‌باشد، اینکه رشته پذیرفته می‌شود یا خیر. زبان‌های پذیرفته شده QFA نه زبان‌های معمول اتوماتای متناهی قطعی هست و نه زبان تصادفی اتوماتای متناهی احتمالاتی. توضیحات اصلی راهی ساده و شهودی برای دریافت درکی صحیح از اتوماتای متناهی کوانتومی وجود دارد که شروع آن از طریق تفسیر اتوماتای متناهی قطعی (DFA) به کمک نظریه گراف امکان‌پذیر می‌شود. یک DFA را می‌توان یک گراف جهت دار، حالات را راس گراف و یال‌های جهت دار را انتقال دهنده‌های حالت در نظر گرفت. هر یال جهت دار با نماد ورودی ممکن برچسب‌گذاری می‌شود؛ بنابراین دادن یک نماد مشخص و حالت مشخص به یال‌های جهت دار قدم بعدی می‌باشد. یکی از راه‌های معرفی همچین گرافی به کمک ماتریس‌های مجاورت امکان‌پذیر است به این صورت که برای هر نماد ورودی یک ماتریس در نظر گرفته شود. با دادن یک نماد ورودی ماتریس مجاورت نشان خواهد داد که چگونه دادن هر (سطر در بردار حالت) به حالت بعدی انتقال خواهد یافت. هر عنصر ورودی، عامل انتقال متفاوتی می‌باشد بنابراین نیاز به یک ماتریس مجاورت متمایز برای هر نماد ورودی ممکن است. برای هر ستون ماتریس فقط یک درایه ناصفر وجود دارد که این درایه نشان دهنده انتقال حالت منحصر به فرد بعدی می‌باشد. به‌طور مشابه، حالت سیستم، یک بردار ستونی است که فقط دارای یک درایه ناصفر می‌باشد که این درایه مطابق حالت فعلی سیستم است. برای هر ، را به عنوان ماتریس مجاورت داریم که نشان دهنده سیر تکامل DFA به حالت بعدی خودش هست؛ بنابراین مجموعه به‌طور کامل انتقال حالت عملگر DFA را شرح می‌دهد. توضیحات بالا در مورد یک DFA، بر حسب بردارها و نگاشت‌های خطی، به طرز تقریباً بدیهی نیاز به عمومی‌سازی دارد که از طریق جایگزین کردن q با یک بردار عمومی و ماتریس‌های با عملگرهای عمومی انجام می‌پذیرد. | ## بخش 2: اتوماتای متناهی کوانتومی | دانستن اینکه یک QFA چه می‌کند ضروریست: q را با یک دامنه احتمال و را با ماتریس‌های واحد جایگزین می‌کند. به همین ترتیب عمومی‌سازی دیگری آشکار می‌گردد آنکه: بردار q در یک منیفلد قابل توزیع می‌شود؛ مجموعه ماتریس‌های انتقال در منیفلد اتومورفیزم می‌شود؛ در واقع یک اتوماتون متناهی توپولوژیکی تعریف می‌کند. در این مورد بردار q توسط برداری که بیشتر از یک درایه آن ناصفر باشد جایگزین می‌شود. چنین برداری سپس عنصری از مجموعه توانی Q را معرفی می‌کند که در واقع تنها تابع مشخصه‌ای بر روی Q می‌باشد. همچنین ماتریس‌های انتقال حالت به این صورت تعریف می‌شوند که هر ستون می‌تواند چندین عامل غیر صفر داشته باشد. بعد از هر کاربرد ، گرچه، هر بردار ستونی q می‌بایست دوباره نرمال شود آنگونه که تمامی درایه‌هایش صفر یا یک باشد. به‌طور مشابه، ماتریس‌ها می‌توانند به عنوان اتومورفیسم‌هایی از یک فضای همگن در نظر گرفته شوند که در واقع این یک اتوماتون متناهی هندسی را تعریف می‌کند. عمومی‌سازی بعدی بلافاصله این‌گونه آشکار می‌شود که از ماتریس Stochastic برا ماتریس‌های انتقال حالت و بردارهای احتمالی برای حالت استفاده شود که اتوماتون متناهی احتمالاتی را می‌دهد. بدیهی است که به عنوان احتمال، درایه‌های این بردار می‌بایست اعداد طبیعی و مثبت، با مجموع ۱ باشد. هر بردار حالت باید به عنوان یک سنقطه مشخص در سیملکس در نظر گرفته شود؛ بنابراین، این یک اتوماتون توپولوژیکی با سیمپلکس منیفلد و ماتریس‌های stochastic اتومورفیسم خطی از سیمپلکس بر روی خودش. چون هر انتقال الزاماً مستقل از قبلی است (با نادیده گرفتن فرق بین زبان‌های پذیرفته شده با نشده)،PFA الزاماً تبدیل به یک نوعی از زنجیره مارکوف می‌شود. نکته قابل اندیشه در واقع توزیع‌های است که باعث تأثیر در منیقلد طی ورود یک زبان می‌شود. برای یک اتوماتون بهینه بودن برای شناخت یک زبان آن است که توزیع می‌بایست تا جایی که امکان دارد یکسان باشد. | ## بخش 3: اتوماتای متناهی کوانتومی | همانند یک اتوماتون متناهی معمولی، اتوماتون کوانتومی دارای حالت درونی امکان‌پذیر می‌باشد، که در این جا به صورت یک -حالت qubit معرفی می‌شود. به همین صورت با دادن ماتریس واحد ذکر شده انتقال حالت اتوماتون را از حالت فعلی اش به حالت بعدی : سپس، سه تایی بر گرفته از نیم اتوماتون را توصیف می‌کند. همچنین برای رشته متناهی داریم: که در اینجا بردار نمایانگر حالت شروع اتوماتون، حالت قبل از پذیرش رشته می‌باشد. رشته تهی نیز به عنوان یک ماتریس واحد تلقی می‌گردد؛ بنابراین احتمال حالت شروع در یک حالت پذیرش شده‌است. واضح است اگر حالت شروع حالت خالص یا باشد، نتیجه به راه‌اندازی یا اجرای ماشین دقیقاً با ماشین حالت قطعی متناهی کلاسیک برابر خواهد شد. به خصوص، زبان پذیرش شده‌ای برای این اتوماتون با احتمال یک در حالت شروع وجود دارد که آن نیز دقیقاً مانند زبان معمول برای DFA کلاسیک که با عبارت با قاعده مفروض است: حالت غیر کلاسیک زمانی رخ می‌دهد که جفت و غیر صفر باشند. این اتوماتا شبیه چارچوب کلی Measure-once می‌باشد با این تفاوت که که به جای وجود یک پروجکشن در انتها وجود دارد یک پروجکشن یا اندازه‌گیری کوانتومی که بعد از خواندن هر حرف اعمال می‌شود. فضای هیلبرت به سه زیرفضای متعامد تجزیه می‌شود در واقع این زیر فضاهای متعامد معمولاً به عنوان مجموعه از بردارهای پایه‌ای متعامد برای فضای هیلبرت فرموله می‌شوند. سه ماتریس تصویر ، و را داریم که هر یک تصویر مربوط به زیر فضایش است: تجزیه یک رشته ورودی به شکل زیر امکان‌پذیر است. در این زمان، سنجشی بر روی حالت از طریق عملگرهای پروجکشن P در زمانی که تابع موجی اش به یکی از سه زیر فضای یا یا فرو بریزد اعمال می‌شود. احتمال فرو ریزش به وسیله برای زیر فضای پذیرش و به‌طور مشابه دو فضای دیگر تعیین می‌شود. | ## جمع‌بندی | اغلب نماد و $ به عنوان نشان دهنده ابتدا و انتهای یک رشته به الفبا اضافه می‌شوند.