Separability of diagonal symmetric states: a quadratic conic optimization problem

Jordi Tura1,2, Albert Aloy1, Ruben Quesada3, Maciej Lewenstein1,4, and Anna Sanpera3,4

1ICFO - Institut de Ciencies Fotoniques, The Barcelona Institute of Science and Technology, 08860 Castelldefels (Barcelona), Spain
2Max-Planck-Institut für Quantenoptik, Hans-Kopfermann-Straße 1, 85748 Garching, Germany
3Departament de Física, Universitat Autònoma de Barcelona, E-08193 Bellaterra, Spain
4ICREA, Pg. Lluís Companys 23, E-08010 Barcelona, Spain

We study the separability problem in mixtures of Dicke states i.e., the separability of the so-called Diagonal Symmetric (DS) states. First, we show that separability in the case of DS in $C^d\otimes C^d$ (symmetric qudits) can be reformulated as a quadratic conic optimization problem. This connection allows us to exchange concepts and ideas between quantum information and this field of mathematics. For instance, copositive matrices can be understood as indecomposable entanglement witnesses for DS states. As a consequence, we show that positivity of the partial transposition (PPT) is sufficient and necessary for separability of DS states for $d \leq 4$. Furthermore, for $d \geq 5$, we provide analytic examples of PPT-entangled states. Second, we develop new sufficient separability conditions beyond the PPT criterion for bipartite DS states. Finally, we focus on $N$-partite DS qubits, where PPT is known to be necessary and sufficient for separability. In this case, we present a family of almost DS states that are PPT with respect to each partition but nevertheless entangled.

Symmetries in physics have far-reaching consequences and they provide an invaluable tool in the physical description of our world. In the quantum setting, their role is also crucial as shown for example in fundamental conservation laws or quantum phase transitions to name some. It is therefore quite natural to ask what role symmetries might play in the undoubtedly genuine quantum problem of entanglement. For arbitrary composite quantum systems, proving if a given state is entangled or not is, in general, an NP-hard problem, despite the fact that certifying its entanglement might be trivial. The reason for this mismatch between membership (does or does not the state belong to the convex set of separable states?) and certification arises from the fact that the problem can be posed as characterizing all positive but not completely positive maps. This is the NP-hard part of the problem. However, to verify if a given state is not positive semidefinite under partial transposition (the so-called NPT conditions), which necessarily implies the state is entangled, corresponds to check a very particular positive, but not completely positive, map. Do symmetries allow in some way to reduce the difficulty of checking membership into the separable set?
Here we focus on symmetric states i.e., those which are invariant under the exchange of their constituents. Symmetric states can be mapped onto spin systems and span solely the largest-spin subspace in the Schur-Weyl duality representation. The Dicke basis (permutationally invariant) provides a very convenient framework to represent the set of symmetric states. An important subset of this set are the diagonal symmetric (DS) states, which correspond to mixtures of Dicke states and, therefore, are diagonal in the Dicke representation.
In our work we have shown that for DS states of two-qudits, i.e. $\rho\in DS( C^d\otimes C^d)$, the problem of separability is completely equivalent to the problem of membership in the set of completely-positive matrices (no to be confused with CP-maps) and the later can be reformulated in terms of a quadratic conic optimization problems. Quadratic conic optimization is an extremely active field of research on mathematics having impact in fields as disparate as economics, genomics or big-data, which provides a way to approach also some important non-convex optimization problems. The equivalence between these two problems has allowed us to import/export ideas between entanglement theory and non-convex quadratic optimization and to provide entanglement witnesses able to detect DS states that are entangled but positive under partial transposition (PPTES). Importantly enough, for such type of states, the entanglement problem is not related to the symmetry, but to the dimension of the constituents. However, it is precisely the symmetry embedded in the DS states which allows to map the problem to a quadratic conic optimization procedure.

► BibTeX data

► References

[1] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki, and Karol Horodecki, ``Quantum entanglement,'' Rev. Mod. Phys. 81, 865-942 (2009).
https://doi.org/10.1103/RevModPhys.81.865

