Verification of Universal Quantum Computation
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
- Single prover protocols
- Single-prover prepare-and-send: Verifier can only prepare and send states
- 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
Properties
- 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).
- 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
- Review Papers
References
contributed by Shraddha Singh