The linear problem specified by an $n \times n$ matrix $M$ over a finite field is the problem of computing the product of $M$ and a given vector $x$. We present optimal error-tolerant random self-reductions (also known as worst-case to average-case reductions) for all linear problems: Given a linear-size circuit that computes $M x$ on an $\varepsilon$-fraction of inputs $x$ for a positive constant $\varepsilon$, we construct a randomized linear-size circuit that computes $M x$ for all inputs $x$ with high probability. This resolves the open problem posed by Asadi, Golovnev, Gur, Shinkar, and Subramanian (SODA'24), who presented quantum $n^{1.5}$-time random self-reductions for all linear problems. Somewhat surprisingly, we also demonstrate the quantum advantage of their quantum reduction over classical uniform algorithms, by proving that any classical subquadratic-time random self-reduction requires the advice complexity of $\Omega(\log(1/\varepsilon) \cdot \log n)$, as long as the field size is at most $1/\varepsilon$. We complement this advice complexity lower bound by presenting (1) a random self-reduction with the optimal advice complexity of $O(\log(1/\varepsilon) \cdot \log n)$ and (2) a uniform random self-reduction over a large finite field.