State Exclusion

The task of quantum state exclusion Caves et al. (2002) Pusey et al. (2012) Bandyopadhyay et al. (2014) arises from a natural relaxation of the task of quantum state discrimination – particularly in scenarios where deterministic quantum state discrimination is impossible. In this task, a weaker aim is considered, with the player instead being asked to determine states from the set they have not been given by the referee.

State Exclusion Overview¶

In the task of quantum state exclusion, the player therefore aims to identify $k$-states that they have not been given to them by the referee.

1-State Exclusion¶

If the player outputs a single label $g$ such that $g \neq x$ with certainty, this is conclusive 1-state exclusion. This occurs if the player is able to find a POVM such that

If the player gets the measurement outcome associated to $T_{g}$, they output $g$ knowing with certainty the referee could not have sent $\rho_{g}$.

In general, a POVM may not exists that can perform conclusive state exclusion. Instead, state exclusion can be performed with some error, as given by the following SPD:

where $P_{err}$ is the probability of making an error when performing exclusion, meaning the probability of outputting the index $g=x$.

k-State Exclusion¶

If the player outputs a set of $k$ labels, $\{ g_{i} \}^{k}$, such that $g_{i} \neq x ~ \forall ~ g_{i} \in \{g_{i}\}^{k}$ with certainty, this is conclusive $k$-state exclusion. There are $N \choose k$ different sets of $k$ labels the player could exclude, corresponding to all the different subsets of $\{1,\ldots,N\}$ of length $k$. Therefore, when performing $k$-state exclusion the player aims to find a POVM with $N \choose k$ elements such that each measurement outcome allows the player to exclude a subset of states from $\{\rho_{x} \}^{N}$ of length $k$.

k-State Exclusion as 1-State Exclusion¶

All $k$-state exclusion tasks can be recast as 1-state exclusion tasks by reformulating the set $\{\rho_{x}\}^{N}$ Bandyopadhyay et al. (2014). Conceptually, this means all $k$-state exclusion tasks have a 1-state exclusion task that they are dual to, allowing all state exclusion tasks to be studied under the 1-state exclusion framework.

Let $Y_{(N, k)}$ be the set of all subsets of the integers $\{1,2,...,N\}$ of length $k$. The player aims to measure a POVM on a state $\sigma \in \{ \rho_{x} \}^{N}$, given to them by the referee, and output a set of labels $Y \in Y_{(N,k)}$ such that $\sigma \notin \{ \rho_{y} \}_{y \in Y}$. Such a measurement will be a POVM with $a = {N \choose k}$ terms as there are $a$ subsets of $\{1,2,...,N\}$ of length $k$. For each elements of this POVM, $S = \{S_{l}\}^{a}_{l=1}$, the following equation must hold,

By defining

the $k$-state exclusion task can be expressed as the following set of equations

This is now the same form as the 1-state exclusion task conditions. This is the dual 1-state exclusion task to the $k$-state exclusion task.

Using the dual 1-state exclusion task, $k$-state exclusion can also now be formulated as an SPD:

where $P^{k}_{err} > 0$ if no POVM to conclusively perform $k$-state exclusion exists.

$(N-1)$-State Exclusion¶

For an ensemble with $N$ states, performing conclusive $(N-1)$-state exclusion is equivalent to performing deterministic quantum state discrimination: knowing for certain $N-1$ states that you do not have is equivalent to knowing which state you do have. Put alternatively,

where $P_{\mathrm{suc}}$ is maximum success probability in performing quantum state discrimination.

As it is known that $P_{\mathrm{suc}} = 1$ if and only if all states in the ensemble are orthogonal. Hence, $P^{N-1}_{\mathrm{err}} = 0$ if and only if all states in the ensemble are orthogonal.

Conclusive state discrimination can therefore be considered to be a special case of conclusive $k$-state exclusion. How the two tasks are related in the non-conclusive case, and for $k< N-1$, remains an active area of research.

Sub-Channel Exclusion¶

A closely related task to state exclusion is sub-channel exclusion. A special case of sub-channel exclusion concerns a collection of completely-positive trace non-increasing linear maps, $\Psi = \{\Psi_{x}\}_{x=1}^N$, such that $\sum_{x=1}^N \Psi_{x}$ is a channel. This collection is a quantum instrument, with each map $\Psi_{x}$ called a sub-channel.

In this task, a player has a reference state $\rho$ that they send to the referee. The referee then measures $\rho$ using the instrument and returns the post-measurement state to the player. The player measures a POVM on the state and outputs a label $g \in \{1, \ldots ,N\}$. They succeed if they output a label of a sub-channel that was not applied. As before, the player can output the label of a sub-channel not applied with certainty, they can output $k$ labels, $\{ g_{i} \}^{k}_{i=1}$, or they can output $k$ labels with certainty.

Weak and Strong Exclusion¶

Here we introduce the notion of weak and strong state exclusion, defined in Stratton et al. (2024).

The additional condition in strong state exclusion ensures that all outcomes of the POVM $\{T_{a}\}_{a=1}^{N}$ have some probability of occurring. Strong conclusive 1-state exclusion on the set $\{ \rho_{x} \}^{N}_{x=1}$ is defined to be the existence of an $N$ element POVM where each element excludes a different state from $\{ \rho_{x} \}^{N}_{x=1}$ with certainty.

Weak conclusive 1-state exclusion on $\{ \rho_{x} \}^{N}_{x=1}$ is defined to be the existence of a POVM with $L$ non-zero elements, where $L\leq N$, such that each conclusively exclude a different state from a subset of $\{ \rho_{x} \}^{N}_{x=1}$ of size $L$. Seen Figure 1 for an example.

When extended to $k$-state exclusion, strong exclusion means that there exists a POVM that can exclude all possible sub-sets of $\{ \rho_{x} \}^{N}_{x=1}$ of length $k$. Weak exclusion then means that there exists a POVM that can only exclude some subsets of $\{ \rho_{x} \}^{N}_{x=1}$ of length $k$. Note, this is equivalent to considering strong and weak exclusion on the equivalent 1-state exclusion task.