Quantum proofs

This talk will introduce the notion of quantum proofs, which are quantum states that certify the validity of a given statement to someone with a polynomial-time bounded quantum computer. This notion gives rise to a quantum complexity class, known as QMA, that represents a quantum computational analogue to the well-known complexity class NP. A problem known as the Group Non-Membership problem that illustrates how quantum information can be exploited in this context will be discussed.