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.