[2] Artur K. Ekert, ``Quantum cryptography based on Bell's theorem,'' Phys. Rev. Lett. 67, 661-663 (1991).
https://doi.org/10.1103/PhysRevLett.67.661

[3] Christian Gross, Tilman Zibold, Eike Nicklas, Jerome Esteve, and Markus K Oberthaler, ``Nonlinear atom interferometer surpasses classical precision limit,'' Nature 464, 1165-1169 (2010).
https://doi.org/10.1038/nature08919

[4] John S Bell, ``On the Einstein Podolsky Rosen paradox,'' Physics 1, 195-200 (1964).

[5] Reinhard F. Werner, ``Quantum states with Einstein-Podolsky-Rosen correlations admitting a hidden-variable model,'' Phys. Rev. A 40, 4277-4281 (1989).
https://doi.org/10.1103/PhysRevA.40.4277

[6] Antonio Acín, Nicolas Brunner, Nicolas Gisin, Serge Massar, Stefano Pironio, and Valerio Scarani, ``Device-independent security of quantum cryptography against collective attacks,'' Physical Review Letters 98, 230501 (2007).
https://doi.org/10.1103/PhysRevLett.98.230501

[7] Leonid Gurvits, ``Classical deterministic complexity of Edmonds' problem and quantum entanglement,'' in Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, STOC '03 (ACM, New York, NY, USA, 2003) pp. 10-19.
https://doi.org/10.1145/780542.780545

[8] Asher Peres, ``Separability criterion for density matrices,'' Phys. Rev. Lett. 77, 1413-1415 (1996).
https://doi.org/10.1103/PhysRevLett.77.1413

[9] Michał Horodecki, Paweł Horodecki, and Ryszard Horodecki, ``Separability of mixed states: necessary and sufficient conditions,'' Physics Letters A 223, 1 - 8 (1996).
https://doi.org/10.1016/S0375-9601(96)00706-2

[10] Erling Størmer, ``Positive linear maps of operator algebras,'' Acta Math. 110, 233-278 (1963).
https://doi.org/10.1007/BF02391860

[11] S.L. Woronowicz, ``Positive maps of low dimensional matrix algebras,'' Reports on Mathematical Physics 10, 165 - 183 (1976).
https://doi.org/10.1016/0034-4877(76)90038-0

[12] Pawel Horodecki, ``Separability criterion and inseparable mixed states with positive partial transposition,'' Physics Letters A 232, 333 - 339 (1997).
https://doi.org/10.1016/S0375-9601(97)00416-7

[13] K. Eckert, J. Schliemann, D. Bruß, and M. Lewenstein, ``Quantum correlations in systems of indistinguishable particles,'' Annals of Physics 299, 88 - 127 (2002).
https://doi.org/10.1006/aphy.2002.6268

[14] Roe Goodman and Nolan R Wallach, Symmetry, representations, and invariants, Vol. 255 (Springer, 2009).
https://doi.org/10.1007/978-0-387-79852-3

[15] R. H. Dicke, ``Coherence in spontaneous radiation processes,'' Phys. Rev. 93, 99-110 (1954).
https://doi.org/10.1103/PhysRev.93.99

[16] Robert McConnell, Hao Zhang, Jiazhong Hu, Senka Ć uk, and Vladan Vuletić, ``Entanglement with negative Wigner function of almost 3,000 atoms heralded by one photon,'' Nature 519, 439-442 (2015).
https://doi.org/10.1038/nature14293

[17] Witlef Wieczorek, Roland Krischek, Nikolai Kiesel, Patrick Michelberger, Géza Tóth, and Harald Weinfurter, ``Experimental entanglement of a six-photon symmetric Dicke state,'' Phys. Rev. Lett. 103, 020504 (2009).
https://doi.org/10.1103/PhysRevLett.103.020504

[18] Chao-Yang Lu, Xiao-Qi Zhou, Otfried Gühne, Wei-Bo Gao, Jin Zhang, Zhen-Sheng Yuan, Alexander Goebel, Tao Yang, and Jian-Wei Pan, ``Experimental entanglement of six photons in graph states,'' Nature Physics 3, 91-95 (2007).
https://doi.org/10.1038/nphys507

