Semidefinite programming relaxations for quantum correlations

Semidefinite programs are convex optimisation problems involving a linear objective function and a domain of positive-semidefinite matrices.Over the past two decades, they have become an indispensable tool in quantum information science.Many otherwise intractable fundamental and applied problems can be successfully approached by means of relaxation to a semidefinite program.Here, we review such methodology in the context of quantum correlations.We discuss how the core idea of semidefinite relaxations can be adapted for a variety of research topics in quantum correlations, including nonlocality, quantum communication, quantum networks, entanglement, and quantum cryptography. CONTENTSI. Introduction 2 II.Background 3 A. Primals and duals 3 B. Correlation scenarios and quantum theory 3 1.Entanglement-based scenarios 4 2. Communication-based scenarios 7 C. Overview of semidefinite relaxation hierarchies 9 III.Semidefinite relaxations for polynomial optimisation 9 A. Commutative polynomial optimisation 9 1.Moment matrix approach 9 2. Sum of squares approach 11 B. Noncommutative polynomial optimisation 12 1.Moment matrix approach 12 2. Sum of squares approach 13 IV.Entanglement 14 A. Doherty-Parrilo-Spedalieri hierarchy 14 B. Bipartite entanglement 15 1.Quantifying entanglement 15 2. Detecting the entanglement dimension 17 C. Multipartite entanglement 18 1.Entanglement detection 18 2.Quantum marginal problems 19 V.Quantum nonlocality 20 A. The Navascués-Pironio-Acín hierarchy 20 1. Macroscopic Locality & Almost-Quantum Correlations 21 2. Tsirelson bounds 22 B. Device-independent certification 23 1.Self-testing 23 2. Entanglement dimension 24 3. Entanglement certification 25 4. Joint measurability 26 VI.Quantum communication 27 A. Channel capacities 27 1.Classical capacities 28 2. Quantum capacities 30 B. Dimension constraints 30 1. Bounding the quantum set 31 2. Applications 32 3. Entanglement-assisted communication 4. Teleportation C. Distinguishability problems 1.Distinguishability constraints for quantum communication 2. Discrimination tasks VII.Randomness and quantum key distribution A. Device-independent approach 1. Bounding the min-entropy 2. Bounding the von Neumann entropy 3. Beyond entropy optimisations B. Device-dependent approach 1. Bounding the min-entropy 2. Bounding the von Neumann entropy C. Semi-device-independent approach VIII.Correlations in networks A. Inflation methods 1. Classical inflation 2. Quantum inflation 3. No-signaling and independence 4. Entanglement in networks B. Other SDP methods in network correlations 1. Relaxations of factorisation 2. Tests for network topology IX.Further topics and methods A. Classical models for quantum correlations B. Generalised Bell scenarios C. Bounding ground-state energies D. Rank-constrained optimisation E. Quantum contextuality F. Symmetrisation methods X. Conclusions A. Table of abbreviations B. Implementation guide C. Strict feasibility optimal value of Eq. (12) is nonnegative.As before, it is also interesting to consider the dual LP, min {c abxy } a,b,x,y c abxy p(a, b|x, y) s.t.λ,a,b,x,y c abxy D(a|x, λ)D(b|y, λ) = 1, a,b,x,y c abxy D(a|x, λ)D(b|y, λ) ≥ 0 ∀ λ.