mos — Mixture-of-Superpositions State

Mixture-of-Superpositions (MoS) State - Definition 8 of Caro et al.

Represents the mixed quantum example state:

\[\rho_D = \mathbb{E}_{f \sim F_D} \bigl[|\psi_{U_n, f}\rangle\langle\psi_{U_n, f}|\bigr]\]

where \(F_D\) is the distribution over Boolean functions induced by independently sampling \(f(x) \sim \text{Bernoulli}(\phi_{\text{eff}}(x))\) for each \(x \in \{0,1\}^n\), and

\[|\psi_{U_n, f}\rangle = \frac{1}{\sqrt{2^n}} \sum_x |x, f(x)\rangle\]

Noise model (Definition 5(iii)). When noise_rate \(\eta > 0\), each label is independently flipped with probability \(\eta\) before state preparation. The effective conditional label probability becomes

\[\phi_{\text{eff}}(x) = (1 - 2\eta)\,\phi(x) + \eta\]

and the effective \(\{-1,1\}\)-valued label expectation is

\[\tilde\phi_{\text{eff}}(x) = (1 - 2\eta)\,\tilde\phi(x).\]

The MoS state \(\rho_D\) is constructed from \(\phi_{\text{eff}}\), so computational-basis measurement yields samples from the noisy distribution (Lemma 1), and Quantum Fourier Sampling (Theorem 5) produces outcomes governed by the effective Fourier coefficients \(\hat{\tilde\phi}_{\text{eff}}(s) = (1 - 2\eta)\,\hat{\tilde\phi}(s)\).

All Fourier-analytic methods accept an effective flag (default True) that controls whether the returned quantities incorporate the noise factor \((1 - 2\eta)\). Set effective=False to obtain the noiseless ground-truth coefficients of \(\tilde\phi\).

This class handles ONLY state-level concerns:

• Storing the distribution \(D = (U_n, \phi)\) and its noise model

• Sampling \(f \sim F_D\)

• Preparing \(|\psi_f\rangle\) as a Statevector or QuantumCircuit

• Approximating \(\rho_D\) via Monte Carlo

• Recovering classical samples via computational basis measurement (Lemma 1)

• Exact Fourier analysis of \(\tilde\phi\) (noiseless or effective)

It does NOT handle Hadamard measurement, post-selection, Fourier sampling, heavy coefficient extraction, or anything verification-related.

Conventions:

• \(\phi(x) = \Pr[y{=}1 \mid x] \in [0, 1]\) — the {0,1}-valued label expectation

• \(\tilde\phi(x) = 1 - 2\phi(x) \in [-1, 1]\) — the {-1,1}-valued label expectation

• Qiskit little-endian: integer \(x = \sum_i x_i \cdot 2^i\)

• Qubits 0..n-1 hold x, qubit n holds the label bit b

class mos.MoSState(n: int, phi: Callable[[int], float] | numpy.ndarray, noise_rate: float = 0.0, seed: int | None = None)

Bases: object

Mixture-of-Superpositions quantum example state (Definition 8).

Parameters:

• n (int) – Number of input bits (dimension of \(X_n = \{0,1\}^n\)).

• phi (callable or array-like) – The conditional probability function \(\phi(x) = \Pr[y{=}1 \mid x]\). If callable: phi(x: int) -> float in [0, 1]. If array: phi[x] for x in 0..2^n - 1, values in [0, 1].

• noise_rate (float) – Label-flip noise rate \(\eta \in [0, 0.5]\). When \(\eta > 0\), each label is independently flipped with probability \(\eta\) before state preparation. This reduces to the MoS noisy functional setting, Definition 5(iii). The MoS state is constructed from the effective label probabilities \(\phi_{\text{eff}}(x) = (1-2\eta)\phi(x)+\eta\), so all quantum operations (state preparation, QFS, classical sampling) see the noisy distribution.

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

property phi: numpy.ndarray

\(\phi(x) = \Pr[y{=}1 \mid x]\) in [0, 1] for all x (noiseless).

property tilde_phi: numpy.ndarray

\(\tilde\phi(x) = 1 - 2\phi(x)\) in [-1, 1] for all x (noiseless).

property phi_effective: numpy.ndarray

\((1 - 2\eta)\phi(x) + \eta\).

