Verification of Universal Quantum Computation: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| Line 5: | Line 5: | ||
==Protocols== | ==Protocols== | ||
*'''Verification for universal protocols''' | *'''Verification for universal protocols''' | ||
#Single-prover prepare-and-send: Verifier can only prepare and send states | #Single-prover prepare-and-send: Verifier can only prepare and send quantum states | ||
##Quantum-authentication based verification | ##Quantum-authentication based verification | ||
##Trap-based based verification: uses blind delegated quantum computation | ##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 states | #Single-prover receive-and-measure: Verifier can only receive and measure quantum states | ||
##Measurement only verification: uses blind delegated quantum computation | ##Measurement only verification: uses blind delegated quantum computation | ||
##Post-hoc verification: Non-interactive (requires only single round of back and forth communication) | ##Post-hoc verification: Non-interactive (requires only single round of back and forth communication) | ||
#Multi-prover entanglement-based: | #Multi-prover entanglement-based: Verifier is completely classical and the provers are entangled | ||
##Verification based on CHSH rigidity | ##Verification based on CHSH rigidity | ||
##Verification based on self-testing graphs | ##Verification based on self-testing graphs | ||
Revision as of 23:17, 11 June 2019
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
Tags: Quantum Functionality, Universal Task
Protocols
- Verification for universal protocols
- Single-prover prepare-and-send: Verifier can only prepare and send quantum states
- Quantum-authentication based verification
- Trap-based based verification: uses blind delegated quantum computation
- Verification based on repeated runs
- Single-prover receive-and-measure: Verifier can only receive and measure quantum states
- Measurement only verification: uses blind delegated quantum computation
- Post-hoc verification: Non-interactive (requires only single round of back and forth communication)
- Multi-prover entanglement-based: Verifier is completely classical and the provers are entangled
- Verification based on CHSH rigidity
- Verification based on self-testing graphs
- Post-hoc verification
- Classical Verification of Quantum Computation
- Verification for sub-universal protocols
- Verification of NP-complete problems
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?
- BQP is the class of problems which can be efficiently solved by quantum computers
- BPP is the class of problems which can be efficiently solved by classical computers.
- 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).
- 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
- Review Papers
contributed by Shraddha Singh