Complessità quantistica di Černý delle parole binarie

Abstract degli autori

Introduciamo la complessità quantistica di Černý $\mathrm{qc}(w)$ di una parola binaria $w$: la dimensione minima $d$ per cui esistono canali quantistici $A_0,A_1$ su matrici di densità $d\times d$ e uno stato iniziale $ρ_0$ tali che $w$ sia l’unica parola più breve il cui canale associato è costante sull’insieme raggiungibile. Dimostriamo che $2\le\mathrm{qc}(w)\le\lceil\sqrt{|w|+1}\,\rceil$ per ogni $w$ non vuota: un risparmio quadratico rispetto all’analogo classico. Dimostriamo inoltre che le parole costanti sono estremali: $\mathrm{qc}(0^m)=\lceil\sqrt{m+1}\,\rceil$. Al contrario, $\mathrm{qc}(01^n0)=2$ per ogni $n\ge 1$, realizzata da un singolo qubit il cui angolo di rotazione funge da contatore; di conseguenza, non esiste un analogo quantistico della funzione di Černý e $\mathrm{qc}$ è fortemente anticorrelata con le nozioni intuitive di complessità descrittiva. Studiamo inoltre la variante $\mathrm{qcp}$, in cui lo stato bersaglio della sincronizzazione deve essere puro. Dimostriamo che in dimensione $2$ nessuna parola di lunghezza almeno $2$ può essere l’unica parola sincronizzante più breve con uno stato bersaglio puro, e presentiamo un esempio esplicito su un qutrit che, combinando una rotazione coerente con un canale di misura e convogliamento, raggiunge $\mathrm{qcp}(01^n0)=3$ con uno stato bersaglio appartenente alla base computazionale e con una sincronizzazione valida universalmente per tutti gli stati di ingresso. Per questa famiglia, dunque, la purezza dello stato di reset richiede esattamente una dimensione in più. Osserviamo inoltre che $\mathrm{qc}$ è calcolabile mediante una riduzione alla teoria del primo ordine dei reali.