×

An improved semidefinite programming hierarchy for testing entanglement. (English) Zbl 1364.81041

Summary: We present a stronger version of the Doherty-Parrilo-Spedalieri (DPS) hierarchy of approximations for the set of separable states. Unlike DPS, our hierarchy converges exactly at a finite number of rounds for any fixed input dimension. This yields an algorithm for separability testing that is singly exponential in dimension and polylogarithmic in accuracy. Our analysis makes use of tools from algebraic geometry, but our algorithm is elementary and differs from DPS only by one simple additional collection of constraints.

MSC:

81P40 Quantum coherence, entanglement, quantum correlations
65D15 Algorithms for approximation of functions

Software:

YALMIP; Mosek
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Grötschel, M., Lovász, L. Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol. 2, second corrected edition edn., Springer (1993) · Zbl 0837.05001
[2] Liu, Y.K.: The complexity of the consistency and N-representability problems for quantum states. Ph.D. thesis, University of California, San Diego (2007) arXiv:0712.3041 · Zbl 1190.14051
[3] Harrow, A.W., Montanaro, A.: Testing product states, quantum Merlin-Arthur games and tensor optimization. J. ACM 60(1), 3:1 (2013). arXiv:1001.0017 · Zbl 1281.68112
[4] Beigi, S., Shor, P.W.: Approximating the set of separable states using the positive partial transpose test. J. Math. Phys. 51(4), 042202 (2010) arXiv:0902.1806 · Zbl 1310.81026
[5] Gall, F.L., Nakagawa, S., Nishimura, H.: On QMA protocols with two short quantum proofs. Q. Inf. Comp. 12, 589 (2012) arXiv:1108.4306 · Zbl 1260.81048
[6] Cubitt, T.S., Perez-Garcia, D., Wolf, M.: Undecidability of the spectral gap problem (2014). (In preparation) · Zbl 1513.81051
[7] Ito, T., Kobayashi, H., Watrous, J.: Quantum Interactive Proofs with Weak Error Bounds. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (2012), ITCS ’12, pp. 266-275. arXiv:1012.4427 · Zbl 1347.68152
[8] Basu S., Pollack R., Roy M.F.: On the combinatorial and algebraic complexity of quantifier elimination. J. ACM 43, 1002 (1996) · Zbl 0885.68070 · doi:10.1145/235809.235813
[9] Doherty, A.C., Parrilo, P.A., Spedalieri, F.M.: A complete family of separability criteria (2003) arXiv:quant-ph/0308032 · Zbl 0796.12002
[10] Barak, B., Steurer D.: Sum-of-squares proofs and the quest toward optimal algorithms (2014) arXiv:1404.5236 · Zbl 1373.68253
[11] Nie J.: An exact Jacobian SDP relaxation for polynomial optimization. Math. Program. 137, 225 (2013) arXiv:1006.2418 · Zbl 1266.65094 · doi:10.1007/s10107-011-0489-4
[12] Gharibian S.: Strong NP-hardness of the quantum separability problem. QIC 10, 343 (2010) arXiv:0810.4507 · Zbl 1234.81033
[13] Aaronson, S., Impagliazzo, R., Moshkovitz, D.: AM with multiple merlins. In: Computational Complexity (CCC), 2014 IEEE 29th Conference on (2014), pp. 44-55. arXiv:1401.6848 · Zbl 1367.90002
[14] Barak, B., Brandão, F.G.S.L., Harrow, A.W., Kelner, J., Steurer, D., Zhou, Y.: Hypercontractivity, sum-of-squares proofs, and their applications. In: Proceedings of the 44th symposium on Theory of Computing (2012), STOC ’12, pp. 307-326 arXiv:1205.4484 · Zbl 1286.68176
[15] Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity?. In: Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on (IEEE, 1998), pp. 653-662 · Zbl 1006.68052
[16] Gurvits, L.: Classical deterministic complexity of Edmonds’ problem and quantum entanglement (2003) arXiv:quant-ph/0303055 · Zbl 1192.68252
[17] Blier, H., Tapp, A.: All languages in NP have very short quantum proofs. In: First International Conference on Quantum, Nano, and Micro Technologies. IEEE Computer Society, Los Alamitos, CA, USA, (2009), pp. 34-37 arXiv:0709.0738 · Zbl 1234.81033
[18] Chiesa, A., Forbes, M.A.: Improved soundness for QMA with multiple provers. Chic. J. Theor. Comput. Sci. 2013(1) (2013) arXiv:1108.2098 · Zbl 1286.68150
[19] Navascués M., Owari M., Plenio M.B.: Power of symmetric extensions for entanglement detection. Phys. Rev. A 80, 052306 (2009) arXiv:0906.2731 · Zbl 1274.81048 · doi:10.1103/PhysRevA.80.052306
[20] Aaronson, S., Beigi, S., Drucker, A., Fefferman, B., Shor, P.: The power of unentanglement. Annual IEEE Conference on Computational Complexity 0, 223 (2008) arXiv:0804.0802 · Zbl 1213.68280
[21] Chen, J., Drucker, A.: Short multi-prover quantum proofs for SAT without entangled measurements (2010) arXiv:1011.0716
[22] Brandão, F.G.S.L., Christandl, M., Yard, J.: Faithful squashed entanglement. Comm. Math. Phys. 306, 805 (2011) arXiv:1010.1750 · Zbl 1231.81011
[23] Li, K., Winter, A.: Relative entropy and squashed entanglement. Comm. Math. Phys. 326, 63 (2014) arXiv:1210.3181 · Zbl 1315.81023
[24] Brandão, F.G.S.L., Harrow, A.W.: Quantum de Finetti theorems under local measurements with applications. In: Proceedings of the 45th annual ACM Symposium on theory of computing. (2013), STOC ’13, pp. 861-870 arXiv:1210.6367 · Zbl 1293.68126
[25] Shi, Y., Wu, X.: Epsilon-net method for optimizations over separable states. In: ICALP12. Springer, (2012), pp. 798-809 arXiv:1112.0808 · Zbl 1272.68136
[26] Brandão, F.G., Harrow, A.W.: Estimating injective tensor norms using nets (2014). (In preparation)
[27] Li, K., Smith, G.: Quantum de Finetti theorem measured with fully one-way LOCC norm (2014) arXiv:1408.6829 · Zbl 1190.14051
[28] Putinar M.: Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42, 969 (1993) · Zbl 0796.12002 · doi:10.1512/iumj.1993.42.42045
[29] Buhrman, H., Regev, O., Scarpa, G., de Wolf, R.: Near-optimal and explicit Bell inequality violations. In: Proceedings of the 2011 IEEE 26th Annual Conference on Computational Complexity. (2011), CCC ’11, pp. 157-166. arXiv:1012.5043 · Zbl 1298.81034
[30] Klerk, E., Laurent, M., Parrilo, P.: On the equivalence of algebraic approaches to the minimization of forms on the simplex. In: Henrion, D., Garulli, A. (eds.) Positive Polynomials in Control, Lecture Notes in Control and Information Science, vol. 312, Springer Berlin Heidelberg, (2005), pp. 121-132. · Zbl 1138.90439
[31] Löfberg, J.: YALMIP : A toolbox for modeling and optimization in MATLAB. In: In Proceedings of the CACSD Conference Taipei, Taiwan, (2004)
[32] Löfberg J.: Pre- and post-processing sum-of-squares programs in practice. IEEE Trans. Autom. Control 54, 1007 (2009) · Zbl 1367.90002 · doi:10.1109/TAC.2009.2017144
[33] MOSEK ApS: The MOSEK optimization toolbox for MATLAB manual. Version 7.1 (Revision 28). (2015)
[34] Permenter, F., Parrilo, P.: Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone (2014) arXiv:1408.4685 · Zbl 1405.90098
[35] Laurent, M.: Sums of squares, Moment matrices and optimization over polynomials. In: Putinar, M., Sullivant, S. (eds) Emerging Applications of Algebraic Geometry, The IMA Volumes in Mathematics and its Applications, vol. 149, Springer New York, (2009), pp. 157-270 · Zbl 1163.13021
[36] Nie J., Ranestad K.: Algebraic degree of polynomial optimization. SIAM J. Optim. 20, 485 (2009). doi:10.1137/080716670 · Zbl 1190.14051 · doi:10.1137/080716670
[37] Trnovská M.: Strong duality conditions in semidefinite programming. J. Electr. Eng. 56, 1 (2005) · Zbl 1105.90057
[38] Cédric Josz, C.(INRIA), Henrion, Didier: (LAAS. Strong duality in Lasserre’s hierarchy for polynomial optimization. Optim. lett. 10, 3 (2016) arXiv:1405.7334 · Zbl 1339.90267
[39] Shapiro, A.: First and second order analysis of nonlinear semidefinite programs. Mathematical Programming pp. 301 (1997) · Zbl 0888.90127
[40] Strelchuk S., Oppenheim J.: Hybrid zero-capacity channels. Phys. Rev. A 86, 022328 (2012) arXiv:1207.1084 · doi:10.1103/PhysRevA.86.022328
[41] Pereszlényi, A.: Multi-prover quantum Merlin-Arthur proof systems with small gap. (2012) arXiv:1205.2761 · Zbl 1286.68162
[42] Cox, D., little, J., O’Shea, D.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, second edition edn. Undergarduate texts in mathematics. Springer, (1996) · Zbl 0861.13012
[43] Harris, J.: Algebraic geometry: a first course. Graduate texts in mathematics. Springer, (1992) · Zbl 0779.14001
[44] Buchberger B.: Ein algorithmisches Kriterum für die Lösbarkeit eines algebraisches Gleichungssystems. Aequationes Mathematicae 4, 374 (1970) · Zbl 0212.06401 · doi:10.1007/BF01844169
[45] Mayr, E.W., Ritscher, S.: Degree bounds for GröBner bases of low-dimensional polynomial ideals. In: Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation. ACM, New York, NY, USA, (2010), ISSAC ’10, pp. 21-27. · Zbl 1321.68539
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.