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:2210.10186 · Quantum Information and Computation

Mermin polytopes quantum computation and foundations

Cihan Okay, Ho Yiu Chung, Selman Ipek

Published Jul 1, 2023• 11 citations
arXivHTMLPDF

Abstract

Mermin square scenario provides a simple proof for state-independent contextuality. In this paper, we study polytopes $\MP_\beta$ obtained from the Mermin scenario, parametrized by a function $\beta$ on the set of contexts. Up to combinatorial isomorphism, there are two types of polytopes $\MP_0$ and $\MP_1$ depending on the parity of $\beta$. Our main result is the classification of the vertices of these two polytopes. In addition, we describe the graph associated with the polytopes. All the vertices of $\MP_0$ turn out to be deterministic. This result provides a new topological proof of a celebrated result of Fine characterizing noncontextual distributions on the CHSH scenario. $\MP_1$ can be seen as a nonlocal toy version of $\Lambda$-polytopes, a class of polytopes introduced for the simulation of universal quantum computation. In the $2$-qubit case, we provide a decomposition of the $\Lambda$-polytope using $\MP_1$, whose vertices are classified, and the nonsignaling polytope of the $(2,3,2)$ Bell scenario, whose vertices are well-known.

DOI
10.26421/qic23.9-10-2

Related papers

The degenerate vertices of the $2$-qubit $Λ$-polytope and their update rules

Selman Ipek, Cihan Okay

Recently, a class of objects, known as $Λ$-polytopes, were introduced for classically simulating universal quantum computation with magic states. In $Λ$-simulation, the probabilistic update of $Λ$ vertices under Pauli measurement yields dynamics consistent with quantum mechanics. Thus, an important open problem in the study of $Λ$-polytopes is characterizing its vertices and determining their update rules. In this paper, we obtain and describe the update of all degenerate vertices of $Λ_{2}$, the $2$-qubit $Λ$ polytope. Our approach exploits the fact that $Λ_{2}$ projects to a well-understood polytope $\text{MP}$ consisting of distributions on the Mermin square scenario. More precisely, we study the ``classical" polytope $\overline{\text{MP}}$, which is $\text{MP}$ intersected by the polytope defined by a set of Clauser-Horne-Shimony-Holt (CHSH) inequalities. Owing to a duality between CHSH inequalities and vertices of $\text{MP}$ we utilize a streamlined version of the double-description method for vertex enumeration to obtain certain vertices of $\overline{\text{MP}}$.

arXiv:2312.10734•Dec 17, 2023•5 citations

Lifting noncontextuality inequalities

Raman Choudhary, Rui Soares Barbosa, Adán Cabello

Kochen--Specker contextuality is a fundamental feature of quantum mechanics and a crucial resource for quantum computational advantage and reduction of communication complexity. Its presence is witnessed in empirical data by the violation of noncontextuality inequalities. However, all known noncontextuality inequalities corresponding to facets of noncontextual polytopes are either Bell inequalities or refer to cyclic or state-independent contextuality scenarios. We introduce a general method for lifting noncontextuality inequalities, deriving facets of noncontextual polytopes for more complex scenarios from known facets of simpler subscenarios. Concretely, starting from an arbitrary scenario, the addition of a new measurement or a new outcome preserves the facet-defining nature of any noncontextuality inequality. This extends the results of Pironio [J. Math. Phys. 46, 062112 (2005)] from Bell nonlocality scenarios to contextuality scenarios, unifying liftings of Bell and noncontextuality inequalities. Our method produces facet-defining noncontextuality inequalities in all scenarios with contextual correlations, and we present examples of facet-defining noncontextuality inequalities for scenarios where no examples were known. Our results shed light on the structure of noncontextuality polytopes and the relationship between such polytopes across different scenarios.

arXiv:2401.12349•Physical Review A•May 13, 2024•5 citations

Canonical decomposition of quantum correlations in the framework of generalized nonsignaling theories

Chellasamy Jebarathinam

