Quantum Multi-Prover Interactive Proof Systems with Limited Prior Entanglement

Simple item page
dc.creatorKobayashi, Hirotada
dc.creatorMatsumoto, Keiji
dc.date2001-02-19
dc.date2003-06-10
dc.date.accessioned2026-07-07T03:16:56Z
dc.date.available2026-07-07T03:16:56Z
dc.descriptionThis paper gives the first formal treatment of a quantum analogue of multi-prover interactive proof systems. It is proved that the class of languages having quantum multi-prover interactive proof systems is necessarily contained in NEXP, under the assumption that provers are allowed to share at most polynomially many prior-entangled qubits. This implies that, in particular, if provers do not share any prior entanglement with each other, the class of languages having quantum multi-prover interactive proof systems is equal to NEXP. Related to these, it is shown that, in the case a prover does not have his private qubits, the class of languages having quantum single-prover interactive proof systems is also equal to NEXP.
dc.descriptionLaTeX2e, 19 pages, 2 figures, title changed, some of the sections are fully revised, journal version in Journal of Computer and System Sciences
dc.identifierhttps://arxiv.org/abs/cs/0102013
dc.identifierhttp://arxiv.org/abs/cs/0102013
dc.identifierJournal of Computer and System Sciences, 66(3):429--450, 2003
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30543
dc.subjectComputational Complexity
dc.subjectQuantum Physics
dc.subjectF.1.2;F.1.3
dc.titleQuantum Multi-Prover Interactive Proof Systems with Limited Prior Entanglement
dc.typetext

Files

Collections

arXiv