| DATE: | Wednesday, April 28th 2004. |
| TIME: | 4:30 PM - 5:30 PM |
| PLACE: | McConnel 320 |
| TITLE: | Quantum multi-prover interactive proof systems with limited prior entanglement |
| SPEAKER: | Hirotada Kobayashi, ERATO, Tokyo Japan |
We give the first formal treatment of a quantum analogue of multi-prover
interactive proof systems. We 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.