QUROPE Quantum Information Processing and Communication in Europe

M. Van den Nest
Phyical Review Letters 110, 060504 (2013)

It is strongly expected that quantum computers will offer an exponential computation advantage over their
classical counterparts. It is therefore a fundamental problem to understand what aspect or aspects of quantum
mechanics are responsible for this improvement, which remains largely unsolved. A natural candidate is the
entanglement present in quantum mechanics as the source of the computation power, however there is no
decisive evidence that the answer actually lies there.

In his paper Van den Nest places severe constraints on this intuition by showing that according to many
measures of entanglement commonly used, including the fundamental bipartite measure of pure-state
entanglement, it can be kept small throughout an entire quantum computation. This shows that many
entanglement measures give little or no information about the computation power of quantum algorithms and
that we still have a long way to go before answering the fundamental question of where the power of
quantum computers lies.