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:1403.2509 · Physical Review A

Information and communication in polygon theories

Serge Massar, Manas K. Patra

Published May 20, 2014• 21 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.89.052124

Related papers

Generalised 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 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.

arXiv:1310.4125•Oct 15, 2013•6 citations

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

Birkhoff violation in even-polygon general probabilistic theories: implications for state transformations and information processing

Ananya Chakraborty, Sahil Gopalkrishna Naik, Samrat Sen +4 more

Abstract The entropy principle asserts that spontaneous processes drive systems toward states of higher disorder. Operational origin of such randomness is a question of utmost importance. The seminal Birkhoff theorem (also known as Birkhoff–von Neumann theorem) identifies doubly stochastic transformations as convex mixtures of reversible transformations, thereby providing an epistemic account of disorder. Quantum theory, however, does not satisfy this equivalence in general. In this work, we investigate this question within the framework of Generalized Probabilistic Theories (GPTs). We prove a violation of the Birkhoff theorem in the square-bit model, a canonical non-quantum GPT, and further show that this violation persists asymptotically under tensor products of any finite, yet arbitrarily large, number of copies of even-polygon models. This provides evidence that the failure of the Birkhoff theorem is an intrinsic operational feature of a wide class of GPTs, rather than a peculiarity of quantum theory. Furthermore, we show that, beyond quantum theory, the preorder over states induced by mixtures of reversible transformations can differ from that induced by doubly stochastic transformations, leading to inequivalent notions of state convertibility and distinct resource theories of purity. Beyond its foundational significance, we show that the violation of the Birkhoff theorem admits a concrete operational interpretation: in the square-bit theory, it serves as a genuine resource for enhancing the performance of Random Access Codes. Finally, we discuss the construction of entropy functions in GPTs that remain consistent with thermodynamic principles, in the spirit of von Neumann’s formulation.

Journal of Physics A Mathematical and Theoretical•Oct 14, 2026•0 citations

Information Thermodynamics in Generalized Probabilistic Theories

Koki Ono, Shun Umekawa, Hiroyasu Tajima

Generalized probabilistic theories (GPTs) provide a unified framework for describing probabilistic physical theories, encompassing classical and quantum theories as well as hypothetical theories beyond quantum mechanics. Since most GPTs are highly unrealistic and far removed from known physical theories, it is important to constrain them by physically reasonable principles. One of the most important such principles is consistency with thermodynamics, which has been extensively studied through toy models involving semipermeable membranes (SPMs) implementing measurements. On the other hand, information thermodynamics, which plays a central role in understanding the relationship between measurement and thermodynamics in classical and quantum theory, has remained largely undeveloped in GPTs. In this work, we construct information thermodynamics in GPTs and provide a unified framework for analyzing the relationship between measurement, feedback, information erasure, and the second law of thermodynamics. We also formulate a general framework for SPM models and analyze the thermodynamic cost of measurements implemented by SPMs. As a result, we show that no work can be extracted in contradiction with the second law as long as the measurement processes are consistent with entropy nondecrease, and derive sufficient conditions for this property for several entropy definitions proposed in GPTs. Moreover, by considering measurement processes violating these conditions, we construct explicit GPT systems realizing isothermal SPM cycles from which positive work can be extracted. These results demonstrate that violations of the second law can arise from the lack of fundamental entropy properties or discrepancies between entropy definitions, and provide a unified and model-independent foundation for understanding the relationship between thermodynamics and measurement in GPTs.

quant-pharXiv:2605.12331•May 13, 2026•0 citations

Classical communication rates for simulating quantum resources

A. Montina, Marcel Pfaffhauser, Stefan Wolf

Quantum theory is, in some sense, “non-classical.” For instance, the behavior of entangled systems (i.e., shared quantum information) under measurements cannot, in general, be explained by shared classical information. With classical communication, on the other hand, both the correlations entanglement leads to as well as quantum channels can be reproduced in principle. Here, crucial questions are whether the required communications is finite; if so, then its exact amount is related to the “degree of non-classicality” of the quantum primitive. We apply information-theoretic results such as the reverse Shannon theorem for determining the required communication in the asymptotic limit. The communication complexity of a quantum channel is the minimal amount of classical communication required for classically simulating the process of preparation, transmission through the channel, and subsequent measurement of a quantum state. At present, only little is known about this quantity. Our generic procedure allows for systematically evaluating the communication complexity of channels in any general probabilistic theory, in particular quantum theory. The procedure is constructive and provides the most efficient classical protocols. We illustrate it by evaluating the communication complexity of sending single qubits over a noiseless quantum channel with some finite sets of quantum states and measurements. As a second application, we determine the classical-communication rate required for the simulation of the behavior under measurements of entangled states. Here, the communication cost can be directly interpreted as the “non-classicality” of the correlation. A particular example is the simulation of non-maximally entangled pure qubit pairs, where we find the required communication rate to behave monotonically with the strength of the entanglement. For different measures of non-locality, such as the number of required non-local (PR) boxes, another behavior had been reported for the single-shot scenario.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2013•0 citations

Antidistinguishability of states in General Probabilistic Theories

Satyaki Manna, Anandamay Das Bhowmik

We investigate antidistinguishability of states within the framework of general probabilistic theories (GPTs). We formulate antidistinguishability, strong and equal antidistinguishability as refined notions that imposed additional constraint on the measurement effects. We establish general results relating these notions of antidistinguishability and derive an upper bound on the cardinality of equally antidistinguishable sets in terms of the affine dimension of the state space. We then study antidistinguishability in polygonal theories, obtaining conditions for antidistinguishability of a set of states. In consequence, we show that the set of all pure states in a polygon model is antidistinguishable. Additionally, we identify broad families of strongly and equally antidistinguishable states. Finally, using Random Exclusion Codes, whose success probability is governed by the antidistinguishability of different sets of encoding states, we probe the nonclassicality of polygon theories. We find that certain polygon models can outperform the optimal quantum value, while their optimal performance converges to the quantum limit in the large-polygon limit.

