Distinguishing quantum states via separable measurements

As previously mentioned, optimizing over the set of separable measurements is NP-hard. However, there does exist a hierarchy of semidefinite programs which eventually does converge to the separable value. This hierarchy is based off the notion of symmetric extensions. More information about this hierarchy of SDPs can be found here [Nav08].

Minimum-error distinguishability via separable measurements

\[\begin{split}\begin{equation} \begin{aligned} \textbf{Primal:} \quad & \\ \text{maximize:} \quad & \sum_{k=1}^N p_k \langle \rho_k, \mu(k) \rangle, \\ \text{subject to:} \quad & \sum_{k=1}^N \mu(k) = \mathbb{I}_{\mathcal{X} \otimes \mathcal{Y}}, \\ & \text{Tr}_{\mathcal{Y}_2 \otimes \ldots \otimes \mathcal{Y}_s}(X_k) = \mu(k), \\ & \left( \mathbb{I}_{\mathcal{X}} \otimes \Pi_{\mathcal{Y} \ovee \mathcal{Y}_2 \ovee \ldots \ovee \mathcal{Y}_s} \right) X_k \left(\mathbb{I}_{\mathcal{X}} \otimes \Pi_{\mathcal{Y} \ovee \mathcal{Y}_2 \ovee \ldots \ovee \mathcal{Y}_s} \right) = X_k \\ & \text{T}_{\mathcal{X}}(X_k) \in \text{Pos}\left( \mathcal{X} \otimes \mathcal{Y} \otimes \mathcal{Y}_2 \otimes \ldots \otimes \mathcal{Y}_s \right), \\ & \text{T}_{\mathcal{Y}_2} (X_k) \in \text{Pos}\left( \mathcal{X} \otimes \mathcal{Y} \otimes \mathcal{Y}_2 \otimes \ldots \otimes \mathcal{Y}_s \right), \\ & \vdots \\ & \text{T}_{\mathcal{Y}_s} (X_k) \in \text{Pos}\left( \mathcal{X} \otimes \mathcal{Y} \otimes \mathcal{Y}_2 \otimes \ldots \otimes \mathcal{Y}_s \right), \\ & X_1, \ldots, X_N \in \text{Pos}\left(\mathcal{X} \otimes \mathcal{Y} \otimes \mathcal{Y}_2 \otimes \ldots \otimes \mathcal{Y}_s \right). \end{aligned} \end{equation}\end{split}\]

\[\begin{split}\begin{equation} \begin{aligned} \textbf{Dual:} \quad & \\ \text{minimize:} \quad & \text{Tr}(H), \\ \text{subject to:} \quad & H - Q_k \geq p_k \rho_k, \\ & Q_k \otimes \mathbb{I}_{\mathcal{Y}_2 \otimes \ldots \otimes \mathcal{Y}_s} + \left(\mathbb{I}_{\mathcal{X}} \otimes \Pi_{\mathcal{Y} \ovee \mathcal{Y}_2 \ldots \ovee \mathcal{Y_s}} \right) R_k \left(\mathbb{I}_{\mathcal{X}} \otimes \Pi_{\mathcal{Y} \ovee \mathcal{Y}_2 \ldots \ovee \mathcal{Y_s}} \right) \\ & \quad - R_k - \text{T}_{\mathcal{X}}(S_k) - \text{T}_{\mathcal{Y}}(Z_k) \in \text{Pos}(\mathcal{X} \otimes \mathcal{Y} \otimes \mathcal{Y}_2 \otimes \ldots \otimes \mathcal{Y}_s) \\ & H, Q_1, \ldots, Q_N \in \text{Herm}(\mathcal{X} \otimes \mathcal{Y}), \\ & R_1, \ldots R_N \in \text{Herm}(\mathcal{X} \otimes \mathcal{Y} \otimes \mathcal{Y}_2 \otimes \ldots \otimes \mathcal{Y}_s), \\ & S_1, \ldots, S_N, Z_1, \ldots, Z_N \in \text{Pos}(\mathcal{X} \otimes \mathcal{Y} \otimes \mathcal{Y}_2 \otimes \ldots \otimes \mathcal{Y}_s). \end{aligned} \end{equation}\end{split}\]

Entanglement cost of distinguishing Bell states

One may ask whether the ability to distinguish a state can be improved by making use of an auxiliary resource state.

\[\begin{equation} | \tau_{\epsilon} \rangle = \sqrt{\frac{1+\epsilon}{2}} | 00 \rangle + \sqrt{\frac{1-\epsilon}{2}} | 11 \rangle, \end{equation}\]

