verifier — Classical Verifier

Classical Verifier for Quantum Learning — §6 of Caro et al. (ITCS 2024).

Implements the verifier side of the interactive verification protocol for distributional agnostic quantum parity and Fourier-sparse learning.

Protocol overview (verifier’s role):

  1. Receive the prover’s message: a list \(L = \{s_1, \ldots, s_{|L|}\}\) of candidate heavy Fourier coefficient indices (and optionally estimated coefficient values).

  2. Validate list size: reject if \(|L|\) exceeds the Parseval bound.

  3. Independently estimate the Fourier coefficients \(\hat{\tilde\phi}(s)\) for each \(s \in L\) using the verifier’s own classical random example access (Lemma 1 / Hoeffding bound).

  4. Check accumulated Fourier weight: verify that

    \[\sum_{s \in L} \hat{\xi}(s)^2 \geq \tau_{\text{accept}}\]

    where \(\tau_{\text{accept}}\) depends on the L2-bracket promise (Definition 14, \(\mathbb{E}[\phi^2] \in [a^2, b^2]\)). The protocol also assumes the granularity promise (Definition 11 in the functional case, Definition 13 in the distributional case: \(\hat\phi(s) \neq 0 \Rightarrow |\hat\phi(s)| \geq \vartheta\)), which is a separate constraint from Definition 14 — Def 14 brackets total Fourier mass while Def 11/13 forbids small-but-nonzero coefficients. For the functional case (\(a = b = 1\)), the acceptance threshold is \(1 - \varepsilon^2/8\); for the distributional case it is \(a^2 - \varepsilon^2/8\).

  5. Output hypothesis:

    • Parity learning (Theorems 7/8/11/12): \(s_{\text{out}} = \arg\max_{s \in L} |\hat{\xi}(s)|\), hypothesis \(h(x) = s_{\text{out}} \cdot x\).

    • Fourier-sparse learning (Theorems 9/10/14/15): pick \(k\) heaviest from \(L\), build randomized hypothesis per Lemma 14.

Soundness is information-theoretic: the verifier’s checks guarantee correctness regardless of the prover’s strategy. In particular, if the verifier accepts, the output hypothesis satisfies the agnostic learning guarantee with high probability — even against a computationally unbounded dishonest prover.

Copy complexity (verifier): \(O(b^4 \log(1/\delta\vartheta^2) / (\varepsilon^4 \vartheta^4))\) classical random examples (Theorem 12).

References

  • Caro et al., “Classical Verification of Quantum Learning”, ITCS 2024. §6.1 (Theorems 7–10), §6.2 (noisy), §6.3 (Theorems 11–16).

  • Definitions 13, 14 for distribution class promises.

class ql.verifier.VerificationOutcome(*values)[source]

Bases: Enum

Outcome of the verification protocol.

ACCEPT = 'accept'
REJECT_LIST_TOO_LARGE = 'reject_list_too_large'
REJECT_INSUFFICIENT_WEIGHT = 'reject_insufficient_weight'
class ql.verifier.HypothesisType(*values)[source]

Bases: Enum

Type of hypothesis output by the verifier.

PARITY = 'parity'
FOURIER_SPARSE = 'fourier_sparse'
class ql.verifier.ParityHypothesis(s: int, n: int, estimated_coefficient: float)[source]

Bases: object

Parity hypothesis \(h(x) = s \cdot x \mod 2\).

s

The parity vector, as an integer in \(\{0, \ldots, 2^n - 1\}\).

Type:

int

n

Number of input bits.

Type:

int

estimated_coefficient

The verifier’s estimate of \(\hat{\tilde\phi}(s)\).

Type:

float

s: int
n: int
estimated_coefficient: float
evaluate(x: int) → int[source]

Evaluate \(h(x) = s \cdot x \mod 2\).

evaluate_batch(xs: numpy.ndarray) → numpy.ndarray[source]

Evaluate the hypothesis on a batch of inputs.

class ql.verifier.FourierSparseHypothesis(coefficients: dict[int, float], n: int)[source]

Bases: object

Randomised Fourier-sparse hypothesis per Lemma 14.

Given estimated coefficients \(\tilde\phi(s_\ell)\) for \(\ell = 1, \ldots, k\), defines \(g(x) = \sum_\ell \tilde\phi(s_\ell) \chi_{s_\ell}(x)\) and the randomised hypothesis

\[h(x) = 1 \text{ with probability } p(x) = \frac{(1 - g(x))^2}{2(1 + g(x)^2)}\]
coefficients

Maps each \(s_\ell\) to its estimated coefficient.

Type:

dict[int, float]

n

Number of input bits.

Type:

int

coefficients: dict[int, float]
n: int
g(x: int) → float[source]

Evaluate \(g(x) = \sum_\ell \hat\xi(s_\ell) \chi_{s_\ell}(x)\).

evaluate(x: int, rng: numpy.random.Generator | None = None) → int[source]

