  Pauli-based computation (PBC) is a universal model for quantum computation
with qubits where the input state is a magic (resource) state and the
computation is driven by a sequence of adaptively chosen and compatible
multiqubit Pauli measurements. Here we generalize PBC for odd-prime-dimensional
systems and demonstrate its universality. Additionally, we discuss how any
qudit-based PBC can be implemented on actual, circuit-based quantum hardware.
Our results show that we can translate a PBC on $n$ $p$-dimensional qudits to
adaptive circuits on $n+1$ qudits with $O\left( pn^2/2 \right)$ $\mathrm{SUM}$
gates and depth. Alternatively, we can carry out the same computation with
$O\left( pn/2\right)$ depth at the expense of an increased circuit width.
Finally, we show that the sampling complexity associated with simulating a
number $k$ of virtual qudits is related to the robustness of magic of the input
states. Computation of this magic monotone for qutrit and ququint states leads
to sampling complexity upper bounds of, respectively, $O\left( 3^{ 1.0848 k}
\epsilon^{-2}\right)$ and $O\left( 5^{ 1.4022 k} \epsilon^{-2}\right)$, for a
desired precision $\epsilon$. We further establish lower bounds to this
sampling complexity for qubits, qutrits, and ququints: $\Omega \left( 2^{0.5431
k} \epsilon^{-2} \right)$, $\Omega \left( 3^{0.7236 k} \epsilon^{-2} \right)$,
and $\Omega \left( 5^{0.8544 k} \epsilon^{-2} \right)$, respectively.

Quantum Physics