אוטומט סופי קוונטי

במחשוב קוונטי, אוטומט סופי קוונטי (Quantum finite automata - QFA) או מכונת מצבים קוונטית הם המקבילים הקוונטים לאוטומט הסתברותי או לתהליך החלטה מרקובי. הם מאפשרים הפשטה מתמטית של מחשבים קוונטים. ניתן להגדיר סוגים שונים של אוטומטים, כגון אוטומט חד-מדידה ואוטומט רב-מדידה.

האוטומט פועל על ידי קבלה של מחרוזת באורך סופי $\sigma =(\sigma _{1},\sigma _{2},\cdots ,\sigma _{k})$ של אותיות $\sigma _{i}$ מעל אלפבית סופי $\Sigma$, אשר מקצה לכל מחרוזת $\sigma$ הסתברות $Pr(\sigma )$ המציינת את ההסתברות של האוטומט להיות במצב של קבלה. כלומר, ההסתברות האם האוטומט קיבל או דחה את המחרוזת.

השפות אשר מתקבלות על ידי אוטומטים סופיים קוונטים אינם שפות רגולריות של אוטומט סופי דטרמיניסטי, ואינן השפות הסטוכסטיות המתקבלות על ידי אוטומטים סופיים הסתברותיים. המחקר של שפות קוונטיות נותר תחום פעיל במחקר.

הגדרה לא פורמלית

ישנה דרך פשוטה ואינטואיטיבית להבין מהו אוטומט סופי קוונטי. ראשית, מתחלים בייצוג גרפי של אוטומט סופי דטרמיניסטי (DFA). אוטומט כזה ניתן לייצוג באמצעות גרף מכוון, כאשר המצבים הם הצמתים בגרף, והקשתות (או חיצים) מייצגות מעברים בין מצבים. כל חץ מסומן בסמל קלט אפשרי, כך שבהינתן מצב מסוים וקלט אפשרי, החץ מצביע על המצב הבא. דרך אחת לייצג את הגרף היא באמצעות סט של מטריצות שכנות, כאשר כך מטריצה משויכת לתו אפשרי. במקרה זה, רשימת המצבים של האוטומט הדטרמיניססי כתובה על ידי וקטור עמודה. עבור כל תו מהקלט, מטריצת השכנות תקבע מציינת כיצד כל מצב נתון (שורה בווקטור המצב) יתקדן למצב הבא כאשר מעבר בין מצבים ניתן בכפל מטריצות.

