Editing Verification of Universal Quantum Computation

Jump to navigation Jump to search
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

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<br/>
'''Tags:'''  [[:Category: Quantum Functionality|Quantum Functionality]], [[Category: Quantum Functionality]] [[:Category:Universal Task|Universal Task]][[Category:Universal Task]], [[Classical Verification of Universal Quantum Computation]], [[Verification of Sub-Universal Quantum Computation]], [[Verification of NP-complete problems]]
'''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
*'''Verification for universal protocols'''
##[[Interactive Proofs for Quantum Computation|Quantum-authentication based verification]]: Protocols use schemes for [[Authentication of Quantum Messages|authentication of quantum messages]] to run interactive proofs.
#Single-prover prepare-and-send: Verifier can only prepare and send quantum states
##Trap-based based verification: Protocol uses [[Prepare-and-Send Universal Blind Quantum Computation|blind delegated quantum computation]]
##Quantum-authentication based verification
##Trap-based based verification: uses 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 15: Line 16:
##Verification based on self-testing graphs
##Verification based on self-testing graphs
##Post-hoc verification
##Post-hoc verification
#Classical Verification of Quantum Computation
*'''Verification for sub-universal protocols'''
*[[Verification of NP-complete problems]]


==Properties==
==Properties==
[[File:Suspected relationship between BQP and MA.png|right|thumb|700px|Figure 1:Suspected relationship between BQP and MA]]
*'''Problem Definition (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 26: Line 31:


==Further Information==   
==Further Information==   
This problem remained unsolved for a completely classical client until Urmila Mahadev's protocol for classical verification of quantum protocols in 2018 (See Tags). The problem was formally addressed by Gottesman in 2004, and then promoted by Aaronson in 2007 [[Verification of Universal Quantum Computation#References||(1)]]. Emphasized by Vazirani later in 2007 from a philosophical point of view [[Verification of Universal Quantum Computation#References||(2)]], he raised the question, 'Is quantum mechanics a falsifiable theory?'
 
*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 are adapted from this review   
==References==
#[http://www.scottaaronson.com/blog/?p=284 The Aaronson $25.00 prize]
#[http://users.cms.caltech.edu/~schulman/Workshops/CS-Lens-2/cs-lens-2.html Vazirani (2007)]


<div style='text-align: right;'>''contributed by Shraddha Singh''</div>
<div style='text-align: right;'>''contributed by Shraddha Singh''</div>
Please note that all contributions to Quantum Protocol Zoo may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see Quantum Protocol Zoo:Copyrights for details). Do not submit copyrighted work without permission!

To protect the wiki against automated edit spam, we kindly ask you to solve the following CAPTCHA:

Cancel Editing help (opens in new window)
Retrieved from "https://wiki.veriqloud.fr/index.php?title=Verification_of_Universal_Quantum_Computation"