Quantum finite automaton (original) (raw)
En informatique quantique et en informatique théorique, un automate fini quantique est une généralisation des automates finis où un mot est accepté selon le résultat d'une certaine mesure. Il existe plusieurs modèles des automates finis quantiques ; le plus restrictif est celui des automates dits « measure-once » de ; un autre est celui des automates « measure-many » de . Ces deux modèles sont très différents l'un de l’autre ; le modèle « measure-once » se rapproche plus de la théorie classique des automates finis. D'autres définitions, plus générales, ont été proposées, en généralisation des diverses variantes des automates, par exemple par . Un des objectifs de l’étude des automates fini quantiques est l’étude des langages formels qu'ils acceptent ; un autre est d'étudier les problèmes
| Property | Value |
|---|---|
| dbo:abstract | En informatique quantique et en informatique théorique, un automate fini quantique est une généralisation des automates finis où un mot est accepté selon le résultat d'une certaine mesure. Il existe plusieurs modèles des automates finis quantiques ; le plus restrictif est celui des automates dits « measure-once » de ; un autre est celui des automates « measure-many » de . Ces deux modèles sont très différents l'un de l’autre ; le modèle « measure-once » se rapproche plus de la théorie classique des automates finis. D'autres définitions, plus générales, ont été proposées, en généralisation des diverses variantes des automates, par exemple par . Un des objectifs de l’étude des automates fini quantiques est l’étude des langages formels qu'ils acceptent ; un autre est d'étudier les problèmes de décidabilité pour ces classes d'automates et de langages. Les automates finis quantiques sont similaires aux automates probabilistes, mais la classe des langages reconnus par automates quantiques est strictement contenue dans la classe des langages reconnus par automates probabilistes.Les automates finis quantiques peuvent aussi être vus comme une version quantique des sous-shifts de type fini, ou comme une variante quantique des chaînes de Markov. Les automates finis quantiques sont, à leur tour, des cas particuliers des automates finis dit géométriques ou des automates finis dit topologiques. Un automate fini quantique opère sur des mots finis , dont les lettres sont dans un alphabet donné . Il attribue à chaque mot une probabilité; en fonction de cette probabilité, le mot est accepté ou rejeté par l'automate. Les langages acceptés par les automates finis quantique ne coïncident pas avec les langages rationnels acceptés par les automates finis, ni avec les langages stochastiques acceptés par les automates finis probabilistes. (fr) In quantum computing, quantum finite automata (QFA) or quantum state machines are a quantum analog of probabilistic automata or a Markov decision process. They provide a mathematical abstraction of real-world quantum computers. Several types of automata may be defined, including measure-once and measure-many automata. Quantum finite automata can also be understood as the quantization of subshifts of finite type, or as a quantization of Markov chains. QFAs are, in turn, special cases of geometric finite automata or topological finite automata. The automata work by receiving a finite-length string of letters from a finite alphabet , and assigning to each such string a probability indicating the probability of the automaton being in an accept state; that is, indicating whether the automaton accepted or rejected the string. The languages accepted by QFAs are not the regular languages of deterministic finite automata, nor are they the stochastic languages of probabilistic finite automata. Study of these quantum languages remains an active area of research. (en) 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 , le cui lettere appartengono a un dato alfabeto . A ogni parola 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. (it) Kwantowy automat skończony (ang. Quantum Finite Automata, QFA) – abstrakcyjna maszyna o skończonej liczbie stanów, która – zaczynając w stanie początkowym – czyta kolejne symbole pewnego ciągu znaków ze skończonego zbioru i przydziela danemu ciągowi liczbę określającą prawdopodobieństwo znajdowania się maszyny w stanie akceptującym (końcowym). Czyli wskazuje na to, czy dany ciąg znaków należy do języka regularnego, do rozpoznawania którego jest zbudowana. Kwantowe automaty skończone są kwantowym analogiem bądź Łańcuchów Markowa i są związane z komputerami kwantowymi podobnie jak automaty skończone z maszynami Turinga. (pl) Na computação quântica, o autômato quântico finito ou QFA é uma analogia quântica do autômato probabilístico. Autômatos probabilísticos estão relacionados à computação quântica da mesma maneira que o autômato finito está relacionado à máquina de Turing. Muitos tipos de autômatos podem ser definidos, incluindo measure-once e measure-many autômatos. Autômatos quânticos de estados finitos podem ser entendidos como uma quantização do , ou uma quantização das cadeias de Markov. QFA é, de certa maneira, um caso especial de autômato geométrico finito ou autômato topológico finito. Os autômatos trabalham aceitando uma string de comprimento finito ou letras de um alfabeto finito e assinalando para cada uma dessas strings uma probabilidade indica a probabilidade do autômato estar em um estado aceitação, isto é,indicando se o autômato aceita ou rejeita a string. (pt) |
| dbo:thumbnail | wiki-commons:Special:FilePath/DFAexample.svg?width=300 |
| dbo:wikiPageID | 7926008 (xsd:integer) |
| dbo:wikiPageLength | 22433 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1120193608 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Power_set dbr:Probabilistic_finite_automaton dbr:Probability_amplitude dbr:Probability_distribution dbr:Quantum_computer dbr:Quantum_logic_gate dbr:Qubit dbr:Mixing_(physics) dbr:Nondeterministic_finite_automaton dbr:Projection_matrix dbr:Non-deterministic_finite_automaton dbr:Bra–ket_notation dbr:De_Bruijn_graph dbr:Deterministic_finite_automata dbr:Deterministic_finite_automaton dbr:Homogeneous_space dbr:Regular_expression dbr:De_Rham_curve dbr:Quantum_computing dbr:Complex_number dbr:Matrix_multiplication dbr:Measure_theory dbr:POVM dbr:Quantum_Markov_chain dbr:Quantum_decoherence dbr:Controlled_NOT_gate dbr:Alphabet_(computer_science) dbc:Quantum_information_theory dbr:Linear_operator dbr:Machine_learning dbr:Simplex dbr:Stack_machine dbr:State_transition_table dbr:Stochastic_matrix dbr:Complex_projective_space dbr:Fubini–Study_metric dbr:String_(computer_science) dbr:Viterbi_algorithm dbr:Automorphisms dbr:Hadamard_transform dbr:James_P._Crutchfield dbr:Linear_span dbr:Topological_dynamics dbr:No-cloning_theorem dbr:Semiautomaton dbr:Adjacency_matrix dbc:Finite_automata dbr:Ergodic dbr:Formal_language dbr:Graph_theory dbr:Probability dbr:Regular_language dbr:Ring_(mathematics) dbr:Hilbert_space dbr:Isometry dbr:Probability_vector dbr:Abuse_of_notation dbr:Characteristic_2 dbr:Hidden_Markov_model dbr:Manifold dbr:Pure_state dbr:Maximum_entropy_method dbr:Indicator_function dbr:Inner_product dbr:Metric_space dbr:Open_function dbr:Markov_chain dbr:Markov_decision_process dbr:Schrödinger_picture dbr:Unitary_matrix dbr:Forward-backward_algorithm dbr:Metric_(mathematics) dbr:Hermitian_transpose dbr:Topological_space dbr:Stochastic_language dbr:Orthogonal_subspace dbr:Riemann_symmetric_space dbr:Mixed_quantum_state dbr:State_transition dbr:Finite_automaton dbr:Cris_Moore dbr:Mixed_state_(physics) dbr:Quantum_measurement dbr:Quantum_semiautomaton dbr:Accept_state dbr:Probabilistic_automata dbr:Probabilistic_finite_automata dbr:Push-down_automaton dbr:Unitary_matrices dbr:Subshifts_of_finite_type dbr:File:DFAexample.svg dbr:Ion_Baianu |
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:Short_description dbt:Quantum_computing |
| dct:subject | dbc:Quantum_information_theory dbc:Finite_automata |
| rdfs:comment | En informatique quantique et en informatique théorique, un automate fini quantique est une généralisation des automates finis où un mot est accepté selon le résultat d'une certaine mesure. Il existe plusieurs modèles des automates finis quantiques ; le plus restrictif est celui des automates dits « measure-once » de ; un autre est celui des automates « measure-many » de . Ces deux modèles sont très différents l'un de l’autre ; le modèle « measure-once » se rapproche plus de la théorie classique des automates finis. D'autres définitions, plus générales, ont été proposées, en généralisation des diverses variantes des automates, par exemple par . Un des objectifs de l’étude des automates fini quantiques est l’étude des langages formels qu'ils acceptent ; un autre est d'étudier les problèmes (fr) In quantum computing, quantum finite automata (QFA) or quantum state machines are a quantum analog of probabilistic automata or a Markov decision process. They provide a mathematical abstraction of real-world quantum computers. Several types of automata may be defined, including measure-once and measure-many automata. Quantum finite automata can also be understood as the quantization of subshifts of finite type, or as a quantization of Markov chains. QFAs are, in turn, special cases of geometric finite automata or topological finite automata. (en) 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. (it) Kwantowy automat skończony (ang. Quantum Finite Automata, QFA) – abstrakcyjna maszyna o skończonej liczbie stanów, która – zaczynając w stanie początkowym – czyta kolejne symbole pewnego ciągu znaków ze skończonego zbioru i przydziela danemu ciągowi liczbę określającą prawdopodobieństwo znajdowania się maszyny w stanie akceptującym (końcowym). Czyli wskazuje na to, czy dany ciąg znaków należy do języka regularnego, do rozpoznawania którego jest zbudowana. (pl) Na computação quântica, o autômato quântico finito ou QFA é uma analogia quântica do autômato probabilístico. Autômatos probabilísticos estão relacionados à computação quântica da mesma maneira que o autômato finito está relacionado à máquina de Turing. Muitos tipos de autômatos podem ser definidos, incluindo measure-once e measure-many autômatos. Autômatos quânticos de estados finitos podem ser entendidos como uma quantização do , ou uma quantização das cadeias de Markov. QFA é, de certa maneira, um caso especial de autômato geométrico finito ou autômato topológico finito. (pt) |
| rdfs:label | Automa a stati finiti quantistico (it) Automate quantique (fr) Quantum finite automaton (en) Kwantowy automat skończony (pl) Autômato quântico (pt) |
| owl:sameAs | wikidata:Quantum finite automaton dbpedia-fa:Quantum finite automaton dbpedia-fr:Quantum finite automaton dbpedia-he:Quantum finite automaton dbpedia-it:Quantum finite automaton dbpedia-pl:Quantum finite automaton dbpedia-pt:Quantum finite automaton https://global.dbpedia.org/id/iYhz |
| prov:wasDerivedFrom | wikipedia-en:Quantum_finite_automaton?oldid=1120193608&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/DFAexample.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Quantum_finite_automaton |
| is dbo:wikiPageRedirects of | dbr:Quantum_finite_automata dbr:Topological_automata dbr:Topological_automaton dbr:Topological_finite_automata dbr:Topological_finite_state_machine dbr:Metric_automata dbr:Metric_automaton dbr:Quantum_finite_state_machine dbr:Geometric_automaton |
| is dbo:wikiPageWikiLink of | dbr:Quantum_finite_automata dbr:Probabilistic_automaton dbr:Topological_automata dbr:Topological_automaton dbr:Topological_finite_automata dbr:Topological_finite_state_machine dbr:Deterministic_finite_automaton dbr:Quantum_Markov_chain dbr:Quantum_Turing_machine dbr:Metric_automata dbr:Metric_automaton dbr:Finite-state_machine dbr:Quantum_finite_state_machine dbr:Geometric_automaton |
| is foaf:primaryTopic of | wikipedia-en:Quantum_finite_automaton |
