Schemes for preparing AKLT states beyond one dimension and studying their quantum computational universality

We investigate a constant-time, fusion measurement-based scheme to create AKLT states beyond one dimension. We show that it is possible to prepare such states on a given graph up to random decorations, each corresponding to a probabilistic insertion of a vertex along an edge. In investigating their utility in measurement-based quantum computation, we demonstrate that any random AKLT state possesses at least the same power as non-random ones, such as those on trivalent planar lattices.