Too Entangled to be Useful?

November 20, 2008 - 1:45-2:10pm

RLE Conference Center 36-428

Abstract

It is often argued that entanglement is at the root of the  speedup for quantum compared to classical computation, and that one needs sufficient entanglement for this speedup to be manifest. In measurement-based quantum computing (MBQC), the need for a highly entangled initial state is particularly obvious. In this work we show that, remarkably, quantum states can be too entangled to be useful for the purpose of computation. What is more, we can prove that this phenomenon occurs for the dramatic majority of all states: the fraction of pure states on n qubits not subject to the problem is smaller than e^(-n^2). Our results show that computational universality is actually a rare property in quantum states. For the proof we establish a link between the ``quantum probabilistic method'' and ideas on quantum many-body systems. This work highlights a new aspect of the question concerning the role entanglement plays for quantum computational speed-ups. We will also present a new classification of primitives that can be used in order to systematically construct new models for measurement-based computation. (D. Gross, S. Flammia, J. Eisert, in preparation)

Bio

Jens Eisert is a full professor at the University of Potsdam and a Visiting Academic at Imperial College London. Before, he was a Lecturer at Imperial College London. He received his PhD in 2001. His research interests are in quantum information science, quantum optics, and quantum many-body theory. He has authored about 80 publications, 26 of which in the Physical Review Letters.