-
Notifications
You must be signed in to change notification settings - Fork 0
/
discrimination.tex
631 lines (570 loc) · 29.8 KB
/
discrimination.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
%!TEX root = thesis.tex
%-------------------------------------------------------------------------------
\chapter{Bipartite state discrimination}
\label{chap:bipartite-state-discrimination}
%-------------------------------------------------------------------------------
This chapter introduces the problem of discriminating quantum states
from a known set.
A scenario describing the problem is first presented for the case where the
unknown state is given to a single individual, and then generalized to a
different scenario where the unknown state is distributed to two parties.
In this thesis we will focus on the bipartite case, leaving for future work
an extension of the results to the multipartite case.
After the problem description, this chapter reviews relevant background work,
including prior results on the local distinguishability of
two classes of pure states that will be the object of study in the following
chapters: maximally entangled states and product states.
\minitoc
%-------------------------------------------------------------------------------
\section{Problem description}
%-------------------------------------------------------------------------------
\subsection*{Global state discrimination}
An instance of the state discrimination problem is defined by a complex
Euclidean space $\X$, a positive integer $N$, and by an ensemble $\E$ of $N$
states, that is,
\begin{equation}
\label{eq:global-ensemble}
\E = \big\{ (p_{1}, \rho_{1}), \ldots, (p_{N}, \rho_{N}) \big\},
\end{equation}
where $(p_{1}, \ldots, p_{N})$ is a probability vector
and $\rho_{1}, \ldots, \rho_{N} \in \Density(\X)$ are density operators representing
quantum states.
We denote the set of all ensemble of this kind by $\Ens(N, \X)$.
The problem is formally described by the following
scenario, which involves two individuals, Alice and Charlie (the reader who misses
Bob can be reassured that he will join us soon).
Charlie picks an index
\[
k \in \{1, \ldots, N \},
\]
according to the probability distribution $(p_{1}, \ldots, p_{N})$,
prepares a quantum register $\reg{X}$ with the state $\rho_{k} \in \Density(\X)$,
and sends it to Alice, whose task is to identify the index $k$ by performing a measurement on the
register $\reg{X}$.
For Alice performing a measurement
\begin{equation}
\label{eq:global-measurement}
\mu : \{1, \ldots, N\} \rightarrow \Pos(\X),
\end{equation}
the probability that she correctly distinguishes $\E$ is given by the expression
\begin{equation}
\label{eq:opt-value-fixed-measurement}
\opt(\E, \mu) = \sum_{k=1}^{N}p_{k}\ip{\mu(k)}{\rho_{k}}.
\end{equation}
Since $\mu$ is a measurement and $\rho_{1}, \ldots, \rho_{N}$ are density
operators, it is clear that
\begin{equation}
\label{eq:ip-bounds}
0 \leq \ip{\mu(k)}{\rho_{k}} \leq 1,
\end{equation}
for each $k \in \{1, \ldots, N \}$.
Moreover, since $p$ is a probability vector, we have that
\begin{equation}
0 \leq \opt(\E, \mu) \leq 1.
\end{equation}
We denote by $\opt(\E)$ the maximum probability of distinguishing $\E$ for any
possible measurement, that is,
\begin{equation}
\label{eq:opt-value}
\opt(\E) = \max_{\mu\in\Meas(N, \X)}\opt(\E, \mu).
\end{equation}
We say that $\E$ is \emph{distinguishable with probability at least $p$} if we
have $\opt(\E) \geq p$. Whenever $\E$ is distinguishable with probability $1$, we say
that $\E$ is \emph{perfectly distinguishable} or that Alice can distinguish
$\E$ \emph{with certainty}.
The probability distribution with which the states are selected is not important
if we are only interested in perfect distinguishability.
In fact, from the bounds in Eq.~\eqref{eq:ip-bounds} and a standard convexity argument,
for any probability vector $p = (p_{1}, \ldots, p_{N})$, it holds that
\begin{equation}
\sum_{k=1}^{N}p_{k}\ip{\mu(k)}{\rho_{k}} = 1
\end{equation}
if and only if
\begin{equation}
\ip{\mu(k)}{\rho_{k}} = 1,
\end{equation}
for each $k \in \supp(p)$.
For this reason, whenever we are only interested in a qualitative result
(whether perfect distinguishability holds or not), we will take $p$ to be the uniform
distribution, that is, $p = (1/N, \ldots, 1/N)$. In such cases, we will simply
denote the ensemble by the list of its states, that is,
\begin{equation}
\E = \{\rho_{1}, \ldots, \rho_{N}\}.
\end{equation}
We will often be interested in the distinguishability of pure-state ensembles,
where each density operator is a rank-one projector, that is, for each
$k \in \{1, \ldots, N\}$, $\rho_{k} = u_{k}u_{k}^{\ast}$,
for a list of unit vectors $\{u_{1}, \ldots, u_{N}\} \in \X$.
In such case, by a further abuse of notation, we simply denote the ensemble by
a list of its vectors:
\begin{equation}
\E = \{u_{1}, \ldots, u_{N}\}.
\end{equation}
If the states are mutually orthogonal, that is,
\begin{equation}
\ip{\rho_{i}}{\rho_{j}} = 0,
\end{equation}
for all $i,j \in \{1, \ldots, N\}$ with $i \neq j$, there is a measurement
that perfectly distinguishes them.
Consider the spectral decomposition of each state:
\begin{equation}
\rho_{k} = \sum_{i=1}^{r_{k}}\lambda_{i}x_{k,i}x_{k,i}^{\ast},
\end{equation}
with $\lambda_{1}, \ldots, \lambda_{r_{k}}$ being positive real numbers
and $\{x_{k,1}, \ldots, x_{k,r_{k}}\} \subset \X$ being an orthonormal set.
Alice can then construct the quantum measurement that perfectly distinguishes
the states, by defining the following measurement operators:
\begin{equation}
\mu(k) = \sum_{i=1}^{r_{k}}x_{k,i}x_{k,i}^{\ast},
\end{equation}
for each $k = 1,\ldots,N-1$, and
\begin{equation}
\mu(N) = \I_{\X} - \sum_{k=1}^{N-1}\mu(k).
\end{equation}
It is clear that $\mu$ is a valid measurement and that
\begin{equation}
\ip{\mu(k)}{\rho_{k}} = 1,
\end{equation}
for all $k \in \{1, \ldots, N\}$.
Global distinguishability of non-orthogonal states is a prolific topic on its own and
a treatment of it is outside the scope of this thesis.
For an exposition of results regarding global state discrimination,
the reader is referred to numerous surveys on the topic \cite{Chefles2000, Bergou2004}.
\subsection*{Bipartite state discrimination}
This dissertation focuses on a modification of the above scenario in which we
have three individuals involved: Alice, Bob, and Charlie.
In this new scenario, the states to be distinguished lie on the tensor product of
two complex Euclidean spaces, which we label by $\X$ and $\Y$ and which are
held respectively by Alice and Bob.
In other words, the ensemble consists of $N$ bipartite states represented
by the density matrices $\rho_{1}, \ldots, \rho_{N} \in \Density(\X\otimes\Y)$.
Charlie picks an index $k \in \{1, \ldots, N\}$ and prepares the corresponding
state $\rho_{k} \in \Density(\X\otimes\Y)$ on a pair of quantum registers
$(\reg{X},\reg{Y})$ that belong to Alice and Bob, in the sense that the
underlying space is $\X\otimes\Y$.
Their task is to identify the index $k$ chosen by Charlie, by means of an LOCC
measurement on $(\reg{X},\reg{Y})$.
We will denote by $\opt_{\LOCC}(\E)$ the maximum success probability for
Alice and Bob to distinguish an ensemble $\E\in\Ens(N, \X\otimes\Y)$ by means of
any LOCC measurement, that is,
\begin{equation}
\label{eq:opt-LOCC}
\opt_{\LOCC}(\E) = \max_{\mu \in \Meas_{\LOCC}(N, \X:\Y)}\opt(\E, \mu).
\end{equation}
As it was discussed in Section \ref{sec:quantum-measurements}, the set of
LOCC measurements has a complex mathematical structure.
For this reason, the state discrimination problem has been analyzed for more
tractable classes of measurements that approximate, in some sense,
the LOCC measurements.
Among these, the classes of separable and PPT measurements are the most studied,
because of their nice mathematical and computational properties.
We denote by $\opt_{\Sep}(\E)$ and $\opt_{\PPT}(\E)$ the optimal probability of
distinguishing an ensemble
$
\E \in \Ens(N, \X\otimes\Y)
$
by separable and PPT measurements, respectively:
\begin{equation}
\label{eq:opt-Sep}
\opt_{\Sep}(\E) = \max_{\mu \in \Meas_{\Sep}(N, \X:\Y)}\opt(\E, \mu),
\end{equation}
and
\begin{equation}
\label{eq:opt-PPT}
\opt_{\PPT}(\E) = \max_{\mu \in \Meas_{\PPT}(N, \X:\Y)}\opt(\E, \mu).
\end{equation}
In lights of the containments pictured by the diagram in Figure \ref{fig:classes-measurements},
we have the following chain of inequalities:
\begin{equation}
\label{eq:inequality-chain}
\opt_{\LOCC}(\E) \leq \opt_{\Sep}(\E) \leq \opt_{\PPT}(\E) \leq \opt(\E),
\end{equation}
for any ensemble $\E$.
Interestingly, for each of these inequalities, there exists a set of states
that makes the inequality strict. For example, an ensemble for which the first
inequality is strict was given by \cite{Bennett99}.
One example that illustrates the difference between the power of separable and
PPT measurements was given in \cite{Terhal01} (more details on the set of states
corresponding to this example are given in Chapter \ref{chap:ups} of this thesis.)
Finally, there are many examples of states that can be perfectly distinguished by
global measurements, but are not perfectly distinguishable by PPT measurement.
The section that immediately follows the present one reviews one of such examples.
One contribution of this thesis is that it presents new discrimination tasks for which
PPT measurements perform strictly better than separable measuerements.
Characteristic to our examples is the fact that the sets for which we show the separation
are composed either fully of maximally entangled states, or fully of product states.
In most of our examples and in most prior works on bipartite state discrimination,
the states are taken to be pure and orthogonal, so that a global measurement can
trivially discriminate them with certainty, that is, $\opt(\E) = 1$.
In such cases, a separation between $\opt(\E)$ and, say, $\opt_{\LOCC}(\E)$ is obtained
by showing that the set of states is not perfectly distinguishable by LOCC measurements.
\section{Discriminating between pairs of states}
A case of particular interest is when there are two states to be distinguished,
chosen with equal probability.
This is equivalent to the quantum data hiding challenge in which a secret bit
$b \in \{0,1\}$ is required to be hidden into a bipartite state
$\sigma_{b}\in\Density(\X\otimes\Y)$. In the language of the previous section,
we say that quantum data hiding is possible if there exists an ensemble
\begin{equation}
\E = \left\{\left(\frac{1}{2},\sigma_{0}\right),
\left(\frac{1}{2},\sigma_{1}\right)\right\}
\end{equation}
such that two conditions are simultaneously satisfied:
\begin{itemize}
\item[(a)] $\opt(\E) = 1$, and
\item[(b)] $\opt_{\LOCC}(\E) \leq 1/2 + \varepsilon$,
\end{itemize}
for some ``small'' values of $\varepsilon$. The exact bounds on
$\varepsilon$ define the strength of the hiding scheme and,
of course, depend on the dimensions of Alice's and Bob's spaces.
The condition (a) above is equivalent to requiring the two states to be
orthogonal\footnote{We could be more general here and define another parameter
$\delta \approx 0$ so to weaken Condition (a) to be $\opt(\E) \geq 1 - \delta$.
This would not affect the discussion that follows, except for making the
presentation less clean.}.
A consequence of this is that at least one of them must be a mixed,
since a result by Walgate, et al. \cite{Walgate00} shows that any two orthogonal
bipartite \emph{pure} states can be perfectly distinguished by LOCC.
The problem of discriminating between two quantum states is also
interesting for its connection with operator norms.
In particular, a connection between the trace norm and the
optimal probability of distinguishing two states by means of global measurements
is estabilished by the following theorem.
\begin{theorem}[Holevo-Helstrom]
Given a complex Euclidean space $\X$ and two density operators
$\sigma_{0}, \sigma_{1} \in \Density(\X)$, it holds that
\begin{equation}
\opt(\{\sigma_{0},\sigma_{1}\}) =
\frac{1}{2} + \frac{1}{4}\norm{\sigma_{0}-\sigma_{1}}_{1}.
\end{equation}
\end{theorem}
By reversing the logic direction of this theorem, one can define operator norms
starting from different set of measurements.
This approach was taken in \cite{Matthews09}, where the so-called $\LOCC$-norm
was defined so that the following holds:
\begin{equation}
\opt_{\LOCC}(\{\sigma_{0},\sigma_{1}\}) =
\frac{1}{2} + \frac{1}{4}\norm{\sigma_{0}-\sigma_{1}}_{\LOCC}.
\end{equation}
Similarly, one may define norms $\norm{\cdot}_{\PPT}$ and $\norm{\cdot}_{\Sep}$
that correspond to distinguishability by PPT and separable measurements,
respectively. (For a recent result concerning these norms, see \cite{Aubrun15}.)
\begin{example}[Werner hiding pairs]
\label{example:werner-hiding-pairs}
One typical quantum data hiding scheme \cite{Terhal01a,DiVincenzo2002} encodes
the hidden classical bit in a \emph{Werner hiding pair}.
For any positive integer $n \geq 2$, let
$W_{n} \in \Unitary(\complex^{n}\otimes\complex^{n})$ be the swap operator
defined in Eq.~\eqref{eq:swap-operator}.
A Werner hiding pair in $\complex^{n}\otimes\complex^{n}$ is defined by two states
\begin{equation}
\label{eq:werner-states}
\sigma_{0}^{(n)} = \frac{\I\otimes\I + W_{n}}{n(n+1)}
\hspace*{1cm}\mbox{and}\hspace*{1cm}
\sigma_{1}^{(n)} = \frac{\I\otimes\I - W_{n}}{n(n-1)}.
\end{equation}
% and let $\E^{(n)} = \{\sigma_{0}^{(n)},\sigma_{1}^{(n)}\}$.
Notice that $\sigma_{0}^{(n)}$ and $\sigma_{1}^{(n)}$ are also the normalized
projections on the symmetric and antisymmetric subspace, respectively.
From the orthogonality of the two states, we have
\begin{equation}
\opt(\E^{(n)}) = 1,
\end{equation}
for any $n$, or equivalently
\begin{equation}
\norm{\sigma_{0}^{(n)} - \sigma_{1}^{(n)}}_{1} = 2.
\end{equation}
In the next chapter we show that
\begin{equation}
\opt_{\PPT}(\E^{(n)}) \leq \frac{1}{2} + \frac{1}{n+1},
\end{equation}
and therefore this is an example of a set of states that makes the rightmost
inequality in Eq. \eqref{eq:inequality-chain} strict.
Since there is an LOCC measurement that achieves the bound
\cite{DiVincenzo2002}, we also have
\begin{equation}
\opt_{\LOCC}(\E^{(n)}) = \opt_{\Sep}(\E^{(n)}) = \opt_{\PPT}(\E^{(n)}) =
\frac{1}{2} + \frac{1}{n+1},
\end{equation}
or equivalently
\begin{equation}
\norm{\sigma_{0}^{(n)} - \sigma_{1}^{(n)}}_{\LOCC} =
\norm{\sigma_{0}^{(n)} - \sigma_{1}^{(n)}}_{\Sep} =
\norm{\sigma_{0}^{(n)} - \sigma_{1}^{(n)}}_{\PPT} = \frac{4}{n+1}.
\end{equation}
\end{example}
% \subsection{A maximally entangled state and its orthogonal complement}
% \begin{equation}
% u = \frac{1}{\sqrt{n}}\sum_{j=1}^{n}e_{j}\otimes e_{j}
% \end{equation}
% \begin{equation}
% \sigma_{0} = uu^{\ast}
% \hspace*{2cm}
% \sigma_{1} = \frac{1}{n^{2}-1}(\I\otimes\I - uu^{\ast})
% \end{equation}
\section{Discrimination of maximally entangled states}
\label{sec:mes-intro}
When investigating some problem, a typical computer science approach is
to bring the operating parameters of the problem to one extreme.
In order to get a better understanding of the role played by entanglement in
bipartite state distinguishability problems, one can restrict their attention to
the case in which the sets to be distinguished consist only of orthogonal
maximally entangled pure states.
Considering states that are maximally entangled, as opposed to partially
entangled, is useful to reduce the number of variables that need to be taken into account, and
it helps to have neater problem statements. It makes the problem easier to handle mathematically
(recall that maximally entangled states are in a one-to-one correspondence with
unitary operators) and, at the same time, it constitutes an edge case that is
interesting from the physical point of view. The reason to consider maximally entangled states
can be summarized into one question: why bother with
more complicated cases when we do not even know how to deal with that?
In this section, some known results on the distinguishability of
maximally entangled states by LOCC, separable, and PPT measurements are reviewed,
whereas new results are presented in Chapter \ref{chap:mes}.
The simplest example of a set of LOCC-indistinguishable maximally entangled
states is the standard $2$-qubit Bell basis (Eq.~\eqref{eq:Bell-states}).
It turns out that the maximum probability of distinguishing these $4$ states,
for any LOCC measurement, is $1/2$ \cite{Ghosh01}. In fact, a similar bound
holds more in general: if we are given an equally probable ensemble of $N$
orthogonal maximally entangled states in $\complex^{n}\otimes\complex^{n}$,
the maximum probability of distinguishing them by LOCC is $n/N$ \cite{Ghosh04}.
This bound holds even for the wider classes of separable \cite{Duan09} and PPT
measurements \cite{Yu12}. In Chapter \ref{chap:mes} this result is re-proved
using our cone programming framework.
The assumption on the sets consisting entirely of maximally entangled states is
particularly significant when we inquire the question of how the size of LOCC-indistinguishable
sets relates to the local dimension of each of Alice's and Bob's subsystems.
In fact, if we allow states that are not maximally entangled to be in the set,
we can construct indistinguishable sets with a fixed size in any dimension we like.
Indeed, whenever we find a set of indistinguishable maximally entangled states
for certain local dimensions, those states remain indistinguishable when embedded
in any larger local dimensions. Nonetheless they are no longer maximally
entangled with respect to the new larger local dimensions.
Whereas this shows that any set of $N > n$ orthogonal maximally entangled states
can never be locally distinguished with certainty, it leaves open the question
whether there exist sets of $N \leq n$ indistinguishable orthogonal maximally
entangled states in $\complex^{n}\otimes\complex^{n}$.
An answer to this question for the particular case of $n = 3 = N$ was given by
Nathanson \cite{Nathanson05}, who showed that any three orthogonal maximally
entangled states in $\complex^{3}\otimes\complex^{3}$ can be perfectly
distinguished by LOCC. In a followup work \cite{Nathanson13},
Nathanson proved that $3$ maximally entangled states
in $\complex^{n}\otimes\complex^{n}$, for any $n \geq 3$, are always perfectly
distinguishable by PPT.
Several results aimed at filling the landscape for the case $3 < N \leq n$.
For the weaker model of \emph{one-way} LOCC protocols,
Bandyopadhyay et al. \cite{Bandyopadhyay11a} showed some explicit examples of
indistinguishable sets of states with the size of the sets being equal to the
dimension of the subsystems, i.e., $N = n$. The states they use for those
examples lie on systems whose local dimension is $n = 4, 5, 6$.
Later in Chapter \ref{chap:mes}, we go back to these examples and give
numerical evidence that the same sets of states cannot be distinguished with
certainty even if we allow the parties to perform PPT measurements.
Recently, Yu et al. \cite{Yu12} presented the first example of $N$ maximally
entangled states in $\complex^{N}\otimes\complex^{N}$ that cannot be
perfectly distinguished by any PPT measurement, and therefore by any general
LOCC protocols.
Their particular example is composed by the following $N = 4$ states in
$\complex^{4}\otimes\complex^{4}$:
\begin{equation}
\label{eq:ydy_states}
\begin{aligned}
\ket{\phi_1} & =
\frac{1}{2} \ket{0}\ket{0} +
\frac{1}{2} \ket{1}\ket{1} +
\frac{1}{2} \ket{2}\ket{2} +
\frac{1}{2} \ket{3}\ket{3}, \\[2mm]
\ket{\phi_2} & =
\frac{1}{2} \ket{0}\ket{3} +
\frac{1}{2} \ket{1}\ket{2} +
\frac{1}{2} \ket{2}\ket{1} +
\frac{1}{2} \ket{3}\ket{0}, \\[2mm]
\ket{\phi_3} & =
\frac{1}{2} \ket{0}\ket{3} +
\frac{1}{2} \ket{1}\ket{2} -
\frac{1}{2} \ket{2}\ket{1} -
\frac{1}{2} \ket{3}\ket{0}, \\[2mm]
\ket{\phi_4} & =
\frac{1}{2} \ket{0}\ket{1} +
\frac{1}{2} \ket{1}\ket{0} -
\frac{1}{2} \ket{2}\ket{3} -
\frac{1}{2} \ket{3}\ket{2}.
\end{aligned}
\end{equation}
Later in Chapter \ref{chap:mes} we turn their result into a quantitative one,
by showing that PPT measurements can only succeed with probability at most $7/8$
and that $3/4$ is a tight bound on the probability of distinguishing these states
by separable (and LOCC) measurements.
Yet another tile in the landscape of maximally entangled states distinguishability
is a result by Fan \cite{Fan04}, for which any $N$ generalized
Bell states in $\complex^{n}\otimes\complex^{n}$ can be perfectly distinguished
by LOCC whenever $n$ is prime and
\[
\binom{N}{2}\leq n.
\]
Table \ref{table:max-ent-states} recaps all above-mentioned results about the
distinguishability of maximally entangled states by LOCC and PPT
measurements, and compares them with the results obtained in this thesis
(highlighted in gray).
\begin{table}[!ht]
\centering
\def\arraystretch{1.5}
\begin{tabular}{|c|c|c|c|}
\hline
& PPT & LOCC & References\\
\hline \hline
$N = 2$ & --- & \emph{all} dist. & \cite{Walgate00}\\
\hline
$N = 3 = n$ & --- & \emph{all} dist. & \cite{Nathanson05}\\
\hline
$N = 4 = n$ & \emph{some} indist. & --- & \cite{Yu12}\\
\hline
\rowcolor{Gray}
$N = n > 4$ & \emph{some} indist. & --- & \cite{Cosentino13}\\
\hline
\rowcolor{Gray}
$4 < N < n$ & \emph{some} indist. & --- & \cite{Cosentino14,Bandyopadhyay15}\\
\hline
$N > n$ & \emph{all} indist. & --- & \cite{Yu12,Duan09,Ghosh04} \\
\hline
\end{tabular}
\caption[Distinguishability of maximally entangled states]{Distinguishability of
maximally entangled states. (``\emph{some} indist.'':
there exist sets of states that are indistinguishable
for the dimension and the class of measurements of the corresponding cell;
``\emph{all} dist./indist.'': all sets of states are distinguishable/indistinguishable;
``---'': the distinguishability can be inferred by the rest of the row.)
}
\label{table:max-ent-states}
\end{table}
\section{Discrimination of product sets}
Indistinguishability by LOCC is not a prerogative of entangled states.
The famous \emph{domino state} set of \cite{Bennett99}, for example, is a
collection of orthogonal \emph{product} states that cannot be perfectly
discriminated by LOCC protocols.
The local dimension of the domino states is $3$, and one takes
$N = 9$, $p_1 = \cdots = p_9 = 1/9$, and
{\setlength{\arraycolsep}{2.5mm}%
\begin{equation} \label{eq:domino}
\begin{array}{ll}
\multicolumn{2}{c}{\ket{\phi_1} = \ket{1}\ket{1},}\\[4mm]
\ket{\phi_2} = \ket{0}\left(\frac{\ket{0} + \ket{1}}{\sqrt{2}}\right),
& \ket{\phi_3} = \ket{2}\left(\frac{\ket{1} + \ket{2}}{\sqrt{2}}\right),
\\[4mm]
\ket{\phi_4} = \left(\frac{\ket{1} + \ket{2}}{\sqrt{2}}\right)\ket{0},
& \ket{\phi_5} = \left(\frac{\ket{0} + \ket{1}}{\sqrt{2}}\right)\ket{2},
\\[4mm]
\ket{\phi_6} = \ket{0}\left(\frac{\ket{0} - \ket{1}}{\sqrt{2}}\right),
& \ket{\phi_7} = \ket{2}\left(\frac{\ket{1} - \ket{2}}{\sqrt{2}}\right),
\\[4mm]
\ket{\phi_8} = \left(\frac{\ket{1} - \ket{2}}{\sqrt{2}}\right)\ket{0},
& \ket{\phi_9} = \left(\frac{\ket{0} - \ket{1}}{\sqrt{2}}\right)\ket{2}.
\end{array}
\end{equation}
}%
A rather complicated argument demonstrates that this collection cannot be
discriminated by LOCC with probability greater than $1 - \varepsilon$ for some choice
of a positive real number $\varepsilon$.
(A simplified proof appears in \cite{Childs13}, where this fact
is proved for $\varepsilon = 1.9 \times 10^{-8}$.)
\section{Entanglement cost of state discrimination}
As explained in the introduction, three Bell states given with uniform
probabilities can be discriminated by separable measurements with success
probability at most 2/3, while four Bell states can be discriminated with success
probability at most 1/2.
These bounds can be obtained by a fairly trivial selection of LOCC
measurements, and can be shown to hold even for PPT measurements.
On the other hand, if the parties are given a maximally entangled bit as a resource,
then they can perform a teleportation protocol to send each other their respective parts of
the Bell pair they have been asked to identify.
The set of Bell states constitutes an example of a set that is distinguishable only if we
are willing to consume some entanglement (given as an additional resource) or, in other words,
we say that the entanglement cost of distinguishing the Bell states with certainty
must be bigger than zero.
The entanglement cost of quantum operations and measurements, within the
paradigm of LOCC, has been considered previously.
For instance, \cite{Cohen08} studied the entanglement cost of perfectly
discriminating elements of unextendable product sets by LOCC measurements.
Interestingly, his work presents some protocol where entanglement is used more
efficiently than in standard teleportation protocols.
In later work, \cite{Bandyopadhyay09} and \cite{Bandyopadhyay10} considered the
entanglement cost of measurements and established lower bounds on the amount of
entanglement necessary for distinguishing complete orthonormal bases of two
qubits.
Our work on the entanglement cost of Bell states was inspired by a question left open by Yu, Duan, and Ying, who considered the entanglement cost of state discrimination problems by PPT and separable measurements \cite{Yu14}.
%-------------------------------------------------------------------------------
\section{Previous approaches}
%-------------------------------------------------------------------------------
In the results roundup of the previous sections, we summarized ``positive''
results, in which it is shown that a certain probability of success can be obtained by
some measurement, as well as ``negative'' results, for which an upper bound
on the probability of success is shown for any measurement in a certain class.
To prove the first kind of results, one needs to show a protocol (for LOCC),
or a collection of measurement operators (for PPT and separable) that achieves
the given probability.
Some protocols/measurements might be complicated to devise, others are based on
the composition of simple primitives. For instance, when Alice and Bob are
supplied with entangled bits as resource, they can a perform a teleportation
protocol on a part of the states they are asked to distinguish
(an example of such a protocol is shown in Chapter \ref{chap:mes}
for the task of distinguishing three and four Bell states).
To show that the states are not distinguishable, many techniques have been devised.
One possible approach is the one pursued by Walgate and Hardy \cite{Walgate02},
which is based on a cases analysis in which all possible measurements are eliminated.
Another method, considered in \cite{Ghosh01,Ghosh04}, is to reduce the distinguishability
problem to a question on the amount of entanglement that can be distilled from a
certain mixed state.
Say you want to prove that the four Bell states from Eq.~\eqref{eq:Bell-states}
are not perfectly distinguishable by any LOCC protocols.
Suppose that the unknown Bell state is shared among two parties, Alice and Bob,
whose spaces are denoted by $\X_{1}$ and $\Y_{1}$. Let $\X_{2}$ and $\Y_{2}$ two
other spaces of the same dimensions held by two more parties, Charlie and Dan.
Consider the state
\begin{equation}
\rho \in \Density\left((\X_{1}\otimes\Y_{1})\otimes(\X_{2}\otimes\Y_{2})\right)
\end{equation}
defined as
\begin{equation}
\rho = \frac{1}{4}\sum_{i\in\{0,1,2,3\}}\psi_{i}\otimes\psi_{i}.
\end{equation}
By contradiction, assume that $\{\psi_{0}, \ldots, \psi_{3}\} \subset \Density(\X_{1}\otimes\Y_{1})$
are distinguishable by an LOCC protocol between Alice and Bob.
Then they could communicate the outcome classically to Charlie and Dan,
who would use this information to create a shared entangled bit between each other.
This is not possible, since $\rho$ can also be written (because of the symmetry among Bell states) as
\begin{equation}
\rho = \frac{1}{4}\sum_{i\in\{0,1,2,3\}}\psi_{i}\otimes\psi_{i}
\in D\left((\X_{1}\otimes\X_{2})\otimes(\Y_{1}\otimes\Y_{2})\right),
\end{equation}
and therefore it contradicts the fact that $\rho$ is separable in the cut
between Alice and Charlie on one side, and Bob and Dan on the other side, that is,
\begin{equation}
\rho \in \Sep(\X_{1}\otimes\X_{2} : \Y_{1}\otimes\Y_{2}).
\end{equation}
A similar argument shows that no three Bell states, and more in general,
no set of $n+1$ orthogonal maximally entangled states in $\complex^{n}\otimes\complex^{n}$,
can be perfectly distinguished by LOCC\footnote{Later in Section \ref{sec:nathansons-bound},
we will show a proof of this fact by using the convex programming framework introduced in this thesis.}.
This method is referred in the literature as \emph{GKRSS method},
by the initials of the authors of \cite{Ghosh01}.
In \cite{Horodecki03}, a modification of the GKRSS method is presented,
called \emph{HSSH method}. In the GKRSS method, the local distinguishability
problem is reduced to analyzing the entanglement contained in a mixed states
constructed starting from the states that are to be distinguished.
The idea is to compare the entanglement in the mixed state before and after
the distinguishability protocol has run its course.
In HSSH the problem is reduced to comparing the entanglement measures in
\emph{pure states} instead. For some instances of the problem, the HSSH method
turns out to be more powerful, due to the fact that entanglement measures for
pure states are better understood. In fact, through the HSSH method, the problem reduces
to understanding entanglement transformations between pure states,
for which necessary and sufficient conditions were derived by Nielsen \cite{Nielsen99}, and
Jonathan and Plenio \cite{Jonathan99}.
An application of the method by \cite{Horodecki03} is the discovery of the first
set of $n$ indistinguishable states in $\complex^{n}\otimes\complex^{n}$.
The original proof in \cite{Terhal01a} that the Werner states form a hiding pair
(Example \ref{example:werner-hiding-pairs} above) also exploits the theory of entanglement,
but makes use of an extra observation, that is, the fact that the operators
that constitute an LOCC measurement must be PPT.
The mathematical properties of PPT measurements were also exploited in the recent
proofs by \cite{Yu12,Yu14}, which triggered the work of this thesis.