Interactive Proofs for Quantum Computation

From Quantum Protocol Zoo
Jump to navigation Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Providing solution to the functionality Verification of Quantum Computation, is a class MA (Merlin-Arthur) that consists of all the problems whose solution can be verified by a BPP machine (verifier that has a classical computer) when given a proof by a 'witness' (prover). As believed, MA is not entirely contained in BQP (problems that can be solved by a quantum computer) (1)(2), the functionality of verification asks 'Does every problem in BQP admit an interactive-proof system in which the prover is restricted to BQP computations?' The example protocol answers this question by defining quantum prover interactive proofs and state 'Any language in BQP has a QPIP (quantum prover interactive proofs) which hides the computation from the prover'. IP (interactive proof systems) is a generalisation of class MA, which involves multiple interaction between the prover (untrusted company) and the verifier (consumer).

Assumptions

  • It is assumed that the company and consumer share a classical key drawn from a probability distribution.

Outline

Notations

  • :classical key
  • :Probability distribution from which the classical key has been drawn
  • : State to be authenticated
  • : Test state for successful authentication
  • : Encoding procedure
  • : Encoded state sent over insecure channel by the sender
  • : Encoded state tampered by eavesdropper through insecure channel, received by the receiver
  • : Decoding procedure
  • : Decoded state obtained by the receiver

Requirements

Protocol Description

Further Information

References

  1. Bernstein and Vazirani (1997)
  2. Watrous (2000)
contributed by Shraddha Singh