for some \(\epsilon \in [0,1]\).

Distinguishing four Bell states

It was shown in [BCJRWY15] that the probability of distinguishing four Bell states with a resource state via separable measurements is given by the closed-form expression:

\[\begin{equation} \text{opt}_{\text{PPT}}(\eta) = \text{opt}_{\text{SEP}}(\eta) = \frac{1}{2} \left(1 + \sqrt{1 - \epsilon^2} \right) \end{equation}\]

where the ensemble is defined as

\[\begin{equation} \eta = \left\{ | \psi_0 \rangle \otimes | \tau_{\epsilon} \rangle, | \psi_1 \rangle \otimes | \tau_{\epsilon} \rangle, | \psi_2 \rangle \otimes | \tau_{\epsilon} \rangle, | \psi_3 \rangle \otimes | \tau_{\epsilon} \rangle \right\}. \end{equation}\]

Using qustop, we may encode this scenario as follows.

import numpy as np
from toqito.states import basis, bell

from qustop import Ensemble, OptDist, State

e_0, e_1 = basis(2, 0), basis(2, 1)

eps = 0.5
tau = np.sqrt((1 + eps) / 2) * np.kron(e_0, e_0) + np.sqrt(
    (1 - eps) / 2
) * np.kron(e_1, e_1)

dims = [2, 2, 2, 2]
ensemble = Ensemble(
    [
        State(np.kron(bell(0), tau), dims),
        State(np.kron(bell(1), tau), dims),
        State(np.kron(bell(2), tau), dims),
        State(np.kron(bell(3), tau), dims),
    ],
    [1 / 4, 1 / 4, 1 / 4, 1 / 4],
)

ppt_res = OptDist(ensemble, "ppt", "min-error")
ppt_res.solve()

sep_res = OptDist(ensemble, "sep", "min-error")
sep_res.solve()

eq = 1 / 2 * (1 + np.sqrt(1 - eps ** 2))

# 0.9330127018922193
print(eq)
# 0.9330127016540999
print(ppt_res.value)
# 0.9330127016540999
print(sep_res.value)

Note that [BCJRWY15] also proved the same closed-form expression for when Alice and Bob make use of PPT measurements (which is an upper bound for separable measurements). More on that in the tutorial on distinguishing via PPT measurements.

Distinguishing three Bell states

It was also shown in [BCJRWY15] that the closed-form probability of distinguishing three Bell states with a resource state using separable measurements to be given by the closed-form expression:

\[\begin{equation} \text{opt}_{\text{SEP}}(\eta) = \frac{1}{3} \left( 2 + \sqrt{1 - \epsilon^2} \right) \end{equation}\]

where the ensemble is defined as

\[\begin{equation} \eta = \left( | \psi_0 \rangle \otimes | \tau_{\epsilon} \rangle, | \psi_1 \rangle \otimes | \tau_{\epsilon} \rangle, | \psi_2 \rangle \otimes | \tau_{\epsilon} \rangle \right). \end{equation}\]

Using qustop, we may encode this scenario as follows.

import numpy as np
from toqito.states import basis, bell

from qustop import Ensemble, OptDist, State

e_0, e_1 = basis(2, 0), basis(2, 1)

eps = 0.5
tau = np.sqrt((1 + eps) / 2) * np.kron(e_0, e_0) + np.sqrt(
    (1 - eps) / 2
) * np.kron(e_1, e_1)

dims = [2, 2, 2, 2]
states = [
    State(np.kron(bell(0), tau), dims),
    State(np.kron(bell(1), tau), dims),
    State(np.kron(bell(2), tau), dims),
]
probs = [1 / 3, 1 / 3, 1 / 3]
ensemble = Ensemble(states, probs)
ensemble.swap([2, 3])

sep_res = OptDist(ensemble, "sep", "min-error", level=2)
sep_res.solve()

eq = 1 / 3 * (2 + np.sqrt(1 - eps ** 2))

# 0.9553418012614794
print(eq)

# 0.9583970406126399
print(sep_res.value)

Note that the value of sep_res.value is actually a bit higher than eq. This is because the separable value is calculated by a hierarchy of SDPs. At low levels of the SDP, the problem can often converge to the optimal value, but other times it is necessary to compute higher levels of the SDP to eventually arrive at the optimal value. While this is intractable in general, in practice, the SDP can often converge, or at least get fairly close to the optimal value for small problem sizes.

Unextendible product bases and separable measurements

