Editing Verification of Universal Quantum Computation
The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then publish the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 1: | Line 1: | ||
==Functionality== | ==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. | 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. <br/>'''Tags:''' [[:Category: Quantum Functionality|Quantum Functionality]], [[Category: Quantum Functionality]] [[:Category:Universal Task|Universal Task]][[Category:Universal Task]] | ||
'''Tags:''' [[:Category: Quantum Functionality|Quantum Functionality]], [[Category: Quantum Functionality]] [[:Category:Universal Task|Universal Task]][[Category:Universal Task | |||
==Protocols== | ==Protocols== | ||
#Single-prover prepare-and-send: Verifier can only prepare and send | *Single prover protocols | ||
#[[Prepare-and-Send Verifiable Universal Blind Quantum Computation|Single-prover prepare-and-send]]: Verifier can only prepare and send states | |||
#[[Measurement-Only Verifiable Universal Blind Quantum Computation|Single-prover receive-and-measure]]: Verifier can only receive and measure states | |||
*Multi-prover protocols | |||
#Multi-prover entanglement-based: verifier is completely classical and the provers are entangled | |||
#Multi-prover entanglement-based: | |||
==Properties== | ==Properties== | ||
*'''[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 23: | 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). | ||
* '''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== | ==Further Information== | ||
*Review Papers | *Review Papers | ||
==References== | ==References== | ||
#[ | #[https://arxiv.org/abs/1709.06984 Gheorghiu et al (2018)] | ||
<div style='text-align: right;'>''contributed by Shraddha Singh''</div> | <div style='text-align: right;'>''contributed by Shraddha Singh''</div> |