Personal tools
You are here: Home Graduate Study Quantum Complexity

Quantum Complexity

How entanglement determines the power of quantum and classical multi-prover interactive proof systems is a long-standing open question. Based on a novel approach connecting blind quantum computing protocol with interactive proof systems, it is proven that a quantum verifier is no more powerful than a classical verifier even in the multi-party scenario. The main goal of the project is to explore further this approach to fully characterise the power of entangled provers with classical verifier, building towards a quantum PCP theorem. Another central concept in complexity theory with a direct application in cryptography is that of a zero-knowledge protocol where a prover wants to convince a verifier about the truth of a statement without revealing any additional information about the statement. In practice, zero-knowledge protocols are used as primitives in larger cryptographic protocols in order to limit the power of malicious parties to disrupt the security of the larger protocol. However, constructing classical and quantum interactive proof systems that are zero knowledge against a quantum attack remains a challenging task. A second goal of the project is to exploit the structural link between blind quantum computing and interactive proof systems to develop general schemes for constructing zero knowledge protocols by exploiting blindness properties to hide the information available to malicious parties in an interactive system.

Potential Supervisors:

Elham Kashefi

Document Actions