prover — Honest Quantum Prover

Honest Quantum Prover for Classical Verification of Quantum Learning.

Implements the prover side of the interactive verification protocol from Caro et al. (ITCS 2024), Theorems 8, 10, 12, and 15.

Protocol overview (prover’s role):

1. Quantum Fourier Sampling (Theorem 5): Given copies of the MoS state \(\rho_D\), apply \(H^{\otimes(n+1)}\), measure, post-select on the label qubit being 1. Each accepted shot yields a sample \(s \in \{0,1\}^n\) from the distribution

   \[\Pr[s \mid b{=}1] = \frac{1 - \mathbb{E}[\tilde\phi_{\text{eff}}(x)^2]}{2^n} + \hat{\tilde\phi}_{\text{eff}}(s)^2\]

2. Empirical spectrum approximation (Corollary 5 via Lemma 3 / DKW): From \(m\) post-selected QFS samples, build the empirical distribution \(\tilde{q}_m\) over \(\{0,1\}^n\). By DKW, \(m = O(\log(1/\delta)/\varepsilon^4)\) samples suffice for \(\|\tilde{q}_m - q\|_\infty \leq \varepsilon^2/8\) with probability \(\geq 1 - \delta/2\).

3. Heavy coefficient extraction: Identify the list

   \[L = \{s \in \{0,1\}^n : \tilde{q}_m(s,1) \geq \varepsilon^2/4\}\]

   By the analysis in Corollary 5:

   • If \(|\hat{\tilde\phi}(s)| \geq \varepsilon\), then \(s \in L\).

   • If \(s \in L\), then \(|\hat{\tilde\phi}(s)| \geq \varepsilon/4\).

4. Fourier coefficient estimation (optional): For each \(s \in L\), estimate \(\hat{\tilde\phi}(s)\) from classical samples of \(D\) (obtained by computational-basis measurement of \(\rho_D\), per Lemma 1).

5. Send \(L\) (and optionally the estimates) to the verifier.

The prover is honest: it follows the protocol faithfully. Soundness holds against any prover — the verifier’s checks ensure correctness regardless.

Copy complexity: The prover uses \(O(\log(1/\delta\varepsilon^2)/\varepsilon^4)\) copies of \(\rho_D\) for QFS (Corollary 5), plus \(O(\log(1/\delta\varepsilon^2)/\varepsilon^4)\) copies for classical estimation (via computational-basis measurement).

References

• Caro et al., “Classical Verification of Quantum Learning”, ITCS 2024. §5.1 (Corollary 5), §6 (Theorems 7–15).

• Lemma 3 (DKW-based empirical approximation).

class ql.prover.SpectrumApproximation(entries: dict[int, float], threshold: float, n: int, num_qfs_samples: int, total_qfs_shots: int)

Bases: object

Succinct approximation to the Fourier spectrum (Corollary 5).

entries

Sparse representation: maps frequency index \(s\) to the estimated squared-coefficient-related quantity \(\tilde{q}_m(s)\). Only entries above the extraction threshold are stored.

Type:

dict[int, float]

threshold

The extraction threshold used (typically \(\varepsilon^2/4\)).

Type:

float

n

Number of input bits.

Type:

int

num_qfs_samples

Number of post-selected QFS samples used to build the empirical distribution.

Type:

int

total_qfs_shots

Total QFS shots consumed (before post-selection).

Type:

int

entries: dict[int, float]

threshold: float

n: int

num_qfs_samples: int

total_qfs_shots: int

class ql.prover.ProverMessage(L: list[int], estimates: dict[int, float], n: int, epsilon: float, theta: float, spectrum_approx: SpectrumApproximation, qfs_result: QFSResult, num_classical_samples: int)

Bases: object

The message sent from the honest prover to the classical verifier.

This implements the communication in Step 2 of the verification protocols (Theorems 7–15): a list \(L\) of candidate heavy Fourier coefficient indices, optionally with estimated coefficient values.

