Measurement-Based Preparation of Higher-Dimensional AKLT States and Their Quantum Computational Power

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 spin-1 `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 such randomly decorated AKLT state possesses at least the same computational power as non-random ones, such as those on trivalent planar lattices. For AKLT states on Bethe lattices and their decorated versions we show that there exists a deterministic, constant-time scheme for their preparation. In addition to randomly decorated AKLT states, we also consider random-bond AKLT states, whose construction involves any of the canonical Bell states in the bond degrees of freedom instead of just the singlet in the original construction. Such states naturally emerge upon measuring all the decorative spin-1 sites in the randomly decorated AKLT states. We show that those random-bond AKLT states on trivalent lattices can be converted to encoded random graph states after acting with the same POVM on all sites. We also argue that these random-bond AKLT states possess similar quantum computational power as the original singlet-bond AKLT states via the percolation perspective.