Πειραματική επίδειξη κβαντικού πεπερασμένου αυτοματισμού

Φιγούρα 1 Μέσος διαγράμματα των οριστικών τελειωμένων αυτομάτων (DFAs) και της κβαντικής πεπερασμένα αυτόματα (QFAs). α Η διαγράμμιση της κατάστασης ενός τυπικού DFA. S 0 και S 1 είναι οι δύο δυνατές καταστάσεις του DFA, όπου S το 0 είναι τόσο το κράτος έναρξης και την αποδεκτή κατάσταση . Για κάθε κράτος, υπάρχει ένα μεταβατικό βέλος που οδηγεί σε μια επόμενη κατάσταση τόσο για 0 ​​και 1. Κατά την ανάγνωση ενός συμβόλου (0 ή 1), το DFA θα πηδήσει νομοτελείας από το ένα κράτος στο άλλο μετά το μεταβατικό βέλος. Η τρέχουσα DFA δέχεται μόνο δυαδικούς αριθμούς που είναι πολλαπλάσια του 2. β Το διάγραμμα κατάστασης ενός γενικού QFA.Μέσα στο QFA είναι ένα m- dimensionτο κβαντική κατάσταση, με | ψ 0 > Ως το κράτος έναρξης και | 0>, | 1>, ..., | m -2>, | m -1> Της ΕΙΝΑΙ μ καταστάσεις ορθοκανονική Βάση, όπου μερικά από αυτά τα κράτη βάση χαρακτηρίζονται ως αποδεκτές καταστάσεις . Η συμβολοσειρά εισόδου σ 1 σ 2 ⋯ σ n -1 σ N καθορίζει πώς η κβαντική κατάσταση θα εξελιχθεί. ΦΟΡΑ που ΚΑΘΕ ΕΝΑ Σύμβολο σ ι διαβάζεται σε, ένα αντίστοιχο ενιαίο φορέα𝑈σ𝑖εφαρμόζεται στην κβαντική κατάσταση. Μετά την ανάγνωση της τελευταίας σύμβολο της σειράς, η τελική κβαντική κατάσταση θα πρέπει να μετρηθεί και ως εκ τούτου αναμένεται να ένα από τα m κράτη βάση. Η συμβολολογία εισόδου θα γίνει δεκτή ή θα απορριφθεί από την QFA ανάλογα με το αν η κατάσταση ή η μηδενική κατάσταση προβλέπεται σε μία από τις αποδεκτές καταστάσεις. γ Ένα DFA για την επίλυση ενός προβλήματος υποσχέσεως. Αυτό το DFA μπορεί να χρησιμοποιηθεί για να καθοριστεί εάν το μήκος μιας εισόδου συμβόλων είναι ένα ακέραιο πολλαπλάσιο ενός πρώτου αριθμού Ρ ή όχι. δ Ένα QFA για την επίλυση του προβλήματος ίδια υποσχέση.Μέσα στο DFA είναι μια τρισδιάστατη κβαντική κατάσταση, με | 0>, | 1> και | 2> είναι κράτη βάσης 3 ορθοκανονική, όπου | 0> είναι τόσο η κρατική αρχή και η μόνη αποδεκτή κατάσταση. Η κβαντική κατάσταση θα περάσει από n αντίγραφα του ενιαίου φορέα U , όπου η είναι το μήκος της εισόδου συμβολοσειράς