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:2312.10734

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

Selman Ipek, Cihan Okay

Published Dec 17, 2023• 5 citations
arXivHTMLPDF

Abstract

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}}$.

DOI
10.48550/arxiv.2312.10734

Related papers

Mermin polytopes quantum computation and foundations

Cihan Okay, Ho Yiu Chung, Selman Ipek

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.

arXiv:2210.10186•Quantum Information and Computation•Jul 1, 2023•11 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

Geometric optimization problems in quantum computation and discrete mathematics: Stabilizer states and lattices

Arne Heimendahl

This thesis consists of two parts: Part I deals with properties of stabilizer states and their convex hull, the stabilizer polytope. Stabilizer states, Pauli measurements and Clifford unitaries are the three building blocks of the stabilizer formalism whose computational power is limited by the Gottesman- Knill theorem. This model is usually enriched by a magic state to get a universal model for quantum computation, referred to as quantum computation with magic states (QCM). The first part of this thesis will investigate the role of stabilizer states within QCM from three different angles. The first considered quantity is the stabilizer extent, which provides a tool to measure the non-stabilizerness or magic of a quantum state. It assigns a quantity to each state roughly measuring how many stabilizer states are required to approximate the state. It has been shown that the extent is multiplicative under taking tensor products when the considered state is a product state whose components are composed of maximally three qubits. In Chapter 2, we will prove that this property does not hold in general, more precisely, that the stabilizer extent is strictly submultiplicative. We obtain this result as a consequence of rather general properties of stabilizer states. Informally our result implies that one should not expect a dictionary to be multiplicative under taking tensor products whenever the dictionary size grows subexponentially in the dimension. In Chapter 3, we consider QCM from a resource theoretic perspective. The resource theory of magic is based on two types of quantum channels, completely stabilizer preserving maps and stabilizer operations. Both classes have the property that they cannot generate additional magic resources. We will show that these two classes of quantum channels do not coincide, specifically, that stabilizer operations are a strict subset of the set of completely stabilizer preserving channels. This might have the consequence that certain tasks which are usually realized by stabilizer operations could in principle be performed better by completely stabilizer preserving maps. In Chapter 4, the last one of Part I, we consider QCM via the polar dual stabilizer polytope (also called the Lambda-polytope). This polytope is a superset of the quantum state space and every quantum state can be written as a convex combination of its vertices. A way to classically simulate quantum computing with magic states is based on simulating Pauli measurements and Clifford unitaries on the vertices of the Lambda-polytope. The complexity of classical simulation with respect to the polytope is determined by classically simulating the updates of vertices under Clifford unitaries and Pauli measurements. However, a complete description of this polytope as a convex hull of its vertices is only known in low dimensions (for up to two qubits or one qudit when odd dimensional systems are considered). We make progress on this question by characterizing a certain class of operators that live on the boundary of the Lambda-polytope when the underlying dimension is an odd prime. This class encompasses for instance Wigner operators, which have been shown to be vertices of Lambda. We conjecture that this class contains even more vertices of Lambda. Eventually, we will shortly sketch why applying Clifford unitaries and Pauli measurements to this class of operators can be efficiently classically simulated. Part II of this thesis deals with lattices. Lattices are discrete subgroups of the Euclidean space. They occur in various different areas of mathematics, physics and computer science. We will investigate two types of optimization problems related to lattices. In Chapter 6 we are concerned with optimization within the space of lattices. That is, we want to compare the Gaussian potential energy of different lattices. To make the energy of lattices comparable we focus on lattices with point density one. In particular, we focus on even unimodular lattices and show that, up to dimension 24, they are all critical for the Gaussian potential energy. Furthermore, we find that all n-dimensional even unimodular lattices with n 24 are local minima or saddle points. In contrast in dimension 32, there are even unimodular lattices which are local maxima and others which are not even critical. In Chapter 7 we consider flat tori R^n/L, where L is an n-dimensional lattice. A flat torus comes with a metric and our goal is to approximate this metric with a Hilbert space metric. To achieve this, we derive an infinite-dimensional semidefinite optimization program that computes the least distortion embedding of the metric space R^n/L into a Hilbert space. This program allows us to make several interesting statements about the nature of least distortion embeddings of flat tori. In particular, we give a simple proof for a lower bound which gives a constant factor improvement over the previously best lower bound on the minimal distortion of an embedding of an n-dimensional flat torus. Furthermore, we show that there is always an optimal embedding into a finite-dimensional Hilbert space. Finally, we construct optimal least distortion embeddings for the standard torus R^n/Z^n and all 2-dimensional flat tori.

•Jan 1, 2023•0 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

Geometry of the skeleton graph of the no-signaling polytope for the 2223 Bell scenario and beyond

José Manuel Méndez Martínez

