  Non-locality is not only one of the most prominent quantum features but can
also serve as a resource for various information-theoretical tasks. Analysing
it from an information-theoretical perspective has linked it to applications
such as non-adaptive measurement-based quantum computing (NMQC). In this type
of quantum computing the goal is to output a multivariate function. The success
of such a computation can be related to the violation of a generalised Bell
inequality. So far, the investigation of binary NMQC with qubits has shown that
quantum correlations can compute all Boolean functions using at most $2^n-1$
qubits, whereas local hidden variables (LHVs) are restricted to linear
functions. Here, we extend these results to NMQC with qutrits and prove that
quantum correlations enable the computation of all ternary functions using the
generalised qutrit Greenberger-Horne-Zeilinger (GHZ) state as a resource and at
most $3^n-1$ qutrits. This yields a corresponding generalised GHZ type paradox
for any ternary function that LHVs cannot compute. We give an example for an
$n$-variate function that can be computed with only $n+1$ qutrits, which leads
to convenient generalised qutrit Bell inequalities whose quantum bound is
maximal. Finally, we prove that not all functions can be computed efficiently
with qutrit NMQC by presenting a counterexample.
