  Linear optics is a promising alternative for the realization of quantum
computation protocols due to the recent advancements in integrated photonic
technology. In this context usually qubit based quantum circuits are
considered, however, photonic systems naturally allow also for d-ary, i.e.,
qudit based, algorithms. This work investigates qudits defined by the possible
photon number states of a single photon in d > 2 optical modes. We demonstrate
how to construct locally optimal non-deterministic many-qudit gates using
linear optics and photon number resolving detectors, and explore the use of
qudit cluster states in the context of a d-ary optimization problem. We find
that the qudit cluster states require less optical modes and are encoded by a
fewer number of entangled photons than the qubit cluster states with similar
computational capabilities. We illustrate the benefit of our qudit scheme by
applying it to the k-coloring problem.
