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.
- Received 21 January 2009
DOI:https://doi.org/10.1103/PhysRevLett.102.190502
©2009 American Physical Society
Viewpoint
Too entangled to quantum compute one-way
Published 11 May 2009
Entanglement may not be the source of a quantum computer’s power. But if not, what is?
See more in Physics