Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1310.4125

Generalised probabilistic theories and conic extensions of polytopes

Samuel Fiorini, Serge Massar, Manas K. Patra, Hans Raj Tiwary

Published Oct 15, 2013• 6 citations
arXivHTMLPDF

Abstract

Generalized probabilistic theories (GPT) provide a general framework that includes classical and quantum theories. It is described by a cone $C$ and its dual $C^*$. We show that whether some one-way communication complexity problems can be solved within a GPT is equivalent to the recently introduced cone factorisation of the corresponding communication matrix $M$. We also prove an analogue of Holevo's theorem: when the cone $C$ is contained in $\mathbb{R}^{n}$, the classical capacity of the channel realised by sending GPT states and measuring them is bounded by $\log n$. Polytopes and optimising functions over polytopes arise in many areas of discrete mathematics. A conic extension of a polytope is the intersection of a cone $C$ with an affine subspace whose projection onto the original space yields the desired polytope. Extensions of polytopes can sometimes be much simpler geometric objects than the polytope itself. The existence of a conic extension of a polytope is equivalent to that of a cone factorisation of the slack matrix of the polytope, on the same cone. We show that all $0/1$ polytopes whose vertices can be recognized by a polynomial size circuit, which includes as a special case the travelling salesman polytope and many other polytopes from combinatorial optimisation, have small conic extension complexity when the cone is the completely positive cone. Using recent exponential lower bounds on the linear extension complexity of polytopes, this provides 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. Our work thus relates the communication complexity of generalisations of quantum theory to questions of mainstream interest in the area of combinatorial optimisation.

DOI
10.48550/arxiv.1310.4125

Related papers

Generalized probabilistic theories and conic extensions of polytopes

Samuel Fiorini, Serge Massar, Manas K. Patra +1 more

Generalized probabilistic theories (GPT) provide a general framework that includes classical and quantum theories. It is described by a cone C and its dual C *. We show that whether some one-way communication complexity problems can be solved within a GPT is equivalent to the recently introduced cone factorization of the corresponding communication matrix M . We also prove an analogue of Holevoʼs theorem: when the cone C is contained in , the classical capacity of the channel realized by sending GPT states and measuring them is bounded by . Polytopes and optimising functions over polytopes arise in many areas of discrete mathematics. A conic extension of a polytope is the intersection of a cone C with an affine subspace whose projection onto the original space yields the desired polytope. Extensions of polytopes can sometimes be much simpler geometric objects than the polytope itself. The existence of a conic extension of a polytope is equivalent to that of a cone factorization of the slack matrix of the polytope, on the same cone. We show that all polytopes whose vertices can be recognized by a polynomial size circuit, which includes as a special case the travelling salesman polytope and many other polytopes from combinatorial optimization, have small conic extension complexity when the cone is the completely positive cone. Using recent exponential lower bounds on the linear extension complexity of polytopes, this provides 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. Our work thus relates the communication complexity of generalizations of quantum theory to questions of mainstream interest in the area of combinatorial optimization.

Journal of Physics A Mathematical and Theoretical•Dec 11, 2014•10 citations

Accessible fragments of generalized probabilistic theories, cone equivalence, and applications to witnessing nonclassicality

John H. Selby, David Schmid, Elie Wolfe +3 more

The formalism of generalized probabilistic theories (GPTs) was originally developed as a way to characterize the landscape of conceivable physical theories. Thus, the GPT describing a given physical theory necessarily includes all physically possible processes. We here consider the question of how to provide a GPT-like characterization of a particular experimental setup within a given physical theory. We show that the resulting characterization is not generally a GPT in and of itself, rather, it is described by a more general mathematical object that we introduce and term an accessible GPT fragment. We then introduce an equivalence relation, termed cone equivalence, between accessible GPT fragments (and, as a special case, between standard GPTs). We give a number of examples of experimental scenarios that are best described using accessible GPT fragments, and where moreover, cone-equivalence arises naturally. We then prove that an accessible GPT fragment admits of a classical explanation if and only if every other fragment that is cone equivalent to it also admits of a classical explanation. Finally, we leverage this result to prove several fundamental results regarding the experimental requirements for witnessing the failure of generalized noncontextuality. In particular, we prove that neither incompatibility among measurements nor the assumption of freedom of choice is necessary for witnessing failures of generalized noncontextuality, and moreover, that such failures can be witnessed even when using arbitrarily inefficient detectors.

arXiv:2112.04521•Physical Review A•Jun 6, 2023•35 citations

