MedianOfMeans¶

Bases: POVMPostProcessor

A POVM result post-processor which uses a ‘median of means’ estimator.

Given num_shots=num_batches*batch_size samples, we partition the samples into num_batches batches. We compute the mean of each batch, \(\hat{o}_j\), and then output the median of the means, \(\hat{o} =\mathrm{median}\{\hat{o}_1, ..., \hat{o}_{\mathrm{num\_batches}}\}\). It can be shown that

\[\lvert \mathrm{Tr}[\mathcal{O} \rho] - \hat{o} \rvert \leq \epsilon \quad \textrm{with probability at least } 1-\delta \, ,\]

where \(\delta = 2 \exp{(-\mathrm{num\_batches}/2)}\) and \(\epsilon = \sqrt{\frac{34}{\mathrm{batch\_size}} } \lVert \mathcal{O} - \frac{\mathrm{Tr} [\mathcal{O}]}{2^N} \mathbb{I} \rVert_\textrm{shadow}\). For more details, see the work of H.-Y. Huang, R. Kueng, and J. Preskill, “Predicting Many Properties of a Quantum System from Very Few Measurements”, Nature Physics 16, 1050 (2020).

The interface of this post-processor is essentially identical to the one of its baseclass (see POVMPostProcessor for more details). For completeness, here is an example how to use it:

>>> from povm_toolbox.library import ClassicalShadows
>>> from povm_toolbox.sampler import POVMSampler
>>> from povm_toolbox.post_processor import MedianOfMeans
>>> from qiskit.circuit import QuantumCircuit
>>> from qiskit.primitives import StatevectorSampler
>>> from qiskit.quantum_info import SparsePauliOp
>>> circ = QuantumCircuit(2)
>>> _ = circ.h(0)
>>> _ = circ.cx(0, 1)
>>> povm = ClassicalShadows(2, seed=42)
>>> sampler = StatevectorSampler(seed=42)
>>> povm_sampler = POVMSampler(sampler)
>>> job = povm_sampler.run([circ], povm=povm, shots=16)
>>> result = job.result()
>>> post_processor = MedianOfMeans(result[0], num_batches=4, seed=42)
>>> post_processor.get_expectation_value(SparsePauliOp("ZI"))  
(-0.75, 2.9154759474226504)

Initialize the median-of-means post-processor.

Parameters:

povm_sample (POVMPubResult) – a result from a POVM sampler run.
dual (BaseDual | None) – the Dual frame that will be used to obtain the decomposition weights of an observable when computing its expectation value. For more details, refer to get_decomposition_weights(). When this is None, the default “state-average” Dual frame will be constructed from the POVM stored in the povm_sample’s POVMPubResult.metadata.
num_batches (int | None) – number of batches, i.e. number of samples means, used in the median-of-means estimator. This value will be overridden if a delta_confidence argument is supplied.
upper_delta_confidence (float | None) – an upper bound for the confidence parameter \(\delta\) used to determine the necessary number of batches as \(\mathrm{num\_batches} = \lceil 2 \log{(2/\delta)} \rceil\). It will override any num_batches supplied argument. If both num_batches and delta_confidence are None, delta_confidence is set to 0.05. Note that this argument is actually an upper bound for the true \(\delta\)-parameter which is given by \(\delta=2 \exp(-\mathrm{num\_batches}/2)\).
seed (int | Generator | None) – optional seed to fix the numpy.random.Generator used to generate the batches. The user can also directly provide a random generator. If None, a random seed will be used.

Raises:

ValueError – If the provided dual is not a dual frame to the POVM stored in the povm_samples’s POVMPubResult.metadata.
TypeError – If the type of seed is not valid.

Attributes

delta_confidence¶: The confidence parameter \(\delta=2 \exp(-\) num_batches \(/2)\).

num_batches: int¶: Number of batches, i.e. number of samples means, used in the median-of-means estimator.

Inherited Attributes

counts¶: Return the histogram of the POVM outcomes via POVMPubResult.get_counts().

dual¶: Return the Dual frame that is used.

Warning

If the dual frame is not already built, accessing this property could be computationally demanding.

povm¶: Return the POVM definition that was used to sample outcomes.

Inherited Methods

get_decomposition_weights(observable: SparsePauliOp, outcome_set: set[Any]) → dict[Any, float]¶

Get the decomposition weights of observable into the elements of povm.

Given an observable \(O\) which is in the span of a POVM (here, povm), one can write \(O\) as the weighted sum of the POVM effects, \(O = \sum_k w_k M_k\) for real weights \(w_k\) and where \(k\) labels the outcomes.