Automa a stati finiti quantistico

Un automa a stati finiti quantistico (QFA) è, in informatica quantistica e in informatica teorica, una generalizzazione degli automi a stati finiti che accettano una parola in base al risultato di una misura.

Gli automi a stati finiti quantistici sono simili agli automi probabilistici, ma la classe dei linguaggi riconosciuta dagli automi quantistici è strettamente contenuta nella classe dei linguaggi riconosciuti dagli automi probabilistici. Gli automi a stati finiti quantistici possono anche essere visti come una versione quantistica di subshift di tipo finito o come una variante quantistica delle catene di Markov. Gli automi quantistici finiti sono, a loro volta, dei casi particolari dei cosiddetti automi finiti geometrici o degli automi finiti topologici.

Un automa quantistico finito opera su parole finite ${\displaystyle w=a_{1}a_{2}\cdots a_{m}}$, le cui lettere ${\displaystyle a_{i}}$ appartengono a un dato alfabeto ${\displaystyle \Sigma }$. A ogni parola ${\displaystyle w}$ viene assegnata una probabilità; a seconda di questa probabilità, la parola viene accettata o rifiutata dall'automa. I linguaggi accettati dagli automi quantistici finiti non coincidono con i linguaggi regolari accettati dagli automi finiti, né con i linguaggi stocastici accettati dagli automi a stati finiti probabilistici.

Lo studio degli automi finiti quantistici si divide in due aree principali che dipendono dalle transizioni autorizzate alla macchina di Turing corrispondente: gli one-way quantum finite automata (1QFA)^[1] per i quali ad ogni passo la testina di lettura si muove di una casella a destra e i two-way quantum finite automata (2QFA)^[2], per i quale la testina si può muovere sia a destra che a sinistra o rimanere ferma.

Esistono diversi tipi di automi a stati finiti quantistici; il più restrittivo è quello detto measure-once e definito da Moore e Crutchfield nel 2000^[3]; un altro è quello degli automi measure-many, definiti da Kondacs e Watrous nel 1997^[2]. Nei measure-once, viene effettuata un'unica misura per ogni stringa d'ingresso dopo aver letto l'ultimo simbolo della parola, mentre per il measure-many, la misura viene effettuata dopo la lettura di ogni simbolo che compone l'input. Il measure-once è considerato il più vicino (anche per costruzione) alla teoria classica degli automi finiti. Altre definizioni più generali sono state proposte^[4]. Uno degli obiettivi dello studio degli automi a stati finiti quantistici è lo studio dei linguaggi formali che accettano; un altro è quello di studiare i problemi di decidibilità per queste classi di automi e linguaggi.

Delle due definizioni più comuni di automa quantistico finito, quella di automi measure once (o MO-1QFA) data da Moore e Crutchfield è la più semplice e la più vicina agli automi probabilistici.

Sia ${\displaystyle n}$ un numero intero positivo. Un automa quantistico nel senso di Moore e Crutchfield, chiamato in inglese measure once one-way quantum finite automata (MO-1QFA), su un alfabeto ${\displaystyle \Sigma }$ è definito^[3] da:

• un insieme finito di stati ${\displaystyle Q=\{q_{1},\ldots ,q_{n}\}}$. Ad ogni stato ${\displaystyle q_{i}}$ è associato un elemento ${\displaystyle |q_{i}\rangle }$ di uno spazio di Hilbert ${\displaystyle H_{n}}$ di dimensione ${\displaystyle n}$, generalmente ${\displaystyle \mathbb {C} ^{n}}$, affinché ${\displaystyle \{|q_{1}\rangle ,\ldots ,|q_{n}\rangle \}}$ formi una base ortonormale di ${\displaystyle H_{n}}$. Si presume generalmente che ${\displaystyle q_{i}}$ è il ${\displaystyle i}$-esimo vettore unitario,
• una matrice unitaria ${\displaystyle U_{a}}$ di ordine ${\displaystyle n}$ per ogni lettera ${\displaystyle a}$ di ${\displaystyle \Sigma }$. Questa matrice è la rappresentazione di un operatore unitario nella base scelta.
• un vettore ${\displaystyle s}$ di ordine ${\displaystyle n}$ con norma ${\displaystyle \Vert s\Vert =1}$ è lo stato quantistico iniziale.
• una matrice di proiezione ortogonale ${\displaystyle P}$ di ordine ${\displaystyle n}$, corrispondente ad un proiettore ortogonale. Questa può essere talvolta sostituita da un insieme finito di stati terminali e la proiezione opera su di essi.

