# Perimeter Institute Quantum Discussions

This series consists of weekly discussion sessions on foundations of quantum Theory and quantum information theory. The sessions start with an informal exposition of an interesting topic, research result or important question in the field. Everyone is strongly encouraged to participate with questions and comments.

## Seminar Series Events/Videos

Currently there are no upcoming talks in this series.

## The Bose-Hubbard model is QMA-complete

Wednesday Dec 18, 2013
Speaker(s):

The Bose-Hubbard model is a system of interacting bosons that live on the vertices of a graph. The particles can move between adjacent vertices and experience a repulsive on-site interaction. The Hamiltonian is determined by a choice of graph that specifies the geometry in which the particles move and interact. We prove that approximating the ground energy of the Bose-Hubbard model on a graph at fixed particle number is QMA-complete. In our QMA-hardness proof, we encode the history of an n-qubit computation in the subspace with at most one particle per site (i.e., hard-core bosons).

Scientific Areas:

## Direct Detection of Classically Undetectable Dark Matter through Quantum Decoherence

Wednesday Dec 04, 2013
Speaker(s):

Although various pieces of indirect evidence about the nature of dark matter have been collected, its direct detection has eluded experimental searches despite extensive effort. If the mass of dark matter is below 1 MeV, it is essentially imperceptible to conventional detection methods because negligible energy is transferred to nuclei during collisions. Here I propose directly detecting dark matter through the quantum decoherence it causes rather than its classical effects such as recoil or ionization.

Scientific Areas:

## Homological Product Codes

Wednesday Nov 27, 2013
Speaker(s):

Quantum codes with

Scientific Areas:

Wednesday Nov 20, 2013
Speaker(s):

I discuss a technique - the quantum adversary upper bound - that uses the structure of quantum algorithms to gain insight into the quantum query complexity of Boolean functions. Using this bound, I show that there must exist an algorithm for a certain Boolean formula that uses a constant number of queries. Since the method is non-constructive, it does not give information about the form of the algorithm. After describing the technique and applying it to a class of functions, I will outline quantum algorithms that match the non-constructive bound.

Scientific Areas:

## Bulk-boundary correspondence in PEPS

Wednesday Nov 13, 2013
Speaker(s):

TBA

Scientific Areas:

## A universal Hamiltonian simulator: the full characterization

Monday Nov 11, 2013
Speaker(s):

We show that if the ground state energy problem of a
classical spin model is NP-hard, then there exists a choice parameters of the
model such that its low energy spectrum coincides with the spectrum of
\emph{any} other model, and, furthermore, the corresponding eigenstates match
on a subset of its spins. This implies that all spin physics, for example all
possible universality classes, arise in a single model. The latter property was
recently introduced and called Hamiltonian completeness'', and it was shown

Scientific Areas:

## Asymptotically Optimal Topological Quantum Compiling

Wednesday Oct 30, 2013
Speaker(s):

In a topological
quantum computer, universality is achieved by braiding and quantum information
is natively protected from small local errors. We address the problem of
compiling single-qubit quantum operations into braid representations for
non-abelian quasiparticles described by the Fibonacci anyon model. We develop a
probabilistically polynomial algorithm that outputs a braid pattern to
approximate a given single-qubit unitary to a desired precision. We also
classify the single-qubit unitaries that can be implemented exactly by a

Scientific Areas:

## Universal fault-tolerant quantum computation with only transversal gates and error correction

Wednesday Sep 25, 2013
Speaker(s):

Transversal
implementations of encoded unitary gates are highly desirable for
fault-tolerant quantum computation.  It is known, however, that
transversal gates alone cannot be computationally universal.  I will show
that the limitation on universality can be circumvented using only
fault-tolerant error correction, which is already required anyway.  This
result applies to triorthogonal'' stabilizer codes, which were recently
introduced by Bravyi and Haah for state distillation.  I will show that

Scientific Areas:

## Generalized Relative Entropies, Entanglement Monotones and One-Shot Information Theory

Monday Jun 17, 2013
Speaker(s):

We introduce two relative entropy quantities called the min- and max-relative
entropies and discuss their properties and operational meanings.

These relative entropies act as parent quantities for tasks such as data compression, information
transmission and entanglement manipulation in one-shot information theory. Moreover, they lead us to define entanglement monotones which have interesting operational interpretations.

Scientific Areas:

## Information Theoretic Benefit of Entanglement in Classical Communication Settings

Monday May 27, 2013
Speaker(s):

Expressions of several information theoretic quantities involve an optimization over auxiliary quantum registers. Entanglement-assisted version of some classical communication problems provides examples of such expressions. Evaluating these expressions requires bounds on the dimension of these auxiliary registers. In the classical case such a bound can usually be obtained based on the

Scientific Areas:

## LECTURES ON-DEMAND

### Jocelyn Bell Burnell: University of Oxford

Speaker: Jocelyn Bell Burnell