A walk on max-plus algebra

Abstract

Max-plus algebra is a kind of idempotent semiring over ${\mathbb{R}}_{\max }:=\mathbb{R}\cup \{-\infty \}$ with two operations $\oplus :=\max$ and $\otimes :=+$.In this paper, we introduce a new model of a walk on one dimensional lattice on $\mathbb{Z}$, as an analogue of the quantum walk, over the max-plus algebra and we call it max-plus walk. In the conventional quantum walk, the summation of the ${\ell }^2$-norm of the states over all the positions is a conserved quantity. In contrast, the summation of eigenvalues of state decision matrices is a conserved quantity in the max-plus walk.Moreover, spectral analysis on the total time evolution operator is also given.

17 pages, 1 figures