Le matrici e i vettori hanno coefficienti complessi.

Uno stato (quantistico) è un vettore ${\displaystyle |q\rangle }$ che si decompone sulla base ${\displaystyle Q}$ ed è scritto, nella notazione bra-ket o nella abituale notazione di Dirac in meccanica quantistica, come una combinazione lineare con coefficienti complessi:

${\displaystyle |q\rangle =\alpha _{1}|q_{1}\rangle +\alpha _{2}|q_{2}\rangle \cdots \alpha _{n}|q_{n}\rangle }$ ,

con la condizione aggiuntiva:

${\displaystyle |\alpha _{1}|^{2}+\cdots +|\alpha _{n}|^{2}=1}$ .

Questa notazione indica che ${\displaystyle |q\rangle }$ è la sovrapposizione degli stati ${\displaystyle |q_{i}\rangle }$, il numero ${\displaystyle \alpha _{i}}$ è l'ampiezza dello stato ${\displaystyle |q_{i}\rangle }$. Ogni stato quantistico definisce quindi una "nube" di stati di ${\displaystyle Q}$: si trova simultaneamente in ciascuno degli stati, con l'ampiezza corrispondente. In particolare, lo stato quantistico iniziale ${\displaystyle s}$ è anche una combinazione lineare di stati ${\displaystyle |q_{i}\rangle }$ di norma 1.

Per una parola ${\displaystyle w=a_{1}a_{2}\cdots a_{m}}$, il vettore

${\displaystyle U_{a_{n}}U_{a_{n-1}}\cdots U_{a_{1}}\,s}$

è lo stato quantistico raggiunto dopo aver letto la parola ${\displaystyle w}$; poiché è rappresentato come un vettore colonna, le matrici si applicano nella direzione opposta. In studi più vicini alla teoria degli automi, si incontra la notazione duale, nella quale i vettori di stato sono vettori riga e la scrittura del prodotto delle matrici corrisponde quindi alla sequenza delle lettere lette.

La probabilità di osservare uno stato ${\displaystyle |q\rangle }$ è il numero ${\displaystyle P|q\rangle }$, dove ${\displaystyle P}$ è la matrice di proiezione data nella definizione precedente. Una variante della definizione consiste nel dare un insieme ${\displaystyle F}$ di stati terminali. La probabilità di osservazione di ${\displaystyle |q\rangle =\alpha _{1}|q_{1}\rangle +\alpha _{2}|q_{2}\rangle \cdots \alpha _{n}|q_{n}\rangle }$ diventa ${\textstyle \sum _{q\in F}|\alpha _{q}|^{2}}$.

Se si scrive ${\displaystyle P=\sum _{q\in F}|q\rangle \,\langle q|}$, si vede che ${\displaystyle P}$ è una proiezione sugli stati terminali^[5], per cui

${\displaystyle P|q\rangle =\sum _{q\in F}\alpha _{q}|q\rangle }$

Ne viene che la probabilità di osservazione si scrive

${\displaystyle \sum _{q\in F}|\alpha _{q}|^{2}=\Vert P|q\rangle \Vert ^{2}}$

La probabilità di accettazione di una parola ${\displaystyle w=a_{1}a_{2}\cdots a_{n}}$ è per definizione il numero ${\displaystyle {\text{Pr}}(w)=\Vert P\,U_{a_{n}}U_{a_{n-1}}\cdots U_{a_{1}}\,s\Vert ^{2}}$.