For complex Euclidean spaces \(\mathcal{X}\) and \(\mathcal{Y}\), an unextendable product basis is defined as an orthonormal collection of vectors

\[\begin{equation} \mathcal{U} = \left\{u_1 \otimes v_1, \ldots, u_m \otimes v_m \right\} \subset \mathcal{X} \otimes \mathcal{Y}, \end{equation}\]

for unit vectors \(u_1, \ldots, u_m \in \mathcal{X}\) and \(v_1, \ldots, v_m \in \mathcal{Y}\) where:

1. \(m < \text{dim}(\mathcal{X} \otimes \mathcal{Y})\).

2. For every \(x \in \mathcal{X}\) and \(y \in \mathcal{Y}\) satisfying \(x \otimes y \perp \mathcal{U}\) it holds that \(x \otimes y = 0\).

All UPBs are known to be indistinguishable by LOCC measurements and all UPBs are distinguishable by PPT measurements. As separable measurements lie in between LOCC and PPT measurements, it is of interest to know which UPBs are distinguishable by separable measurements.

For instance, in [DMSST99], it was shown that all UPBs in \(\mathbb{C}^3 \otimes \mathbb{C}^3\) are perfectly distinguishable via separable measurements.

Consider the “Tiles” UPB

\[\begin{split}\begin{equation} \begin{array}{llll} | \phi_0 \rangle = | 0 \rangle \left(\frac{| 0 \rangle - | 1 \rangle}{\sqrt{2}}\right), &| \phi_1 \rangle = | 2 \rangle\left(\frac{| 1 \rangle - | 2 \rangle }{\sqrt{2}}\right), \\ | \phi_2 \rangle = \left(\frac{| 0 \rangle - | 1 \rangle}{\sqrt{2}}\right)| 2 \rangle, &| \phi_3 \rangle = \left(\frac{| 1 \rangle - | 2 \rangle}{\sqrt{2}}\right)| 0 \rangle,\\ | \phi_4 \rangle = \frac{1}{3}\left(| 0 \rangle + | 1 \rangle + | 2 \rangle\right), \left(| 0 \rangle + | 1 \rangle + | 2 \rangle \right). \end{array} \end{equation}\end{split}\]

Note that the “Tiles” states are contained in \(\mathbb{C}^3 \otimes \mathbb{C}^3\). We can use qustop to indeed verify that these states are perfectly distinguishable via separable measurements.

from toqito.states import basis, tile

from qustop import Ensemble, OptDist, State

# Construct the corresponding density matrices of the Tiles UPB.
dims = [3, 3]
ensemble = Ensemble(
    [
        State(tile(0) * tile(0).conj().T, dims),
        State(tile(1) * tile(1).conj().T, dims),
        State(tile(2) * tile(2).conj().T, dims),
        State(tile(3) * tile(3).conj().T, dims),
        State(tile(4) * tile(4).conj().T, dims),
    ]
)
res = OptDist(ensemble, "sep", "min-error", level=2)
res.solve()

# 0.999999
print(res.value)

In [BCJRWY15], it was shown that the 8-state UPB contained in \(\mathbb{C}^4 \otimes \mathbb{C}^4\) introduced in [Feng06] defined as

\[\begin{split}\begin{equation} \begin{array}{ll} | \phi_1 \rangle = | 0 \rangle | 0 \rangle, & | \phi_5 \rangle = \left(| 1 \rangle + | 2 \rangle + | 3 \rangle \right)\left(| 0 \rangle - | 1 \rangle + | 2 \rangle \right)/3, \\ | \phi_2 \rangle = | 1 \rangle \left(| 0 \rangle - | 2 \rangle + | 3 \rangle \right)/\sqrt{3}, \quad & | \phi_6 \rangle = \left(| 0 \rangle - | 2 \rangle + | 3 \rangle \right)| 2 \rangle/\sqrt{3}, \\ | \phi_3 \rangle = | 2 \rangle \left(| 0 \rangle + | 1 \rangle - | 3 \rangle \right)/\sqrt{3}, & | \phi_7 \rangle = \left(| 0 \rangle + | 1 \rangle - | 3 \rangle \right)| 1 \rangle/\sqrt{3}, \\ | \phi_4 \rangle = | 3 \rangle | 3 \rangle, & | \phi_8 \rangle = \left(| 0 \rangle - | 1 \rangle + | 2 \rangle \right)\left(| 1 \rangle + | 2 \rangle + | 3 \rangle \right)/3. \end{array} \end{equation}\end{split}\]

