# Tag Info

5

One recent breakthrough which is not covered in that survey is cheat sheets. See, Separations in communication complexity using cheat sheets and information complexity; Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, and Miklos Santha; arXiv:1605.01142 [quant-ph] It might be a good idea to first ...

5

This is a purely hypothetical answer - I don't know if anybody has ever studied it, and have not attempted to find out - but think about public key cryptography. Current public key systems are based on the idea that some problems in the complexity class NP are probably hard to solve directly, but there exists a "proof" that lets you verify the solution ...

4

For a review of the subject, see this paper: "Non-locality and Communication Complexity" https://arxiv.org/abs/0907.3584

2

There are two different complexity considerations that you might be interested in in this scenario. The one that most people think about is the communication complexity, i.e. how many qubits Alice and Bob have to send to the referee. This is relatively simple to calculate - it's just $mk$ where $k$ is the number of times you have to repeat the controlled-...

Only top voted, non community-wiki answers of a minimum length are eligible