Friday, 13 July 2012, 4:00 pm
Room G.07, School of Informatics
10 Crichton Street, Edinburgh EH8 9AB
and afterwards for a drinks and canapé reception

Quantum Computing and the Limits of the Efficiently Computable

I’ll discuss what can and can’t be feasibly computed according to physical law. I’ll argue that this is a fundamental question, not only for mathematics and computer science, but also for physics; and that the infeasibility of certain computational problems (such as NP-complete problems) could plausibly be taken as a physical principle, analogous to the Second Law or the impossibility of superluminal signalling. I’ll first explain the basics of computational complexity, including the infamous P versus NP problem and the Extended Church-Turing Thesis. Then I’ll discuss quantum computers: what they are, whether they can be scalably built, and what’s known today about their capabilities and limitations.

Lastly, I’ll touch on speculative models of computation that would go even beyond quantum computers, using (for example) closed timelike curves or nonlinearities in the Schrodinger equation. I’ll emphasize that, even if “intractable” computations occur in a particular description of a physical system, what really matters is whether those  computations have observable consequences.

Venue: School of Informatics, University of Edinburgh, Room 4.33/4.31
Times: 15:00 till 16:30

New Computational Insights from Quantum Optics

Tuesday 10/7/2012

In work with Aleksandr Arkhipov, we proposed a rudimentary form of quantum computing, based on linear optics with nonadaptive measurements; and used a connection between linear optics and the permanent function to show that even this limited model could solve sampling and search problems that are intractable for classical computers under plausible complexity assumptions.  In this talk, I’ll discuss this work in a self-contained way, and mention some of its implications for quantum computing experiments. I’ll also discuss some more general results that emerged from our work. These include a new equivalence between sampling problems and search problems based on Kolmogorov complexity; a new, linear-optics-based proof of Valiant’s famous theorem that the permanent is #P-complete; and a new classical approximation algorithm for the permanent.

Papers:
The Computational Complexity of Linear Optics
The Equivalence of Sampling and Searching
A Linear-Optical Proof that the Permanent is #P-Hard

How Much Information Is In A Quantum State?

Wednesday 11/7/2012

People often talk about the quantum state of n entangled particles as if it contained an amount of information exponential in n.  In this talk, I’ll discuss three results that suggest that, in various senses relevant for computation, prediction, and learning, quantum states
actually *don’t* behave as if they contained exponential amounts of information. Specifically, I’ll discuss the limitations of “quantum advice states,”the approximate “learnability” of quantum states from random measurement results, and the simulation of arbitrary quantum state preparation tasks by the preparation of ground states of local Hamiltonians (joint work with Andrew Drucker).

Papers:
Limitations of Quantum Advice and One-Way Communication
The Learnability of Quantum States
A Full Characterization of Quantum Advice

Talk #3

Thursday 12/7/2012

Talk #3 will be determined based on audience interest.