Quantum alternation

DOI10.1134/S1995080216060196zbMath1407.68182OpenAlexW3192680852MaRDI QIDQ2361668

Abuzer Yakaryılmaz

Publication date: 30 June 2017

Published in: Lobachevskii Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s1995080216060196

zbMATH Keywords

quantum computationpolynomial hierarchyalternationquantum automataPSPACELOGSPACEsubset-sum problems

Mathematics Subject Classification ID

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

Related Items

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Superiority of exact quantum automata for promise problems
• Computing with new resources. Essays dedicated to Jozef Gruska on the occasion of his 80th birthday
• Unbounded-error quantum computation with small space bounds
• The complexity of two-player games of incomplete information
• Games against nature
• \(\text{NQP}_\mathbb{C}=\text{co-C}_=\text{P}\)
• On the complexity of simulating space-bounded quantum computations
• Computer science -- theory and applications. 8th international computer science symposium in Russia, CSR 2013, Ekaterinburg, Russia, June 25--29, 2013. Proceedings
• Space-bounded quantum complexity
• Relationships between nondeterministic and deterministic tape complexities
• The Knowledge Complexity of Interactive Proof Systems
• Alternation
• Proving the Power of Postselection
• Computational Complexity
• Reachability in Two-Clock Timed Automata Is PSPACE-Complete
• Quantum computing, postselection, and probabilistic polynomial-time
• A context-free language which is not acceptable by a probabilistic automaton
• Debates with Small Transparent Quantum Verifiers