The NP-complete Dog and Pony Show Comes to Seattle

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!

This entry was posted in Computer Science, Quantum, Science, Seattle. Bookmark the permalink.

11 Responses to The NP-complete Dog and Pony Show Comes to Seattle

  1. John Sidles says:

    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.

  2. Chris says:

    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

  3. Dave Bacon says:

    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.

  4. Chris says:

    Sweeeeeeeet

  5. JOE says:

    Ok – thanks man. I will just have to watch the talk.

  6. JOE says:

    I am also interested in seeing this talk. Do you know if there an accompanying paper or even a pdf of the talk available?

  7. Dave Bacon says:

    Actually Scott’s talk won’t be available for a while afterwards it turns out.

  8. Scott says:

    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…

  9. Erach Irani says:

    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

  10. Erach Irani says:

    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.

  11. Aani says:

    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.

Leave a Reply

Your email address will not be published. Required fields are marked *