Semiclassical formulation of the Gottesman-Knill theorem and universal quantum computation

We give a path-integral formulation of the time evolution of qudits of odd dimension. This allows us to consider semiclassical evolution of discrete systems in terms of an expansion of the propagator in powers of $\hslash$. The largest power of $\hslash$ required to describe the evolution is a traditional measure of classicality. We show that the action of the Clifford operators on stabilizer states can be fully described by a single contribution of a path integral truncated at order ${\hslash }^0$ and so are “classical,” just like propagation of Gaussians under harmonic Hamiltonians in the continuous case. Such operations have no dependence on phase or quantum interference. Conversely, we show that supplementing the Clifford group with gates necessary for universal quantum computation results in a propagator consisting of a finite number of semiclassical path-integral contributions truncated at order ${\hslash }^1$, a number that nevertheless scales exponentially with the number of qudits. The same sum in continuous systems has an infinite number of terms at order ${\hslash }^1$.

Figure 1

Translation of (a) a position state and (b) a momentum state along the chord $({\xi }_p,{\xi }_q)$ in phase space.

Figure 2

Reflection of (a) a position state and (b) a momentum state across the center $(x_p,x_q)$ in phase space.

Figure 3

The two classes of stabilizer states possible for odd prime $d=7$ in terms of support: (a) maximally supported in $p$ or $q$ and (b) maximally supported in $p$ and $q$. The central grids denote the Wigner function ${\mathrm{\Psi }}_x(p,q)$ of a stabilizer state $\mathrm{\Psi }$ with $d=7$. The projection of this state onto $p$ space is shown in the upper right $\left[\right|\mathrm{\Psi }\left(p\right){|}^2]$ and the projection onto $q$ space is shown in the upper left $\left[\right|\mathrm{\Psi }\left(q\right){|}^2]$.

Figure 4

The four classes of stabilizer states possible for odd nonprime $d=15$ in terms of support: (a), (b) maximally supported in $p$ or $q$, (c) maximally supported in $p$ and $q$, and (d) not maximally supported in $p$ or $q$. The central grids denote the Wigner function ${\mathrm{\Psi }}_x(p,q)$ for a stabilizer state $\mathrm{\Psi }$ with $d=15$. The projection of this state onto $p$ space is shown in the upper right $\left[\right|\mathrm{\Psi }\left(p\right){|}^2]$ and the projection onto $q$ space is shown in the upper left $\left[\right|\mathrm{\Psi }\left(q\right){|}^2]$.