Guesswork of a quantum ensemble

We consider a communication scenario involving two parties, Alice and Bob. An ensemble $\boldsymbol{\rho}$ of quantum states with labels in a set $\mathcal{M}$ is given and known to both parties. At each round, Alice picks a label $m\in\mathcal{M}$ with probability $\operatorname{Tr}[\boldsymbol{\rho}(m)]$ and hands state $\operatorname{Tr}[\boldsymbol{\rho}(m)]^{-1}\boldsymbol{\rho}(m)$ over to Bob. Bob aims at correctly guessing label $m$ being allowed to query one element of $\mathcal{M}$ at a time, until his query is correct, at which point the round is over. The cost function incurred by Bob is the average number of guesses, or guesswork, until he correctly guesses $m$. Bob’s most general strategy consists of performing a quantum measurement $\boldsymbol{\pi}$ outputing an element $\mathbf{n}$ from the set $\mathcal{N}_{\mathcal{M}}$ of numberings of $\mathcal{M}$ and querying the elements of $\mathcal{M}$ in the order specified by $\mathbf{n}$. Hence, the guesswork is given by the occurence of label $m$ in numbering $\mathbf{n}$, averaged over all numberings. Using the formalism [1] of quantum circuits, the setup is as follows:

(3)

The guesswork has been extensively studied for classical ensembles [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], but only very recently tackled for quantum ensembles [13, 14, 15]. While previous works focused on the derivation of entropic bounds, our aim is instead the derivation of analytical solutions. Our main result, Theorem 1, provides an analytical solution subject to a finite set of conditions. In particular, Corollary 1 provides the analytical solution for any qubit ensemble with uniform probability distribution, thus disproving the conjecture [13] that analytical solutions exist only for binary and symmetric ensembles. As explicit examples, in Corollaries 2 and 3 we explicitly compute the minimum guesswork of any qubit regular polygonal and polyhedral ensebles, respectively. This proves a conjecture [14] on the guesswork of the square qubit ensemble.

In this section we define the guesswork problem. We use standard results from quantum information theory [1].

First, we introduce the sets of ensembles and numbering-valued measurements that appear in the setup of Eq. (3). For any finite dimensional Hilbert space $\mathcal{H}$, we denote with $\mathcal{L}_{+}(\mathcal{H})$ the cone of positive semi-definite operators on $\mathcal{H}$. For any finite set $\mathcal{M}$, we denote with $\mathcal{N}_{\mathcal{M}}$ the set of numberings given by

$\displaystyle\mathcal{N}_{\mathcal{M}}:=\left\{\mathbf{n}:\left\{1,\dots,\left|\mathcal{M}\right|\right\}\to\mathcal{M}\Big{|}\mathbf{n}\textrm{ bijective}\right\}.$

We denote with $\mathcal{E}(\mathcal{M},\mathcal{H})$ the set of ensembles given by

$\displaystyle\mathcal{E}\left(\mathcal{M},\mathcal{H}\right):=\left\{\boldsymbol{\rho}:\mathcal{M}\to\mathcal{L}_{+}\left(\mathcal{H}\right)\Big{|}\sum_{m\in\mathcal{M}}\operatorname{Tr}\left[\boldsymbol{\rho}\left(m\right)\right]=1\right\}.$

and with $\mathcal{P}(\mathcal{N}_{\mathcal{M}},\mathcal{H})$ the set of numbering-valued measurements given by

$\displaystyle\mathcal{P}\left(\mathcal{N}_{\mathcal{M}},\mathcal{H}\right):=\left\{\boldsymbol{\pi}:\mathcal{N}_{\mathcal{M}}\to\mathcal{L}_{+}\left(\mathcal{H}\right)\Big{|}\sum_{\mathbf{n}\in\mathcal{N}_{\mathcal{M}}}\boldsymbol{\pi}\left(\mathbf{n}\right)=\operatorname{\mathds{1}}\right\}.$

Next, we introduce the probability distributions that describe the setup in Eq. (3). For any ensemble $\boldsymbol{\rho}$ and any numbering-valued measurement $\boldsymbol{\pi}$, we denote with $p_{\boldsymbol{\rho},\boldsymbol{\pi}}$ the joint probability distribution that the outcome of $\boldsymbol{\pi}$ is numbering $\mathbf{n}$ and that the $t$-th guess is correct, that is $\mathbf{n}(t)=m$. In formula:

	$\displaystyle p_{\boldsymbol{\rho},\boldsymbol{\pi}}\;:\;$	$\displaystyle\mathcal{N}_{\mathcal{M}}\times\{1,\dots,|\mathcal{M}|\}\longrightarrow[0,1]$
		$\displaystyle\left(\mathbf{n},t\right)\longmapsto\operatorname{Tr}\left[\boldsymbol{\rho}\left(\mathbf{n}\left(t\right)\right)\boldsymbol{\pi}\left(\mathbf{n}\right)\right],$