is not perfectly distinguishable via separable measurements. This can be observed using qustop as follows.

import numpy as np
from toqito.states import basis

from qustop import Ensemble, OptDist, State

e_0, e_1, e_2, e_3 = basis(4, 0), basis(4, 1), basis(4, 2), basis(4, 3)

phi_1 = np.kron(e_0, e_0)
phi_2 = np.kron(e_1, (e_0 - e_2 + e_3) / np.sqrt(3))
phi_3 = np.kron(e_2, (e_0 + e_1 - e_3) / np.sqrt(3))
phi_4 = np.kron(e_3, e_3)
phi_5 = np.kron((e_1 + e_2 + e_3), (e_0 - e_1 + e_2) / 3)
phi_6 = np.kron((e_0 - e_2 + e_3), e_2 / np.sqrt(3))
phi_7 = np.kron((e_0 + e_1 - e_3), e_1 / np.sqrt(3))
phi_8 = np.kron((e_0 - e_1 + e_2), (e_1 + e_2 + e_3) / 3)

dims = [4, 4]
ensemble = Ensemble(
    [
        State(phi_1, dims),
        State(phi_2, dims),
        State(phi_3, dims),
        State(phi_4, dims),
        State(phi_5, dims),
        State(phi_6, dims),
        State(phi_7, dims),
        State(phi_8, dims),
    ]
)
res = OptDist(ensemble, "sep", "min-error", level=2)
res.solve()

# 0.9967296337698935
print(res.value)

Impossibility to distinguish a UPB plus one extra pure state

It was shown in [BCJRWY15] that if we consider an ensemble of states consisting of a UPB along with a pure state that is orthogonal to all states in said ensemble, then it is impossible to perfectly distinguish this ensemble.

\[\begin{split}\begin{equation} \begin{array}{llll} | \phi_0 \rangle = | 0 \rangle \left(\frac{| 0 \rangle - | 1 \rangle}{\sqrt{2}}\right), &| \phi_1 \rangle = | 2 \rangle\left(\frac{| 1 \rangle - | 2 \rangle }{\sqrt{2}}\right), \\ | \phi_2 \rangle = \left(\frac{| 0 \rangle - | 1 \rangle}{\sqrt{2}}\right)| 2 \rangle, &| \phi_3 \rangle = \left(\frac{| 1 \rangle - | 2 \rangle}{\sqrt{2}}\right)| 0 \rangle,\\ | \phi_4 \rangle = \frac{1}{3}\left(| 0 \rangle + | 1 \rangle + | 2 \rangle\right) \left(| 0 \rangle + | 1 \rangle + | 2 \rangle \right), & | \phi_5 \rangle = \frac{1}{2} \left( | 0 \rangle | 0 \rangle + | 0 \rangle | 1 \rangle - | 0 \rangle | 2 \rangle - | 1 \rangle | 2 \rangle \right) \end{array} \end{equation}\end{split}\]

import numpy as np
from toqito.states import basis, tile

from qustop import Ensemble, OptDist, State

dims = [3, 3]
e_0, e_1, e_2 = basis(3, 0), basis(3, 1), basis(3, 2)

# Define a pure state to add to the ensemble.
psi = (
    1
    / 2
    * (
        np.kron(e_0, e_0)
        + np.kron(e_0, e_1)
        - np.kron(e_0, e_2)
        - np.kron(e_1, e_2)
    )
)

# Construct the corresponding density matrices of the Tiles UPB + pure state:
ensemble = Ensemble(
    [
        State(tile(0) * tile(0).conj().T, dims),
        State(tile(1) * tile(1).conj().T, dims),
        State(tile(2) * tile(2).conj().T, dims),
        State(tile(3) * tile(3).conj().T, dims),
        State(tile(4) * tile(4).conj().T, dims),
        State(psi * psi.conj().T, dims),
    ]
)

res = OptDist(ensemble, "sep", "min-error", level=2)
res.solve()

# 0.9860588510298623
print(res.value)

References

Nav08

Navascués, Miguel. “Pure state estimation and the characterization of entanglement.” Physical review letters 100.7 (2008): 070503. https://arxiv.org/abs/0707.4398

DMSST99

DiVincenzo, David P., et al. “Unextendible product bases, uncompletable product bases and bound entanglement.” Communications in Mathematical Physics 238.3 (2003): 379-410.

Feng06

Feng, Keqin. “Unextendible product bases and 1-factorization of complete graphs.” Discrete applied mathematics 154.6 (2006): 942-949.