L

List of frequency indices \(s\) identified as having non-negligible Fourier weight. Sorted by estimated weight (descending).

Type:

list[int]

estimates

For each \(s \in L\), an estimate of \(\hat{\tilde\phi}(s)\) obtained from classical samples. Empty if estimate_coefficients=False was used.

Type:

dict[int, float]

n

Number of input bits.

Type:

int

epsilon

Accuracy parameter used by the prover.

Type:

float

theta

Fourier coefficient resolution threshold \(\vartheta\).

Type:

float

spectrum_approx

The intermediate Fourier spectrum approximation (for diagnostics).

Type:

SpectrumApproximation

qfs_result

Raw QFS result (for diagnostics / post-hoc analysis).

Type:

QFSResult

num_classical_samples

Number of classical samples used for coefficient estimation.

Type:

int

L: list[int]

estimates: dict[int, float]

n: int

epsilon: float

theta: float

spectrum_approx: SpectrumApproximation

qfs_result: QFSResult

num_classical_samples: int

property list_size: int

Number of candidate heavy coefficients.

property total_copies_used: int

Total MoS copies consumed (QFS + classical estimation).

summary() → str

Human-readable summary of the prover’s message.

class ql.prover.MoSProver(mos_state: MoSState, seed: int | None = None, noise_model: object | None = None)

Bases: object

Honest quantum prover for the verification protocol.

Follows the prover side of Theorems 8/10/12/15: uses MoS copies for Quantum Fourier Sampling, builds a succinct Fourier spectrum approximation, extracts heavy coefficients, and optionally estimates their values from classical samples.

Parameters:

• mos_state (MoSState) – The MoS state to work with. The prover has quantum access to copies of \(\rho_D\).

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

Notes

The prover’s computational complexity is dominated by QFS (Section 5.1): \(O(n \cdot m)\) single-qubit gates and \(\tilde{O}(n \cdot m)\) classical processing, where \(m = O(\log(1/\delta)/\varepsilon^4)\) is the number of QFS copies.

_rng: numpy.random.Generator

run_protocol(epsilon: float, delta: float = 0.1, theta: float | None = None, estimate_coefficients: bool = True, qfs_mode: str = 'statevector', qfs_shots: int | None = None, classical_samples: int | None = None) → ProverMessage

Execute the prover’s side of the verification protocol.

Step 1: Perform QFS to obtain post-selected samples.

Step 2: Build the empirical spectrum approximation (Corollary 5 / Lemma 3).

Step 3: Extract the heavy coefficient list \(L\).

Step 4 (optional): Estimate the Fourier coefficients for each \(s \in L\) using classical samples.

Step 5: Package and return the message.

Parameters:

• epsilon (float) – Accuracy parameter \(\varepsilon \in (0, 1)\). The prover resolves the Fourier spectrum to accuracy \(\varepsilon\) in \(\ell_\infty\)-norm.

• delta (float) – Confidence parameter \(\delta \in (0, 1)\). The protocol succeeds with probability \(\geq 1 - \delta\).

• theta (float, optional) – Fourier coefficient resolution threshold \(\vartheta\). If not provided, defaults to epsilon (appropriate for the functional agnostic case per Theorem 8). For the distributional case (Theorem 12), should be set according to the promise on the distribution class.

• estimate_coefficients (bool) – If True (default), estimate \(\hat{\tilde\phi}(s)\) for each \(s \in L\) using classical samples (computational-basis measurement of \(\rho_D\)). This is needed for the verifier’s Fourier weight check.

• qfs_mode (str) – QFS simulation mode ("statevector" or "circuit").

• qfs_shots (int, optional) – Override the number of QFS shots. If not provided, computed from the DKW bound (Lemma 3): \(m = \lceil 2\log(4/\delta) / (\varepsilon^2/8)^2 \rceil\). Note: since post-selection succeeds with probability 1/2, we double this to get the expected number of accepted samples.

