Phase-space-simulation method for quantum computation with magic states on qubits

We propose a method for classical simulation of finite-dimensional quantum systems, based on sampling from a quasiprobability distribution, i.e., a generalized Wigner function. Our construction applies to all finite dimensions, with the most interesting case being that of qubits. For multiple qubits, we find that quantum computation by Clifford gates and Pauli measurements on magic states can be efficiently classically simulated if the quasiprobability distribution of the magic states is non-negative. This provides the so far missing qubit counterpart of the corresponding result [V. Veitch et al., New J. Phys. 14, 113011 (2012)] applying only to odd dimension. Our approach is more general than previous ones based on mixtures of stabilizer states. Namely, all mixtures of stabilizer states can be efficiently simulated, but for any number of qubits there also exist efficiently simulable states outside the stabilizer polytope. Further, our simulation method extends to negative quasiprobability distributions, where it provides probability estimation. The simulation cost is then proportional to a robustness measure squared. For all quantum states, this robustness is smaller than or equal to robustness of magic.

Figure 1

Three types of cnc sets $\mathrm{\Omega }$ for Mermin's square. (a) Union of two isotropic subspaces intersecting in one element, (b) isotropic subspace, (c) triple of anticommuting elements.

Figure 2

Two-dimensional cross section of the two-qubit state space, as parameterized in Eq. (13). The shaded regions indicate the positively representable states by various methods; (a) mixtures of stabilizer states, (b) hyperoctahedral states [38], and (c) states positively represented by the present phase space method.

Figure 3

Commutativity graph representation for the cosets of Eq. (15) sets. Elements pairwise commute within each vertex and elements in adjacent vertices pairwise commute. Elements in nonadjacent vertices anticommute.

Figure 4

Forbidden induced subgraphs of the commutativity graph, resulting from Mermin's square (also see Ref. [39]).

Figure 5

Update of a cnc set $\mathrm{\Omega }$ in Mermin's square, under two Pauli measurements. (a) The measured observable $X_2$ is such that $a\left(X_2\right)\in \mathrm{\Omega }$; hence the update proceeds by Eq. (26a). (b) The measured observable $X_1$ is such that $a\left(X_1\right)\notin \mathrm{\Omega }$; hence the update proceeds by Eq. (26b).

Figure 6

Diagrams representing the quantum and the classical way of calculating the probability of measurement outcomes (left) and the postmeasurement state (right).

Figure 7

Robustness $\mathfrak{R}$ (solid line) and robustness of magic ${\mathfrak{R}}_S$ (dotted line) for the state ${|H\left(\varphi \right)\rangle }^{\otimes 3}$, cf. Eq. (14), as a function of $\varphi$. Highlighted is the region near a stabilizer state, at $\varphi =\pi$.