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.