[Colloquium] REMINDER: today's talk by Scott Aaronson

[Margery Ishmael]

DEPARTMENT OF COMPUTER SCIENCE - TALK

Date: Tuesday, March 6
Time: 3:00 p.m.
Place: Ryerson 251 (1100 E. 58th St.)

-------------------------------------------

Title: The Limitations of Quantum Computers
Speaker: SCOTT AARONSON (University of Waterloo)
Url: http://www.scottaaronson.com/

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.


***The talk will be followed by refreshments in Ryerson 255***

-------------------------------------------------------

Host:  Laci Babai

People in need of assistance should call 773-834-8977 in advance.

For information on future CS talks: http://www.cs.uchicago.edu/events




-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20070306/d04278f7/attachment.htm