[quantum-info] Two PIQuDos seminars Mon Dec 1, Wed Dec 3: Jamie Sikora, Elizabeth Crosson

[Gus Gutoski]

Reminder: PIQuDos seminar by Elizabeth Crosson this afternoon at 4pm in the
Time room.

On Fri, Nov 28, 2014 at 9:36 AM, Gus Gutoski <ggutoski at perimeterinstitute.ca
> wrote:

> *Monday, Dec. 1st, 2014*
>
> at 4:00 p.m. in Time Room (294)
>
> *Perimeter Institute Quantum Discussions
> <http://perimeterinstitute.ca/video-library/collection/perimeter-institute-quantum-discussions>*
>  *–* *Ground state connectivity of local Hamiltonians
> <http://perimeterinstitute.ca/seminar/ground-state-connectivity-local-hamiltonians>*
>  - *with Jamie Sikora, Universite Paris Diderot*
>
> The study of ground spaces of local Hamiltonians is a fundamental task in
> condensed matter physics. In terms of computational complexity theory, a
> common focus in this area has been to estimate a given Hamiltonian’s ground
> state energy. However, from a physics perspective, it is sometimes more
> relevant to understand the structure of the ground space itself. In this
> talk, we pursue the latter direction by introducing the notion of “ground
> state connectivity” of local Hamiltonians. In particular, we show that
> determining how “connected” the ground space of a local Hamiltonian is can
> range from QCMA-complete to NEXP-complete. (Here, QCMA is the same as QMA,
> but with a classical witness.) As a result, we obtain a natural
> QCMA-complete problem, a task which has generally proven difficult since
> the conception of QCMA over a decade ago.
>
>
>
> *Wednesday, Dec. 3rd, 2014*
>
> at 4:00 p.m. in Time Room (294)
>
> *Perimeter Institute Quantum Discussions
> <http://perimeterinstitute.ca/video-library/collection/perimeter-institute-quantum-discussions>*
>  *–* *Different Strategies for Quantum Adiabatic Optimization, and the
> Computational Power of Simulated Quantum Annealing
> <http://perimeterinstitute.ca/seminar/different-strategies-quantum-adiabatic-optimization-and-computational-power-simulated>*
>  -
> *with Elizabeth Crosson, MIT*Quantum Adiabatic Optimization proposes to
> solve discrete optimization problems by mapping them onto quantum spin
> systems in such a way that the optimal solution corresponds to the ground
> state of the quantum system. The standard method of preparing these ground
> states is using the adiabatic theorem, which tells us that quantum systems
> tend to remain in the ground state of a time-dependent Hamiltonian which
> transforms sufficiently slowly. In this talk I'll show that alternative
> strategies using non-adiabatic effects can in some cases be dramatically
> faster for instances which are hard for the traditional adiabatic method. I
> will also discuss Simulated Quantum Annealing (SQA), which is a classical
> simulation of adiabatic optimization at non-zero temperature based on
> Path-Integral Quantum Monte Carlo. SQA is widely used in practice to study
> adiabatic optimization, but relatively little is known about the rate of
> convergence of the markov chain that underlies the algorithm. By focusing
> on a family of instances which adiabatic optimization solves in polynomial
> time, but require exponential time to solve using classical (thermal)
> simulated annealing, I will present numerical evidence as well as a
> work-in-progress proof that SQA can be exponentially faster than classical
> simulated annealing.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.uwaterloo.ca/pipermail/quantum-info/attachments/20141203/3b173fee/attachment.html>