The study of no-signaling polytopes is addressed under an alternative approach, focusing on the skeleton graph of the polytopes rather than on the Bell inequalities solely. The paper starts with the study of the Bell scenario where one of the parties (Bob) has three output options (2223 scenario). We found that in this polytope the Popescu-Rohrlich (PR) vertices are interconnected, making up two networks around the polytope of local correlations, which is a new feature in relation to the 2222 polytope. We also found that in this scenario each CHSH inequality is violated by five PR vertices: the PR vertex associated to that inequality and its four adjacent PR vertices. Later, we study the facet structure of the corresponding polytope of local correlations. What we obtain is a one-to-one correspondence between some two-dimensional faces of the no-signaling polytope defined by specific loops in the adjacency networks of PR vertices, the lifting Bell functions, and the nontrivial facets of the local polytope. Finally, by studying the skeleton graphs of the polytopes for the general $222{v}_{B}$ scenarios, where ${v}_{B}$ is the number of possible Bob's outcomes, a striking high degeneracy is unveiled. We show that the set of local vertices exhibits a much higher degeneracy than the PR vertices, which in turn are more degenerate than a regular vertex.

Physical Review A•Jan 13, 2023•3 citations

Bell's Inequality, Causal Bounds, and Quantum Bayesian Computation: A Unified Framework

Nick Polson, Vadim Sokolov, Daniel Zantedeschi

Bell inequalities characterize the boundary of the local-realist correlation polytope -- the set of joint probability distributions achievable by classical hidden-variable models. Quantum mechanics exceeds this boundary through non-commutativity, reaching the Tsirelson bound $2\sqrt{2}$ for CHSH. We show that this polytope structure is not specific to quantum foundations: it appears identically in the causal inference literature, where the instrumental inequality, the Balke--Pearl linear programming bounds, and the Tian--Pearl probabilities of causation all arise as facets of the same marginal compatibility polytope. Fine's theorem -- that CHSH inequalities hold if and only if a joint distribution exists -- is precisely the pivot: the instrumental variable model in causal inference is structurally equivalent to the Bell local hidden-variable model, with the instrument playing the role of the measurement setting and the latent confounder playing the role of the hidden variable $λ$. We develop this correspondence in detail, extending it to algorithmic (Kolmogorov complexity) and entropic formulations of Bell inequalities, the NPA semidefinite programming hierarchy, and the MIP$^*$=RE undecidability result. We further show that the Born-rule / Bayes-rule duality underlying quantum Bayesian computation exploits the same non-commutativity that enables Bell violation, providing polynomial speedups for posterior inference. The framework yields a concrete dictionary between quantum information theory, causal econometrics, and Bayesian computation, and suggests new directions including NPA-based quantum causal inference algorithms and quantum architectures for function approximation.

