Are Random Pure States Useful for Quantum Computation

American Physical Society
Publication Type:
Journal Article
Physical Review Letters, 2009, 102 (19)
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2013003976OK.pdf114.48 kB
Adobe PDF
We show the following: a randomly chosen pure state as a resource for measurement-based quantum computation iswith overwhelming probabilityof 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.
Please use this identifier to cite or link to this item: