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

[Gus Gutoski]

*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/20141128/fb1d0456/attachment.html>