quant-pharXiv:2603.28973•Apr 1, 2026•0 citations
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.
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 222-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)(2,3,2)(2,3,2) Bell scenario, whose vertices are well-known.
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.
This thesis consists of two parts: Part I deals with properties of stabilizer states and their convex hull, the stabilizer polytope. Stabilizer states, Pauli measurements and Clifford unitaries are the three building blocks of the stabilizer formalism whose computational power is limited by the Gottesman- Knill theorem. This model is usually enriched by a magic state to get a universal model for quantum computation, referred to as quantum computation with magic states (QCM). The first part of this thesis will investigate the role of stabilizer states within QCM from three different angles. The first considered quantity is the stabilizer extent, which provides a tool to measure the non-stabilizerness or magic of a quantum state. It assigns a quantity to each state roughly measuring how many stabilizer states are required to approximate the state. It has been shown that the extent is multiplicative under taking tensor products when the considered state is a product state whose components are composed of maximally three qubits. In Chapter 2, we will prove that this property does not hold in general, more precisely, that the stabilizer extent is strictly submultiplicative. We obtain this result as a consequence of rather general properties of stabilizer states. Informally our result implies that one should not expect a dictionary to be multiplicative under taking tensor products whenever the dictionary size grows subexponentially in the dimension. In Chapter 3, we consider QCM from a resource theoretic perspective. The resource theory of magic is based on two types of quantum channels, completely stabilizer preserving maps and stabilizer operations. Both classes have the property that they cannot generate additional magic resources. We will show that these two classes of quantum channels do not coincide, specifically, that stabilizer operations are a strict subset of the set of completely stabilizer preserving channels. This might have the consequence that certain tasks which are usually realized by stabilizer operations could in principle be performed better by completely stabilizer preserving maps. In Chapter 4, the last one of Part I, we consider QCM via the polar dual stabilizer polytope (also called the Lambda-polytope). This polytope is a superset of the quantum state space and every quantum state can be written as a convex combination of its vertices. A way to classically simulate quantum computing with magic states is based on simulating Pauli measurements and Clifford unitaries on the vertices of the Lambda-polytope. The complexity of classical simulation with respect to the polytope is determined by classically simulating the updates of vertices under Clifford unitaries and Pauli measurements. However, a complete description of this polytope as a convex hull of its vertices is only known in low dimensions (for up to two qubits or one qudit when odd dimensional systems are considered). We make progress on this question by characterizing a certain class of operators that live on the boundary of the Lambda-polytope when the underlying dimension is an odd prime. This class encompasses for instance Wigner operators, which have been shown to be vertices of Lambda. We conjecture that this class contains even more vertices of Lambda. Eventually, we will shortly sketch why applying Clifford unitaries and Pauli measurements to this class of operators can be efficiently classically simulated. Part II of this thesis deals with lattices. Lattices are discrete subgroups of the Euclidean space. They occur in various different areas of mathematics, physics and computer science. We will investigate two types of optimization problems related to lattices. In Chapter 6 we are concerned with optimization within the space of lattices. That is, we want to compare the Gaussian potential energy of different lattices. To make the energy of lattices comparable we focus on lattices with point density one. In particular, we focus on even unimodular lattices and show that, up to dimension 24, they are all critical for the Gaussian potential energy. Furthermore, we find that all n-dimensional even unimodular lattices with n 24 are local minima or saddle points. In contrast in dimension 32, there are even unimodular lattices which are local maxima and others which are not even critical. In Chapter 7 we consider flat tori R^n/L, where L is an n-dimensional lattice. A flat torus comes with a metric and our goal is to approximate this metric with a Hilbert space metric. To achieve this, we derive an infinite-dimensional semidefinite optimization program that computes the least distortion embedding of the metric space R^n/L into a Hilbert space. This program allows us to make several interesting statements about the nature of least distortion embeddings of flat tori. In particular, we give a simple proof for a lower bound which gives a constant factor improvement over the previously best lower bound on the minimal distortion of an embedding of an n-dimensional flat torus. Furthermore, we show that there is always an optimal embedding into a finite-dimensional Hilbert space. Finally, we construct optimal least distortion embeddings for the standard torus R^n/Z^n and all 2-dimensional flat tori.
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.
The study of no-signaling polytopes is addressed under an alternative approach, focusing on the skeleton graph of the polytopes rather than on the Bell inequalities solely. The paper starts with the study of the Bell scenario where one of the parties (Bob) has three output options (2223 scenario). We found that in this polytope the Popescu-Rohrlich (PR) vertices are interconnected, making up two networks around the polytope of local correlations, which is a new feature in relation to the 2222 polytope. We also found that in this scenario each CHSH inequality is violated by five PR vertices: the PR vertex associated to that inequality and its four adjacent PR vertices. Later, we study the facet structure of the corresponding polytope of local correlations. What we obtain is a one-to-one correspondence between some two-dimensional faces of the no-signaling polytope defined by specific loops in the adjacency networks of PR vertices, the lifting Bell functions, and the nontrivial facets of the local polytope. Finally, by studying the skeleton graphs of the polytopes for the general 222vB222{v}_{B}222vB​ scenarios, where vB{v}_{B}vB​ is the number of possible Bob's outcomes, a striking high degeneracy is unveiled. We show that the set of local vertices exhibits a much higher degeneracy than the PR vertices, which in turn are more degenerate than a regular vertex.
Bell inequalities characterize the boundary of the local-realist correlation polytope -- the set of joint probability distributions achievable by classical hidden-variable models. Quantum mechanics exceeds this boundary through non-commutativity, reaching the Tsirelson bound 222\sqrt{2}22​ for CHSH. We show that this polytope structure is not specific to quantum foundations: it appears identically in the causal inference literature, where the instrumental inequality, the Balke--Pearl linear programming bounds, and the Tian--Pearl probabilities of causation all arise as facets of the same marginal compatibility polytope. Fine's theorem -- that CHSH inequalities hold if and only if a joint distribution exists -- is precisely the pivot: the instrumental variable model in causal inference is structurally equivalent to the Bell local hidden-variable model, with the instrument playing the role of the measurement setting and the latent confounder playing the role of the hidden variable λλλ. We develop this correspondence in detail, extending it to algorithmic (Kolmogorov complexity) and entropic formulations of Bell inequalities, the NPA semidefinite programming hierarchy, and the MIP∗^*∗=RE undecidability result. We further show that the Born-rule / Bayes-rule duality underlying quantum Bayesian computation exploits the same non-commutativity that enables Bell violation, providing polynomial speedups for posterior inference. The framework yields a concrete dictionary between quantum information theory, causal econometrics, and Bayesian computation, and suggests new directions including NPA-based quantum causal inference algorithms and quantum architectures for function approximation.