Class Description

QPIP: Quantum Prover Interactive Proof

Like IP, but the prover is a BQP machine, not unbounded. The prover and verifier can only exchange classical information in their interaction. Shown to be equal to BQP in [Mah18].

Similarly, QPIPk is like QPIP, but the verifier is a BPP machine with access to a k qubit quantum computer, and the verifier and prover can exchange classical and quantum information.

Defined in [ABOE08], where they showed that BQP=QPIPc for some constant c.

Linked From

No class.