Write, autoreview, editor, reviewer
3,129
edits
Verification of Universal Quantum Computation: Difference between revisions
Verification of Universal Quantum Computation (edit)
Revision as of 04:53, 11 June 2019
, 11 June 2019→Properties
| Line 9: | Line 9: | ||
==Properties== | ==Properties== | ||
*[https://complexityzoo.uwaterloo.ca/Complexity_Zoo Complexity Classes] | |||
#'''BQP''' is the class of problems which can be efficiently solved by quantum computers | |||
#'''BPP''' is the class of problems which can be efficiently solved by classical computers. | |||
#'''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). | |||
*'''Correctness''' | *'''Correctness''' | ||
*'''Soundness''' | *'''Soundness''' | ||