  Recent hardware demonstrations and advances in circuit compilation have made
quantum computing with higher-dimensional systems (qudits) on near-term devices
an attractive possibility. Some problems have more natural or optimal encodings
using qudits over qubits. We explore this potential by formulating graph
3-coloring, a well-known and difficult problem with practical applications,
using qutrits, and solve it using the quantum approximate optimization
algorithm (QAOA). Qutrit-based cost and mixer Hamiltonians are constructed
along with appropriate quantum circuits using qutrit gates. We run noiseless
simulations using PennyLane to compare the formulation against qubit-based
QAOA, and analyze the solution quality and resources required. Preliminary
results show that the qutrit encoding finds more accurate solutions with a
comparable set of hyperparameters, uses half as many qudits, and has a notably
smaller circuit depth per layer than an efficient qubit encoding. This work
suggests that qutrits may be useful in solving some problems on near-term
devices, however further work is required to assess their potential in a noisy
environment.
