Are Random Pure States Useful for Quantum Computation?
- 11 May 2009
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 102 (19) , 190502
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.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Most Quantum States Are Too Entangled To Be Useful As Computational ResourcesPhysical Review Letters, 2009
- Computational Power of CorrelationsPhysical Review Letters, 2009
- Measurement-Based Quantum Computer in the Gapped Ground State of a Two-Body HamiltonianPhysical Review Letters, 2008
- Measurement-based quantum computation beyond the one-way modelPhysical Review A, 2007
- Fundamentals of universality in one-way quantum computationNew Journal of Physics, 2007
- Novel Schemes for Measurement-Based Quantum ComputationPhysical Review Letters, 2007
- Universal Resources for Measurement-Based Quantum ComputationPhysical Review Letters, 2006
- Algorithmic Complexity and Entanglement of Quantum StatesPhysical Review Letters, 2005
- Measurement-based quantum computation on cluster statesPhysical Review A, 2003
- A One-Way Quantum ComputerPhysical Review Letters, 2001