Verification of Universal Quantum Computation: Difference between revisions

From Quantum Protocol Zoo
Jump to navigation Jump to search
No edit summary
Line 14: Line 14:
#'''MA (Merlin-Arthur)''' is the class of problems whose solutions can be verified when given a proof setting called [[witness]].  
#'''MA (Merlin-Arthur)''' is the class of problems whose solutions can be verified when given a proof setting called [[witness]].  
#'''IP (interactive-proof system)''' is a generalization of MA, which involves back and forth communication between a verifier (a BPP machine) and prover (has unbounded computational power).
#'''IP (interactive-proof system)''' is a generalization of MA, which involves back and forth communication between a verifier (a BPP machine) and prover (has unbounded computational power).
 
* '''Problem 1 (Verifiability of BQP computations)''' Does every problem in BQP admit an interactive-proof system in which the prover is restricted to BQP computations?
*'''Correctness'''
*'''Soundness'''


==Further Information==   
==Further Information==   

Revision as of 05:22, 11 June 2019

Functionality

Quantum Computers perform task which are intractable for classical computers. The basic question here would be, "How should one verify the result of a quantum computer? This task is known as quantum verification or verification of quantum computation.
Tags: Quantum Functionality, Universal Task

Protocols

  1. Single-prover prepare-and-send
  2. Single-prover receive-and-measure
  3. Multi-prover entanglement-based

Properties

  1. BQP is the class of problems which can be efficiently solved by quantum computers
  2. BPP is the class of problems which can be efficiently solved by classical computers.
  3. MA (Merlin-Arthur) is the class of problems whose solutions can be verified when given a proof setting called witness.
  4. IP (interactive-proof system) is a generalization of MA, which involves back and forth communication between a verifier (a BPP machine) and prover (has unbounded computational power).
  • Problem 1 (Verifiability of BQP computations) Does every problem in BQP admit an interactive-proof system in which the prover is restricted to BQP computations?

Further Information

  • Review Papers

References

  1. Gheorghiu et al (2018)
contributed by Shraddha Singh
Retrieved from "https://wiki.veriqloud.fr/index.php?title=Verification_of_Universal_Quantum_Computation&oldid=3138"