Suppose we have $k$ $n\times n$ matrices $A,B,C,\ldots$. Is there a way to compute/approximate the trace of their product much faster than computing/approximating the full matrix product? IE, computing
$$\text{tr}(ABC\ldots)$$
A related problem of computing vector matrix product $v'ABC$ can be done in $O(n^2)$ time by skipping most of the computation needed for the full matrix product, so I'm wondering if there's a trick to speed up the trace as well