Write, autoreview, editor, reviewer
3,129
edits
Interactive Proofs for Quantum Computation: Difference between revisions
Jump to navigation
Jump to search
→Further Information
No edit summary |
|||
| Line 1: | Line 1: | ||
Providing solution to the functionality [[Verification of Universal Quantum Computation|Verification of Quantum Computation]], is a class [https://complexityzoo.uwaterloo.ca/Complexity_Zoo:M#ma 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) [[Interactive Proofs for Quantum Computation#References|(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 [https://arxiv.org/pdf/1704.04487.pdf 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'. [https://complexityzoo.uwaterloo.ca/Complexity_Zoo:I#ip IP] (interactive proof systems) is a generalisation of class MA, which involves multiple interaction between the prover (untrusted company) and the verifier (consumer). | Providing solution to the functionality [[Verification of Universal Quantum Computation|Verification of Quantum Computation]], is a class [https://complexityzoo.uwaterloo.ca/Complexity_Zoo:M#ma 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) [[Interactive Proofs for Quantum Computation#References|(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 [https://arxiv.org/pdf/1704.04487.pdf 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'. [https://complexityzoo.uwaterloo.ca/Complexity_Zoo:I#ip 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== | |||
*<math>k</math>:classical key | |||
*<math>p(k)</math>:Probability distribution from which the classical key has been drawn | |||
*<math>|\psi\rangle</math>: State to be authenticated | |||
*<math>|flag\rangle</math>: Test state for successful authentication | |||
*<math>Enc_{k}</math>: Encoding procedure | |||
*<math>\rho</math>: Encoded state sent over insecure channel by the sender | |||
*<math>\rho '</math>: Encoded state tampered by eavesdropper through insecure channel, received by the receiver | |||
*<math>Dec_k</math>: Decoding procedure | |||
*<math>Dec_k (\rho')</math>: Decoded state obtained by the receiver | |||
==Requirements== | |||
==Pseudo Code== | |||
==Further Information== | ==Further Information== | ||
==References== | ==References== | ||
#[https://epubs.siam.org/doi/10.1137/S0097539796300921 Bernstein and Vazirani (1997)] | #[https://epubs.siam.org/doi/10.1137/S0097539796300921 Bernstein and Vazirani (1997)] | ||
#[https://dl.acm.org/citation.cfm?id=796590 Watrous (2000)] | #[https://dl.acm.org/citation.cfm?id=796590 Watrous (2000)] | ||
<div style='text-align: right;'>''contributed by Shraddha Singh''</div> | <div style='text-align: right;'>''contributed by Shraddha Singh''</div> | ||