Interactive Proofs Work Against Entanglement

Category: Science & Technology
Posted: July 31, 2012 03:14PM
Author: Guest_Jim_*

What do you do when you cannot find the answer to a problem on your own? You ask someone or something else for the answer. What if you cannot trust them to always give you a correct answer; can you still extract useful information from them? This is the basis of what is known as an interactive proof in theoretical computer science, which has a computationally weak questioner use unreliable but computationally powerful respondents to answer questions. It turns out you can extract reliable information in this scenario.

About twenty years ago the idea of multiple respondents that could not communicate with each other, called a multiprover system, was introduced. A questioner can also get reliable information from a multiprover system, but ten years ago researchers asked if quantum entanglement could defeat interactive proofs. By sharing entangled particles between the respondents, can the questioner be lied to? Recent work at MIT has found the answer to be 'sometimes.' When the idea of entanglement was first added, researchers immediately recognized it could defeat some forms of interactive proofs, but were not sure which ones would be affected. Now the MIT researchers have found there do exist some scenarios that are immune to quantum entanglement, but have only made the tools to identify which scenarios they may be.

This finding could be very important for many quantum technologies as it broadens our understanding of entanglement and quantum complexity. Also security techniques could be affected by this, as it gives a potential way to crack them.

• Email Link
• Print News

This news has comment postings disabled because it is now archived.