Are random pure States useful for quantum computation?

We show the following: a randomly chosen pure state as a resource for measurement-based quantum computation is-with overwhelming probability-of no greater help to a polynomially bounded classical control computer, than a string of random bits. Thus, unlike the familiar "cluster states," the computing power of a classical control device is not increased from P to BQP (bounded-error, quantum polynomial time), but only to BPP (bounded-error, probabilistic polynomial time). The same holds if the task is to sample from a distribution rather than to perform a bounded-error computation. Furthermore, we show that our results can be extended to states with significantly less entanglement than random states.

Algorithmic complexity and entanglement of quantum states.

We define the algorithmic complexity of a quantum state relative to a given precision parameter, and give upper bounds for various examples of states. We also establish a connection between the entanglement of a quantum state and its algorithmic complexity.