Hi all,

Tomorrow we are in a different room, F31.2, as E41.1 is in use by someone else. We have a visitor talk by Chris Cade of CWI and QuSoft in Amsterdam. His title and abstract are below.

Best,

-joe

Title: The one clean qubit model without entanglement is classically

simulable

Abstract:

Entanglement has been shown to be necessary for pure state quantum

computation to have an advantage over classical computation. However, it

remains open whether entanglement is necessary for the speedups achieved

by quantum computers that use mixed states. The one clean qubit model is

a model of quantum computation, inspired by NMR computing, in which the

input state is very close to a maximally mixed state. Despite the

apparent weakness of this model, it has been shown to be able to solve

some problems that appear to be intractable classically, and there are a

number of complexity-theoretic results that give strong evidence that

the model is indeed hard to classically simulate in general. It is

fairly well known that the amount of entanglement present in these

computations is severely limited, prompting very credible suggestions

that entanglement is not necessary for (mixed-state) quantum computers

to achieve significant speedups over classical ones, with alternative

proposals often focussing on other (non-classical) correlations that are

present in mixed-state computation. In this work we show that the

presence of entanglement is indeed necessary for any kind of

computational speedup in the one clean qubit model, and that without it,

the model becomes classically simulable.

Joint work with Mithuna Yoganathan.