[19] José I. Latorre, Román Orús, Enrique Rico, and Julien Vidal, ``Entanglement entropy in the Lipkin-Meshkov-Glick model,'' Phys. Rev. A 71, 064101 (2005).
https://doi.org/10.1103/PhysRevA.71.064101

[20] J. Tura, R. Augusiak, P. Hyllus, M. Kuś, J. Samsonowicz, and M. Lewenstein, ``Four-qubit entangled symmetric states with positive partial transpositions,'' Phys. Rev. A 85, 060302 (2012).
https://doi.org/10.1103/PhysRevA.85.060302

[21] R. Augusiak, J. Tura, J. Samsonowicz, and M. Lewenstein, ``Entangled symmetric states of $n$ qubits with all positive partial transpositions,'' Phys. Rev. A 86, 042316 (2012).
https://doi.org/10.1103/PhysRevA.86.042316

[22] Jordi Tura i Brugués, Characterizing Entanglement and Quantum Correlations Constrained by Symmetry (Springer International Publishing, 2017).
https://doi.org/10.1007/978-3-319-49571-2

[23] Alejandro González-Tudela and Diego Porras, ``Mesoscopic entanglement induced by spontaneous emission in solid-state quantum optics,'' Phys. Rev. Lett. 110, 080502 (2013).
https://doi.org/10.1103/PhysRevLett.110.080502

[24] Maciej Lewenstein and Anna Sanpera, ``Separability and entanglement of composite quantum systems,'' Phys. Rev. Lett. 80, 2261-2264 (1998).
https://doi.org/10.1103/PhysRevLett.80.2261

[25] Ruben Quesada and Anna Sanpera, ``Best separable approximation of multipartite diagonal symmetric states,'' Physical Review A 89, 052319 (2014).
https://doi.org/10.1103/PhysRevA.89.052319

[26] Elie Wolfe and S. F. Yelin, ``Certifying separability in symmetric mixed states of $n$ qubits, and superradiance,'' Phys. Rev. Lett. 112, 140402 (2014).
https://doi.org/10.1103/PhysRevLett.112.140402

[27] Nengkun Yu, ``Separability of a mixture of Dicke states,'' Phys. Rev. A 94, 060101 (2016).
https://doi.org/10.1103/PhysRevA.94.060101

[28] Ruben Quesada, Swapan Rana, and Anna Sanpera, ``Entanglement and nonlocality in diagonal symmetric states of n qubits,'' Physical Review A 95, 042128 (2017).
https://doi.org/10.1103/PhysRevA.95.042128

[29] Asher Peres, ``All the Bell inequalities,'' Foundations of Physics 29, 589-614 (1999).
https://doi.org/10.1023/A:1018816310000

[30] J. Tura, R. Augusiak, A. B. Sainz, T. Vértesi, M. Lewenstein, and A. Acín, ``Detecting nonlocality in many-body quantum states,'' Science 344, 1256-1258 (2014).
https://doi.org/10.1126/science.1247715

[31] J. Tura, R. Augusiak, A.B. Sainz, B. Lücke, C. Klempt, M. Lewenstein, and A. Acín, ``Nonlocality in many-body quantum systems detected with two-body correlators,'' Annals of Physics 362, 370 - 423 (2015).
https://doi.org/10.1016/j.aop.2015.07.021

[32] Matteo Fadel and Jordi Tura, ``Bounding the set of classical correlations of a many-body system,'' Phys. Rev. Lett. 119, 230402 (2017).
https://doi.org/10.1103/PhysRevLett.119.230402

[33] Elias Amselem and Mohamed Bourennane, ``Experimental four-qubit bound entanglement,'' Nature Physics 5, 748 EP - (2009), article.
https://doi.org/10.1038/nphys1372

[34] Jonathan Lavoie, Rainer Kaltenbaek, Marco Piani, and Kevin J. Resch, ``Experimental bound entanglement in a four-photon state,'' Phys. Rev. Lett. 105, 130501 (2010).
https://doi.org/10.1103/PhysRevLett.105.130501