We introduce the measures, Bell discord (BD) and Mermin discord (MD), to characterize bipartite quantum correlations in the context of nonsignaling (NS) polytopes. These measures divide the full NS polytope into four regions depending on whether BD and/or MD is zero. This division of the NS polytope allows us to obtain a 3-decomposition that any bipartite box with two binary inputs and two binary outputs can be decomposed into Popescu-Rohrlich (PR) box, a maximally local box, and a local box with BD and MD equal to zero. BD and MD quantify two types of nonclassicality of correlations arising from all quantum correlated states which are neither classical-quantum states nor quantum-classical states. BD and MD serve us the semi-device-independent witnesses of nonclassicality of local boxes in that nonzero value of these measures imply incompatible measurements and nonzero quantum discord only when the dimension of the measured states is fixed. The 3-decomposition serves us to isolate the origin of the two types of nonclassicality into a PR-box and a maximally local box which is related to EPR-steering, respectively. We consider a quantum polytope that has an overlap with all the four regions of the full NS polytope to figure out the constraints of quantum correlations.

arXiv:1407.3170•Jul 11, 2014•6 citations

Vertex structure of fiber products of probability polytopes

Aziz Kharoof, Cihan Okay

We develop tools for characterizing vertices of fiber products of polytopes and apply them to simplicial distribution polytopes, a class of probability polytopes arising in quantum foundations and quantum information. In the theory of simplicial distributions, a pair of simplicial sets encoding measurement and outcome spaces determines a convex polytope of compatible probability assignments. Our first results give geometric criteria for detecting vertices of fiber products in terms of support data. These results are obtained in the more general framework of inverse limits of diagrams of polytopes in standard form, and they translate to corresponding criteria for simplicial distributions on arbitrary colimits of measurement spaces. We then focus on one-dimensional measurement spaces, where simplicial distributions recover and generalize local marginal polytopes in graphical models. In this setting, our sharpest results concern dipole graphs, for which we obtain a complete characterization of vertices and refine it to a graph-theoretic criterion. These characterizations are reminiscent of the classical support-graph criteria for transportation polytopes, but they arise in a richer class of polytopes in which vertex structure depends not only on support acyclicity but also on additional geometric compatibility data. Using the collapsing method from simplicial topology, we transfer the dipole characterization to rose graphs and obtain analogous results there. Finally, we apply collapsing to complete bipartite graphs, which encode physically relevant bipartite Bell scenarios, and more generally to arbitrary connected graphs, yielding lower bounds on the number of vertices.

math.COCross-listedarXiv:2603.19479•Mar 23, 2026•3 citations

Local friendliness polytopes in multipartite scenarios

Marwan Haddara, Eric G. Cavalcanti

Recently, the local friendliness (LF) no-go theorem has attracted considerable interest due to its deep foundational implications. This no-go theorem applies to scenarios which combine Bell experiments with Wigner's friend-type setups, containing spacelike separated superobservers assumed to be capable of performing quantum operations on a local observer, also known as their ``friend.'' The theorem shows that a set of assumptions termed ``local friendliness''---weaker than the set of assumptions required for proving Bell's theorem---constrains the space of probabilistic behaviors in extended Wigner's friend scenarios to the ``local friendliness (LF) polytope,'' and that quantum correlations can, in principle, violate those constraints. In this work, we extend the study of local friendliness to multipartite scenarios---with arbitrary but finite numbers of superobservers, friends, measurements, and outcomes---and fully characterize the corresponding LF polytopes, their relationships with each other, with the Bell polytope, the no-signaling polytope, and the quantum set of correlations. In particular, we identify, via constructive proofs, all the canonical LF scenarios where the LF polytope coincides with the Bell polytope---hence identifying all the scenarios where ``genuine LF inequalities'' may arise. Among other results, we also show that whenever the LF polytope is distinct from the Bell and the no-signaling polytope, it also is neither contained in nor contains the quantum set of correlations. Apart from the foundational motivation of better understanding the constraints from local friendliness, our results may also find use in a priori unrelated contexts of device-independent information processing, where the LF polytopes have also been shown to arise, under the name of ``partially deterministic polytopes.''

arXiv:2407.20346•Physical Review A•Jan 9, 2025•7 citations

On the extremal points of the Lambda polytopes and classical simulation of quantum computation with magic states

Cihan Okay, Michael Zurel, Robert Raussendorf

We investigate the $\Lambda$-polytopes, a convex-linear structure recently defined and applied to the classical simulation of quantum computation with magic states by sampling. There is one such polytope, $\Lambda_n$, for every number $n$ of qubits. We establish two properties of the family $\{\Lambda_n, n\in \mathbb{N}\}$, namely (i) Any extremal point (vertex) $A_\alpha \in \Lambda_m$ can be used to construct vertices in $\Lambda_n$, for all $n>m$. (ii) For vertices obtained through this mapping, the classical simulation of quantum computation with magic states can be efficiently reduced to the classical simulation based on the preimage $A_\alpha$. In addition, we describe a new class of vertices in $\Lambda_2$ which is outside the known classification. While the hardness of classical simulation remains an open problem for most extremal points of $\Lambda_n$, the above results extend efficient classical simulation of quantum computations beyond the presently known range.

