Computer Science – Computational Complexity
Scientific paper
2001-02-19
Journal of Computer and System Sciences, 66(3):429--450, 2003
Computer Science
Computational Complexity
LaTeX2e, 19 pages, 2 figures, title changed, some of the sections are fully revised, journal version in Journal of Computer an
Scientific paper
This 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.
Kobayashi Hirotada
Matsumoto Keiji
No associations
LandOfFree
Quantum Multi-Prover Interactive Proof Systems with Limited Prior Entanglement does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quantum Multi-Prover Interactive Proof Systems with Limited Prior Entanglement, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Multi-Prover Interactive Proof Systems with Limited Prior Entanglement will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-212365