On the extremal points of the $\hat{I}›$-polytopes and classical simulation of quantum computation with magic states

Abstract

We investigate the $\hat{I}›$-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, $\hat{I}{›}_n$, for every number $n$ of qubits. We establish two properties of the family $\{\hat{I}{›}_n,n\in \mathbb{N}\}$, namely (i) Any extremal point (vertex) $A_{\hat{I}}\pm \in \hat{I}{›}_m$ can be used to construct vertices in $\hat{I}{›}_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_{\hat{I}}\pm$. In addition, we describe a new class of vertices in $\hat{I}{›}_2$ which is outside the known classification. While the hardness of classical simulation remains an open problem for most extremal points of $\hat{I}{›}_n$, the above results extend efficient classical simulation of quantum computations beyond the presently known range.

19 pages