Accreditation Against Limited Adversarial Noise

1. Problem Statement

Quantum verification is essential for establishing trust in quantum computations, particularly in the Noisy Intermediate-Scale Quantum (NISQ) era. Existing verification methods generally fall into two categories:

• Cryptographic Verification: Relies on adversarial models (e.g., Delegated Quantum Computation) where a malicious prover (Bob) attempts to trick a verifier (Alice). These often assume no errors in specific components (like state preparation or measurement) or rely on unproven cryptographic hardness assumptions.
• Accreditation (Physics-Based): Relies on physical assumptions about noise, specifically that errors are Independent and Identically Distributed (IID) and modeled by Completely Positive Trace-Preserving (CPTP) maps. While experimentally implementable, these protocols fail if the noise is "adversarial" (i.e., if the error depends on the specific circuit being run or correlates across executions).

The Core Gap: There is a lack of protocols that can verify quantum computations under an adversarial noise model while retaining the efficiency and near-term suitability of physics-based accreditation. Previous accreditation protocols could not handle adversarial noise because their assumptions (IID errors) clashed with the worst-case nature of adversarial models.

2. Methodology

The author proposes a hybrid approach that upgrades a pre-existing accreditation protocol (from Ferracin et al., 2021) to function under a limited adversarial model. This is achieved through a new problem setting involving three parties and specific constraints on the adversary.

A. The Problem Setting (Adapted Cryptographic Model)

The paper introduces a three-party framework:

1. Alice: The client who wants to verify a specific quantum computation (sampBQP). She has polynomial classical computational power.
2. Bob: The adversary representing the noise. He is computationally unbounded and aims to trick Alice into accepting incorrect results.
3. Robert: An impartial referee who actually executes the quantum circuits. He enforces the rules of the protocol and ensures Alice and Bob adhere to constraints.

Key Constraints on Bob (The "Limited" Adversary):
To make the problem solvable, the protocol imposes two physical-motivated limitations on Bob, enforced by Robert:

1. Redaction of Single-Qubit Gates: When Bob receives the list of circuits to execute, the specific single-qubit gates (e.g., whether it is an $X$ or $Z$ gate) are "redacted" (hidden). He only sees the circuit structure (where gates occur) but not their specific operators. This models the physical reality that single-qubit gates typically experience Gate-Independent (GI) error.
2. Probabilistic Similarity of CPTP Lists: Bob must choose error maps (CPTP lists) from a Set of Probabilistically Similar CPTP Lists ($SPSCL_\beta$). This means that for a batch of circuits executed in quick succession, the probability of error induced by Bob cannot vary wildly; it must remain within a bounded interval $[(1-\beta)P_0, (1+\beta)P_0]$. This reflects the experimental observation that hardware noise is relatively stable over short timeframes.

B. Protocol Mechanics

The upgraded protocol utilizes Trap Circuits and Target Circuits:

• Trap Circuits: Designed to detect errors. If no error occurs, they output a specific known value $m$. If error occurs, they output something else with probability at least $k$.
• Target Circuits: The actual computation Alice wants to perform.
• Redaction & Encryption:
  • Single-qubit gates in both trap and target circuits are redacted before being shown to Bob.
  • Algorithm 2 is introduced to encrypt the measurement outcomes of the circuits using a random key (One-Time Pad style). This prevents Bob from knowing the "trap" status based on the output or adapting his error strategy based on previous results.
• Execution Flow (Protocol 3):
  1. Alice generates a set of circuits ($N_{trap}$ traps + 1 target) using classical algorithms $P'_{trap}$ and $P'_{targ}$.
  2. These are sent to Robert.
  3. Bob selects a valid $SPSCL_\beta$ and specific CPTP error maps for each execution.
  4. Robert executes all circuits (in random order) applying Bob's chosen errors.
  5. Alice checks the outcomes of the trap circuits. If the fraction of incorrect trap outputs is low, she accepts the target result with a calculated bound on the error.

3. Key Contributions

1. Adversarial Accreditation Protocol: The first accreditation protocol that functions under an adversarial noise model without sacrificing the efficiency of near-term protocols. It bridges the gap between cryptographic verification and physics-based accreditation.
2. Limited Adversarial Model: The introduction of a novel problem setting where the adversary (Bob) is constrained by physical realities (Gate-Independence and temporal stability of error rates) rather than being all-powerful.
3. Redaction and Encryption Mechanism: The development of a method to hide single-qubit gate identities and encrypt measurement outcomes, ensuring that the adversary cannot distinguish between trap and target circuits or adapt errors based on previous outcomes.
4. Theoretical Guarantees:
   • Lemma 3 & 4: Statistical proofs showing that if the error probability is bounded within an $SPSCL_\beta$, the average error of the traps provides a valid upper bound for the error of the target circuit.
   • Theorem 1: Proves that Alice can obtain a bound on the Ideal-Actual Variation Distance ($\nu$) of the target circuit execution with arbitrary confidence ($\alpha$) and accuracy ($\theta$), even in the presence of limited adversarial noise.

4. Results

• Efficiency: The protocol does not require lengthening the circuit, adding extra two-qubit gates, or using ancilla qubits. It retains the resource efficiency of the original Ferracin et al. (2021) protocol.
• Robustness: The protocol successfully bounds the error of the target computation. The bound is given by:
  $$\nu[\tilde{C}_{targ}] \leq \frac{1+\beta}{k(1-\beta)}(\bar{v} + \theta)$$
  Where $\bar{v}$ is the observed fraction of failed traps, $k$ is the trap detection probability, and $\beta$ represents the allowed variation in error probability.
• Validity: The protocol works for any $sampBQP$ computation and remains valid in all scenarios where the previous IID-based protocols were valid, but extends to scenarios with limited adversarial noise.

5. Significance

• Trust in NISQ Devices: This work provides a rigorous method to quantify the quality of quantum outputs in the NISQ era, moving beyond simple "pass/fail" verification to providing a quantitative bound on error.
• Bridging Theory and Practice: It resolves the conflict between the "worst-case" assumptions of cryptography and the "average-case" assumptions of physics. By acknowledging that real-world noise has limits (stability and gate-independence), it allows for stronger security guarantees without requiring unrealistic hardware perfection.
• Scalability: Since the protocol does not increase circuit depth or qubit count, it is immediately applicable to current and near-future quantum hardware.
• Future Directions: The paper opens the door to relaxing the constraints on Bob further (e.g., allowing weak gate-dependence) as hardware improves, potentially leading to even more robust verification methods.

In summary, Andrew Jackson presents a significant advancement in quantum verification by creating an accreditation protocol that is robust against limited adversarial noise, ensuring that quantum computations can be trusted even when the noise is not perfectly random or independent, provided it adheres to physically motivated constraints.