Date: Monday 19 December

Who: Scott Aaronson

When: 12 Midday

Where: Conference Room, Physics Annexe

Seminar type: Research

Abstract:
Quantum computing skeptics have claimed that any theory involving exponentially-long vectors is inherently unreasonable. But if someone hands you a quantum state, is that really like being handed an exponential amount of classical information? I’ll describe recent results suggesting that the answer, at least for complexity-theoretic purposes, is “no.” These results include simulations of quantum advice using classical advice, and a conditional “dequantization” of John Watrous’s quantum proof protocol for the Group Non-Membership problem.

How much I actually cover will be tailored based on audience interest. Based partly on joint work with Greg Kuperberg.

Date: Thursday 22 December

Who: Scott Aaronson

When: 4.00pm

Where: Conference room, Physics Annexe

Seminar type: Tutorial 3 of 3

In this set of three tutorial talks, I’ll explore why it’s so hard to prove complexity classes equal or unequal. The first talk concentrated on P versus NP. After giving some history of the question and explaining why it’s important, I’ll talk about two barriers that any solution will have to overcome: relativization and natural proofs. As time permits, I’ll also discuss the current ideas for non-relativizing, non-naturalizing proof techniques.

Depending on audience interest, the next two talks might go further into P versus NP, or they might address why *quantum* complexity is so hard.

Date: Tuesday 20 December

Who: Scott Aaronson

When: 4.00pm

Where: Conference room, Physics Annexe

Seminar type: Tutorial 2 of 3

In this talk I’ll discuss interactive proofs, the only technique we know that’s strong enough to evade both barriers to proving P!=NP (namely relativization and natural proofs). Unfortunately, it *still* doesn’t seem strong enough!

I’ll describe the interactive proof for unsatisfiability, and try to convey why it was so surprising. I’ll then explain how interactive proofs yield a nonrelativizing circuit lower bound: that for every fixed k, there exists a language in the class PP that does not have circuits of size n^k (not even quantum circuits with quantum advice).

Date: Tuesday 13 December

Who: Scott Aaronson

When: 4.00pm

Where: Conference room, Physics Annexe

Seminar type: Tutorial 1 of 3

In this set of three tutorial talks, I’ll explore why it’s so hard to prove complexity classes equal or unequal. The first talk will concentrate on P versus NP. After giving some history of the question and explaining why it’s important, I’ll talk about two barriers that any solution will have to overcome: relativization and natural proofs. As time permits, I’ll also discuss the current ideas for non-relativizing, non-naturalizing proof techniques.

Depending on audience interest, the next two talks might go further into P versus NP, or they might address why *quantum* complexity is so hard.

Date: Thursday 15 December

Who: Jacob Dunningham

When: 4.00-5.15pm

Where: Conference Room, Phyics Annexe

Seminar type: Tutorial

Abstract:
One of the most fascinating properties of Bose-Einstein condensates is that they contain large numbers of particles all in the same quantum state. This opens up the possibility of creating macroscopic superposition (cat) states with them. In this final talk, I will discuss how these superpositions can be generated in the laboratory and how they may be useful in a range of new technologies. I will also outline the difficulties associated with using them, in particular the problems with “seeing” them.

Date: Thursday 8 December

Who: Jacob Dunningham

When: 4.00-5.15pm

Where: Conference Room, Phyics Annexe

Seminar type: Tutorial

Abstract:
A central problem in the theory of matter wave sources is whether we can attribute a definite quantum phase to a condensed gas. Can such a phase be defined in a manner that everyone will agree on? Is it more than a convenient fiction or an unwarranted extrapolation of the ideas of spontaneous symmetry breaking from infinite systems to the finite condensates produced in the laboratory? These issues and many related ones have caused a great deal of discussion and confusion. In this tutorial, I will introduce the subject of the quantum phase of BECs and, with some simple models, attempt to resolve some of the confusion. I will also discuss some of the important issues and consequences that this subject gives rise to.