La probabilità di accettazione è quindi la probabilità di osservazione dello stato quantistico ottenuto dopo aver letto la parola ${\displaystyle w}$. L'operazione che consiste nella valutazione di questo numero è una misura.

Il linguaggio ${\displaystyle L}$ accettato o riconosciuto con la probabilità ${\displaystyle p}$ è l'insieme delle parole ${\displaystyle w}$ tali che ${\displaystyle {\text{Pr}}(w)>p}$ oppure ${\displaystyle {\text{Pr}}(w)\geq p}$ (a seconda di quanto rigida si richiede che sia la soglia di accettazione).

Al posto della notazione matriciale, si incontrano anche funzioni di transizione ${\displaystyle \delta :Q\times A\times Q\to \mathbb {C} }$ che suonano più familiari nella teoria degli automi. Una matrice ${\displaystyle U_{a}}$ è considerata come un'applicazione dell'insieme degli stati verso sé stesso, con ${\displaystyle (U_{a})_{k,j}=\delta (k,a,j)}$ e i coefficienti del vettore ${\displaystyle tU_{a}}$ definiti come:

${\displaystyle (tU_{a})_{j}=\sum _{q\in Q}t_{k}\delta (k,a,j)}$ .

Infine, si possono usare numeri reali piuttosto che numeri complessi. Le matrici unitarie sono allora delle matrici ortogonali.

Sia un automa quantistico ${\displaystyle {\mathcal {A}}}$, si indica con ${\displaystyle f_{\mathcal {A}}}$ la funzione definita da ${\displaystyle f_{\mathcal {A}}(w)={\text{Pr}}(w)}$.

Questa funzione associa a ogni parola, la sua probabilità di accettazione. Moore e Crutchfield dimostrano una serie di proprietà di queste funzioni^[6]. Innanzitutto, la serie formale in variabili non commutative è una serie formale razionale:

${\displaystyle \sum _{w\in \Sigma ^{*}}f_{\mathcal {A}}(w)}$

Le seguenti proprietà di chiusura sussistono: siano ${\displaystyle f}$ e ${\displaystyle g}$ funzioni calcolate da automi a stati finiti quantistici.

• (convessità): ${\displaystyle \alpha f+\beta g}$ è calcolabile da un automa a stati finiti quantistico se ${\displaystyle |\alpha |^{2}+|\beta |^{2}=1}$ .
• (intersezione): ${\displaystyle fg}$ è calcolata da un automa a stati finiti quantistico.
• (complemento): ${\displaystyle 1-f}$ è calcolata da un automa a stati finiti quantistico.
• (morfismo inverso): Se ${\displaystyle h:\Delta ^{*}\to \Sigma ^{*}}$ è un morfismo, allora ${\displaystyle fh}$ è calcolabile da un automa a stati finiti quantistico.

Esiste anche una sorta di pumping lemma per queste funzioni^[7]; per ogni ${\displaystyle w}$ e ogni ${\displaystyle \epsilon }$, esiste un ${\displaystyle k}$ tale che per ogni ${\displaystyle u}$ e ${\displaystyle v}$, abbiamo ${\displaystyle f_{\mathcal {A}}(uw^{k}v)-f_{\mathcal {A)}}(uv)|<\epsilon }$.

Numerosi risultati riguardano la decidibilità per un automa a stati finiti quantistico ${\displaystyle {\mathcal {A}}}$, con la notazione ${\displaystyle f_{\mathcal {A}}(w)={\text{Pr}}(w)}$ e per un valore di soglia ${\displaystyle \lambda }$ dato. I seguenti problemi sono indecidibili:

• Esiste una parola ${\displaystyle w}$ tale che ${\displaystyle f_{\mathcal {A}}(w)\geq \lambda }$
• Esiste una parola ${\displaystyle w}$ tale che ${\displaystyle f_{\mathcal {A}}\leq \lambda }$
• Esiste una parola ${\displaystyle w}$ tale che ${\displaystyle f_{\mathcal {A}}(w)=\lambda }$

