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

Gus Gutoski ggutoski at perimeterinstitute.ca
Mon Feb 23 09:53:25 EST 2015


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."


More information about the quantum-info mailing list