Abstract
It is often argued that entanglement is at the root of the speedup for quantum compared to classical computation, and that one needs a sufficient amount of entanglement for this speedup to be manifest. In measurement-based quantum computing, the need for a highly entangled initial state is particularly obvious. Defying this intuition, we show that quantum states can be too entangled to be useful for the purpose of computation, in that high values of the geometric measure of entanglement preclude states from offering a universal quantum computational speedup. We prove that this phenomenon occurs for a dramatic majority of all states: the fraction of useful -qubit pure states is less than . This work highlights a new aspect of the role entanglement plays for quantum computational speedups.
- Received 7 January 2009
DOI:https://doi.org/10.1103/PhysRevLett.102.190501
©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