I keep seeing in the literature that the triangle problem can be solved using the quantum walk algorithm. There is plenty of mathematical detail (eg. Magniez et al.'s paper), but I don't get why it's important.
What are some real-world examples of the triangle problem? Are there any good references about it?
How is it used in engineering and industry (if at all)?
According to Le Gall and Nakajima's paper Quantum Algorithm for Triangle Finding in Sparse Graphs,
Williams and Williams have shown a surprising reduction from Boolean matrix multiplication to triangle finding, which indicates that efficient algorithms for triangle finding may be used to design efficient algorithms for matrix multiplication, and thus also for a vast class of problems related to matrix multiplication.
and
Another reason why triangle finding has received much attention from the quantum computing community is that work on the quantum complexity of triangle finding has been central to the development of algorithmic techniques. Indeed, all the improvement mentioned in the previous paragraph have been obtained by introducing either new quantum techniques or new paradigms for the design of quantum algorithms: applications of quantum walks to graph-theoretic problems, introduction of the concept of learning graphs and improvements to this technique, introduction of quantum walks with quantum data structures, association of combinatorial arguments with quantum walks.
