Quantum algorithms for finding constant-sized sub-hypergraphs

We develop a general framework to construct quantum algorithms that detect if a 3-uniform hypergraph given as input contains a sub-hypergraph isomorphic to a prespecified constant-sized hypergraph. This framework is based on the concept of nested quantum walks recently proposed by Jeffery, Kothari and Magniez (2013) [12], and extends the methodology designed by Lee, Magniez and Santha (2013) [18] for similar problems over graphs. As applications, we obtain a quantum algorithm for finding a 4-clique in a 3-uniform hypergraph on n   vertices with query complexity O(n1.883)O(n1.883), and a quantum algorithm for determining if a ternary operator over a set of size n   is associative with query complexity O(n2.113)O(n2.113).