Approximate stabilizer rank and improved weak simulation of Clifford-dominated circuits for qudits

Bravyi and Gosset [S. Bravyi and D. Gosset, Phys. Rev. Lett. 116, 250501 (2016)] recently gave classical simulation algorithms for quantum circuits dominated by Clifford operations. These algorithms scale exponentially with the number of T gates in the circuit, but polynomially in the number of qubits and Clifford operations. Here we extend their algorithm to qudits of odd prime dimension. We generalize their approximate stabilizer rank method for weak simulation to qudits and obtain the scaling of the approximate stabilizer rank with the number of single-qudit magic states. We also relate the canonical form of qudit stabilizer states to Gauss sum evaluations and give an O(n(3)) algorithm for calculating the inner product of two n-qudit stabilizer states.