• Featured in Physics

Most Quantum States Are Too Entangled To Be Useful As Computational Resources

D. Gross, S. T. Flammia, and J. Eisert
Phys. Rev. Lett. 102, 190501 – Published 11 May 2009
Physics logo See Viewpoint: Too entangled to quantum compute one-way

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 n-qubit pure states is less than exp(n2). This work highlights a new aspect of the role entanglement plays for quantum computational speedups.

  • Figure
  • Received 7 January 2009

DOI:https://doi.org/10.1103/PhysRevLett.102.190501

©2009 American Physical Society

Viewpoint

Key Image

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

Authors & Affiliations

D. Gross1, S. T. Flammia2, and J. Eisert3,4

  • 1Institut für Mathematische Physik, Technische Universität Braunschweig, 38106 Braunschweig, Germany
  • 2Perimeter Institute for Theoretical Physics, Waterloo, Ontario, N2L 2Y5 Canada
  • 3Physics Department, University of Potsdam, 14469 Potsdam, Germany
  • 4Institute for Mathematical Sciences, Imperial College London, London SW7 2PE, United Kingdom

See Also

Are Random Pure States Useful for Quantum Computation?

Michael J. Bremner, Caterina Mora, and Andreas Winter
Phys. Rev. Lett. 102, 190502 (2009)

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 102, Iss. 19 — 15 May 2009

Reuse & Permissions
Access Options

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review Letters

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×