Interactive Proofs for Quantum Computation

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.

Notations

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} :classical key
• $p(k)$:Probability distribution from which the classical key has been drawn
• $|\psi \rangle$: State to be authenticated
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |flag\rangle} : Test state for successful authentication
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Enc_{k}} : Encoding procedure
• $\rho$: Encoded state sent over insecure channel by the sender
• $\rho '$: Encoded state tampered by eavesdropper through insecure channel, received by the receiver
• $Dec_{k}$: Decoding procedure
• $Dec_{k}(\rho ')$: Decoded state obtained by the receiver

References

1. Bernstein and Vazirani (1997)
2. Watrous (2000)

contributed by Shraddha Singh