Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization

DOI10.1007/S10107-018-1287-ZzbMATH Open1456.90122arXiv1708.09696OpenAlexW2752158681WikidataQ93164458 ScholiaQ93164458MaRDI QIDQ1650765FDOQ1650765

Authors: Sander Gribling, David de Laat, Monique Laurent 

Publication date: 13 July 2018

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: In this paper we study bipartite quantum correlations using techniques from tracial noncommutative polynomial optimization. We construct a hierarchy of semidefinite programming lower bounds on the minimal entanglement dimension of a bipartite correlation. This hierarchy converges to a new parameter: the minimal average entanglement dimension, which measures the amount of entanglement needed to reproduce a quantum correlation when access to shared randomness is free. For synchronous correlations, we show a correspondence between the minimal entanglement dimension and the completely positive semidefinite rank of an associated matrix. We then study optimization over the set of synchronous correlations by investigating quantum graph parameters. We unify existing bounds on the quantum chromatic number and the quantum stability number by placing them in the framework of tracial optimization. In particular, we show that the projective packing number, the projective rank, and the tracial rank arise naturally when considering tracial analogues of the Lasserre hierarchy for the stability and chromatic number of a graph. We also introduce semidefinite programming hierarchies converging to the commuting quantum chromatic number and commuting quantum stability number.

Full work available at URL: https://arxiv.org/abs/1708.09696

Recommendations

• Optimization over trace polynomials
• Quantum bilinear optimization
• Convergent relaxations of polynomial optimization problems with noncommuting variables
• Quantum entanglement and approximation by positive matrices
• Estimating quantum chromatic numbers

zbMATH Keywords

polynomial optimizationquantum graph parametersquantum correlationentanglement dimension

Mathematics Subject Classification ID

Semidefinite programming (90C22) Coloring of graphs and hypergraphs (05C15) Quantum coherence, entanglement, quantum correlations (81P40) Quantum information, communication, networks (quantum-theoretic aspects) (81P45) Polynomial optimization (90C23)

Cites Work

• On the quantum chromatic number of a graph
• Quantum graph homomorphisms via operator systems
• Quantum homomorphisms
• Global optimization with polynomials and the problem of moments
• Title not available (Why is that?)
• Synchronous correlation matrices and Connes' embedding conjecture
• New Separations in Zero-Error Channel Capacity Through Projective Kochen–Specker Sets and Quantum Coloring
• On the Shannon capacity of a graph
• Proposed experiment to test local hidden-variable theories
• Operator algebras. Theory of \(C^*\)-algebras and von Neumann algebras
• Simple unified form for the major no-hidden-variables theorems
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• Kneser's conjecture, chromatic number, and homotopy
• The Operator $\Psi$ for the Chromatic Number of a Graph
• Solution of the truncated complex moment problem for flat data
• Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
• Connes' embedding conjecture and sums of Hermitian squares
• Convergent relaxations of polynomial optimization problems with noncommuting variables
• Matrices with high completely positive semidefinite rank
• The tracial moment problem and trace-optimization of polynomials
• Tsirelson's problem and Kirchberg's conjecture
• About the Connes embedding conjecture
• Computing Semidefinite Programming Lower Bounds for the (Fractional) Chromatic Number Via Block-Diagonalization
• Connes' embedding problem and Tsirelson's problem
• Linear conic formulations for two-party correlations and values of nonlocal games
• Estimating quantum chromatic numbers
• Testing the dimension of Hilbert spaces
• Symmetric tensor nuclear norms
• A non-commutative spectral theorem
• The truncated tracial moment problem
• Brownian local minima, random dense countable sets and random equivalence classes
• Title not available (Why is that?)
• Optimization of polynomials in non-commuting variables
• Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization
• Completely positive semidefinite rank
• Survey on nonlocal games and operator space theory
• SDP relaxations for non-commutative polynomial optimization
• Constrained trace-optimization of polynomials in freely noncommuting variables

Cited In (11)

• Lifting for simplicity: concise descriptions of convex sets
• Minimizer Extraction in Polynomial Optimization Is Robust
• Optimization over trace polynomials
• Quantum entanglement, symmetric nonnegative quadratic polynomials and moment problems
• Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization
• Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
• Certifying optimality of Bell inequality violations: noncommutative polynomial optimization through semidefinite programming and local optimization
• \texttt{libCreme}: an optimization library for evaluating convex-roof entanglement measures
• Sparse noncommutative polynomial optimization
• Exploiting term sparsity in noncommutative polynomial optimization
• The constant trace property in noncommutative optimization

This page was built for publication: Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1650765)