Complexity Bounds of Constant-Space Quantum Computation

DOI10.1007/978-3-319-21500-6_34zbMath1434.68292arXiv1606.08764OpenAlexW2963288794MaRDI QIDQ3451121

Tomoyuki Yamakami

Publication date: 10 November 2015

Published in: Developments in Language Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Quantum computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12)

Cites Work

• Unnamed Item
• Unnamed Item
• Unbounded-error quantum computation with small space bounds
• Multihead two-way probabilistic finite automata
• An application of quantum finite automata to interactive proof systems
• Quantum automata and quantum grammars
• \(\text{NQP}_\mathbb{C}=\text{co-C}_=\text{P}\)
• On the complexity of simulating space-bounded quantum computations
• Finite state verifiers I
• Quantum Computability
• Probabilistic automata
• ANALYSIS OF QUANTUM FUNCTIONS