Interactive Proofs for Quantum Computation: Difference between revisions

From Quantum Protocol Zoo
Jump to navigation Jump to search
No edit summary
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 MA does not include BQP (problems that can be solved by a quantum computer), 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 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 MA is not entirely contained in BQP (problems that can be solved by a quantum computer), 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).

Revision as of 21:42, 17 June 2019

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 MA is not entirely contained in BQP (problems that can be solved by a quantum computer), 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).

Retrieved from "https://wiki.veriqloud.fr/index.php?title=Interactive_Proofs_for_Quantum_Computation&oldid=3300"