Interactive proofs with quantum finite automata

DOI10.1016/J.TCS.2014.11.030MaRDI QIDQ2513604zbMATH OpenOpenAlexWikidataFDO

Authors Harumichi Nishimura, Tomoyuki Yamakami

Publication date 28 January 2015

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

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

zbMATH Keywords

classical proverfinite automatoninteractioninteractive proof systemquantum computingquantum prover

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Quantum computation (81P68)

Abstract: Following an early work of Dwork and Stockmeyer on interactive proof systems whose verifiers are two-way probabilistic finite automata, the authors initiated in 2004 a study on the computational power of quantum interactive proof systems whose verifiers are particularly limited to quantum finite automata. As a follow-up to the authors' early journal publication [J. Comput. System Sci., vol.75, pp.255-269, 2009], we further investigate the quantum nature of interactions between provers and verifiers by studying how various restrictions on quantum interactive proof systems affect the language recognition power of the proof systems. In particular, we examine three intriguing restrictions that (i) provers always behave in a classical fashion, (ii) verifiers always reveal to provers the information on next moves, and (iii) the number of interactions between provers and verifiers is bounded.

Recommendations

• An application of quantum finite automata to interactive proof systems
• Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
• Constant-space quantum interactive proofs against multiple provers
• Implementation and Application of Automata
• Finite state verifiers I

Cites work

• An application of quantum finite automata to interactive proof systems
• Finite state verifiers I
• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 1688355 (Why is no real title available?)
• scientific article; zbMATH DE number 512803 (Why is no real title available?)
• scientific article; zbMATH DE number 1500664 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• Implementation and Application of Automata
• On the Power of Finite Automata with both Nondeterministic and Probabilistic States
• PSPACE has constant-round quantum interactive proof systems
• Quantum automata and quantum grammars

Cited in

(7)

• An application of quantum finite automata to interactive proof systems
• Constant-space, constant-randomness verifiers with arbitrarily small error
• Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
• scientific article; zbMATH DE number 5899305 (Why is no real title available?)
• One-way topological automata and the tantalizing effects of their topological features
• scientific article; zbMATH DE number 7378343 (Why is no real title available?)
• Implementation and Application of Automata

This page was built for publication: Interactive proofs with quantum finite automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2513604)