[quantum-info] PIQuDos seminar Wed Feb 25: Ciaran Lee

[Gus Gutoski]

Reminder: Ciaran Lee today at 4pm in the Time room.

On Mon, Feb 23, 2015 at 9:53 AM, Gus Gutoski
<ggutoski at perimeterinstitute.ca> wrote:
> Please join us on Wednesday, February 25 at 4pm in the Time room for a
> quantum information seminar by Ciaran Lee.
>
> Title:
>
> "Computation in generalised probabilistic theories"
>
> Abstract:
>
> "From the general difficulty of simulating quantum systems using
> classical systems, and in particular the existence of an efficient
> quantum algorithm for factoring, it is likely that quantum computation
> is intrinsically more powerful than classical computation. At present,
> the best upper bound known for the power of quantum computation is
> that BQP is in AWPP, where AWPP is a classical complexity class (known
> to be included in PP, hence PSPACE). This work investigates limits on
> computational power that are imposed by simple physical, or
> information theoretic, principles. To this end, we define a
> circuit-based model of computation in a class of operationally-defined
> theories more general than quantum theory, and ask: what is the
> minimal set of physical assumptions under which the above inclusions
> still hold? We show that given only an assumption of tomographic
> locality (roughly, that multipartite states and transformations can be
> characterised by local measurements), efficient computations are
> contained in AWPP. This inclusion still holds even without assuming a
> basic notion of causality (where the notion is, roughly, that
> probabilities for outcomes cannot depend on future measurement
> choices). Then, following Aaronson, we extend the computational model
> by allowing post-selection on measurement outcomes. Aaronson showed
> that the corresponding quantum complexity class, PostBQP, is equal to
> PP. Given only the assumption of tomographic locality, the inclusion
> in PP still holds for post-selected computation in general theories.
> Hence in a world with post-selection, quantum theory is optimal for
> computation in the space of all operational theories. We then consider
> whether one can obtain relativised complexity results for general
> theories. It is not obvious how to define a sensible notion of a
> computational oracle in the general framework that reduces to the
> standard notion in the quantum case. Nevertheless, it is possible to
> define computation relative to a `classical oracle'. Then, we show
> there exists a classical oracle relative to which efficient
> computation in any theory satisfying the causality assumption does not
> include NP. This provides some degree of evidence that NP-complete
> problems cannot be solved efficiently in any theory satisfying
> tomographic locality and causality. Based on arXiv:1412.8671. Joint
> work with Jon Barrett."