Come to Japan! See who can eat more sushi, Dave or Scott?
Asian Conference on Quantum Information Science
September 3-6, 2007
Shiran Kaikan, Kyoto University
Webpage http://qc.naist.jp/aqis07. Poster here.
O brave new quantum world!
Come to Japan! See who can eat more sushi, Dave or Scott?
Asian Conference on Quantum Information Science
September 3-6, 2007
Shiran Kaikan, Kyoto University
Webpage http://qc.naist.jp/aqis07. Poster here.
A new quantum computing blog: nextquant. Also Strange Paths.
My new favorite quantum hyperbole:
Handed to generals, a quantum computer might transform an ordinary nation into an instant superpower. Dozens of incoming missiles could be tracked at once.
Things that happened while I was off the edge of the Interwebs:
April 15, 2007 in Ashland, Oregon
That other Pontiff has declared that he “believes in evolution.” Am I the only one who read “[reclaim] a dimension of reason we have lost” and thought of string theory? (That’s a joke peoples, so don’t get your stringy hair in an uproar!)
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!
A new website of great interest to those of us punished under the crush of information in science, Academic Reader. Created by (I hope I have this right) Michael Nielsen, Peter Rhode, and Alexei Gilchrist the website is a way to manage your academic reading:
The Academic Reader is a new web site that makes it easier to keep track of your scientific reading. Rather than going to multiple websites every day to keep up, we pull all the sources together in a single location, so you can keep track easily. Sources include the preprint arXiv, the Physical Review, and Nature, and many new sources will be added in the months to come, including sources outside physics.
Good stuff, check it out!
And yes, Scirate.com is still down. The open archive protocol they are using is back up but has been changed in ways that may take a bit to fix is still down. Hopefully I can get the site running again before I drop off the edge of the internet and get married.