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

## Adiabatic quantum optimization fails for random instances of NP-complete problems

Wednesday Oct 07, 2009
Speaker(s):

Adiabatic quantum optimization has attracted a lot of attention because small scale simulations gave hope that it would allow to solve NP-complete problems efficiently. Later, negative results proved the existence of specifically designed hard instances where adiabatic optimization requires exponential time. In spite of this, there was still hope that this would not happen for random instances of NP-complete problems.

Scientific Areas:

## Adiabatic Gate Teleportation and Topological Quantum Computing

Monday Sep 14, 2009
Speaker(s):

TBA

Scientific Areas:

## Innovations in Maximum Likelihood Quantum State Tomography

Wednesday Sep 09, 2009
Speaker(s):

At NIST we are engaged in an experiment whose goal is to create superpositions of optical coherent states (such superpositions are sometimes called "Schroedinger cat" states). We use homodyne detection to measure the light, and we apply maximum likelihood quantum state tomography to the homodyne data to estimate the state that we have created.

Scientific Areas:

## The quantum adiabatic theorem and eigenpath traversal

Wednesday Aug 12, 2009
Speaker(s):

We review situations under which standard quantum adiabatic conditions fail. We reformulate the problem of adiabatic evolution as the problem of Hamiltonian eigenpath traversal, and give cost bounds in terms of the length of the eigenpath and the minimum energy gap of the Hamiltonians. We introduce a randomized evolution method that can be used to traverse the eigenpath and show that a standard adiabatic condition is recovered. We then describe more efficient methods for the same task and show that their implementation complexity is close to optimal.

Scientific Areas:

## Quantum State and Process Measurement and Characterization

Wednesday Jun 03, 2009
Speaker(s):

This talk will present an overview of work done in the past decade on quantum state and process tomography, describing the basic notions at an introductory level, and arguing for a pragmatic approach for data reconstruction. The latest results include recent numerical comparison of different reconstruction techniques, aimed at answering the question: "is 'the best' the enemy of 'good enough'?"

Scientific Areas:

## A strong converse for classical channel coding using entangled inputs

Wednesday May 20, 2009
Speaker(s):

A fully general strong converse for channel coding states that when the rate of sending classical information exceeds the capacity of a quantum channel, the probability of correctly decoding goes to zero exponentially in the number of channel uses, even when we allow code states which are entangled across several uses of the channel. Such a statement was previously only known for classical channels and the quantum identity channel.

Scientific Areas:

## Physical Implementation of Quantum Random Walks

Wednesday May 06, 2009
Speaker(s):

Quantum random walks have received much interest due to their non-
intuitive dynamics, which may hold a key to radically new quantum
algorithms. What remains a major challenge is a physical realization
that is experimentally viable, readily scalable, and not limited to
specific connectivity criteria. In this seminar, I will present an
implementation scheme for quantum walking on arbitrarily complex
graphs. This scheme is particularly elegant since the walker is not

Scientific Areas:

## Decoherence and Entanglement Dynamics of Coupled Qubits

Monday Mar 23, 2009
Speaker(s):

We study the entanglement dynamics and relaxation properties of a system of two interacting qubits in the two cases (I) two independent bosonic baths and (II) one common bath, at temperature $T$. The entanglement dynamics is studied in terms of the concurrence C(t) between the two spins and of the von Neumann entropy S(t) with respect to the bath, as a function of time. We prove that the system does thermalize. In the case (II) of a single bath, the existence of a decoherence-free (DFS) subspace makes entanglement dynamics very rich.

Scientific Areas:

## Permutational quantum computation and spin networks

Wednesday Mar 04, 2009
Speaker(s):

In topological quantum computation the geometric details of a particle trajectory become irrelevant; only the topology matters. This is one reason for the inherent fault tolerance of topological quantum computation. I will speak about a model in which this idea is taken one step further. Even the topology is irrelevant. The computation is determined solely by the permutation of the particles.

Scientific Areas:

## Quantum algorithm for Statistical Difference problem

Wednesday Feb 18, 2009
Speaker(s):

Suppose we are given two probability distributions on some N-element set. How many samples do we need to test whether the two distributions are close or far from each other in the L_1 norm? This problem known as Statistical Difference has been extensively studied during the last years in the field of property testing. I will describe quantum algorithms for Statistical Difference problem that provide a polynomial speed up in terms of the query complexity compared to the known classical lower bounds.

Scientific Areas:

## RECENT PUBLIC LECTURE

### Amber Straughn: A New Era in Astronomy: NASA’s James Webb Space Telescope

Speaker: Amber Straughn