Type:

Effective phi after noise

property tilde_phi_effective: numpy.ndarray

\((1 - 2\eta) \tilde\phi(x)\).

Type:

Effective tilde_phi after noise

sample_f(rng: numpy.random.Generator | None = None) → numpy.ndarray

Sample a random Boolean function \(f \sim F_D\).

For each \(x \in \{0,1\}^n\), independently sample \(f(x) \sim \text{Bernoulli}(\phi_{\text{eff}}(x))\).

When noise_rate > 0, \(\phi_{\text{eff}}\) incorporates the label-flip noise, so the sampled \(f\) is drawn from the noisy MoS distribution.

Parameters:

rng (Generator, optional) – NumPy random generator. Uses internal RNG if not provided.

Returns:

f – f[x] is the value f(x) in {0, 1}.

Return type:

np.ndarray of shape (2^n,), dtype=np.uint8

statevector_f(f: numpy.ndarray) → qiskit.quantum_info.Statevector

Construct the Qiskit Statevector \(|\psi_{U_n, f}\rangle\) for a fixed function f.

\[|\psi_{U_n, f}\rangle = \frac{1}{\sqrt{2^n}} \sum_x |x,\, f(x)\rangle\]

In Qiskit’s little-endian convention, \(|x, b\rangle\) maps to index \(x + b \cdot 2^n\) since qubit n (the label) is the highest-index qubit.

Parameters:

f (np.ndarray of shape (2^n,), dtype=np.uint8) – Boolean function values.

Returns:

sv – The (n+1)-qubit state \(|\psi_{U_n, f}\rangle\).

Return type:

Statevector

_circuit_oracle_f(f: numpy.ndarray) → qiskit.QuantumCircuit

Build an oracle circuit \(U_f\) mapping \(|x\rangle|0\rangle \to |x\rangle|f(x)\rangle\).

For each x where f(x) = 1, applies a multi-controlled X gate on the label qubit, controlled on the input register being \(|x\rangle\).

Note: This constructs up to \(2^n\) multi-controlled gates and is intended for simulation only (impractical for n > ~10).

Parameters:

f (np.ndarray) – Boolean function values.

Returns:

qc – Oracle circuit on n+1 qubits.

Return type:

QuantumCircuit

circuit_prepare_f(f: numpy.ndarray) → qiskit.QuantumCircuit

Build a circuit preparing \(|\psi_{U_n, f}\rangle\) via \(H^{\otimes n}\) + oracle.

\[|0\rangle^{\otimes(n+1)} \xrightarrow{H^{\otimes n} \otimes I} |{+}\rangle^{\otimes n}|0\rangle \xrightarrow{U_f} |\psi_{U_n, f}\rangle\]

This is more hardware-friendly than arbitrary state initialisation.

Parameters:

f (np.ndarray) – Boolean function values.

Returns:

qc – Circuit on n+1 qubits that prepares \(|\psi_{U_n, f}\rangle\).

Return type:

QuantumCircuit

circuit_prepare_f_initialize(f: numpy.ndarray) → qiskit.QuantumCircuit

Build a circuit preparing \(|\psi_{U_n, f}\rangle\) via Qiskit’s Initialize.

Exact but synthesises an arbitrary state preparation unitary — less portable to real hardware.

Parameters:

f (np.ndarray) – Boolean function values.

Returns:

qc – Circuit on n+1 qubits.

Return type:

QuantumCircuit

density_matrix(num_samples: int = 1000, rng: numpy.random.Generator | None = None) → qiskit.quantum_info.DensityMatrix

Approximate \(\rho_D\) by Monte Carlo averaging over sampled f.

\[\rho_D \approx \frac{1}{M} \sum_{m=1}^{M} |\psi_{f_m}\rangle\langle\psi_{f_m}|\]

The functions \(f_m\) are sampled using \(\phi_{\text{eff}}\), so the resulting density matrix incorporates any label-flip noise.

Parameters:

• num_samples (int) – Number of functions f to sample (M).

• rng (Generator, optional) – NumPy random generator.

Returns:

rho – Monte Carlo estimate of the MoS density matrix.

Return type:

DensityMatrix

sample_classical(rng: numpy.random.Generator | None = None) → Tuple[int, int]