[35] Joonwoo Bae, Markus Tiersch, Simeon Sauer, Fernando de Melo, Florian Mintert, Beatrix Hiesmayr, and Andreas Buchleitner, ``Detection and typicality of bound entangled states,'' Phys. Rev. A 80, 022317 (2009).
https://doi.org/10.1103/PhysRevA.80.022317

[36] Beatrix C Hiesmayr and Wolfgang Löffler, ``Complementarity reveals bound entanglement of two twisted photons,'' New Journal of Physics 15, 083036 (2013).
https://doi.org/10.1088/1367-2630/15/8/083036

[37] Christoph Spengler, Marcus Huber, Stephen Brierley, Theodor Adaktylos, and Beatrix C. Hiesmayr, ``Entanglement detection via mutually unbiased bases,'' Phys. Rev. A 86, 022311 (2012).
https://doi.org/10.1103/PhysRevA.86.022311

[38] Avi Berman, Mirjam Dur, and Naomi Shaked-Monderer, ``Open problems in the theory of completely positive and copositive matrices,'' Electronic Journal of Linear Algebra 29, 46-58 (2015).
https://doi.org/10.13001/1081-3810.2943

[39] Leonard J Gray and David G Wilson, ``Nonnegative factorization of positive semidefinite nonnegative matrices,'' Linear Algebra and its Applications 31, 119-127 (1980).
https://doi.org/10.1016/0024-3795(80)90212-8

[40] Marshall Hall and Morris Newman, ``Copositive and completely positive quadratic forms,'' Mathematical Proceedings of the Cambridge Philosophical Society 59, 329–339 (1963).
https://doi.org/10.1017/S0305004100036951

[41] Sudip Bose and Eric Slud, ``Maximin efficiency-robust tests and some extensions,'' Journal of statistical planning and inference 46, 105-121 (1995).
https://doi.org/10.1016/0378-3758(94)E0091-8

[42] A. Berman and N. Shaked-Monderer, Completely Positive Matrices (World Scienfic, 2003).
https:/​/​books.google.de/​books?id=AllToPtYGGgC

[43] Chris Ding, Xiaofeng He, and Horst D Simon, ``On the equivalence of nonnegative matrix factorization and spectral clustering,'' in Proceedings of the 2005 SIAM International Conference on Data Mining (SIAM, 2005) pp. 606-610.
https://doi.org/10.1137/1.9781611972757.70

[44] Abraham Berman, Christopher King, and Robert Shorten, ``A characterisation of common diagonal stability over cones,'' Linear and Multilinear Algebra 60, 1117-1123 (2012).
https://doi.org/10.1080/03081087.2011.647018

[45] Oliver Mason and Robert Shorten, ``On linear copositive lyapunov functions and the stability of switched positive linear systems,'' IEEE Transactions on Automatic Control 52, 1346-1349 (2007).
https://doi.org/10.1109/TAC.2007.900857

[46] Barbara M. Terhal, ``Bell inequalities and the separability criterion,'' Physics Letters A 271, 319 - 326 (2000).
https://doi.org/10.1016/S0375-9601(00)00401-1

[47] R Augusiak, J Tura, and M Lewenstein, ``A note on the optimality of decomposable entanglement witnesses and completely entangled subspaces,'' Journal of Physics A: Mathematical and Theoretical 44, 212001 (2011).
https://doi.org/10.1088/1751-8113/44/21/212001

[48] Sevag Gharibian, ``Strong np-hardness of the quantum separability problem,'' Quantum Information & Computation 10, 343-360 (2010).
http:/​/​www.rintonpress.com/​xxqic10/​qic-10-34/​0343-0360.pdf

[49] Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman & Co., New York, NY, USA, 1979).
https://doi.org/10.2307/2273574

[50] Martin Grötschel, László Lovász, and Alexander Schrijver, Geometric algorithms and combinatorial optimization, Vol. 2 (Springer Science & Business Media, 2012).
https://doi.org/10.1112/blms/22.2.203

