Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with quantum interactive proofs:
TR05-038 | 10th April 2005
Ran Raz

Quantum Information and the PCP Theorem

We show how to encode $2^n$ (classical) bits $a_1,...,a_{2^n}$
by a single quantum state $|\Psi \rangle$ of size $O(n)$ qubits,
such that:
for any constant $k$ and any $i_1,...,i_k \in \{1,...,2^n\}$,
the values of the bits $a_{i_1},...,a_{i_k}$ can be retrieved
from $|\Psi \rangle$ by a one-round Arthur-Merlin interactive ... more >>>

TR12-085 | 5th July 2012
Tsuyoshi Ito, Thomas Vidick

A multi-prover interactive proof for NEXP sound against entangled provers

We prove a strong limitation on the ability of entangled provers to collude in a multiplayer game. Our main result is the first nontrivial lower bound on the class MIP* of languages having multi-prover interactive proofs with entangled provers; namely MIP* contains NEXP, the class of languages decidable in non-deterministic ... more >>>

TR18-044 | 5th March 2018
Alessandro Chiesa, Michael Forbes, Tom Gur, Nicholas Spooner

Spatial Isolation Implies Zero Knowledge Even in a Quantum World

Revisions: 1

Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben-Or et al. (STOC 1988) shows that zero knowledge can be achieved unconditionally for any language in NEXP, as long as one is willing to make a suitable physical assumption: if the provers are spatially isolated, ... more >>>

ISSN 1433-8092 | Imprint