Generalised Probabilistic Theories and the extension complexity of polytopes

Generalised Probabilistic Theories and the extension complexity of polytopes

Seminar author:Serge Massar

Event date and time:10/29/2013 03:00:pm

Event location:IFAE seminar room

Event contact:

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) is equivalent to the linear (SDP) (cone) factorization of the corresponding communication matrix 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.

All linear programs whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric, have exponential size. That is the linear extension complexity of the TSP polytope is exponential. This solves a 20 year old open problem.

The completely positive cone has a simple operational interpretation: it is the cone of density matrices obtained as convex combinations of 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.

References :
-S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, R. de Wolf, “Linear vs. Semi definite Extended Formulations: Exponential Separation and Strong Lower Bounds”,  In Proceedings of STOC 2012, p. 95 (best paper award at STOC, selected as “complexity paper of the year” on the “complexity blog”)
-S. Fiorini, S. Massar, M. K. Patra, H. R. Tiwary, Generalised probabilistic theories and the extension complexity of polytopes, in preparation.