Hierarchy and equivalence of multi-letter quantum finite automata

DOI10.1016/j.tcs.2009.03.040zbMath1179.68073WikidataQ62049436 ScholiaQ62049436MaRDI QIDQ2271440

Sheng Yu, Dao Wen Qiu

Publication date: 7 August 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.03.040

zbMATH Keywords

equivalence; quantum computing; hierarchy; quantum finite automata; multi-letter finite automata

Mathematics Subject Classification ID

68Q45: Formal languages and automata

81P68: Quantum computation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quantum computing.
• Quantum automata and quantum grammars
• Characterization of sequential quantum machines
• The computer as a physical system: a microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines
• One way multihead deterministic finite automata
• Automata theory based on quantum logic: reversibilities and pushdown automata
• Determination of equivalence between quantum sequential machines
• Determining the equivalence for one-way quantum finite automata
• Undecidability on quantum finite automata
• Quantum computational networks
• Characterizations of 1-Way Quantum Finite Automata
• A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Complexity Theory
• On the equivalence problem for deterministic multitape automata and transducers
• Multi-letter Reversible and Quantum Finite Automata
• Improved Undecidability Results on the Emptiness Problem of Probabilistic and Quantum Cut-Point Languages