Abstract
As quantum computing transitions toward cloud-based service models, the ability to verify the integrity of remote quantum computations becomes paramount. Traditional verification protocols often require explicit knowledge of the quantum circuit's internal gate decomposition. This paper addresses the Quantum Black-Box Computation (QBBC) problem, where a verifier must validate the output of a proprietary or unknown quantum device. We present two interactive proof systems: one for a verifier with limited quantum capabilities and another for a fully classical verifier. By leveraging a novel "information versus disturbance" lemma and the Learning With Errors (LWE) assumption, these protocols allow a verifier to reliably distinguish between a functional quantum device and a malicious prover using only classical knowledge of the target function's input-output behavior.
1. Introduction
The emergence of quantum-computing-as-a-service (QCaaS) from providers like IBM and Google has highlighted a critical verification gap. While existing "verifiable quantum computation" (VQC) methods are robust, they typically assume the user knows the exact sequence of gates being executed. In practice, however, a user may interact with a "black box"—a specialized hardware component designed for a specific task (e.g., chemical simulation or factoring) whose internal architecture is proprietary or unknown. This paper formalizes this challenge as the QBBC problem, seeking to determine if a device $D$ correctly computes a function $F$ without requiring the verifier to understand the device's internal mechanics.
2. The Quantum Black-Box Computation (QBBC) Problem
The QBBC problem is framed as a promise problem. Given a function $F$ and a quantum device $D$, the verifier must distinguish between two cases:
- YES Instance: The device $D$ computes $F$ with high probability (accuracy $a$).
- NO Instance: The device $D$ is significantly inaccurate or malicious.
The goal is to achieve this verification using minimal interaction and, ideally, only classical communication.
3. Methodology
The authors propose two distinct interactive proof systems to solve the QBBC problem.
3.1 Limited Quantum Verifier
The first protocol involves a verifier capable of preparing and measuring a small number of qubits. This approach relies on a newly developed Information versus Disturbance Lemma. The core logic is that if a malicious prover attempts to "cheat" by classically querying the function $F$, they must first measure the quantum state provided by the verifier to obtain a valid input. This measurement inevitably collapses the quantum superposition, creating a detectable "disturbance." The verifier can then detect this interference during a subsequent "uncomputing" step, effectively catching the prover in the act of unauthorized measurement.
3.2 Fully Classical Verifier
To remove the requirement for quantum hardware on the verifier's side, the second protocol utilizes the Learning With Errors (LWE) assumption. By employing Extended Noisy Trapdoor Claw-Free (eNTCF) functions, the verifier can cryptographically delegate quantum tasks to the prover. This primitive allows a classical user to "force" a quantum prover to prepare specific states and perform measurements honestly, effectively bridging the gap between classical communication and quantum execution.
4. Key Insights
- Global vs. Local Verification: Unlike previous BQP-verification methods that check individual gates, this approach evaluates the global behavior of the unitary operation. This makes it uniquely suited for specialized, non-universal hardware.
- Information vs. Disturbance: The protocol formalizes the trade-off between a prover's ability to gain information about a secret input and the resulting noise introduced into the quantum system.
- ROM vs. QROM Separation: A significant cryptographic contribution of this work is the formal separation between the Random Oracle Model (ROM) and the Quantum Random Oracle Model (QROM) under the standard LWE assumption. This resolves a long-standing question in the field without relying on non-standard timing assumptions.
5. Results and Performance
The proposed protocols demonstrate high efficiency and theoretical rigor:
- Interaction: Both protocols are efficient, requiring only two rounds of interaction.
- Query Complexity: The prover makes at most two quantum queries to the device $D$, while the verifier requires only a single classical query to validate the output.
- Soundness and Completeness: For the quantum verifier, the protocol achieves completeness of $(1+a)/2$ and a soundness error of approximately $31/32$ (assuming accuracy $a > 15/16$). The classical verifier (under LWE) maintains a functional gap for any constants $0 < b < a \le 1$.
6. Discussion and Future Work
While the paper establishes a theoretical foundation for black-box verification, several avenues for future research remain. The current quantum verifier protocol requires a high baseline accuracy ($a > 15/16$), which may be challenging for current Noisy Intermediate-Scale Quantum (NISQ) devices without significant repetition. Additionally, while the classical verifier relies on the widely accepted LWE assumption, exploring whether QBBC verification can be achieved unconditionally or under different cryptographic primitives remains an open question. Future work should also focus on the practical implementation of these protocols on existing noisy hardware to assess their robustness in real-world environments.
Summary updated