Write, autoreview, editor, reviewer
3,125
edits
Verification of Universal Quantum Computation: Difference between revisions
Jump to navigation
Jump to search
Verification of Universal Quantum Computation (edit)
Revision as of 06:27, 11 June 2019
, 11 June 2019→Properties
| Line 15: | Line 15: | ||
#'''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). | ||
#Protocols 1.1, 1.2 are '''QPIP''' protocols and 2.1 is an MIP protocol. QPIP and MIP are classes of decision problems and can be decided by protocols 1.1, 1.2 and 2.1, respectively. | |||
* '''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? | * '''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? | ||