.. _randomization:

=====================================
Randomization of Quantum Measurements
=====================================

.. seealso::

   This content is adapted from the work of Timothée Dao; "*Informationally
   Complete Generalized Measurements for Estimating Quantum Expectation Values*"
   [Unpublished master's thesis]; ETH Zürich (2023).

---------
Convexity
---------

Following Ref. [#oszmaniec_simulating_2017]_, the set of
:math:`n`-outcome POVMs on the Hilbert space :math:`\mathcal{H}` is denoted by
:math:`\mathcal{M}(\mathcal{H},n)`. If only the dimension :math:`d` of the
Hilbert space is relevant, we can denote this set by
:math:`\mathcal{M}(d,n)`. Note that for :math:`m<n`, an
:math:`m`-outcome POVM can be seen as an :math:`n`-outcome POVM with
:math:`(n-m)` null effects. Hence we have
:math:`\mathcal{M}(d,m) \subset \mathcal{M}(d,n)` for all :math:`m<n`.

**Example**:
   Consider a :math:`3`-outcome POVM on a single-qubit system :
   :math:`\mathbf{M} = \{M_1,M_2,M_3\} \in \mathcal{M}(2,3)`. It can be
   considered as a 4-outcome POVM with a null effect,
   :math:`\mathbf{M} = \{M_1,M_2,M_3,0\} \in \mathcal{M}(2,4)`. Note that
   :math:`\{M_1,0,M_2,M_3\}` is an equivalent POVM up to the re-ordering
   of the effects.

Consider two POVMs :math:`\mathbf{M}_1,\mathbf{M}_2 \in \mathcal{M}(d,n)`, where
:math:`\mathbf{M}_i = \{ M_{i,k}\}_k`, and a real number
:math:`p \in \mathbb{R}`. The multiplication of a POVM by a scalar and
the addition of two POVMs are defined element-wise, namely,

.. math::
   :label: povm_relations

   \begin{aligned}
       p \mathbf{M}_1 &= \{p M_{1,k}\}_k \, , \\
       \mathbf{M}_1 + \mathbf{M}_2 &= \{ M_{1,k} + M_{2,k}\}_k \, ,
   \end{aligned}

respectively. Crucially, these operations do not preserve the set of
POVMs. That is, the effects resulting from these operations do not form
POVMs in general. Indeed, it is easy to check that the resulting effects
do not sum to the identity (except for the scalar multiplication by
:math:`p=1`). However, by taking convex combinations we arrive at the
following result.

**Lemma** [#lem_convex]_:

   The set :math:`\mathcal{M}(d,n)` is convex. That is, for any
   :math:`\mathbf{M}_1, \mathbf{M}_2 \in \mathcal{M}(d,n)` and any
   :math:`p \in [0,1]`, we have
   :math:`\mathbf{M} = p\mathbf{M}_1+ (1-p)\mathbf{M}_2 \in \mathcal{M}(d,n)`.

**Proof**:
   The elements of :math:`\mathbf{M}`, given by
   :math:`M_k = p M_{1,k} + (1-p) M_{2,k}` for
   :math:`k\in \{1,\dots,n\}`, are positive semi-definite by the
   convexity of the set of positive semi-definite operators
   :math:`\mathrm{Pos}(\mathcal{H})`. Moreover,

   .. math::
      :label: convexity_proof

      \sum_k M_k = p \sum_k M_{1,k} + (1-p) \sum_k M_{2,k} = p  \mathbb{I}_\mathcal{H} + (1-p)  \mathbb{I}_\mathcal{H} =  \mathbb{I}_\mathcal{H} \, ,

   \ which concludes the proof. ◻

Such convex combinations can be extended to more than two POVMs.
Consider a set of POVMs
:math:`\mathcal{S} = \{\mathbf{M}_i\} \subset \mathcal{M}(d,n)` and a
probability distribution :math:`\{q_i\}`, then

.. math::
   :label: convexity_corollary

   \mathbf{M} = \sum_i q_i \mathbf{M}_i \, \in \mathcal{M}(d,n)

as a corollary of Lemma [#lem_convex]_.

The set of all convex combinations generated by a set
:math:`\mathcal{S} = \{\mathbf{M}_i\}`, i.e. its convex hull, is denoted by
:math:`\mathcal{S}^\mathrm{conv}`. 

-----------
In practice
-----------

These convex combinations can be achieved in
practice by the so-called *randomization of quantum measurements*
procedure, which simply consists of two steps for each measurement shot:

#. Randomly pick :math:`\mathbf{M}_i` with probability :math:`q_i`,

#. Perform the measurement associated with :math:`\mathbf{M}_i`.

Indeed, the probability of obtaining the outcome :math:`k` with this
procedure is

.. math::
   :label: probability_for_randomized_povms

   \begin{split}
       \Pr(\textrm{outcome is }k) & = \sum_i \Pr(\textrm{outcome is } k \mid i \textrm{ was picked}) \Pr(i \textrm{ was picked}) \\
       & = \sum_i  \mathrm{Tr}[M_{i,k}\rho] q_i  = \mathrm{Tr}[\sum_i q_i M_{i,k}\rho] \\
       & = \mathrm{Tr}[M_k\rho] \, , 
   \end{split}

which is exactly equivalent to directly performing the measurement
associated with :math:`\mathbf{M}`. 


**Example**:
   To illustrate the usefulness of this
   procedure, imagine one has two measurement apparatuses associated with
   the POVMs :math:`\mathbf{M}_1` and :math:`\mathbf{M}_2` respectively. To perform
   the measurement associated with
   :math:`\mathbf{M} = p\mathbf{M}_1+ (1-p)\mathbf{M}_2`, one does not need to build a
   new apparatus but only needs to use each of the two existing apparatuses
   with probability :math:`p` and :math:`1-p` respectively.

**Example**:
   Consider two POVMs :math:`\mathbf{M},\mathbf{N} \in \mathcal{M}(2,2)`. We
   have

   .. math::
      :label:

      \frac{1}{3} \mathbf{M} + \frac{2}{3}\mathbf{N} = \{ \, \frac{1}{3} M_1 + \frac{2}{3} N_1\, , \; \frac{1}{3} M_2 + \frac{2}{3} N_2 \, \} \in \mathcal{M}(2,2)\, ,

   and also

   .. math::
      :label:

      \frac{1}{3} \{M_1,  M_2,0,0\} + \frac{2}{3} \{0,0,N_1,  N_2\} =  \{\frac{1}{3} M_1 \, , \; \frac{1}{3} M_2 \, , \;  \frac{2}{3} N_1 \, , \;  \frac{2}{3} N_2\} \in \mathcal{M}(2,4)\, ,

   where in the second example :math:`\mathbf{M}` and :math:`\mathbf{N}` are
   considered as 4-outcome POVMs with 2 null effects:
   :math:`\{M_1,  M_2,0,0\}, \{0,0, N_1,  N_2\}  \in \mathcal{M}(2,4)`
   respectively.

We will use the latter construction very often. Therefore, given two
POVMs :math:`\mathbf{M}_1` and :math:`\mathbf{M}_2`, we introduce the notation

.. math::
   :label:

   \mathbf{M}_1 \uplus \mathbf{M}_2 = \{ M_{1,k}\}_k \uplus \{M_{2,k}\}_k =  \{ M_{i,k}\}_{i,k}

where :math:`\uplus` is the multiset sum [#multiset]_. More generally, for any
set of POVMs :math:`\{\mathbf{M}_i \mid \mathbf{M}_i \in \mathcal{M}(d, n_i)\}`
and any probability distribution :math:`\{q_i\}`, we have

.. math::
   :label:

   \mathbf{M} = \biguplus_i q_i \mathbf{M}_i = \left\{ q_i M_{i,k} \right\}_{i,k} \ \in \mathcal{M}(d, {\textstyle\sum_i} n_i)

where the outcomes are now denoted by the pair :math:`(i,k)`.


.. rubric:: References

.. [#oszmaniec_simulating_2017] M. Oszmaniec, F. B. Maciejewski, Z. Puchała,
   Physical Review A 100, 012351 (2019).

.. rubric:: Footnotes

.. [#lem_convex] Convexity LEMMA
.. [#multiset] The concept of multiset is an extension of the notion of set, where
   each element can be represented multiple times.