Analogies and differences between quantum and stochastic automata

DOI10.1016/S0304-3975(00)00154-7zbMath0983.68094OpenAlexW1964952177MaRDI QIDQ5958112

Alberto Bertoni, Marco Carpentieri

Publication date: 3 March 2002

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(00)00154-7

zbMATH Keywords

automataquantum computingformal power series

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)

Related Items

Unary probabilistic and quantum automata on promise problems, Very narrow quantum OBDDs and width hierarchies for classical OBDDs, Nondeterministic unitary OBDDs, Quantum Finite Automata: A Modern Introduction, Mirrors and memory in quantum automata, Preface, Computation in finitary stochastic and quantum processes, Automata theory based on quantum logic: reversibilities and pushdown automata, Quantum automata and algebraic groups, Quantum finite automata: advances on Bertoni's ideas, More on quantum, stochastic, and pseudo stochastic languages with few states, Unbounded-error quantum computation with small space bounds, Determination of equivalence between quantum sequential machines, Determining the equivalence for one-way quantum finite automata, Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice, Languages Recognized with Unbounded Error by Quantum Finite Automata, Regular languages accepted by quantum automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quantum mechanical Hamiltonian models of Turing machines
• An introduction to Hilbert space and quantum logic
• Quantum computational networks
• Quantum Computation
• On the definition of a family of automata
• Rapid solution of problems by quantum computation
• A method for obtaining digital signatures and public-key cryptosystems
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• On the Power of Quantum Computation
• Quantum Complexity Theory
• Strengths and Weaknesses of Quantum Computing
• Oracle Quantum Computing
• Realizable Universal Quantum Logic Gates
• Probabilistic automata
• Logical Reversibility of Computation