  We show how to efficiently generate pseudo-random states suitable for quantum
information processing via cluster-state quantum computation. By reformulating
pseudo-random algorithms in the cluster-state picture, we identify a strategy
for optimizing pseudo-random circuits by properly choosing single-qubit
rotations. A Markov chain analysis provides the tool for analyzing convergence
rates to the Haar measure and finding the optimal single-qubit gate
distribution. Our results may be viewed as an alternative construction of
approximate unitary 2-designs.
