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

1. Single prover protocols
   1. Single-prover prepare-and-send: Verifier can only prepare and send states
   2. Single-prover receive-and-measure: Verifier can only receive and measure states
2. Multi-prover protocols
   1. Multi-prover entanglement-based: verifier is completely classical and the provers are entangled

Properties

• Complexity Classes

1. BQP is the class of problems which can be efficiently solved by quantum computers
2. BPP is the class of problems which can be efficiently solved by classical computers.
3. MA (Merlin-Arthur) is the class of problems whose solutions can be verified when given a proof setting called witness.
4. 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).
5. 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.

• 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

1. Gheorghiu et al (2018)

contributed by Shraddha Singh