In this tutorial we are going to cover the problem of quantum state
distinguishability (sometimes analogously referred to as quantum state
discrimination). We are going to briefly describe the problem setting and
then describe how one may use qustop
to calculate the optimal
probability with which this problem can be solved when given access to
certain measurements.
Further information beyond the scope of this tutorial can be found in the text [WatrousQI] as well as the course [SikoraSDP].
The quantum state distinguishability problem is phrased as follows.
Alice possesses an ensemble of n quantum states:
\begin{equation} \eta = \left( (p_0, \rho_0), \ldots, (p_n, \rho_n) \right), \end{equation}
where p_i is the probability with which state \rho_i is selected from the ensemble. Alice picks \rho_i with probability p_i from her ensemble and sends \rho_i to Bob.
- Bob receives \rho_i. Both Alice and Bob are aware of how the ensemble is defined but he does not know what index i corresponding to the state \rho_i he receives from Alice is.
- Bob wants to guess which of the states from the ensemble he was given. In order to do so, he may measure \rho_i to guess the index i for which the state in the ensemble corresponds.
This setting is depicted in the following figure.
- Minimum-error discrimination:
Minimize the average probability of making an error in conclusively identifying the state.
- Unambiguous discrimination:
Never give an incorrect answer, although the answer can be inconclusive.
Depending on the sets of measurements that Alice and Bob are allowed to use, the optimal probability of distinguishing a given set of states is characterized by the following image.
That is, the probability that Alice and Bob are able to distinguish using PPT measurements is a natural upper bound on the optimal probability of distinguishing via separable measurements and so on.
In general:
- LOCC: These are difficult objects to handle mathematically; difficult to design protocols for and difficult to provide bounds on their power.
- Separable: Separable measurements have a nicer structure than LOCC. Unfortunately, optimizing over separable measurements in NP-hard.
- PPT: PPT measurements offer a nice structure and there exists efficient techniques that allow one to optimize over the set of PPT measurements via semidefinite programming.
- Positive: These measurements are the most general and constitute the set of all valid quantum operations that Alice and Bob can perform. The optimal value of distinguishing via positive operations can be phrased as an SDP.
The optimal probability of distinguishing using positive measurements serves as an upper bound on the optimal probability of distinguishing using PPT, separable, and LOCC measurements. Specifically, given an ensemble of quantum states, \eta, it holds that
0 \leq \text{opt}_{\text{LOCC}}(\eta) \leq \text{opt}_{\text{SEP}}(\eta) \leq \text{opt}_{\text{PPT}}(\eta) \leq \text{opt}_{\text{POS}}(\eta) \leq 1
where:
- \text{opt}_{\text{POS}}(\eta) represents the optimal probability of distinguishing using positive measurements,
- \text{opt}_{\text{PPT}}(\eta) represents the probability of distinguishing via PPT measurements,
- \text{opt}_{\text{SEP}}(\eta) represents the probability of distinguishing via separable measurements,
- \text{opt}_{\text{LOCC}}(\eta) represents the probability of distinguishing via LOCC measurements.
[WatrousQI] | Watrous, John "The theory of quantum information" Section: "A semidefinite program for optimal measurements" Cambridge University Press, 2018 |
[SikoraSDP] | Sikora, Jamie "Semidefinite programming in quantum theory (lecture series)" Lecture 2: Semidefinite programs for nice problems and popular functions Perimeter Institute for Theoretical Physics, 2019 |