In this paper we construct quantum algorithms for matrix products over several algebraic structures called semirings, including the (max,min)-matrix product, the distance matrix product and the Boolean matrix product. In particular, we obtain the following results.

• We construct a quantum algorithm computing the product of two $n\times n$ matrices over the (max,min) semiring with time complexity $O(n^{2.473})$. In comparison, the best known classical algorithm for the same problem, by Duan and Pettie (SODA'09), has complexity $O(n^{2.687})$.
• We construct a quantum algorithm computing the $\ell$ most significant bits of each entry of the distance product of two $n\times n$ matrices in time $O(2^{0.64\ell} n^{2.46})$. In comparison, the best known classical algorithm for the same problem, by Vassilevska and Williams (STOC'06) and Yuster (SODA'09), has complexity $O(2^{\ell}n^{2.69})$.
• The above two algorithms are the first quantum algorithms that perform better than the $\tilde O(n^{5/2})$-time straightforward quantum algorithm based on quantum search for matrix multiplication over these semirings. We also consider the Boolean semiring, and construct a quantum algorithm computing the product of two $n\times n$ Boolean matrices that outperforms the best known classical algorithms for sparse matrices.

A random jigsaw puzzle is constructed by arranging $n^2$ square pieces into an $n \times n$ grid and assigning to each edge of a piece one of $q$ available colors uniformly at random, with the restriction that touching edges receive the same color. We show that if $q = o(n)$ then with high probability such a puzzle does not have a unique solution, while if $q \ge n^{1 + \varepsilon}$ for any constant $\varepsilon > 0$ then the solution is unique. This solves a conjecture of Mossel and Ross (Shotgun assembly of labeled graphs, arXiv:1504.07682).