title: Are random pure States useful for quantum computation?
abstract: 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.
authors.affiliation: Department of Computer Science, University of Bristol, Bristol BS8 1UB, United Kingdom. michael.bremner@bris.ac.uk
authors.forename: Michael J
authors.initials: MJ
authors.lastname: Bremner
authors.forename: Caterina
authors.initials: C
authors.lastname: Mora
authors.forename: Andreas
authors.initials: A
authors.lastname: Winter