Sono invece risolvibili i seguenti problemi:

• Esiste una parola ${\displaystyle w}$ tale che ${\displaystyle f_{\mathcal {A}}(w)>\lambda }$ ,
• Esiste una parola ${\displaystyle w}$ tale che ${\displaystyle f_{\mathcal {A}}(w)<\lambda }$ .

D'altra parte, tutti questi problemi sono indecidibili per gli automi probabilistici.

Il linguaggio riconosciuto da un automa quantistico con "soglia" ${\displaystyle \lambda }$ è dato da uno degli insiemi seguenti (a seconda se si include il valore della soglia o meno):

${\displaystyle L_{\geq }=\{w\mid f_{\mathcal {A}}(w)\geq \lambda \},|\quad L_{>}=\{w\mid f_{\mathcal {A}}(w)>\lambda \}}$ ,

dove ${\displaystyle f_{\mathcal {A}}(w)}$ è la probabilità di accettazione di ${\displaystyle w}$ con l'automa ${\displaystyle {\mathcal {A}}}$. Il numero ${\displaystyle \lambda }$ è chiamato "cut-point".

I problemi di decidere se i linguaggi ${\displaystyle L_{\geq }}$ e ${\displaystyle L_{>}}$ sono vuoti, sono entrambi indecidibili per gli automi probabilistici^[8]. D'altra parte, per gli automi quantistici nella definizione di Moore e Crutchfield, il primo problema è indecidibile mentre il secondo è decidibile.

Un cut-point ${\displaystyle \lambda }$ si dice "isolato" se esiste un numero ε tale che

${\displaystyle \vert f_{\mathcal {A}}(w)-\lambda \vert \geq \epsilon }$

per ogni parola ${\displaystyle w}$; equivale a dire che esiste un intervallo non vuoto intorno a ${\displaystyle \lambda }$ che non contiene la probabilità di accettare alcuna parola. Se un cut-point è isolato, i linguaggi ${\displaystyle L_{\geq }}$ e ${\displaystyle L_{>}}$ sono regolari: sono linguaggi a gruppo, ossia dei linguaggi regolari i cui monoidi sintattici sono gruppi finiti^[9].

Tabella di transizione

	1	0
S 1	S 1	S 2
S 2	S 2	S 1

Consideriamo l'automa finito deterministico a due stati in figura. Uno stato quantistico è un vettore scritto in notazione bra-ket:

${\displaystyle |q\rangle =|\alpha _{1}|S_{1}\rangle +\alpha _{2}|S_{2}\rangle ={\begin{pmatrix}a_{1}\\a_{2}\end{pmatrix}}}$

dove i numeri complessi ${\displaystyle \alpha _{1},\alpha _{2}}$ sono normalizzati in modo che ${\displaystyle |\alpha _{1}|^{2}+|\alpha _{2}|^{2}=1}$. Le matrici di transizione unitarie possono essere semplicemente scritte nel seguente modo:

${\displaystyle U_{0}={\begin{pmatrix}0&1\\1&0\end{pmatrix}}}$ e ${\displaystyle U_{1}={\begin{pmatrix}1&0\\0&1\end{pmatrix}}}$ .

Se scegliamo ${\displaystyle S_{1}}$ come stato finale, come mostrato nel diagramma, la matrice di proiezione è:

${\displaystyle P={\begin{pmatrix}1&0\\0&0\end{pmatrix}}}$

Se lo stato iniziale è ${\displaystyle |S_{1}\rangle }$ oppure ${\displaystyle |S_{2}\rangle }$, il comportamento dell'automa è esattamente quello della macchina a stati abituale. In particolare, le parole che vengono accettate lo sono con probabilità uno e il linguaggio accettato è dato dall'espressione regolare ${\displaystyle (1+01^{*}0)^{*}}$ per ${\displaystyle |S_{1}\rangle }$ e dall'espressione ${\displaystyle (1+01^{*}0)^{*}01^{*}}$ per ${\displaystyle |S_{2}\rangle }$. Se d'altra parte ${\displaystyle \alpha _{1}}$ e ${\displaystyle \alpha _{2}}$ sono entrambi diversi da zero, il comportamento è più complicato, e se le matrici ${\displaystyle U_{0}}$ e ${\displaystyle U_{1}}$ non sono scritte in modo così semplice, i risultati possono ancora essere diversi.

