[Colloquium] Two talks by Scott Aaronson next week

[Margery Ishmael]

>             DEPARTMENT OF COMPUTER SCIENCE
>           TWO LECTURES ON QUANTUM COMPUTING
>                  by Scott Aaronson
>
>  Scott Aaronson (University of Waterloo) will give  two talks
> on quantum computing.    The second talk, on Wednesday, March 7,
> 12:30pm, is intended for a GENERAL SCIENCE AUDIENCE and physicists
> in particular.
>
>   The first talk, on Tuesday, March 6, 3pm, is intended for a
> computer science audience (of course everybody is welcome to attend).
>
> The two talks are independent.   The abstracts are appended below.
>
> Host: Laci Babai   773-702-3486   laci at cs.uchicago.edu
> ============================================================
> (second lecture)
>
>           DEPARTMENT OF COMPUTER SCIENCE
>       Lecture of general interest to science
>             *** Please distribute ***
>
> Title: Computational Intractability as a Law of Physics
> Speaker: Scott Aaronson (University of Waterloo)
>
> Date: Wednesday, March 7, 12:30 pm
> Place: Ryerson 251
>
> ABSTRACT
>
> Several of the deepest principles in physics can be seen as limits on
> technology: for example, the Second Law of Thermodynamics and the
> impossibility of superluminal communication.  In this talk, I'll ask
> whether the hardness of NP-complete computational problems would
> likewise be useful to assume as a physical principle.  To investigate
> this question, I'll study the computational effects of living in a
> universe with closed timelike curves, a universe where the  
> Schroedinger
> equation was nonlinear, a universe with particular many-particle
> entangled states left over from the Big Bang, or a universe where you
> could kill yourself with some probability and then 'postselect' on
> remaining alive.  I'll show that one can make definite, nontrivial
> statements about what problems could be efficiently solved in each of
> these universes -- and also about what problems still couldn't be.
>
> =========================================================
> (first lecture)
>
> Title: The Limitations of Quantum Computers
> Speaker: Scott Aaronson (University of Waterloo)
>
> Date: Tuesday, March 6, 3pm
> Place: Ryerson 251
>
> ABSTRACT
>
> In the popular imagination, quantum computers would be almost magical
> devices, able to "solve impossible problems in an instant" by trying
> exponentially many solutions in parallel.  In this talk, I'll describe
> four results in quantum computing theory that directly challenge this
> view.
>
> First, I'll show that any quantum algorithm to decide whether a
> function f:[n]->[n] is one-to-one or two-to-one needs to query the
> function at least n^{1/5} times.  This provides strong evidence that
> collision-resistant hash functions, and hence secure electronic
> commerce, would still be possible in a world with quantum computers.
>
> Second, I'll show that in the "black-box" or "oracle" model that we
> know how to analyze, quantum computers could not solve NP-complete
> problems in polynomial time, even with the help of nonuniform "quantum
> advice states."
>
> Third, I'll show that quantum computers need exponential time to find
> local optima -- and surprisingly, that the ideas used to prove this
> result also yield new classical lower bounds for the same problem.
>
> Finally, I'll show how to do "pretty-good quantum state tomography"
> using a number of measurements that increases only linearly, not
> exponentially, with the number of qubits.  This illustrates how one
> can sometimes turn the limitations of computational devices on their
> head, and use them to develop new techniques for experimentalists.
>
> No quantum computing background is assumed.
>
>
>