Generalised Probabilistic Theories and the extension complexity of polytopes

Add to your list(s) Download to your calendar using vCal

• Massar, S (Universit Libre Bruxelles)
• Tuesday 03 December 2013, 14:00-15:00
• Seminar Room 2, Newton Institute Gatehouse.

If you have a question about this talk, please contact Mustapha Amrani.

This talk has been canceled/deleted

In this work we present connections between the foundations of quantum mechanics, communication complexity, and the geometry of polytopes. Generalised Probabilistic Theories are a framework, described by a cone C and its dual C*, that allows generalisations of both classical and quantum theories.

Communication complexity is the area of computers science that studies how much communication between two parties is necessary for them to solve specific tasks.

We compare communication complexity when the states that are sent are classical, quantum, or states of a GPT . The existence of a randomised one-way communication complexity problems with positive outputs using classical (quantum) (GPT) states that produces on average the matrix M is equivalent to the linear (SDP) (cone) factorization of M.

Polytopes arise in many areas of combinatorics. For instance solving the famous NP-complete Travelling Salesman Problem (TSP) is equivalent to linear optimisation over the corresponding TSP polytope.

However many polytopes of interest (such as the TSP polytope) have exponentially many facets, which makes them intractable. An extended formulation of a polytope is a geometric object in a larger dimensional space whose projection onto the original space yields the desired polytope. Linear extensions of polytopes are given in terms of linear programs. Semi-definite and conic extensions of polytopes are given in terms of semi-definite positive (SDP) and conic programs. The extended formulation can sometimes be much simpler than the original polytope, hence the interest in extended formulations and the definition of the linear (SDP) (conic) extension complexity of a polytope as the size of the corresponding linear (SDP) (conic) program.

The existence of a linear (SDP) (cone) extension of a polytope is equivalent to the cone factorisation of the slack matrix S of the polytope, and hence to a classical (quantum) (GPT) communication complexity problem. Using these connections, we show that all linear programs whose associated polytope projects to the traveling salesman polytope have exponential size. That is the linear extension complexity of the TSP polytope is exponential.

The completely positive cone has a simple operational interpretation: it is the cone of density matrices obtained as convex combinations of quantum states with positive real coefficients. This cone is known to have an extremely complex geometry. All combinatorial polytopes, including the TSP polytope and any polytope whose vertices can be computed in polynomial time on a Turing machine, have polynomial size conic extension complexity when the cone is the completely positive cone.

Using the connection with communication complexity, this implies an exponential gap between the communication complexity of GPT based on the completely positive cone and classical communication complexity, and a conjectured exponential gap with quantum communication complexity.

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

This talk is not included in any other list

Note that ex-directory lists are not shown.