for any $\boldsymbol{\rho}\in\mathcal{E}(\mathcal{M},\mathcal{H})$ and any $\boldsymbol{\pi}\in\mathcal{P}(\mathcal{N}_{\mathcal{M}},\mathcal{H})$. We denote with $q_{\boldsymbol{\rho},\boldsymbol{\pi}}$ the probability distribution that the $t$-th guess is correct, obtained marginalizing the joint probability distribution $p_{\boldsymbol{\rho},\boldsymbol{\pi}}$. In formula:

	$\displaystyle q_{\boldsymbol{\rho},\boldsymbol{\pi}}\;:\;$	$\displaystyle\left\{1,\dots,|\mathcal{M}|\right\}\longrightarrow\left[0,1\right]$
		$\displaystyle t\longmapsto\sum_{\mathbf{n}\in\mathcal{N}_{\mathcal{M}}}p_{\boldsymbol{\rho},\boldsymbol{\pi}}\left(\mathbf{n},t\right),$

for any $\boldsymbol{\rho}\in\mathcal{E}(\mathcal{M},\mathcal{H})$ and any $\boldsymbol{\pi}\in\mathcal{P}(\mathcal{N}_{\mathcal{M}},\mathcal{H})$.

Finally, we are in a position to introduce the guesswork. The guesswork $G$ is a function mapping any pair $(\boldsymbol{\rho},\boldsymbol{\pi})$ of ensemble and numbering-valued measurement into the expectation value of the number $t$ of guesses, averaged with the probability distribution $q_{\boldsymbol{\rho},\boldsymbol{\pi}}$ of correctness of the $t$-th guess. In formula:

	$\displaystyle G\;:\;$	$\displaystyle\mathcal{E}(\mathcal{M},\mathcal{H})\times\mathcal{P}(\mathcal{N}_{\mathcal{M}},\mathcal{H})\longrightarrow[1,\infty)$
		$\displaystyle\left(\boldsymbol{\rho},\boldsymbol{\pi}\right)\longmapsto\sum_{t=1}^{\left|\mathcal{M}\right|}q_{\boldsymbol{\rho},\boldsymbol{\pi}}\left(t\right)t.$

The minimum guesswork $G_{\textrm{min}}$ is a function mapping any ensemble $\boldsymbol{\rho}$ into the minimum over numbering-valued measurements of the guesswork $G$. In formula:

	$\displaystyle G_{\textrm{min}}\;:\;$	$\displaystyle\mathcal{E}(\mathcal{M},\mathcal{H})\longrightarrow[1,\infty)$
		$\displaystyle\boldsymbol{\rho}\longmapsto\min_{\boldsymbol{\pi}\in\mathcal{P}\left(\mathcal{N}_{\mathcal{M}},\mathcal{H}\right)}G\left(\boldsymbol{\rho},\boldsymbol{\pi}\right).$

In this section we derive the analytical solution of the guesswork problem subject to a finite set of conditions, including any qubit ensemble with uniform probability distribution.

In order to state our main result, we need the following definitions. For any finite dimensional Hilbert space $\mathcal{H}$, we denote with $\mathcal{L}(\mathcal{H})$ the space of Hermitian operators on $\mathcal{H}$. For any finite set $\mathcal{M}$ and any ensemble $\boldsymbol{\rho}\in\mathcal{E}(\mathcal{M},\mathcal{H})$, we denote with $E_{\boldsymbol{\rho}}:\mathcal{N}_{\mathcal{M}}\to\mathcal{L}(\mathcal{H})$ the map given by

$\displaystyle E_{\boldsymbol{\rho}}\left(\mathbf{n}\right)$

$\displaystyle:=\sum_{t=1}^{\left|\mathcal{M}\right|}\left(2t-\left|\mathcal{M}\right|-1\right)\boldsymbol{\rho}\left(\mathbf{n}\left(t\right)\right),$

for any $\mathbf{n}\in\mathcal{N}_{\mathcal{M}}$. For any numbering $\mathbf{n}\in\mathcal{N}_{\mathcal{M}}$, we denote with $\overline{\mathbf{n}}$ the reversed numbering. In formula:

$\displaystyle\overline{\mathbf{n}}\left(t\right):=\mathbf{n}\left(\left|\mathcal{M}\right|+1-t\right),$

