Constant-space quantum interactive proofs against multiple provers

DOI10.1016/j.ipl.2014.05.012zbMath1371.68090arXiv1309.0429OpenAlexW2057357905MaRDI QIDQ2252642

Tomoyuki Yamakami

Publication date: 18 July 2014

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

recursively enumerable setformal languagenondeterministic exponential timetheory of computingquantum interactive proof system

Mathematics Subject Classification ID

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

Related Items

One-way reversible and quantum finite automata with advice

Cites Work

• Unnamed Item
• Unnamed Item
• Non-deterministic exponential time has two-prover interactive protocols
• An application of quantum finite automata to interactive proof systems
• Multi-oracle interactive protocols with constant space verifiers
• Quantum multi-prover interactive proof systems with limited prior entanglement.
• PSPACE has constant-round quantum interactive proof systems
• Polynomial time quantum computation with advice
• Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
• Finite state verifiers I
• QIP = PSPACE
• Implementation and Application of Automata
• SOFSEM 2004: Theory and Practice of Computer Science