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