Scott’s coming to town:
CSE Colloquium, 04/12/2007 3:30 pm, EE-105
Talk: The Limits of Quantum Computers
Speaker: Scott Aaronson (University of Waterloo)
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 quantum computers on their head, and use them to develop new techniques for experimentalists.
No quantum computing background will be assumed.
Since no quantum computing background is assumed, I may even be able to follow this one!
I’m travelling, otherwise I’d be there — I’ll be very sorry to miss Scott’s talk.
Scott, I uttered the words “Clifford algebra” at Intel yesterday … if you’re still around the UW on Friday, I’d be happy to say how the topic came up.
Dave
Are there any plans in the future to webcast any of the quantum seminars at UW? I thought I remember reading somewhere on here that you guys do em like weekly. I for one would watch em. Thanks again.
Chris
We videotape the CSE colloquium, but as of yet the quantum seminar doesn’t exactly exist in any tapeable manner. Scott’s talk will be available soon after the talk and I’ll post once it gets up.
update 4/12/07: Actually Scott’s talk won’t be available for a while now.
Sweeeeeeeet
Ok – thanks man. I will just have to watch the talk.
I am also interested in seeing this talk. Do you know if there an accompanying paper or even a pdf of the talk available?
Actually Scott’s talk won’t be available for a while afterwards it turns out.
Hey everyone, the video and slides will both be available in two weeks, after I’m done all my job interviews. Until then I need to carefully safeguard my jokes…
A quantum computer should be able to solve an NP complete problem having (power set of natural numbers) power.
But what about power set of power set of natural numbers. (That requires a higher order super-quantum computer). (Check cardinality of power set of natural numbers in Wikipedia)
And what about power set of power set of power set of natural numbers.
and so on.
Is there a JOURNAL ARTICLE ON THIS MACHINE.
Has it started solving prime number problems yet as required to crack encryption.
Erach
What about Shor’s algorithm.
See arxiv.com paper
reference
http://arxiv.org/PS_cache/quant-ph/pdf/9508/9508027v2.pdf
author Peter W. Shor.
title:
Polynomial-Time Algorithms for Prime Factorization
and Discrete Logarithms on a Quantum Computer.
I’m travelling, otherwise I’d be there — I’ll be very sorry to miss Scott’s talk.
Scott, I uttered the words “Clifford algebra†at Intel yesterday … if you’re still around the UW on Friday, I’d be happy to say how the topic came up.