arXiv:2104.05822•Quantum Information and Computation•Sep 1, 2021•22 citations
Mermin square scenario provides a simple proof for state-independent contextuality. In this paper, we study polytopes \MPβ\MP_\beta\MPβ​ obtained from the Mermin scenario, parametrized by a function β\betaβ on the set of contexts. Up to combinatorial isomorphism, there are two types of polytopes \MP0\MP_0\MP0​ and \MP1\MP_1\MP1​ depending on the parity of β\betaβ. Our main result is the classification of the vertices of these two polytopes. In addition, we describe the graph associated with the polytopes. All the vertices of \MP0\MP_0\MP0​ turn out to be deterministic. This result provides a new topological proof of a celebrated result of Fine characterizing noncontextual distributions on the CHSH scenario. \MP1\MP_1\MP1​ can be seen as a nonlocal toy version of Λ\LambdaΛ-polytopes, a class of polytopes introduced for the simulation of universal quantum computation. In the 222-qubit case, we provide a decomposition of the Λ\LambdaΛ-polytope using \MP1\MP_1\MP1​, whose vertices are classified, and the nonsignaling polytope of the (2,3,2)(2,3,2)(2,3,2) Bell scenario, whose vertices are well-known.
The degenerate vertices of the 222-qubit ΛΛΛ-polytope and their update rules
Recently, a class of objects, known as ΛΛΛ-polytopes, were introduced for classically simulating universal quantum computation with magic states. In ΛΛΛ-simulation, the probabilistic update of ΛΛΛ vertices under Pauli measurement yields dynamics consistent with quantum mechanics. Thus, an important open problem in the study of ΛΛΛ-polytopes is characterizing its vertices and determining their update rules. In this paper, we obtain and describe the update of all degenerate vertices of Λ2Λ_{2}Λ2​, the 222-qubit ΛΛΛ polytope. Our approach exploits the fact that Λ2Λ_{2}Λ2​ projects to a well-understood polytope MP\text{MP}MP consisting of distributions on the Mermin square scenario. More precisely, we study the ``classical" polytope MP‾\overline{\text{MP}}MP, which is MP\text{MP}MP intersected by the polytope defined by a set of Clauser-Horne-Shimony-Holt (CHSH) inequalities. Owing to a duality between CHSH inequalities and vertices of MP\text{MP}MP we utilize a streamlined version of the double-description method for vertex enumeration to obtain certain vertices of MP‾\overline{\text{MP}}MP.
Kochen--Specker contextuality is a fundamental feature of quantum mechanics and a crucial resource for quantum computational advantage and reduction of communication complexity. Its presence is witnessed in empirical data by the violation of noncontextuality inequalities. However, all known noncontextuality inequalities corresponding to facets of noncontextual polytopes are either Bell inequalities or refer to cyclic or state-independent contextuality scenarios. We introduce a general method for lifting noncontextuality inequalities, deriving facets of noncontextual polytopes for more complex scenarios from known facets of simpler subscenarios. Concretely, starting from an arbitrary scenario, the addition of a new measurement or a new outcome preserves the facet-defining nature of any noncontextuality inequality. This extends the results of Pironio [J. Math. Phys. 46, 062112 (2005)] from Bell nonlocality scenarios to contextuality scenarios, unifying liftings of Bell and noncontextuality inequalities. Our method produces facet-defining noncontextuality inequalities in all scenarios with contextual correlations, and we present examples of facet-defining noncontextuality inequalities for scenarios where no examples were known. Our results shed light on the structure of noncontextuality polytopes and the relationship between such polytopes across different scenarios.
We introduce the measures, Bell discord (BD) and Mermin discord (MD), to characterize bipartite quantum correlations in the context of nonsignaling (NS) polytopes. These measures divide the full NS polytope into four regions depending on whether BD and/or MD is zero. This division of the NS polytope allows us to obtain a 3-decomposition that any bipartite box with two binary inputs and two binary outputs can be decomposed into Popescu-Rohrlich (PR) box, a maximally local box, and a local box with BD and MD equal to zero. BD and MD quantify two types of nonclassicality of correlations arising from all quantum correlated states which are neither classical-quantum states nor quantum-classical states. BD and MD serve us the semi-device-independent witnesses of nonclassicality of local boxes in that nonzero value of these measures imply incompatible measurements and nonzero quantum discord only when the dimension of the measured states is fixed. The 3-decomposition serves us to isolate the origin of the two types of nonclassicality into a PR-box and a maximally local box which is related to EPR-steering, respectively. We consider a quantum polytope that has an overlap with all the four regions of the full NS polytope to figure out the constraints of quantum correlations.
We develop tools for characterizing vertices of fiber products of polytopes and apply them to simplicial distribution polytopes, a class of probability polytopes arising in quantum foundations and quantum information. In the theory of simplicial distributions, a pair of simplicial sets encoding measurement and outcome spaces determines a convex polytope of compatible probability assignments. Our first results give geometric criteria for detecting vertices of fiber products in terms of support data. These results are obtained in the more general framework of inverse limits of diagrams of polytopes in standard form, and they translate to corresponding criteria for simplicial distributions on arbitrary colimits of measurement spaces. We then focus on one-dimensional measurement spaces, where simplicial distributions recover and generalize local marginal polytopes in graphical models. In this setting, our sharpest results concern dipole graphs, for which we obtain a complete characterization of vertices and refine it to a graph-theoretic criterion. These characterizations are reminiscent of the classical support-graph criteria for transportation polytopes, but they arise in a richer class of polytopes in which vertex structure depends not only on support acyclicity but also on additional geometric compatibility data. Using the collapsing method from simplicial topology, we transfer the dipole characterization to rose graphs and obtain analogous results there. Finally, we apply collapsing to complete bipartite graphs, which encode physically relevant bipartite Bell scenarios, and more generally to arbitrary connected graphs, yielding lower bounds on the number of vertices.
Recently, the local friendliness (LF) no-go theorem has attracted considerable interest due to its deep foundational implications. This no-go theorem applies to scenarios which combine Bell experiments with Wigner's friend-type setups, containing spacelike separated superobservers assumed to be capable of performing quantum operations on a local observer, also known as their ``friend.'' The theorem shows that a set of assumptions termed ``local friendliness''---weaker than the set of assumptions required for proving Bell's theorem---constrains the space of probabilistic behaviors in extended Wigner's friend scenarios to the ``local friendliness (LF) polytope,'' and that quantum correlations can, in principle, violate those constraints. In this work, we extend the study of local friendliness to multipartite scenarios---with arbitrary but finite numbers of superobservers, friends, measurements, and outcomes---and fully characterize the corresponding LF polytopes, their relationships with each other, with the Bell polytope, the no-signaling polytope, and the quantum set of correlations. In particular, we identify, via constructive proofs, all the canonical LF scenarios where the LF polytope coincides with the Bell polytope---hence identifying all the scenarios where ``genuine LF inequalities'' may arise. Among other results, we also show that whenever the LF polytope is distinct from the Bell and the no-signaling polytope, it also is neither contained in nor contains the quantum set of correlations. Apart from the foundational motivation of better understanding the constraints from local friendliness, our results may also find use in a priori unrelated contexts of device-independent information processing, where the LF polytopes have also been shown to arise, under the name of ``partially deterministic polytopes.''
We investigate the Λ\LambdaΛ-polytopes, a convex-linear structure recently defined and applied to the classical simulation of quantum computation with magic states by sampling. There is one such polytope, Λn\Lambda_nΛn​, for every number nnn of qubits. We establish two properties of the family {Λn,n∈N}\{\Lambda_n, n\in \mathbb{N}\}{Λn​,n∈N}, namely (i) Any extremal point (vertex) Aα∈ΛmA_\alpha \in \Lambda_mAα​∈Λm​ can be used to construct vertices in Λn\Lambda_nΛn​, for all n>mn>mn>m. (ii) For vertices obtained through this mapping, the classical simulation of quantum computation with magic states can be efficiently reduced to the classical simulation based on the preimage AαA_\alphaAα​. In addition, we describe a new class of vertices in Λ2\Lambda_2Λ2​ which is outside the known classification. While the hardness of classical simulation remains an open problem for most extremal points of Λn\Lambda_nΛn​, the above results extend efficient classical simulation of quantum computations beyond the presently known range.