Il modello di un automa quantistico nel senso di Kondacs e Watrous, chiamato automa measure-many o MM, differisce dal modello precedente MO nel senso in cui la misura viene eseguita in ogni fase del calcolo piuttosto che unicamente alla fine della computazione^[2]. Secondo la meccanica quantistica, una misura è distruttiva nel senso in cui influenza il valore dell'osservabile misurato; questo principio trova la sua espressione nel formalismo proposto.

Vengono considerati tre tipi di stati che formano una partizione dell'insieme degli stati:

• gli stati di accettazione ${\displaystyle Q_{a}}$
• gli stati di rifiuto, ${\displaystyle Q_{r}}$
• gli stati di continuazione, ${\displaystyle Q_{c}}$, detti anche stati "neutrali".

Lo spazio di Hilbert ${\displaystyle H_{n}}$ è scomposto in tre sottospazi ortogonali^[10] che corrispondono ai tre tipi di stati ${\displaystyle Q_{a},Q_{r},Q_{c}}$:

${\displaystyle H_{n}=H_{a}\oplus H_{r}\oplus H_{c}}$

Per ciascuno dei tre insiemi di stati distinti, esiste una matrice di proiezione associata, indicata con ${\displaystyle P(a),P(r)}$ e ${\displaystyle P(c)}$ che proietta sul corrispondente sottospazio. Essa è definita da

${\displaystyle P(a)=\sum _{q\in Q_{a}}|q\rangle \langle q|}$

e in modo simile per gli altri due insiemi.

Dopo ogni lettura di una lettera della parola in ingresso, l'automa:

• misura l'ampiezza sugli stati di accettazione,
• misura l'ampiezza sugli stati di rifiuto,
• prosegue mantenendo solo le ampiezze degli stati di continuazione.

La misura consiste nel verificare se la proiezione è in un sottospazio appropriato. Dopo la lettura della parola, vi è una probabilità di accettazione e una probabilità di rifiuto^[11].

Più precisamente, sia ${\displaystyle |q\rangle }$ lo stato attuale dell'automa. Dopo la lettura di una lettera ${\displaystyle a}$, lo stato dell'automa è

${\displaystyle |t\rangle =U_{a}|q\rangle }$

Utilizzando gli operatori di proiezione, che indicano in quale dei tre sottospazi ${\displaystyle H_{a}}$, ${\displaystyle H_{r}}$ o ${\displaystyle H_{c}}$ è l'immagine del vettore. La probabilità per lo spazio degli stati accettanti (e analogamente per gli altri) è data da

${\displaystyle \operatorname {Pr} _{a}(t)=\Vert P_{a}|t\rangle \Vert ^{2}}$

Per una parola ${\displaystyle a_{1}a_{2}\cdots a_{m}}$, l'automa agisce come segue: partendo dal vettore iniziale ${\displaystyle s}$, i vettori ${\displaystyle sU_{a_{1}}}$, ${\displaystyle sU_{a_{1}}U_{a_{2}}}$ sono misurati fintanto che il risultato rimane nello spazio di continuazione. Se è nello spazio dell'accettazione, il computo si ferma e la parola è accettata. Se è nello spazio del rifiuto, la parola è respinta. Si presume che la parola sia delimitata da un identificatore di fine stringa, il che implica che l'automa non può rimanere in uno stato neutrale e deve terminare accettando o rifiutando la parola. L'automa può accettare o rifiutare una parola anche senza averla letta nella sua interezza.

Formalmente, l'automa definisce una funzione sulle parole in input che è la probabilità di accettazione di queste ultime:

