This functionality is relevant in the context of Interactive Proof Systems (IPs). Verification of Quantum Computation refers to the general cryptographic and computational two-party or multi-party functionality in which a verifier interacts with one or more quantum provers to check the correctness of a claimed quantum computation or decision, without necessarily performing the computation themselves.

The verifier may be classical or quantum, and the prover is typically a quantum entity with the ability to carry out a computational task beyond the verifier’s capabilities. The goal is to ensure that, with high probability, a correct quantum computation is accepted and an incorrect one is rejected, under a well-defined completeness-soundness gap.

This functionality does not necessarily involve the delegation or outsourcing of computation, but rather focuses on verifying the correctness of a result, a central problem in the theory of quantum interactive proofs, quantum PCP, and complexity theory (e.g., QMA, QIP).

This specific instance is a naturally quantum functionality. However, the classical analogue of this functionality is the well-studied domain of interactive proofs (IP), where a computationally weak verifier interacts with a powerful prover to verify statements in complexity classes like NP or PSPACE. For example, the class IP = PSPACE captures what classical interactive proofs can verify. In NP, a single message (proof) is enough for verification.

In the quantum setting, the goal is similar, but the prover executes a quantum computation, and verifying it poses unique challenges due to quantum state inaccessibility, no-cloning, and measurement limitations.

This general functionality has many applications, such as:

• Theoretical Guarantees of Correctness: In quantum computing experiments or future quantum services, protocols may certify the correctness of outputs without requiring full trust in the quantum hardware.
• Post hoc Verification of Quantum Advantage: For claims of quantum advantage (e.g., in sampling tasks), verification protocols allow a classical verifier to check if a quantum computation truly outperformed classical systems.
• Certifying Solutions to Hard Problems: For problems in QMA, a verifier can check that a prover holds a quantum witness for a problem instance, which is of practical interest as well.

The main properties include: 

Completeness: A correct quantum computation is accepted with high probability

Soundness: An incorrect computation or cheating prover is rejected with high probability.

Verifier Capabilities: The verifier can be of different capabilities:

• Fully classical verifier [1]
• Constant-qubit quantum verifier [2]
• Quantum verifier with full quantum access: Standard QIP model [3]

Protocols are designed to minimise verifier power while preserving verifiability.

1. Mahadev, Urmila. “Classical verification of quantum computations.” In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 259-267. IEEE, 2018.
2. Broadbent, Anne. “How to verify a quantum computation.” arXiv preprint arXiv:1509.09180 (2015).
3. Vidick, Thomas, and John Watrous. “Quantum proofs.” Foundations and Trends® in Theoretical Computer Science 11, no. 1-2 (2016): 1-215.