Quantum Finite Automata: A Modern Introduction

DOI10.1007/978-3-319-13350-8_16zbMath1323.68278arXiv1406.4048OpenAlexW1932923986MaRDI QIDQ2944891

A. C. Cem Say, Abuzer Yakaryılmaz

Publication date: 8 September 2015

Published in: Computing with New Resources (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1406.4048

Mathematics Subject Classification ID

Related Items (25)

Unary probabilistic and quantum automata on promise problems ⋮ Two-way and one-way quantum and classical automata with advice for online minimization problems ⋮ Nondeterministic unitary OBDDs ⋮ Unnamed Item ⋮ Classical and Quantum Counter Automata on Promise Problems ⋮ Language recognition power and succinctness of affine automata ⋮ Exact Affine Counter Automata ⋮ Learning quantum finite automata with queries ⋮ Error-Free Affine, Unitary, and Probabilistic OBDDs ⋮ Energy complexity of regular languages ⋮ GAPs for Shallow Implementation of Quantum Finite Automata ⋮ On a Conjecture by Christian Choffrut ⋮ Computing with a single qubit faster than the computation quantum speed limit ⋮ Unnamed Item ⋮ Unnamed Item ⋮ More on quantum, stochastic, and pseudo stochastic languages with few states ⋮ Affine Computation and Affine Automaton ⋮ Debates with Small Transparent Quantum Verifiers ⋮ New Results on Vector and Homing Vector Automata ⋮ New Results on the Minimum Amount of Useful Space ⋮ Language Recognition Power and Succinctness of Affine Automata ⋮ Uncountable classical and quantum complexity classes ⋮ Adjacent vertices can be hard to find by quantum walks ⋮ Quantum algorithm for shortest path search in directed acyclic graph ⋮ Looking for Pairs that Hard to Separate: A Quantum Approach

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Superiority of exact quantum automata for promise problems
• Unbounded-error quantum computation with small space bounds
• Characterizations of one-way general quantum finite automata
• Improved constructions of quantum automata
• Quantum automata and quantum grammars
• Two-way finite automata with quantum and classical states.
• Automata and quantum computing
• Algebraic results on quantum automata
• Quantum, Stochastic, and Pseudo Stochastic Languages with Few States
• Potential of Quantum Finite Automata with Exact Acceptance
• Generalizations of the distributed Deutsch–Jozsa promise problem
• Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent Languages
• One-Way Finite Automata with Quantum and Classical States
• On quantum and probabilistic communication
• Implications of Quantum Automata for Contextuality
• A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
• Quantum Computability
• On the State Complexity of Semi-quantum Finite Automata
• Classical Automata on Promise Problems
• Probabilistic automata
• Analogies and differences between quantum and stochastic automata

This page was built for publication: Quantum Finite Automata: A Modern Introduction