for any $t\in\{1,\dots,|\mathcal{M}|\}$. We denote with $\Pi_{-}(\cdot)$ and $\Pi_{0}(\cdot)$ the projectors on the negative and null parts of $(\cdot)$, respectively. We denote with $\{\boldsymbol{\pi}_{\boldsymbol{\rho},\mathbf{n}^{*}}\in\mathcal{P}(\mathcal{N}_{\mathcal{M}})\}_{\mathbf{n}^{*}\in\mathcal{N}_{\mathcal{M}}}$ the family of numbering-valued measurements given by

$\displaystyle\boldsymbol{\pi}_{\boldsymbol{\rho},\mathbf{n}^{*}}\left(\mathbf{n}\right):=\begin{cases}\left(\Pi_{-}+\frac{1}{2}\Pi_{0}\right)\left(E_{\boldsymbol{\rho}}\left(\mathbf{n}\right)\right),&\textrm{if }\mathbf{n}\in\{\mathbf{n}^{*},\overline{\mathbf{n}}^{*}\},\\ 0,&\textrm{otherwise},\end{cases}$

for any $\mathbf{n}^{*},\mathbf{n}\in\mathcal{N}_{\mathcal{M}}$. It follows from Lemma 1 that the corresponding guesswork is given by

$\displaystyle G\left(\boldsymbol{\rho},\boldsymbol{\pi}_{\boldsymbol{\rho},\mathbf{n}^{*}}\right)=\frac{\left|\mathcal{M}\right|+1}{2}-\frac{1}{2}\left\|E_{\boldsymbol{\rho}}\left(\mathbf{n}^{*}\right)\right\|_{1},$

(4)

for any $\mathbf{n}^{*}\in\mathcal{N}_{\mathcal{M}}$.

Upon denoting with $|\cdot|$ the absolute value of operator $(\cdot)$, the following theorem provides analytical solutions of the minimum guesswork problem subject to a finite set of conditions.

We remark that, while the minimum guesswork problem is by definition an optimization over a continuous set, the conditions given by Eq. (5) are finite in number and hence can be checked by exhaustive search. If they hold, Eq. (4) provides the analytical solution of the minimum guesswork problem.

The following corollary provides the analytical solution of the minimum guesswork problem for any qubit ensemble with uniform probability distribution.

We remark that Corollary 1 recasts the minimum guesswork problem, by definition an optimization problem over a continuous set, as an optimization problem over a finite set, that can be therefore performed by exhaustive search.

In this section we provide the minimum guesswork of any qubit regular polygonal or polyhedral ensemble by explicitly solving the optimization over a finite set given by Corollary 1.

In this appendix we derive technical results needed for the derivation of our main results.

For any finite dimensional Hilbert space $\mathcal{H}$ and any operator $A\in\mathcal{L}(\mathcal{H})$, let $\mathcal{P}_{A}:\mathcal{L}(\mathcal{H})\to\mathcal{L}(\mathcal{H})$ be a dephasing map given by $\mathcal{P}_{A}(\cdot)=\sum_{a}\bra{a}\cdot\ket{a}\ket{a}\!\!\bra{a}$, where $\{\ket{a}\}$ is a complete set of eigenvectors of $A$.

The following lemma provides a necessary condition for any measurement to attain the minimum guesswork.

The guesswork of a quantum ensemble quantifies the minimum number of guesses needed in average to correctly guess the state of the ensemble, when only one state can be queried at a time. Here, we derived analytical solutions subject to a finite set of conditions, including analytical solutions for any qubit ensemble with uniform probability distribution, thus disproving the conjecture [13] that analytical solutions only exist for binary and symmetric ensembles. As explicit examples, we computed the guesswork for any qubit regular polygonal and polyhedral ensemble, thus proving a conjecture [14] on the guesswork of the square qubit ensemble.

M. D. is grateful to Eric Hanson and Nilanjana Datta for insightful discussions during a visit to the University of Cambridge. M. D. acknowledges support from MEXT Quantum Leap Flagship Program (MEXT Q-LEAP) Grant No. JPMXS0118067285, JSPS KAKENHI Grant Number JP20K03774, and the International Research Unit of Quantum Information, Kyoto University. F. B. acknowledges support from MEXT Quantum Leap Flagship Program (MEXT Q-LEAP) Grant No. JPMXS0120319794; from MEXT-JSPS Grant-in-Aid for Transformative Research Areas (A) “Extreme Universe”, No. 21H05183; from JSPS KAKENHI Grants No. 19H04066 and 20K03746. T. K. acknowledges support from MEXT Quantum Leap Flagship Program (MEXT Q-LEAP) Grant No. JPMXS0118067285 and No. JPMXS0120319794 and JSPS KAKENHI Grant Number 16H01705, 17H01695, 19K22849 and 21H04879.