Consistency of Generalised Probabilistic Theories is Undecidable

Serge Massar

Generalised Probabilistic Theories (GPTs) provide a unifying framework encompassing classical theories, quantum theories, as well as hypothetical alternatives. We investigate both the problem of extending a system with a finite set of transformations, and the problem of adding to a translation-invariant set of systems a finite set of entangled states and effects, plus all their images under the translation symmetry. We show that determining whether such extensions are consistent with the axioms of GPTs is undecidable. The source of the undecidability is that these finite extensions can generate infinitely many conditions which must be checked: iterating transformations may produce infinitely many new transformations; and similarly, entangled states and effects may generate infinitely many new states via the analogue of teleportation. Our results show that extending GPTs to include dynamics or entanglement encounters fundamental computability obstructions, which can only be circumvented by introducing additional physical or mathematical assumptions.

quant-pharXiv:2603.07002•Mar 10, 2026•0 citations

Information and communication in polygon theories

Serge Massar, Manas K. Patra

Generalized probabilistic theories (GPTs) provide a framework in which one can formulate physical theories that includes classical and quantum theories, but also many other alternative theories. In order to compare different GPTs, we advocate an approach in which one views a state in a GPT as a resource and quantifies the cost of interconverting between different such resources. We illustrate this approach on polygon theories [New J. Phys. 13, 063024 (2011).] that interpolate (as the number $n$ of edges of the polygon increases) between a classical trit (when $n=3$) and a real quantum bit (when $n=\ensuremath{\infty}$). Our main results are that simulating the transmission of a single $n$-gon state requires more than one qubit, or more than $log(log(n))$ bits, and that $n$-gon states with $n$ odd cannot be simulated by ${n}^{\ensuremath{'}}$-gon states with ${n}^{\ensuremath{'}}$ even (for all $n,{n}^{\ensuremath{'}}$). These results are obtained by showing that the classical capacity of a single $n$-gon state with $n$ even is 1 bit, whereas it is larger than 1 bit when $n$ is odd; by showing that transmitting a single $n$-gon state with $n$ even violates information causality; and by studying the communication complexity cost of the nondeterministic not-equal function using $n$-gon states.

arXiv:1403.2509•Physical Review A•May 20, 2014•21 citations

Classical, quantum, and general probabilistic state-discrimination profiles

Mihály Weiner

For a collection of states indexed by $[n]={1,\ldots,n}$, let $F(H)$ denote the optimal unnormalized minimum discrimination error for each nonempty subfamily $H\subseteq[n]$. We call $F$ the discrimination profile and characterize exactly which profiles can arise in a general probabilistic theory (GPT). For fixed $n$, the GPT region $\mathfrak{G}_n$ is a bounded rational polytope, giving a hierarchy $\mathfrak{C}_n\subseteq\mathfrak{Q}_n\subseteq\mathfrak{G}_n$ of classical, quantum, and GPT profiles, analogous to the local--quantum--no-signalling hierarchy in Bell theory. For $n=3$ we determine the classical and GPT polytopes explicitly. Within $\mathfrak{G}_3$, the classical region is characterized by $β:=F(123)-F(12)-F(13)-F(23)\le0$, while the GPT maximum is $1$. For qubit triples, the maximal value is attained by the trine, $β_{\mathrm{tr}}=3\sqrt3/2-2$, and we prove the dimension-independent quantum bound $β_{\mathrm Q}\le2/3$, with a slight further improvement. Hence $0=β_{\mathrm C}<3\sqrt3/2-2\leβ_{\mathrm Q}\le2/3<1=β_{\mathrm{GPT}}$. We conjecture $β_{\mathrm Q}=β_{\mathrm{tr}}$ and prove this for arbitrary pure-state triples, together with further supporting evidence. For arbitrary $n$, every classical facet admitting a GPT violation already admits a quantum violation in dimension at most $3$. A four-state qubit example shows that quantum success profiles need not be submodular, unlike for $n=3$. Finally, we exhibit a four-dimensional quantum triple whose discrete profile is classical for all subfamilies but becomes nonclassical when unequal priors are allowed.

quant-pharXiv:2609.17920•Sep 17, 2026•0 citations

On the signaling dimension of the cross-polytope

Tamás Bencze, Péter E. Frenkel

In the general probabilistic model of information theory, the signaling dimension of a given communication protocol (or, equivalently, of its state space) is the smallest possible complexity of a classical communication protocol capable of perfectly simulating the given one in terms of input-output correlations. The signaling dimensions of three-, four-, and five-dimensional cross-polytopes have been known to be 3. We give logarithmic lower and upper bounds for the signaling dimensions of higher dimensional cross-polytopes, pinning down the value up to an additive gap of 2. The lower bound shows that the signaling dimension goes to infinity, in contrast to the case of balls and hypercubes.

arXiv:2610.05924•Oct 5, 2026•0 citations
Generalized probabilistic theories (GPT) provide a general framework that includes classical and quantum theories. It is described by a cone CCC and its dual C∗C^*C∗. We show that whether some one-way communication complexity problems can be solved within a GPT is equivalent to the recently introduced cone factorisation of the corresponding communication matrix MMM. We also prove an analogue of Holevo's theorem: when the cone CCC is contained in Rn\mathbb{R}^{n}Rn, the classical capacity of the channel realised by sending GPT states and measuring them is bounded by log⁡n\log nlogn. Polytopes and optimising functions over polytopes arise in many areas of discrete mathematics. A conic extension of a polytope is the intersection of a cone CCC with an affine subspace whose projection onto the original space yields the desired polytope. Extensions of polytopes can sometimes be much simpler geometric objects than the polytope itself. The existence of a conic extension of a polytope is equivalent to that of a cone factorisation of the slack matrix of the polytope, on the same cone. We show that all 0/10/10/1 polytopes whose vertices can be recognized by a polynomial size circuit, which includes as a special case the travelling salesman polytope and many other polytopes from combinatorial optimisation, have small conic extension complexity when the cone is the completely positive cone. Using recent exponential lower bounds on the linear extension complexity of polytopes, this provides 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. Our work thus relates the communication complexity of generalisations of quantum theory to questions of mainstream interest in the area of combinatorial optimisation.
Generalized probabilistic theories (GPT) provide a general framework that includes classical and quantum theories. It is described by a cone C and its dual C *. We show that whether some one-way communication complexity problems can be solved within a GPT is equivalent to the recently introduced cone factorization of the corresponding communication matrix M . We also prove an analogue of Holevoʼs theorem: when the cone C is contained in , the classical capacity of the channel realized by sending GPT states and measuring them is bounded by . Polytopes and optimising functions over polytopes arise in many areas of discrete mathematics. A conic extension of a polytope is the intersection of a cone C with an affine subspace whose projection onto the original space yields the desired polytope. Extensions of polytopes can sometimes be much simpler geometric objects than the polytope itself. The existence of a conic extension of a polytope is equivalent to that of a cone factorization of the slack matrix of the polytope, on the same cone. We show that all polytopes whose vertices can be recognized by a polynomial size circuit, which includes as a special case the travelling salesman polytope and many other polytopes from combinatorial optimization, have small conic extension complexity when the cone is the completely positive cone. Using recent exponential lower bounds on the linear extension complexity of polytopes, this provides 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. Our work thus relates the communication complexity of generalizations of quantum theory to questions of mainstream interest in the area of combinatorial optimization.
The formalism of generalized probabilistic theories (GPTs) was originally developed as a way to characterize the landscape of conceivable physical theories. Thus, the GPT describing a given physical theory necessarily includes all physically possible processes. We here consider the question of how to provide a GPT-like characterization of a particular experimental setup within a given physical theory. We show that the resulting characterization is not generally a GPT in and of itself, rather, it is described by a more general mathematical object that we introduce and term an accessible GPT fragment. We then introduce an equivalence relation, termed cone equivalence, between accessible GPT fragments (and, as a special case, between standard GPTs). We give a number of examples of experimental scenarios that are best described using accessible GPT fragments, and where moreover, cone-equivalence arises naturally. We then prove that an accessible GPT fragment admits of a classical explanation if and only if every other fragment that is cone equivalent to it also admits of a classical explanation. Finally, we leverage this result to prove several fundamental results regarding the experimental requirements for witnessing the failure of generalized noncontextuality. In particular, we prove that neither incompatibility among measurements nor the assumption of freedom of choice is necessary for witnessing failures of generalized noncontextuality, and moreover, that such failures can be witnessed even when using arbitrarily inefficient detectors.
Generalised Probabilistic Theories (GPTs) provide a unifying framework encompassing classical theories, quantum theories, as well as hypothetical alternatives. We investigate both the problem of extending a system with a finite set of transformations, and the problem of adding to a translation-invariant set of systems a finite set of entangled states and effects, plus all their images under the translation symmetry. We show that determining whether such extensions are consistent with the axioms of GPTs is undecidable. The source of the undecidability is that these finite extensions can generate infinitely many conditions which must be checked: iterating transformations may produce infinitely many new transformations; and similarly, entangled states and effects may generate infinitely many new states via the analogue of teleportation. Our results show that extending GPTs to include dynamics or entanglement encounters fundamental computability obstructions, which can only be circumvented by introducing additional physical or mathematical assumptions.
Generalized probabilistic theories (GPTs) provide a framework in which one can formulate physical theories that includes classical and quantum theories, but also many other alternative theories. In order to compare different GPTs, we advocate an approach in which one views a state in a GPT as a resource and quantifies the cost of interconverting between different such resources. We illustrate this approach on polygon theories [New J. Phys. 13, 063024 (2011).] that interpolate (as the number nnn of edges of the polygon increases) between a classical trit (when n=3n=3n=3) and a real quantum bit (when $n=\ensuremath{\infty}$). Our main results are that simulating the transmission of a single nnn-gon state requires more than one qubit, or more than log(log(n))log(log(n))log(log(n)) bits, and that nnn-gon states with nnn odd cannot be simulated by ${n}^{\ensuremath{'}}$-gon states with ${n}^{\ensuremath{'}}$ even (for all $n,{n}^{\ensuremath{'}}$). These results are obtained by showing that the classical capacity of a single nnn-gon state with nnn even is 1 bit, whereas it is larger than 1 bit when nnn is odd; by showing that transmitting a single nnn-gon state with nnn even violates information causality; and by studying the communication complexity cost of the nondeterministic not-equal function using nnn-gon states.
For a collection of states indexed by [n]=1,…,n[n]={1,\ldots,n}[n]=1,…,n, let F(H)F(H)F(H) denote the optimal unnormalized minimum discrimination error for each nonempty subfamily H⊆[n]H\subseteq[n]H⊆[n]. We call FFF the discrimination profile and characterize exactly which profiles can arise in a general probabilistic theory (GPT). For fixed nnn, the GPT region Gn\mathfrak{G}_nGn​ is a bounded rational polytope, giving a hierarchy Cn⊆Qn⊆Gn\mathfrak{C}_n\subseteq\mathfrak{Q}_n\subseteq\mathfrak{G}_nCn​⊆Qn​⊆Gn​ of classical, quantum, and GPT profiles, analogous to the local--quantum--no-signalling hierarchy in Bell theory. For n=3n=3n=3 we determine the classical and GPT polytopes explicitly. Within G3\mathfrak{G}_3G3​, the classical region is characterized by β:=F(123)−F(12)−F(13)−F(23)≤0β:=F(123)-F(12)-F(13)-F(23)\le0β:=F(123)−F(12)−F(13)−F(23)≤0, while the GPT maximum is 111. For qubit triples, the maximal value is attained by the trine, βtr=33/2−2β_{\mathrm{tr}}=3\sqrt3/2-2βtr​=33​/2−2, and we prove the dimension-independent quantum bound βQ≤2/3β_{\mathrm Q}\le2/3βQ​≤2/3, with a slight further improvement. Hence 0=βC<33/2−2≤βQ≤2/3<1=βGPT0=β_{\mathrm C}<3\sqrt3/2-2\leβ_{\mathrm Q}\le2/3<1=β_{\mathrm{GPT}}0=βC​<33​/2−2≤βQ​≤2/3<1=βGPT​. We conjecture βQ=βtrβ_{\mathrm Q}=β_{\mathrm{tr}}βQ​=βtr​ and prove this for arbitrary pure-state triples, together with further supporting evidence. For arbitrary nnn, every classical facet admitting a GPT violation already admits a quantum violation in dimension at most 333. A four-state qubit example shows that quantum success profiles need not be submodular, unlike for n=3n=3n=3. Finally, we exhibit a four-dimensional quantum triple whose discrete profile is classical for all subfamilies but becomes nonclassical when unequal priors are allowed.
In the general probabilistic model of information theory, the signaling dimension of a given communication protocol (or, equivalently, of its state space) is the smallest possible complexity of a classical communication protocol capable of perfectly simulating the given one in terms of input-output correlations. The signaling dimensions of three-, four-, and five-dimensional cross-polytopes have been known to be 3. We give logarithmic lower and upper bounds for the signaling dimensions of higher dimensional cross-polytopes, pinning down the value up to an additive gap of 2. The lower bound shows that the signaling dimension goes to infinity, in contrast to the case of balls and hypercubes.