Skip to content. Skip to navigation
McGill Home SOCS Home
Personal tools
You are here: Home Announcements and Events Seminars Schedule

Seminar Home
Fall 2013 Schedule
Winter 2014 Schedule
Summer 2014 Schedule
Archives

SOCS CQIL - Cryptography and Quantum Information Seminar Schedule

Date Category Seminar Info
2013/04/25 CQIL - Cryptography and Quantum Information Place: McConnell 321
Time: 16:00 - 17:00
Speaker: Maris Ozols
Affiliation: University of Waterloo
Title: The classical analogue of quantum mechanics
Abstract:

Richard Feynman is known for his quote "I think I can safely say that nobody understands quantum mechanics." In this talk I will establish a weaker result, namely "to fully understand something quantum, one has to at least know what the classical equivalent of it is." As observed by Bell in 1964, quantum mechanics is not compatible with certain classical theories. Nevertheless, classical theories, such as Spekkens toy theory, can exhibit many quantum-like features. In fact, Collins and Popescu has established a strong analogy between quantum entanglement and secret classical correlations. For example, teleportation corresponds to one-time pad according to their framework. I will extend their framework by describing a classical analogue of mixed quantum states. This leads to even more striking classical analogues of quantum phenomena, such as bound entanglement and superactivation of quantum capacity. To illustrate the usefulness of this unusual classical theory, I will explain a new construction of bound entangled states with smaller dimension (3 x 3) and higher amount of secret key, and show that local noise can increase privacy in classical secret key distillation protocols. This is joint work with Graeme Smith and John Smolin from IBM.


2013/03/25 CQIL - Cryptography and Quantum Information Place: McConnell 103
Time: 16:00 - 17:00
Speaker: Gus Gutowski
Affiliation: University of Waterloo
Title: Parallel approximation of min-max problems
Abstract:

This paper presents an efficient parallel approximation scheme for a new class of min-max problems. The algorithm is derived from the matrix multiplicative weights update method and can be used to find near-optimal strategies for competitive two-party classical or quantum interactions in which a referee exchanges any number of messages with one party followed by any number of additional messages with the other. It considerably extends the class of interactions which admit parallel solutions, demonstrating for the first time the existence of a parallel algorithm for an interaction in which one party reacts adaptively to the other. As a consequence, we prove that several competing-provers complexity classes collapse to PSPACE such as QRG(2), SQG and two new classes called DIP and DQIP. A special case of our result is a parallel approximation scheme for a specific class of semidefinite programs whose feasible region consists of lists of semidefinite matrices that satisfy a transcript-like consistency condition. Applied to this special case, our algorithm yields a direct polynomial-space simulation of multi-message quantum interactive proofs resulting in a first-principles proof of QIP=PSPACE. Joint work with Xiaodi Wu. Based on http://arxiv.org/abs/1011.2787.