${\displaystyle \operatorname {Pr} (a_{1}a_{2}\cdots a_{m})=\sum _{k=1}^{m}\left\Vert s\left(\prod _{i=1}^{k-1}U(a_{i})P(c)\right)U(a_{k})P(a)\right\Vert ^{2}}$

Gli stessi problemi posti per il modello MO sono tutti indecidibili per il modello MM.

I linguaggi riconosciuti dagli automi MM con un cut-point isolato sono regolari, ma questi automi non sono abbastanza potenti da riconoscere tutti i linguaggi regolari. Ad esempio, il linguaggio ${\displaystyle \{a,b\}^{*}a}$ non può essere riconosciuto da un automa MM con cut-point isolato.

I linguaggi riconosciuti dagli automi MM non sono chiusi per unione, intersezione o altre normali operazioni booleane.

• (EN) Vincent D. Blondel, Emmanuel Jeandel e Pascal Koiran, Decidable and Undecidable Problems about Quantum Automata, in SIAM Journal on Computing, vol. 34, n. 6, gennaio 2005, pp. 1464–1473, DOI:10.1137/S0097539703425861. URL consultato il 3 settembre 2021.
• (EN) Harm Derksen, Emmanuel Jeandel e Pascal Koiran, Quantum automata and algebraic groups, in Journal of Symbolic Computation, vol. 39, n. 3-4, marzo 2005, pp. 357–371, DOI:10.1016/j.jsc.2004.11.008. URL consultato il 3 settembre 2021.
• (EN) Alberto Bertoni, Christian Choffrut e Flavio D’Alessandro, On the decidability of the intersection problem for quantum automata and context-free languages, in International Journal of Foundations of Computer Science, vol. 25, n. 08, dicembre 2014, pp. 1065–1081, DOI:10.1142/S0129054114400243, arXiv:https://arxiv.org/pdf/1303.2967v1.pdf. URL consultato il 3 settembre 2021.
• (EN) Cristopher Moore e James P. Crutchfield, Quantum automata and quantum grammars, in Theoretical Computer Science, vol. 237, 2000, pp. 275-306.
• (EN) Attila Kondacs e John Watrous, On the power of quantum finite state automata (PDF), in FOCS’97: Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997, pp. 66-75. URL consultato il 3 settembre 2021.
• (EN) Andris Ambainis, Abuzer Yakaryilmaz, Automata and Quantum Computing (PDF), su arxiv.org, giugno 2015.
• (EN) Mika Hirvensalo, Quantum Computing – A Review, in Werner Kuich e George Rahonis (a cura di), Algebraic Foundations in Computer Science : Bozapalidis Festschrift, collana Lecture Notes in Computer Science, vol. 7020, Berlino-Heidelberg, Springer-Verlag, 2011, pp. 146–167, DOI:10.1007/978-3-642-24897-9, ISBN 978-3-642-24896-2.
• (EN) Luigi Accardi, Quantum stochastic processes, in Michiel Hazewinkel (a cura di), Encyclopædia of Mathematics: an updated and annotated translation of the Soviet "Mathematical encyclopaedia", Reidel, 1988-1994, ISBN 1-55608-010-7, OCLC 16755499. URL consultato il 3 settembre 2021.

• Informatica quantistica
• Spazio di Hilbert
• Matrice unitaria

Teoria degli automi: linguaggi formali e grammatiche formali
Gerarchia di Chomsky	Grammatica formale	Linguaggio	Automa minimo
Tipo-0	(illimitato)	Ricorsivamente enumerabile	Macchina di Turing
	(illimitato)	Ricorsivo	Decider
Tipo-1	Dipendente dal contesto	Dipendente dal contesto	Automa lineare
Tipo-2	Libera dal contesto	Libero dal contesto	Automa a pila ND
Tipo-3	Regolare	Regolare	A stati finiti
Ciascuna categoria di linguaggio o grammatica è un sottoinsieme proprio della categoria immediatamente sovrastante.