• classical_samples (int, optional) – Override the number of classical samples for coefficient estimation. If not provided, computed from Hoeffding: \(m_2 = O(|L| \cdot \log(|L|/\delta) / \varepsilon^2)\).

Returns:

The prover’s message to the verifier.

Return type:

ProverMessage

Raises:

ValueError – If parameters are out of range.

_build_spectrum_approximation(qfs_result: QFSResult, theta: float) → SpectrumApproximation

Build a succinct empirical approximation to the QFS distribution.

From the post-selected QFS samples, compute the empirical distribution \(\tilde{q}_m(s, 1)\) for each observed frequency \(s\).

By Lemma 3 (DKW), with \(m\) post-selected samples:

\[\|\tilde{q}_m - q\|_\infty \leq \tau\]

with probability \(\geq 1 - 2\exp(-m\tau^2/2)\).

The empirical distribution \(\tilde{q}_m(s, 1)\) relates to the Fourier coefficients via:

\[\tilde{q}_m(s, 1) \approx q(s, 1) = \frac{1}{2}\Bigl[ \frac{1 - \mathbb{E}[\tilde\phi^2]}{2^n} + \hat{\tilde\phi}(s)^2 \Bigr]\]

We store the (sparse) empirical distribution and use it to identify heavy coefficients.

Parameters:

• qfs_result (QFSResult) – Output from the QFS procedure.

• theta (float) – Resolution threshold.

Return type:

SpectrumApproximation

_extract_heavy_list(spectrum_approx: SpectrumApproximation, theta: float) → list[int]

Extract the list \(L\) of candidate heavy Fourier coefficient indices.

From Corollary 5:

• Completeness: If \(|\hat{\tilde\phi}(s)| \geq \vartheta\), then \(s \in L\).

• Partial soundness: If \(s \in L\), then \(|\hat{\tilde\phi}(s)| \geq \vartheta/4\).

The list size is bounded by Parseval: \(|L| \leq 16/\vartheta^2\).

Parameters:

• spectrum_approx (SpectrumApproximation) – The empirical spectrum approximation.

• theta (float) – Resolution threshold \(\vartheta\).

Returns:

L – Sorted by empirical weight (descending).

Return type:

list[int]

_estimate_coefficients(L: list[int], epsilon: float, delta: float, num_samples_override: int | None = None) → tuple[dict[int, float], int]

Estimate Fourier coefficients for each \(s \in L\) from classical random examples.

By Lemma 1, computational-basis measurement of \(\rho_D\) yields classical samples from \(D\). For each \(s\),

\[\hat{\tilde\phi}(s) = \mathbb{E}_{(x,y) \sim D} [(1 - 2y)(-1)^{s \cdot x}]\]

so we estimate this expectation via sample mean. By Hoeffding, \(m_2 = O(\log(|L|/\delta) / \varepsilon^2)\) samples suffice for simultaneous \(\varepsilon\)-accuracy across all \(s \in L\).

Parameters:

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

• epsilon (float) – Desired accuracy per coefficient.

• delta (float) – Overall confidence parameter.

• num_samples_override (int, optional) – Override the computed sample count.

Returns:

• estimates (dict[int, float]) – estimates[s] is the empirical estimate of \(\hat{\tilde\phi}(s)\) for each \(s \in L\).

• num_samples (int) – Number of classical samples used.

exact_heavy_coefficients(theta: float, *, effective: bool = True) → list[tuple[int, float]]

Return the exact list of heavy Fourier coefficients (for validation / comparison with the empirical list).

Parameters:

• theta (float) – Threshold: returns all \(s\) with \(|\hat{\tilde\phi}(s)| \geq \vartheta\).

• effective (bool) – If True, use noise-adjusted coefficients.

Returns:

heavy – Pairs \((s, \hat{\tilde\phi}(s))\), sorted by absolute value descending.

Return type:

list[tuple[int, float]]