Revision History for: Interactive Verification of Quantum Computation
- 2025-06-24 at 21:24 by JuliaM
Functionality Description
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).
Classical Analogues
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.
Real-world Use Cases
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.
Properties
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.
Further Information
No content has been added to this section, yet!
References
- Mahadev, Urmila. “Classical verification of quantum computations.” In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 259-267. IEEE, 2018.
- Broadbent, Anne. “How to verify a quantum computation.” arXiv preprint arXiv:1509.09180 (2015).
- Vidick, Thomas, and John Watrous. “Quantum proofs.” Foundations and Trends® in Theoretical Computer Science 11, no. 1-2 (2016): 1-215.
- 2025-05-15 at 17:03 by Mina Doosti
Functionality Description
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).
Protocols
No protocols implement this functionality yet.
Classical Analogues
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.
Real-world Use Cases
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.
Properties
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.
Further Information
No content has been added to this section, yet!
References
- Mahadev, Urmila. “Classical verification of quantum computations.” In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 259-267. IEEE, 2018.
- Broadbent, Anne. “How to verify a quantum computation.” arXiv preprint arXiv:1509.09180 (2015).
- Vidick, Thomas, and John Watrous. “Quantum proofs.” Foundations and Trends® in Theoretical Computer Science 11, no. 1-2 (2016): 1-215.