Draw a classical sample \((x, y)\) by measuring \(\rho_D\) in the computational basis.

By Lemma 1, this is equivalent to sampling from the distribution \(D\) encoded by the MoS state. When noise_rate > 0, the sampled labels reflect the noisy distribution (i.e. \(y\) is drawn from \(\phi_{\text{eff}}(x)\)).

Equivalently (and more efficiently), we sample \(x \sim U_n\) and \(y \sim \text{Bernoulli}(\phi_{\text{eff}}(x))\) directly.

Parameters:

rng (Generator, optional) – NumPy random generator.

Returns:

• x (int) – Input in {0, …, 2^n - 1}.

• y (int) – Label in {0, 1}.

sample_classical_batch(num_samples: int, rng: numpy.random.Generator | None = None) → Tuple[numpy.ndarray, numpy.ndarray]

Draw a batch of classical samples \((x_i, y_i)\).

Labels are drawn from \(\phi_{\text{eff}}\) (see sample_classical()).

Parameters:

• num_samples (int) – Number of samples.

• rng (Generator, optional) – NumPy random generator.

Returns:

• xs (np.ndarray of shape (num_samples,), dtype=int) – Input values.

• ys (np.ndarray of shape (num_samples,), dtype=int) – Label values.

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

Compute the Fourier coefficient \(\hat{\tilde\phi}(s)\).

\[\hat{\tilde\phi}(s) = \mathbb{E}_{x \sim U_n}[\tilde\phi(x) \cdot \chi_s(x)]\]

where \(\chi_s(x) = (-1)^{s \cdot x}\) and \(\tilde\phi = 1 - 2\phi\).

Parameters:

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

• effective (bool) – If True (default), return the noise-adjusted coefficient \(\hat{\tilde\phi}_{\text{eff}}(s) = (1-2\eta)\hat{\tilde\phi}(s)\), which governs the actual QFS sampling distribution (Theorem 5 / Lemma 6). If False, return the noiseless coefficient.

Returns:

coeff – The Fourier coefficient.

Return type:

float

fourier_spectrum(*, effective: bool = True) → numpy.ndarray

Compute the full Fourier spectrum for all s.

Parameters:

effective (bool) – If True (default), return the noise-adjusted spectrum \(\{\hat{\tilde\phi}_{\text{eff}}(s)\}_s\). If False, return the noiseless spectrum \(\{\hat{\tilde\phi}(s)\}_s\).

Returns:

spectrum – spectrum[s] is the Fourier coefficient at frequency s.

Return type:

np.ndarray of shape (2^n,)

parseval_check(*, effective: bool = True) → Tuple[float, float]

Verify Parseval’s identity: \(\sum_s \hat{\tilde\phi}(s)^2 = \mathbb{E}[\tilde\phi(x)^2]\).

When effective=True, both sides are computed with the noise-adjusted \(\tilde\phi_{\text{eff}}\), so the identity remains valid.

Parameters:

effective (bool) – If True (default), check Parseval for the effective (noise-adjusted) spectrum and \(\tilde\phi_{\text{eff}}\). If False, check for the noiseless quantities.

Returns:

• fourier_sum (float) – \(\sum_s \hat{\tilde\phi}(s)^2\) (or effective variant).

• expected_sq (float) – \(\mathbb{E}_{x \sim U_n}[\tilde\phi(x)^2]\) (or effective variant).

qfs_probability(s: int) → float

Probability of observing frequency \(s\) from Quantum Fourier Sampling, conditioned on the last qubit being 1 (Theorem 5).

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

This always uses the effective (noise-adjusted) coefficients, since the QFS circuit acts on the physical MoS state.

Parameters:

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

Returns:

prob – Conditional probability of observing s.

Return type:

float

qfs_distribution() → numpy.ndarray

Full QFS conditional distribution over \(\{0,1\}^n\), conditioned on the last qubit being 1 (Theorem 5).

Always uses effective (noise-adjusted) coefficients.

Returns:

dist – dist[s] is the conditional probability of observing s.

Return type:

np.ndarray of shape (2^n,)

summary(*, effective: bool = True) → str

Human-readable summary of the MoS state.

Parameters:

effective (bool) – If True (default), report the noise-adjusted Fourier spectrum that governs actual QFS outcomes. If False, report noiseless ground-truth coefficients.