English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We present upper and lower bounds of the computational complexity of thetwo-way communication model of multiple-prover quantum interactive proofsystems whose verifiers are limited to measure-many two-way quantum finiteautomata. We prove that (i) the languages recognized by those multiple-proversystems running in expected polynomial time are exactly the ones in NEXP, thenondeterministic exponential-time complexity class, (ii) if we further requireverifiers to be one-way quantum automata, then their associated proof systemsrecognize context-free languages but not beyond languages in NE, thenondeterministic linear exponential-time complexity class, and moreover, (iii)when no time bound is imposed, the proof systems become as powerful as Turingmachines. The first two results answer affirmatively an open question, posed byNishimura and Yamakami [J. Comput. System Sci, 75, pp.255--269, 2009], ofwhether multiple-prover quantum interactive proof systems are more powerfulthan single-prover ones. Our proofs are simple and intuitive, although theyheavily rely on an earlier result on multiple-prover interactive proof systemsof Feige and Shamir [J. Comput. System Sci., 44, pp.259--271, 1992].

Constant-Space Quantum Interactive Proofs Against Multiple Provers