sampler — Quantum Fourier Sampling

Quantum Fourier Sampling from MoS states — Theorem 5 of Caro et al.

Implements the QFS procedure: given a copy of the MoS state \(\rho_D\), apply \(H^{\otimes(n+1)}\), measure all qubits in the computational basis, and post-select on the label qubit being 1.

Theorem 5 (Distributional agnostic approximate quantum Fourier sampling). Conditioned on observing outcome 1 for the last qubit (which occurs with probability 1/2), the first \(n\) qubits output \(s \in \{0,1\}^n\) with probability

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

This module provides two simulation strategies:

• statevector (default): For each sampled \(f \sim F_D\), constructs \(|\psi_f\rangle\) as a Statevector, applies \(H^{\otimes(n+1)}\), and samples from the resulting probability distribution. Exact (no shot noise beyond finite sampling). Cost: \(O(2^n)\) per copy. Practical for \(n \leq 20\).

• circuit: Builds a Qiskit circuit (Hadamard layer + oracle) for each \(f\) and executes it via StatevectorSampler. Produces identical distributions to statevector mode but uses the Qiskit primitives pipeline, validating circuit construction. Practical for \(n \leq 12\) due to multi-controlled gate overhead.

Both modes return raw measurement counts (before post-selection) so that the caller can verify the 1/2 label-qubit marginal and inspect rejection rates.

References:

• Caro et al., “Classical Verification of Quantum Learning”, ITCS 2024. Theorem 5 (Section 5.1), Lemma 2 (Section 4.1), Corollary 5 (Section 5.1).

• Bernstein & Vazirani (1997) for the original QFS idea.

class mos.sampler.QFSResult(raw_counts: dict[str, int], postselected_counts: dict[str, int], total_shots: int, postselected_shots: int, n: int, mode: str)

Bases: object

Container for raw and post-selected QFS measurement outcomes.

raw_counts

Full \((n+1)\)-bit measurement counts (bitstrings in Qiskit little-endian convention: rightmost character = qubit 0).

Type:

dict[str, int]

postselected_counts

\(n\)-bit frequency counts for the input register, conditioned on the label qubit being 1.

Type:

dict[str, int]

total_shots

Number of MoS copies consumed (= circuits executed).

Type:

int

postselected_shots

Number of shots surviving post-selection (label qubit = 1).

Type:

int

n

Number of input qubits.

Type:

int

mode

Simulation mode used ("statevector" or "circuit").

Type:

str

raw_counts: dict[str, int]

postselected_counts: dict[str, int]

total_shots: int

postselected_shots: int

n: int

mode: str

property postselection_rate: float

Fraction of shots surviving post-selection.

By Theorem 5(i) this should concentrate around 1/2.

empirical_distribution() → numpy.ndarray

Normalised empirical distribution over \(\{0,1\}^n\) from the post-selected counts.

Returns:

dist – dist[s] is the empirical probability of frequency s. Zero everywhere if no shots survived post-selection.

Return type:

np.ndarray of shape \((2^n,)\)

class mos.sampler.QuantumFourierSampler(mos_state: MoSState, seed: int | None = None, noise_model: object | None = None)

Bases: object

Approximate quantum Fourier sampling from MoS states (Theorem 5).

Consumes copies of \(\rho_D\), applies \(H^{\otimes(n+1)}\), measures all \(n+1\) qubits in the computational basis, and post-selects on the label qubit (qubit \(n\)) being 1.

Protocol (one copy):

1. Sample \(f \sim F_D\) using \(\phi_{\text{eff}}\).

2. Prepare \(|\psi_{U_n,f}\rangle = 2^{-n/2}\sum_x |x,f(x)\rangle\).

3. Apply \(H^{\otimes(n+1)}\).

4. Measure all qubits → outcome \((s, b) \in \{0,1\}^n \times \{0,1\}\).

5. If \(b = 1\), record \(s\).

By Theorem 5, the conditional distribution is

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

Parameters:

• mos_state (MoSState) – The MoS state to sample from. Defines \(n\), \(\phi\), and the noise model.

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

_MODES = {'circuit', 'statevector'}

_rng: numpy.random.Generator

sample(shots: int, mode: str = 'statevector') → QFSResult

Execute the QFS protocol and return raw + post-selected counts.

Each shot consumes one independent copy of \(\rho_D\). The label qubit marginal should be close to 1/2 (Theorem 5(i)); any significant deviation indicates a bug.

Parameters:

• shots (int) – Number of MoS copies to consume (\(\geq 1\)).

• mode (str) –

  Simulation strategy:

  • "statevector" — direct Statevector computation per copy.

  • "circuit" — Qiskit circuit + StatevectorSampler per copy.

Returns:

Raw and post-selected measurement counts.

Return type:

QFSResult

Raises:

ValueError – If shots < 1 or mode is unrecognised.

theoretical_distribution() → numpy.ndarray

Exact \(\Pr[s \mid b{=}1]\) from Theorem 5.

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

Always uses the effective (noise-adjusted) spectrum, since this is what the physical QFS circuit produces.

Returns:

dist

Return type:

np.ndarray of shape \((2^n,)\)

fourier_coefficient(s: int, effective: bool = True) → float

Exact Fourier coefficient for validation.

Parameters:

• s (int) – Frequency index in \(\{0, \ldots, 2^n - 1\}\).

• effective (bool) – If True (default), return \(\hat{\tilde\phi}_{\text{eff}}(s) = (1-2\eta)\hat{\tilde\phi}(s)\). If False, return the noiseless \(\hat{\tilde\phi}(s)\).

Return type:

float

_sample_statevector(shots: int) → dict[str, int]

Statevector mode: for each copy, build \(H^{\otimes(n+1)}|\psi_f\rangle\) and sample.

For every sampled \(f\), the Hadamard-transformed statevector has closed-form amplitudes (proof of Lemma 2):

\[H^{\otimes(n+1)}|\psi_f\rangle = \frac{1}{\sqrt{2}}|0\rangle^{\otimes(n+1)} + \frac{1}{\sqrt{2}}\sum_s \hat{g}_f(s)\,|s,1\rangle\]

where \(g_f = (-1)^f\). Rather than recomputing this symbolically, we apply the Hadamard via Statevector.evolve() and use Statevector.sample_counts().

_sample_circuit(shots: int) → dict[str, int]

Circuit mode: build a full Qiskit circuit per copy and execute via StatevectorSampler.

Each circuit is:

\[|0\rangle^{\otimes(n+1)} \;\xrightarrow{H^{\otimes n}\otimes I}\; |{+}\rangle^{\otimes n}|0\rangle \;\xrightarrow{U_f}\; |\psi_f\rangle \;\xrightarrow{H^{\otimes(n+1)}}\; \text{measure}\]

This validates the circuit-construction pipeline (oracle gates, Hadamard layer, measurement) against the statevector mode. Practical for \(n \leq 12\) due to multi-controlled gate overhead in MoSState._circuit_oracle_f().

_postselect(raw_counts: dict[str, int]) → tuple[dict[str, int], int]

Extract the \(n\)-bit frequency distribution conditioned on the label qubit \(b = 1\).

In the raw bitstrings (Qiskit convention: highest qubit index on the left), the label qubit (qubit \(n\)) is the leftmost character. We keep only bitstrings where this character is '1', then strip it to obtain the \(n\)-bit frequency string.

Parameters:

raw_counts (dict[str, int]) – Full \((n+1)\)-bit counts from measurement.

Returns:

• ps_counts (dict[str, int]) – \(n\)-bit post-selected counts.

• ps_total (int) – Total shots surviving post-selection.