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. [https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#bqp BQP] is the class of problems that can be solved by a quantum computer and [https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#bpp BPP] is the class of problems that can be solved by a classical computer. BPP is contained in BQP and hence, there are problems a quantum computer would solve that are intractable for a classical computer, to put it simply. Thus, if in future, an untrusted company claims to have built a quantum computer, how can the consumer be sure of the [https://people.eecs.berkeley.edu/~sanjamg/classes/cs276-fall14/scribe/lec09.pdf correctness] of the results when he/she (the consumer) cannot compare the results predicted by the proposed quantum computer? This problem is addressed by the functionality, 'verification of quantum computers'. Verification of universal quantum computation targets every computation that can be performed by a quantum computer.<br/><br/> | 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. [https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#bqp BQP] is the class of problems that can be solved by a quantum computer and [https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#bpp BPP] is the class of problems that can be solved by a classical computer. BPP is contained in BQP and hence, there are problems a quantum computer would solve that are intractable for a classical computer, to put it simply. Thus, if in future, an untrusted company claims to have built a quantum computer, how can the consumer be sure of the [https://people.eecs.berkeley.edu/~sanjamg/classes/cs276-fall14/scribe/lec09.pdf correctness] of the results when he/she (the consumer) cannot compare the results predicted by the proposed quantum computer? This problem is addressed by the functionality, 'verification of quantum computers'. Verification of universal quantum computation targets every computation that can be performed by a quantum computer.<br/><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 quantum states to delegate a BQP computation to the prover | #Single-prover prepare-and-send: Verifier can only prepare and send quantum states to delegate a BQP computation to the prover | ||
##[[Interactive Proofs for Quantum Computation|Quantum-authentication based verification]]: | ##[[Interactive Proofs for Quantum Computation|Quantum-authentication based verification]]: | ||
##Trap-based based verification: | ##Trap-based based verification: uses verifiable blind delegated quantum computation | ||
##Verification based on repeated runs | ##Verification based on repeated runs | ||
#Single-prover receive-and-measure: Verifier can only receive and measure quantum states | #Single-prover receive-and-measure: Verifier can only receive and measure quantum states | ||
Line 17: | Line 17: | ||
==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 24: | Line 23: | ||
#'''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. | ||
[[File:Suspected relationship between BQP and MA.png]] | |||
==Further Information== | ==Further Information== | ||
*Review Papers | *Review Papers | ||
# [https://arxiv.org/abs/1709.06984 Gheorghiu et al (2018)]: Major portion of this functionality file has been adapted from this review | # [https://arxiv.org/abs/1709.06984 Gheorghiu et al (2018)]: Major portion of this functionality file has been adapted from this review | ||
<div style='text-align: right;'>''contributed by Shraddha Singh''</div> | <div style='text-align: right;'>''contributed by Shraddha Singh''</div> |