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 $w=a_{1}a_{2}\cdots a_{m}$, le cui lettere $a_{i}$ appartengono a un dato alfabeto $\Sigma$. A ogni parola $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) 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), 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; un altro è quello degli automi measure-many, definiti da Kondacs e Watrous nel 1997. 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. 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.

Automa a stati finiti quantistico Measure-Once

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.

Definizione

Sia $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 $\Sigma$ è definito da:

• un insieme finito di stati $Q=\{q_{1},\ldots ,q_{n}\}$. Ad ogni stato $q_{i}$ è associato un elemento $|q_{i}\rangle$ di uno spazio di Hilbert $H_{n}$ di dimensione $n$, generalmente $\mathbb {C} ^{n}$, affinché $\{|q_{1}\rangle ,\ldots ,|q_{n}\rangle \}$ formi una base ortonormale di $H_{n}$. Si presume generalmente che $q_{i}$ è il $i$-esimo vettore unitario,
• una matrice unitaria $U_{a}$ di ordine $n$ per ogni lettera $a$ di $\Sigma$. Questa matrice è la rappresentazione di un operatore unitario nella base scelta.
• un vettore $s$ di ordine $n$ con norma $\Vert s\Vert =1$ è lo stato quantistico iniziale.
• una matrice di proiezione ortogonale $P$ di ordine $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 $|q\rangle$ che si decompone sulla base $Q$ ed è scritto, nella notazione bra-ket o nella abituale notazione di Dirac in meccanica quantistica, come una combinazione lineare con coefficienti complessi:

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

con la condizione aggiuntiva:

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

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

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

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

è lo stato quantistico raggiunto dopo aver letto la parola $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 $|q\rangle$ è il numero $P|q\rangle$, dove $P$ è la matrice di proiezione data nella definizione precedente. Una variante della definizione consiste nel dare un insieme $F$ di stati terminali. La probabilità di osservazione di $|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 $P=\sum _{q\in F}|q\rangle \,\langle q|$, si vede che $P$ è una proiezione sugli stati terminali, per cui

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

Ne viene che la probabilità di osservazione si scrive

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

La probabilità di accettazione di una parola $w=a_{1}a_{2}\cdots a_{n}$ è per definizione il numero ${\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 $w$. L'operazione che consiste nella valutazione di questo numero è una misura.

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

Notazione alternativa

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

$(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.

Funzione calcolata da un automa quantistico

Sia un automa quantistico ${\mathcal {A}}$, si indica con $f_{\mathcal {A}}$ la funzione definita da $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. Innanzitutto, la serie formale in variabili non commutative è una serie formale razionale:

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

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

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

Pumping Lemma

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

Problemi di decidibilità

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

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

Sono invece risolvibili i seguenti problemi:

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

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

Linguaggi cut point

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

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

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

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

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

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

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

Esempio

Automa a due stati.

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:

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

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

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

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

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

Se lo stato iniziale è $|S_{1}\rangle$ oppure $|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 $(1+01^{*}0)^{*}$ per $|S_{1}\rangle$ e dall'espressione $(1+01^{*}0)^{*}01^{*}$ per $|S_{2}\rangle$. Se d'altra parte $\alpha _{1}$ e $\alpha _{2}$ sono entrambi diversi da zero, il comportamento è più complicato, e se le matrici $U_{0}$ e $U_{1}$ non sono scritte in modo così semplice, i risultati possono ancora essere diversi.

Automa a stati finiti quantistico measure-many

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. 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 $Q_{a}$
• gli stati di rifiuto, $Q_{r}$
• gli stati di continuazione, $Q_{c}$, detti anche stati "neutrali".

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

$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 $P(a),P(r)$ e $P(c)$ che proietta sul corrispondente sottospazio. Essa è definita da

$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.

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

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

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

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

Per una parola $a_{1}a_{2}\cdots a_{m}$, l'automa agisce come segue: partendo dal vettore iniziale $s$, i vettori $sU_{a_{1}}$, $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:

$\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 $\{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.

Bibliografia

• (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.

Voci correlate

• Informatica quantistica
• Spazio di Hilbert
• Matrice unitaria