-
Notifications
You must be signed in to change notification settings - Fork 29
/
IsSeparable.m
389 lines (343 loc) · 18.2 KB
/
IsSeparable.m
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
%% ISSEPARABLE Determines whether or not a bipartite operator is separable
% This function has one required argument:
% X: a positive semidefinite matrix
%
% SEP = IsSeparable(X) is either -1, 0, or 1. A value of 0 indicates that
% X is entangled, a value of 1 indicates that X is separable, and a value
% of -1 indicates that the separability of X could not be determined.
%
% This function has four optional arguments:
% DIM (default has both subsystems of equal dimension)
% STR (default 2)
% VERBOSE (default 1)
% TOL (default eps^(3/8))
%
% SEP = IsSeparable(X,DIM,STR,VERBOSE,TOL) is as above, where DIM is
% a 1-by-2 vector containing the dimensions of the subsystems on which X
% acts.
%
% STR is an integer that determines how hard the script should work to
% determine separability before giving up (STR = -1 means that the script
% won't stop working until it finds an answer). Other valid values are 0,
% 1, 2, 3, ... In practice, if STR >= 4 then most computers will run out
% of memory and/or the sun will explode before computation completes.
%
% VERBOSE is a flag (either 0 or 1) that indicates that the script will
% or will not display a line of text describing how it proved that X is
% or is not separable.
%
% TOL is the numerical tolerance used throughout the script.
%
% URL: http://www.qetlab.com/IsSeparable
% requires: ApplyMap.m, CVX (http://cvxr.com/cvx/), FilterNormalForm.m,
% iden.m, InSeparableBall.m, IsPPT.m, IsPSD.m, jacobi_poly.m,
% kpNorm.m, MaxEntangled.m, OperatorSchmidtDecomposition.m,
% OperatorSchmidtRank.m, opt_args.m, opt_disp.m, PartialMap.m,
% PartialTrace.m, PartialTranspose.m, PermutationOperator.m,
% PermuteSystems.m, Realignment.m, SchmidtDecomposition.m,
% SchmidtRank.m, sporth.m, Swap.m, SwapOperator.m,
% SymmetricExtension.m, SymmetricInnerExtension.m,
% SymmetricProjection.m, TraceNorm.m
%
% author: Nathaniel Johnston ([email protected])
% package: QETLAB
% last updated: November 14, 2014
function sep = IsSeparable(X,varargin)
X = full(X);
if(~IsPSD(X))
error('IsSeparable:NotPSD','X is not positive semidefinite, so the idea of it being separable does not make sense.');
end
lX = length(X);
rX = rank(X);
X = X/trace(X);
sep = -1;
% set optional argument defaults: dim=sqrt(length(X)), str=2, verbose=1, tol=eps^(1/4)
[dim,str,verbose,tol] = opt_args({ round(sqrt(lX)), 2, 1, eps^(3/8) },varargin{:});
if(str == -1)
str = 1/eps; % keep going forever!
end
% allow the user to enter a single number for dim
if(length(dim) == 1)
dim = [dim,lX/dim];
if abs(dim(2) - round(dim(2))) >= 2*lX*eps
error('IsSeparable:InvalidDim','If DIM is a scalar, it must evenly divide length(X); please provide the DIM array containing the dimensions of the subsystems.');
end
dim(2) = round(dim(2));
end
nD = min(dim);
xD = max(dim);
pD = prod(dim);
if(nD == 1)
sep = 1;
opt_disp(['Every positive semidefinite matrix is separable when one of the local dimensions is 1.\n'],verbose);
return
end
XA = PartialTrace(X,2,dim);
XB = PartialTrace(X,1,dim);
% pre-load various references
refs = {'A. Peres. Separability criterion for density matrices. Phys. Rev. Lett., 77:1413-1415, 1996.', ... % refs[1]
'M. Horodecki, P. Horodecki, and R. Horodecki. Separability of mixed states: Necessary and sufficient conditions. Phys. Lett. A, 223:1-8, 1996.', ...
'P. Horodecki, M. Lewenstein, G. Vidal, and I. Cirac. Operational criterion and constructive checks for the separability of low-rank density matrices. Phys. Rev. A, 62:032310, 2000.', ...
'K. Chen and L.-A. Wu. A matrix realignment method for recognizing entanglement. Quantum Inf. Comput., 3:193-202, 2003.', ...
'F. Verstraete, J. Dehaene, and B. De Moor. Normal forms and entanglement measures for multipartite quantum states. Phys. Rev. A, 68:012103, 2003.', ...
'K.-C. Ha and S.-H. Kye. Entanglement witnesses arising from exposed positive linear maps. Open Systems & Information Dynamics, 18:323-337, 2011.', ... % refs[6]
'O. Gittsovich, O. Guehne, P. Hyllus, and J. Eisert. Unifying several separability conditions using the covariance matrix criterion. Phys. Rev. A, 78:052319, 2008.', ...
'L. Gurvits and H. Barnum. Largest separable balls around the maximally mixed bipartite quantum state. Phys. Rev. A, 66:062311, 2002.', ...
'H.-P. Breuer. Optimal entanglement criterion for mixed quantum states. Phys. Rev. Lett., 97:080501, 2006.', ...
'W. Hall. Constructions of indecomposable positive maps based on a new criterion for indecomposability. E-print: arXiv:quant-ph/0607035, 2006.', ...
'A. C. Doherty, P. A. Parrilo, and F. M. Spedalieri. A complete family of separability criteria. Phys. Rev. A, 69:022308, 2004.', ... % refs[11]
'M. Navascues, M. Owari, and M. B. Plenio. A complete criterion for separability detection. Phys. Rev. Lett., 103:160404, 2009.', ...
'N. Johnston. Separability from spectrum for qubit-qudit states. Phys. Rev. A, 88:062330, 2013.', ...
'C.-J. Zhang, Y.-S. Zhang, S. Zhang, and G.-C. Guo. Entanglement detection beyond the cross-norm or realignment criterion. Phys. Rev. A, 77:060301(R), 2008.', ...
'R. Hildebrand. Semidefinite descriptions of low-dimensional separable matrix cones. Linear Algebra Appl., 429:901-932, 2008,', ...
'R. Hildebrand. Comparison of the PPT cone and the separable cone for 2-by-n systems. http://www-ljk.imag.fr/membres/Roland.Hildebrand/coreMPseminar2005_slides.pdf', ... % refs[16]
'D. Cariello. Separability for weak irreducible matrices. E-print: arXiv:1311.7275 [quant-ph], 2013.', ...
'L. Chen and D. Z. Djokovic. Separability problem for multipartite states of rank at most four. J. Phys. A: Math. Theor., 46:275304, 2013.', ...
'G. Vidal and R. Tarrach. Robustness of entanglement. Phys. Rev. A, 59:141-155, 1999.'};
% Start with the really easy separability checks (we always do these,
% regardless of str).
% PPT is used in so many tests, just always compute it
ppt = IsPPT(X,2,dim,tol);
% Check the PPT criterion
if(~ppt)
sep = 0;
opt_disp(['Determined to be entangled via the PPT criterion. Reference:\n',refs{1},'\n'],verbose);
return
% Sometimes the PPT criterion is also sufficient for separability.
elseif(pD <= 6 || min(dim) <= 1)
sep = 1;
opt_disp(['Determined to be separable via sufficiency of the PPT criterion in small dimensions. Reference:\n',refs{2},'\n'],verbose);
return
% Be careful with the next test! Checking that rX <= max(dim) is
% *incorrect* here, and is not what is meant by refs{3}.
elseif(rX <= 3 || rX <= rank(XB) || rX <= rank(XA))
sep = 1;
opt_disp(['Determined to be separable via sufficiency of the PPT criterion for low-rank operators. Reference:\n',refs{3},'\n'],verbose);
return
end
% Realignment (aka computable cross norm) criterion. Only do it if
% VERBOSE = 1, since we are about to do another test that is strictly
% stronger.
if(verbose && TraceNorm(Realignment(X,dim)) > 1)
sep = 0;
opt_disp(['Determined to be entangled via the realignment criterion. Reference:\n',refs{4},'\n'],verbose);
return
end
% Another test that is strictly stronger than the realignment criterion
if(TraceNorm(Realignment(X - kron(XA,XB),dim)) > sqrt((1-trace(XA^2))*(1-trace(XB^2))))
sep = 0;
opt_disp(['Determined to be entangled by using Theorem 1 of reference:\n',refs{14},'\n'],verbose);
return
end
lam = sort(real(eig(X)),'descend'); % eigenvalues of X
% There are some separability tests that work specifically in the
% qubit-qudit (i.e., 2 \otimes n) case. Do these now.
if(nD == 2)
% check if X is separable from spectrum
if((lam(1) - lam(2*xD-1))^2 <= 4*lam(2*xD-2)*lam(2*xD) + tol^2)
sep = 1;
opt_disp(['Determined to be separable by inspecting its eigenvalues. Reference:\n',refs{13},'\n'],verbose);
return
end
% For the rest of the block matrix tests, we need the 2-dimensional
% subsystem to be the *first* subsystem, so swap accordingly.
if(dim(1) > 2)
Xt = Swap(X,[1,2],dim);
else
Xt = X;
end
% Check if Lemma 1 of refs{13} applies to X. Also check the
% Hildebrand 2xn results.
A = Xt(1:xD,1:xD);
B = Xt(1:xD,xD+1:2*xD);
C = Xt(xD+1:2*xD,xD+1:2*xD);
% This test is weaker than the next one, so only do it if VERBOSE =
% 1.
if(verbose && norm(B-B') < tol^2)
sep = 1;
opt_disp(['Determined to be separable by being a block Hankel matrix:\n',refs{15},'\n'],verbose);
return
end
if(rank(B-B') <= 1 && ppt)
sep = 1;
opt_disp(['Determined to be separable by being a perturbed block Hankel matrix:\n',refs{16},'\n'],verbose);
return
end
X_2n_ppt_check = [(5/6)*A-C/6, B; B', (5/6)*C-A/6];
if(IsPSD(X_2n_ppt_check) && IsPPT(X_2n_ppt_check,2,[2,xD]))
sep = 1;
opt_disp(['Determined to be separable via the homothetic images approach of:\n',refs{16},'\n'],verbose);
return
end
if(norm(B)^2 <= min(real(eig(A)))*min(real(eig(C))) + tol^2)
sep = 1;
opt_disp(['Determined to be separable by using Lemma 1 of reference:\n',refs{13},'\n'],verbose);
return
end
end
% There are conditions that are both necessary and sufficient when both
% dimensions are 3 and the rank is 4
if(rX == 4 && nD == 3 && xD == 3)
% this method computes more determinants than are actually
% necessary, but the speed loss isn't too great
ranX = orth(X);
for j = 6:-1:1
for k = 7:-1:j+1
for l = 8:-1:k+1
for m = 9:-1:l+1
p(j,k,l,m) = det(ranX([j,k,l,m],:));
end
end
end
end
F = det([p(1,2,4,5), p(1,3,4,6), p(2,3,5,6), p(1,2,4,6)+p(1,3,4,5), p(1,2,5,6)+p(2,3,4,5), p(1,3,5,6)+p(2,3,4,6);
p(1,2,7,8), p(1,3,7,9), p(2,3,8,9), p(1,2,7,9)+p(1,3,7,8), p(1,2,8,9)+p(2,3,7,8), p(1,3,8,9)+p(2,3,7,9);
p(4,5,7,8), p(4,6,7,9), p(5,6,8,9), p(4,5,7,9)+p(4,6,7,8), p(4,5,8,9)+p(5,6,7,8), p(4,6,8,9)+p(5,6,7,9);
p(1,2,4,8)-p(1,2,5,7), p(1,3,4,9)-p(1,3,6,7), p(2,3,5,9)-p(2,3,6,8), p(1,2,4,9)-p(1,2,6,7)+p(1,3,4,8)-p(1,3,5,7), p(1,2,5,9)-p(1,2,6,8)+p(2,3,4,8)-p(2,3,5,7), p(1,3,5,9)-p(1,3,6,8)+p(2,3,4,9)-p(2,3,6,7);
p(1,4,5,8)-p(2,4,5,7), p(1,4,6,9)-p(3,4,6,7), p(2,5,6,9)-p(3,5,6,8), p(1,4,5,9)-p(2,4,6,7)+p(1,4,6,8)-p(3,4,5,7), p(1,5,6,8)-p(2,5,6,7)+p(2,4,5,9)-p(3,4,5,8), p(1,5,6,9)-p(3,4,6,8)+p(2,4,6,9)-p(3,5,6,7);
p(1,5,7,8)-p(2,4,7,8), p(1,6,7,9)-p(3,4,7,9), p(2,6,8,9)-p(3,5,8,9), p(1,5,7,9)-p(2,4,7,9)+p(1,6,7,8)-p(3,4,7,8), p(1,5,8,9)-p(2,4,8,9)+p(2,6,7,8)-p(3,5,7,8), p(1,6,8,9)-p(3,4,8,9)+p(2,6,7,9)-p(3,5,7,9)]);
sep = (abs(F) < max(tol^2,eps^(3/4))); % X is separable iff F is zero (or suffiently close to it, for numerical reasons)
if(sep == 1)
opt_disp(['Determined to be separable by checking the Chow form. Reference:\n',refs{18},'\n'],verbose);
else
opt_disp(['Determined to be entangled by checking the Chow form. Reference:\n',refs{18},'\n'],verbose);
end
return
end
% Check proximity of X with the maximally mixed state.
if(InSeparableBall(X))
sep = 1;
opt_disp(['Determined to be separable by closeness to the maximally mixed state. Reference:\n',refs{8},'\n'],verbose);
return
end
% Check if X is a rank-1 perturbation of the identity, which is
% necessarily separable if it's PPT, which we have already checked.
if(lam(2) - lam(pD) < tol^2)
sep = 1;
opt_disp(['Determined to be separable by being a small rank-1 perturbation of the maximally-mixed state. Reference:\n',refs{19},'\n'],verbose);
return
end
% Check tensor rank equalling 2
if(OperatorSchmidtRank(X,dim) <= 2)
sep = 1;
opt_disp(['Determined to be separable by having operator Schmidt rank at most 2. Reference:\n',refs{17},'\n'],verbose);
return
end
% There is a family of known optimal positive maps in the qutrit-qutrit
% case. Check for entanglement using these.
if(dim(1) == 3 && dim(2) == 3)
phi = MaxEntangled(3,0,0);
for t=0:0.1:0.9
for j=1:2
if(t>0)
t = 1/t; % this is a weird way of using both t and 1/t as indices for the maps Phi we generate
elseif(j>1)
break;
end
a = (1-t)^2/(1-t+t^2);
b = t^2/(1-t+t^2);
c = 1/(1-t+t^2);
Phi = diag([a+1,c,b,b,a+1,c,c,b,a+1]) - phi*phi';
if(~IsPSD(PartialMap(X,Phi,2,dim)))
sep = 0;
opt_disp(['Determined to be entangled via the positive map Phi[a,b,c] with a=',num2str(a),', b=',num2str(b),', c=',num2str(c),'. Reference:\n',refs{6},'\n'],verbose);
return
end
end
end
end
% Use the Breuer-Hall positive maps (in even dimensions only) based on
% antisymmetric unitary matrices.
for p = 1:2
if(mod(dim(p),2) == 0)
phi = MaxEntangled(dim(p),0,0);
U = kron(eye(dim(p)),fliplr(diag([ones(dim(p)/2,1);-ones(dim(p)/2,1)])));
Phi = diag(ones(dim(p)^2,1)) - phi*phi' - U*SwapOperator(dim(p))*U';
if(~IsPSD(PartialMap(X,Phi,p,dim)))
sep = 0;
opt_disp(['Determined to be entangled via the Breuer-Hall positive maps based on antisymmetric unitary matrices. References:\n',refs{9},'\n',refs{10},'\n'],verbose);
return
end
end
end
% The next tests for entanglement and separability are slightly more
% time-intensive, so we only do them if str >= 1.
if(str >= 1)
% Use the filter covariance matrix criterion (Filter CMC) for entanglement.
% This strengthens the realignment criterion considerably, but we do the
% realignment first anyway, since it is quicker and simpler (and thus
% provides a more useful reference).
try
xi = FilterNormalForm(X,dim);
if(sum(xi) > min( sqrt(nD*xD*(nD-1)*(xD-1)), nD*xD*(1 - 1/nD + (nD^2 - 1)/xD + min(0,(xD^2-nD^2)/xD - (xD-1)))/2 ) + 10*xD*eps)
sep = 0;
opt_disp(['Determined to be entangled via the Filter Covariance Matrix Criterion. Reference:\n',refs{7},'\n'],verbose);
return
end
% FilterNormalForm often is slow and results in an error when X is
% low-rank, but the partial transpose criterion already took care of those
% situations anyway. Nonetheless, we err on the side of caution and ignore
% the cases when the state doesn't have a filter normal form.
catch err
if(~strcmpi(err.identifier,'FilterNormalForm:NoFNF'))
rethrow(err);
end
end
% Try the Guhne method of enhancing the separability within X.
Xsep = X;
XSeig = sort(real(eig(Xsep)));
e_norm = norm(XSeig);
it_ct = 0;
while it_ct < 10
lb = -1;
% Iteratively find a product state whose maximal overlap with Xsep
% is close to optimal. This has a non-zero chance of failing, so we
% make sure that the obtained overlap isn't terrible before moving
% on.
while lb < XSeig(sum(dim)-1) - pD*eps;
[lb,v] = sk_iterate(Xsep,1,dim);
end
% compute the minimum amount that we can subtract off v*v' and
% still be positive semidefinite
gen_eig = eig(Xsep,v*v');
gen_eig = min(real(gen_eig(~isinf(gen_eig))));
% actually subtract half that amount
Xsep2 = Xsep - gen_eig*(v*v')/2;
Xsep2 = Xsep2/trace(Xsep2);
XSeig2 = sort(real(eig(Xsep)));
e_norm2 = norm(XSeig);
if(e_norm - e_norm2 < 10^(-4)) % don't use abs() -- we want e_norm2 to be smaller, not larger
it_ct = it_ct + 1;
if(e_norm - e_norm2 > -10^(-4)) % if e_norm2 isn't larger, then do the update anyway
XSeig = XSeig2;
Xsep = Xsep2;
e_norm = e_norm2;
end
else
it_ct = 0;
XSeig = XSeig2;
Xsep = Xsep2;
e_norm = e_norm2;
if(InSeparableBall(Xsep))
sep = 1;
opt_disp('Determined to be separable by subtracting product states until the operator was close to the maximally-mixed state.',verbose);
return
end
end
end
end
% If str is high enough, also try the stronger separability tests based on
% symmetric extensions. These are much more time-intensive.
for k = 2:str
if(~SymmetricExtension(X,k,dim,1,1))
sep = 0;
opt_disp(['Determined to be entangled by not having a ',num2str(k),'-copy PPT symmetric extension. Reference:\n',refs{11},'\n'],verbose);
return
end
if(SymmetricInnerExtension(Xsep,k,dim,1)) % Use Xsep instead of X, since Xsep is in some sense "more" separable, so it is easier to detect
sep = 1;
opt_disp(['Determined to be separable via the semidefinite program based on ',num2str(k),'-copy PPT symmetric extensions from reference:\n',refs{12},'\n'],verbose);
return
end
end
end