יש צורך במטריצת שכנות נפרדת לכל תו קלט אפשרי, מכיוון שכל סמל קלט יכול לגרום למעבר אחר. הערכים במטריצת הסמיכות חייבים להיות אפסים ואחדים. לכל עמודה במטריצה, רק רשומה אחת בלבד יכולה להיות ללא אפס: זהו הערך המציין את המעבר למצב הבא (הייחודי). באופן דומה, מצב המערכת הוא וקטור עמודות, שבו רק ערך אחד אינו אפס: ערך זה תואם את המצב הנוכחי של המערכת. אנו מציינים את סט האותיות של הקלט כ-$\Sigma$. עבור כל תו קלט $\alpha \in \Sigma$, אנו מציינים את $U_{\alpha }$ כמטריצת השכנויות המתארת את ההתקדמות של ה-DFA למצבו הבא. הסט $\{U_{\alpha }|\alpha \in \Sigma \}$ מציין באופן מלא את טבלת המעברים של האוטומט. בנוסף נציין את $Q$ כסט כל המצבים האפשריים של ה-DFA. אם ישנם $n$ מצבים ב-$Q$, אז המטריצה $U_{\alpha }$ היא בגודל של $n\times n$. המצב ההתחלתי $q_{0}\in Q$ תואם לוקטור עמודה עם הערך אחד בשורה המתאימה ל-$q_{0}$. יהי מצב $q$ כללי, אז עבורו יהיה הערך אחד בשורה התואמת ל-$q$. לכן, ובאופן א-פורמלי, יהיו $q_{0}$ ו-$q$ הווקטורים אשר מייצגים את אותם מצבים בהתאמה. לכן, לאחר קריאת התווים $\alpha \beta \gamma \cdots$ מסרט הקלט, המצב אשר מתאר את ה-DFA יינתן על ידי $q=\cdots U_{\gamma }U_{\beta }U_{\alpha }q_{0}$. מעברי המצב ניתנים על ידי כפל מטריצות רגיל (כלומר הכפל את $q_{0}$ ב-$U_{\alpha }$ וכו'); סדר ההכפלה "הפוך" רק מכיוון שאנו עוקבים אחר ההגדרות של אלגברה ליניארית.

התיאור לעיל של ה-DFA, במונחים של אופרטורים ליניאריים ווקטורים, ניתן להכללה על ידי החלפה של וקטור המצבים $q$ בווקטור כללי, ואת המטריצות $\{U_{\alpha }|\alpha \in \Sigma \}$ באופרטורים ליניאריים כלליים. זה למעשה מה שאוטומט סופי קוונטי עושה: הוא מחליף את $q$ באמפליטודה הסתברותית, ואת $\{U_{\alpha }|\alpha \in \Sigma \}$ במטריצות אוניטריות. ישנן הכללות נוספות, הווקטור $q$ יכול להיות הסברות כלשהי על יריעה, סט המטריצות יכול להיות איזומורפיזם מעל היריעה. באופן המתואר ניתן להגדיר אוטומט סופי טופולוגי. אילו נעשה שימוש באיזומורפיזם מעל מרחב הומוגני נוכל להגדיר אוטומט סופי גאומטרי.

לפני המעבר להגדרה הפורמלית של אוטומט סופי קוונטי (QFA), ישנן שתי הכללות נוספות: ההכללה הראשונה היא אוטומט סופי לא דטרמיניסטי (NFA). במקרה זה, הווקטור $q$ מוחלף בוקטור אשר יכול לכלול יותר מרשומה אחת שהיא לא אפס. לכן, הווקטור מתאר את איבר יחיד מקבוצת החזקה של $Q$, למעשה זוהי פונקציה מציינת על $Q$. באופן דומה, אוסף מטריצות המעבר $\{U_{\alpha }|\alpha \in \Sigma \}$ מוגדר כך שעבור כל עמודה עשויות להיות מספר רשומות שאינן אפסים. באופן דומה, יש להחליף את פעולות הכפל והחיבור אשר נעשות במהלך הכפלת המטריצות בפעולות בוליאניות של או ו-וגם כך שלמעשה אנו נעבוד עם חוג עם מאפיין של 2.

לפי משפט ידוע עבור כל אוטומט סופי דטרמיניסטי יש אוטומט סופי לא דטרמיניסטי תואם ולהפך. כתוצאה מכך, סט השפות אשר יכולות להתקבל על ידי אוטומטים סופיים דטרמיניסטים וא-דטרמיניסטים הוא זהה - אלו השפות הרגולריות. עם זאת, בהכללה עבור אוטומטים סופיים קוונטים סט השפות אשר יכולות להתקבל על ידי מודלים שונים עשוי להיות שונה. תיאור סט השפות הוא אחת מבעיות המחקר הבולטות בתורת האוטומטיים הקוונטים.

ההכללה השנייה היא אוטומט סופי הסתברותי. הכללה ניתנת על ידי החלפת אוסף מטריצות המעבר במטריצות סטוכסטיות ואת וקטור המצב בוקטור הסתברותי. הערכים בווקטור המצב חייבים להיות מספרים ממשיים, חיוביים ולסכם לאחד, על מנת שווקטור המצב יתפרש כהסתברות. על מטריצות המעבר לשמר תכונה זו: זו הסיבה שהן חייבות להיות סטוכסטיות. ניתן לדמיין כל וקטור מצב כמציין נקודה בסימפלקס; לפיכך, זהו אוטומט סופי טופולוגי, כאשר הסימפלקס הוא יריעה, והמטריצות הסטוכסטיות הן אוטומורפיזמים ליניאריים של הסימפלקס על עצמו. מכיוון שכל מעבר הוא למעשה בלתי תלוי בקודם (אם אנו מתעלמים מההבחנה בין שפות מקובלות לדחויות), האוטומט הסופי ההסתברותי בעצם הופך למעין שרשרת מרקוב.

לעומת זאת, ב- QFA, היריעה היא מרחב פרויקטיבי מעל המרוכבים $\mathbb {C} P^{N}$, ומטריצות המעבר הן מטריצות אוניטריות. כל נקודה ב-$\mathbb {C} P^{N}$ תואמת לאמפליטודה הסתברותית קוונטית או למצב טהור; ניתן לחשוב על המטריצות האוניטריות כמנהלות את התפתחות הזמן של המערכת (כלומר בתמונת שרדינגר). ההכללה ממצבים טהורים למצבים מעורבים צריכה להיות פשוטה: מצב מעורב הוא בפשטות התפלגות הסתברותית למדידה מעל $\mathbb {C} P^{N}$.