Metraipolis › archive › dc_65eebef27e01
Automa a stati finiti quantistico — Wikipedia
- Source
- Wikipedia (it)
- Original
- https://it.wikipedia.org/wiki/Automa_a_stati_finiti_quantistico
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-18T07:50:45.619Z
- SHA-256 of the archived text
a873c253ee3401fedf2e7637c3c0d720204fc0aec3475ab968e7bc0ae8873a6e- Stable URL of this page
https://metraipolis.com/documento/dc_65eebef27e01
How to cite
Automa a stati finiti quantistico — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Automa_a_stati_finiti_quantistico (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_65eebef27e01 (Metraipolis archive dc_65eebef27e01, sha256 a873c253ee3401fedf2e7637c3c0d720204fc0aec3475ab968e7bc0ae8873a6e)
BibTeX
@misc{dc65eebef27e01,
title = {Automa a stati finiti quantistico — Wikipedia},
howpublished = {Wikipedia (it)},
url = {https://it.wikipedia.org/wiki/Automa_a_stati_finiti_quantistico},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_65eebef27e01; sha256 a873c253ee3401fedf2e7637c3c0d720204fc0aec3475ab968e7bc0ae8873a6e},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Automa_a_stati_finiti_quantistico. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 ⋯ a m {\displaystyle w=a_{1}a_{2}\cdots a_{m}} , le cui lettere a i {\displaystyle a_{i}} appartengono a un dato alfabeto Σ {\displaystyle \Sigma } . A ogni parola w {\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) 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.
Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in italiano, in ordine alfabetico).
Fonte: Wikipedia in italiano, voce «Automa a stati finiti quantistico» — https://it.wikipedia.org/wiki/Automa_a_stati_finiti_quantistico
Wikidata Q176837 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q176837
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Automa_a_stati_finiti_quantistico?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 144154586, consultata il 2026-10-18T07:47:41.126Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: c68025d2ea787bda6772d52448570e5f848c616660449bae0d5f2f636a4cdb8b