Evaluate the randomised hypothesis at x.

evaluate_batch(xs: numpy.ndarray, rng: numpy.random.Generator | None = None) → numpy.ndarray[source]

Evaluate the hypothesis on a batch of inputs.

class ql.verifier.VerificationResult(outcome: VerificationOutcome, hypothesis: ParityHypothesis | FourierSparseHypothesis | None, hypothesis_type: HypothesisType | None, verifier_estimates: dict[int, float], accumulated_weight: float, acceptance_threshold: float, list_received: list[int], list_size_bound: int, n: int, epsilon: float, num_classical_samples: int)[source]

Bases: object

Complete result of the classical verification protocol.

outcome

Whether the verifier accepted or rejected (and why).

Type:

VerificationOutcome

hypothesis

The output hypothesis (None if rejected).

Type:

ParityHypothesis | FourierSparseHypothesis | None

hypothesis_type

The type of hypothesis produced.

Type:

HypothesisType | None

verifier_estimates

The verifier’s independent Fourier coefficient estimates \(\hat\xi(s)\) for each \(s \in L\).

Type:

dict[int, float]

accumulated_weight

\(\sum_{s \in L} \hat\xi(s)^2\).

Type:

float

acceptance_threshold

The threshold that accumulated_weight was compared against.

Type:

float

list_received

The list \(L\) received from the prover.

Type:

list[int]

list_size_bound

The Parseval-derived bound on \(|L|\).

Type:

int

n

Number of input bits.

Type:

int

epsilon

Accuracy parameter.

Type:

float

num_classical_samples

Number of classical samples the verifier consumed.

Type:

int

outcome: VerificationOutcome
hypothesis: ParityHypothesis | FourierSparseHypothesis | None
hypothesis_type: HypothesisType | None
verifier_estimates: dict[int, float]
accumulated_weight: float
acceptance_threshold: float
list_received: list[int]
list_size_bound: int
n: int
epsilon: float
num_classical_samples: int
property accepted: bool
summary() → str[source]

Human-readable summary.

class ql.verifier.MoSVerifier(mos_state: MoSState, seed: int | None = None)[source]

Bases: object

Classical verifier for the interactive quantum learning protocol.

Implements the verifier side of the verification protocols from §6 of Caro et al. (ITCS 2024). The verifier has access to classical random examples from the distribution \(D\) (obtained by computational-basis measurement of \(\rho_D\), per Lemma 1) and interacts with a (potentially dishonest) quantum prover.

The verifier’s checks are sufficient to guarantee:

  • Completeness (Theorems 8/12): when interacting with the honest prover, the verifier accepts and outputs a good hypothesis with probability \(\geq 1 - \delta\).

  • Soundness (information-theoretic): even against a computationally unbounded dishonest prover, if the verifier accepts, the output hypothesis satisfies the agnostic learning guarantee.

Parameters:

  • mos_state (MoSState) – The MoS state encoding the distribution \(D\). The verifier uses this only to draw classical random examples via computational-basis measurement (MoSState.sample_classical_batch()).

  • seed (int, optional) – Random seed for reproducibility.

Notes

In a real deployment, the verifier would have access only to a classical random example oracle — not to the full MoSState. Here we pass the MoSState to enable classical sampling (Lemma 1), which is the verifier’s only use of it.

_rng: numpy.random.Generator
verify_parity(prover_message: ProverMessage, epsilon: float, delta: float = 0.1, theta: float | None = None, a_sq: float = 1.0, b_sq: float = 1.0, num_samples: int | None = None) → VerificationResult[source]

Verify agnostic parity learning (Theorems 7/8/11/12).

Implements the verifier’s protocol for 1-agnostic proper parity verification.

Protocol steps (Theorems 8/12):

  1. Receive \(L\) from prover; reject if \(|L| > 64b^2/\vartheta^2\).

  2. Estimate \(\hat{\tilde\phi}(s)\) for each \(s \in L\) using classical random examples.

  3. Check \(\sum_{s \in L} \hat\xi(s)^2 \geq a^2 - \varepsilon^2/8\).

  4. Output \(h(x) = s_{\text{out}} \cdot x\) where \(s_{\text{out}} = \arg\max_{s \in L} |\hat\xi(s)|\).

Parameters:

  • prover_message (ProverMessage) – The message received from the (potentially dishonest) prover.

  • epsilon (float) – Accuracy parameter \(\varepsilon \in (0, 1)\).

  • delta (float) – Confidence parameter \(\delta \in (0, 1)\).

  • theta (float, optional) – Fourier resolution threshold \(\vartheta\). Defaults to epsilon.

  • a_sq (float) – Lower bound on \(\mathbb{E}[\tilde\phi(x)^2]\) (Definition 14). For the functional case, \(a^2 = 1\). For the distributional case with noise rate \(\eta\), \(a^2 = (1 - 2\eta)^2\).

  • b_sq (float) – Upper bound on \(\mathbb{E}[\tilde\phi(x)^2]\) (Definition 14). For the functional case, \(b^2 = 1\).

  • num_samples (int, optional) – Override the number of classical samples. If not provided, computed from the Hoeffding bound.