quant-pharXiv:2609.17498•Sep 16, 2026•0 citations
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∞n=\ensuremath{\infty}n=\ensuremath∞). 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′{n}^{\ensuremath{'}}n\ensuremath′-gon states with n\ensuremath′{n}^{\ensuremath{'}}n\ensuremath′ even (for all n,n\ensuremath′n,{n}^{\ensuremath{'}}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.
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.
Abstract The entropy principle asserts that spontaneous processes drive systems toward states of higher disorder. Operational origin of such randomness is a question of utmost importance. The seminal Birkhoff theorem (also known as Birkhoff–von Neumann theorem) identifies doubly stochastic transformations as convex mixtures of reversible transformations, thereby providing an epistemic account of disorder. Quantum theory, however, does not satisfy this equivalence in general. In this work, we investigate this question within the framework of Generalized Probabilistic Theories (GPTs). We prove a violation of the Birkhoff theorem in the square-bit model, a canonical non-quantum GPT, and further show that this violation persists asymptotically under tensor products of any finite, yet arbitrarily large, number of copies of even-polygon models. This provides evidence that the failure of the Birkhoff theorem is an intrinsic operational feature of a wide class of GPTs, rather than a peculiarity of quantum theory. Furthermore, we show that, beyond quantum theory, the preorder over states induced by mixtures of reversible transformations can differ from that induced by doubly stochastic transformations, leading to inequivalent notions of state convertibility and distinct resource theories of purity. Beyond its foundational significance, we show that the violation of the Birkhoff theorem admits a concrete operational interpretation: in the square-bit theory, it serves as a genuine resource for enhancing the performance of Random Access Codes. Finally, we discuss the construction of entropy functions in GPTs that remain consistent with thermodynamic principles, in the spirit of von Neumann’s formulation.
Generalized probabilistic theories (GPTs) provide a unified framework for describing probabilistic physical theories, encompassing classical and quantum theories as well as hypothetical theories beyond quantum mechanics. Since most GPTs are highly unrealistic and far removed from known physical theories, it is important to constrain them by physically reasonable principles. One of the most important such principles is consistency with thermodynamics, which has been extensively studied through toy models involving semipermeable membranes (SPMs) implementing measurements. On the other hand, information thermodynamics, which plays a central role in understanding the relationship between measurement and thermodynamics in classical and quantum theory, has remained largely undeveloped in GPTs. In this work, we construct information thermodynamics in GPTs and provide a unified framework for analyzing the relationship between measurement, feedback, information erasure, and the second law of thermodynamics. We also formulate a general framework for SPM models and analyze the thermodynamic cost of measurements implemented by SPMs. As a result, we show that no work can be extracted in contradiction with the second law as long as the measurement processes are consistent with entropy nondecrease, and derive sufficient conditions for this property for several entropy definitions proposed in GPTs. Moreover, by considering measurement processes violating these conditions, we construct explicit GPT systems realizing isothermal SPM cycles from which positive work can be extracted. These results demonstrate that violations of the second law can arise from the lack of fundamental entropy properties or discrepancies between entropy definitions, and provide a unified and model-independent foundation for understanding the relationship between thermodynamics and measurement in GPTs.
Quantum theory is, in some sense, “non-classical.” For instance, the behavior of entangled systems (i.e., shared quantum information) under measurements cannot, in general, be explained by shared classical information. With classical communication, on the other hand, both the correlations entanglement leads to as well as quantum channels can be reproduced in principle. Here, crucial questions are whether the required communications is finite; if so, then its exact amount is related to the “degree of non-classicality” of the quantum primitive. We apply information-theoretic results such as the reverse Shannon theorem for determining the required communication in the asymptotic limit. The communication complexity of a quantum channel is the minimal amount of classical communication required for classically simulating the process of preparation, transmission through the channel, and subsequent measurement of a quantum state. At present, only little is known about this quantity. Our generic procedure allows for systematically evaluating the communication complexity of channels in any general probabilistic theory, in particular quantum theory. The procedure is constructive and provides the most efficient classical protocols. We illustrate it by evaluating the communication complexity of sending single qubits over a noiseless quantum channel with some finite sets of quantum states and measurements. As a second application, we determine the classical-communication rate required for the simulation of the behavior under measurements of entangled states. Here, the communication cost can be directly interpreted as the “non-classicality” of the correlation. A particular example is the simulation of non-maximally entangled pure qubit pairs, where we find the required communication rate to behave monotonically with the strength of the entanglement. For different measures of non-locality, such as the number of required non-local (PR) boxes, another behavior had been reported for the single-shot scenario.
We investigate antidistinguishability of states within the framework of general probabilistic theories (GPTs). We formulate antidistinguishability, strong and equal antidistinguishability as refined notions that imposed additional constraint on the measurement effects. We establish general results relating these notions of antidistinguishability and derive an upper bound on the cardinality of equally antidistinguishable sets in terms of the affine dimension of the state space. We then study antidistinguishability in polygonal theories, obtaining conditions for antidistinguishability of a set of states. In consequence, we show that the set of all pure states in a polygon model is antidistinguishable. Additionally, we identify broad families of strongly and equally antidistinguishable states. Finally, using Random Exclusion Codes, whose success probability is governed by the antidistinguishability of different sets of encoding states, we probe the nonclassicality of polygon theories. We find that certain polygon models can outperform the optimal quantum value, while their optimal performance converges to the quantum limit in the large-polygon limit.