[51] Peter J. C. Dickinson, Mirjam Dür, Luuk Gijben, and Roland Hildebrand, ``Scaling relationship between the copositive cone and parrilo's first level approximation,'' Optimization Letters 7, 1669-1679 (2013).
https://doi.org/10.1007/s11590-012-0523-3

[52] M. Kaykobad, ``On nonnegative factorization of matrices,'' Linear Algebra and its Applications 96, 27 - 33 (1987).
https://doi.org/10.1016/0024-3795(87)90334-X

[53] Jon Magne Leinaas, Jan Myrheim, and Per Øyvind Sollid, ``Numerical studies of entangled positive-partial-transpose states in composite quantum systems,'' Phys. Rev. A 81, 062329 (2010).
https://doi.org/10.1103/PhysRevA.81.062329

[54] Remigiusz Augusiak, Janusz Grabowski, Marek Kuś, and Maciej Lewenstein, ``Searching for extremal PPT entangled states,'' Optics Communications 283, 805 - 813 (2010), quo vadis Quantum Optics?.
https://doi.org/10.1016/j.optcom.2009.10.050

[55] T. Baumgratz, M. Cramer, and M. B. Plenio, ``Quantifying coherence,'' Phys. Rev. Lett. 113, 140401 (2014).
https://doi.org/10.1103/PhysRevLett.113.140401

[56] Dariusz Chruściński, Gniewomir Sarbicki, and Filip Wudarski, ``Entanglement witnesses from mutually unbiased bases,'' arXiv preprint arXiv:1708.05181 (2017).
arXiv:1708.05181

[57] Beatrix C Hiesmayr and Wolfgang Löffler, ``Mutually unbiased bases and bound entanglement,'' Physica Scripta 2014, 014017 (2014).
https://doi.org/10.1088/0031-8949/2014/T160/014017

[58] Gábor Pataki, ``Strong duality in conic linear programming: Facial reduction and extended duals,'' in Computational and Analytical Mathematics: In Honor of Jonathan Borwein's 60th Birthday, edited by David H. Bailey, Heinz H. Bauschke, Peter Borwein, Frank Garvan, Michel Théra, Jon D. Vanderwerff, and Henry Wolkowicz (Springer New York, New York, NY, 2013) pp. 613-634.
https://doi.org/10.1007/978-1-4614-7621-4_28

[59] Peter J.C. Dickinson, ``Geometry of the copositive and completely positive cones,'' Journal of Mathematical Analysis and Applications 380, 377 - 395 (2011).
https://doi.org/10.1016/j.jmaa.2011.03.005

[60] Gábor Pataki, ``The geometry of semidefinite programming,'' in Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, edited by Henry Wolkowicz, Romesh Saigal, and Lieven Vandenberghe (Springer US, Boston, MA, 2000) pp. 29-65.
https://doi.org/10.1007/978-1-4615-4381-7_3

[61] P. Sonneveld, J.J.I.M. van Kan, X. Huang, and C.W. Oosterlee, ``Nonnegative matrix factorization of a correlation matrix,'' Linear Algebra and its Applications 431, 334 - 349 (2009).
https://doi.org/10.1016/j.laa.2009.01.004

► Cited by (beta)

[1] Eyal Cornfeld, Moshe Goldstein, Eran Sela, "Imbalance entanglement: Symmetry decomposition of negativity", Physical Review A 98 3, 032302 (2018).

[2] Michał Oszmaniec, Daniel J Brod, "Classical simulation of photonic linear optics with lost particles", New Journal of Physics 20 9, 092002 (2018).

[3] Joshua Lockhart, Otfried Gühne, Simone Severini, "Entanglement properties of quantum grid states", Physical Review A 97 6, 062340 (2018).

[4] Maciej Demianowicz, Remigiusz Augusiak, "From unextendible product bases to genuinely entangled subspaces", Physical Review A 98 1, 012313 (2018).

(The above data is from Crossref's cited-by service. Unfortunately not all publishers provide suitable and complete citation data so that some citing works or bibliographic details may be missing.)