Return type:

VerificationResult

verify_fourier_sparse(prover_message: ProverMessage, epsilon: float, k: int, delta: float = 0.1, theta: float | None = None, a_sq: float = 1.0, b_sq: float = 1.0, num_samples: int | None = None) → VerificationResult[source]

Verify agnostic Fourier-sparse learning (Theorems 9/10/14/15).

Implements the verifier’s protocol for 2-agnostic improper Fourier-\(k\)-sparse verification.

Protocol steps (Theorems 10/15):

  1. Receive \(L\) from prover; reject if \(|L| > 64b^2/\vartheta^2\).

  2. Estimate \(\hat{\tilde\phi}(s)\) for each \(s \in L\).

  3. Check \(\sum_{s \in L} \hat\xi(s)^2 \geq a^2 - \varepsilon^2/(128k^2)\).

  4. Pick \(k\) heaviest from \(L\), build randomised hypothesis per Lemma 14.

Parameters:

  • prover_message (ProverMessage) – The message received from the prover.

  • epsilon (float) – Accuracy parameter.

  • k (int) – Fourier sparsity parameter (number of terms).

  • delta (float) – Confidence parameter.

  • theta (float, optional) – Fourier resolution threshold. Defaults to epsilon.

  • a_sq (float) – Lower bound on \(\mathbb{E}[\tilde\phi^2]\).

  • b_sq (float) – Upper bound on \(\mathbb{E}[\tilde\phi^2]\).

  • num_samples (int, optional) – Override the number of classical samples.

Return type:

VerificationResult

_verify_core(prover_message: ProverMessage, epsilon: float, delta: float, theta: float, a_sq: float, b_sq: float, hypothesis_type: HypothesisType, k: int | None, num_samples: int | None) → VerificationResult[source]

Core verification protocol shared by parity and Fourier-sparse modes.

Follows the structure of Theorems 8/10/12/15 in §6.

_estimate_coefficients_independently(L: list[int], num_samples: int) → dict[int, float][source]

Estimate Fourier coefficients using the verifier’s own classical random examples — independent of the prover.

For each \(s \in L\):

\[\hat\xi(s) = \frac{1}{m} \sum_{i=1}^{m} (1 - 2y_i)(-1)^{s \cdot x_i}\]

where \((x_i, y_i) \sim D\) are i.i.d. classical samples.

This independence is the foundation of information-theoretic soundness: the verifier’s estimates are uncontaminated by anything the prover does.

Parameters:

  • L (list[int]) – Frequency indices to estimate.

  • num_samples (int) – Number of classical samples to draw.

Returns:

estimates – The verifier’s independent estimates.

Return type:

dict[int, float]

_build_parity_hypothesis(L: list[int], verifier_estimates: dict[int, float]) → ParityHypothesis[source]

Build parity hypothesis \(h(x) = s_{\text{out}} \cdot x\) where \(s_{\text{out}} = \arg\max_{s \in L} |\hat\xi(s)|\).

This is Step 4 of Theorems 7/8/11/12.

_build_fourier_sparse_hypothesis(L: list[int], verifier_estimates: dict[int, float], k: int) → FourierSparseHypothesis[source]

Build Fourier-sparse randomised hypothesis per Lemma 14.

Pick \(k\) heaviest from \(L\) (by \(|\hat\xi(s)|\)), construct \(g(x) = \sum_{\ell=1}^{k} \hat\xi(s_\ell) \chi_{s_\ell}(x)\).

This is Step 4 of Theorems 9/10/14/15.

run_full_protocol(prover_message: ProverMessage, mode: str = 'parity', epsilon: float | None = None, delta: float = 0.1, theta: float | None = None, k: int = 1, a_sq: float = 1.0, b_sq: float = 1.0, num_samples: int | None = None) → VerificationResult[source]

Run the full verification given a prover message.

Convenience wrapper that dispatches to verify_parity() or verify_fourier_sparse().

Parameters:

  • prover_message (ProverMessage) – The prover’s message.

  • mode (str) – "parity" or "fourier_sparse".

  • epsilon (float, optional) – Accuracy parameter. Defaults to the prover’s epsilon.

  • delta (float) – Confidence parameter.

  • theta (float, optional) – Fourier resolution threshold.

  • k (int) – Fourier sparsity (only used in "fourier_sparse" mode).

  • a_sq (float) – Lower bound on \(\mathbb{E}[\tilde\phi^2]\).

  • b_sq (float) – Upper bound on \(\mathbb{E}[\tilde\phi^2]\).

  • num_samples (int, optional) – Override classical sample count.

Return type:

VerificationResult