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

Abstract

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)Anyextremalpoint(vertex)$A_\alpha \in \Lambda_m$canbeusedtoconstructverticesin$\Lambda_n$,forall$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.