Perimeter Institute Quantum Discussions

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.

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. 

In unidirectional communication theory, two of the most prominent problems are those of compressing a source of information and of transmitting data noiselessly over a noisy channel. In 1948, Shannon introduced information theory as a tool to address both of these problems. Since then, information theory has flourished into an important field of its own. It has also been successfully extended to the quantum setting, where it has also served to address questions about quantum source compression and transmission of classical and quantum data over noisy quantum channels.

However, in interactive communication theory, more specifically communication complexity, it is much more recently that tools from information theory have been successfully applied. Indeed, the interactive nature of communication protocols in this setting imposes new constraints and tools specific to this setting need to be developed, both for the interactive analogue of source compression and that of coding for noisy channels. The exciting field of classical interactive information theory has been very active in recent years.

We discuss recent works for its quantum counterpart. In particular, we discuss joint work showing that a constant factor overhead is sufficient for robustly implementing interactive quantum communication over noisy channels [1]. We also discuss work introducing a new notion of quantum information complexity that exactly captures the amortized cost per copy for implementing many copies of a communication task in parallel, such that compressing to this information complexity leads to a bounded-round direct sum theorem [2].

For both of these, we further discuss many interesting potential research directions that follow.

[1] joint work with Gilles Brassard, Ashwin Nayak, Alain Tapp, Falk Unger, QIP’14, FOCS’14 [2] Merge of arXiv:1404.3733 and arXiv:1409.4391, to appear at QIP’15