Category: Science

Posted on

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!

Posted on

Science 2.0: Academic Reader

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.

Posted on

Lightning Rods Against God's Fury

I recently picked up Discarded Science: Ideas that seemed good at the time… by John Grant, a delightful little book about ideas in science that just didn’t pan out (hmmm….how many of my papers will be relegated to that dustbin? Ack, down that pathway lies depression.) When I was but a wee lad I spent many hours reading books about the Loch Ness monster, UFOs, and Bigfoot. (Not only did I learn to debug before I learned to program, apparently I learned pseudoscience before I learned science. Hmmm.) My experience with these early pseudoscience books has led me to think an important part of understanding science is to understand what is not science. Plus I am a real sucker for the kind of half baked arguments that are a stable of those pseudoscientific books. My favorite passage from the book so far is a classic illustration

…In November 1755 the most destructive earthquake ever to strike the northeastern US hit at Cape Ann, some 50km south of Boston. The Reverend Thomas Prince, of South Church, Boston, knew at once who was to blame: Benjamin Franklin (1706-1790), for having invented the lightning conductor. Before Franklin’s scheme of putting pointed metal rods on tall buildings had been universally adopted, God had been able to express His wrath by blasting something with lightning. Now that the presumptuous Franklin had taken that option away from Him, He was having to use earthquakes instead.

Which leads, of course, to the question of just how many tools of God has Science destroyed?

Posted on

America COMPETES

New legislation designed to help foster science, innovation, and education: the America COMPETES (Creating Opportunities to Meaningfully Promote Excellence in Technology, Education, and Science) Act. Proposes, among other things, the doubling of NSF/DoE Office of Science budgets in four years.

Posted on

Mock Theta Functions?

Any mathematician care to comment on this press coverage of a recent preprint on Mock Theta Functions? Oh, right I scared away all the mathematicians when I urged computer scientists and physicists to join in war against the evil mathematicians (a war since expanded to include evil biologists. 😉 )

Posted on

Scientometrics On Your Desktop

Publish or Perish: a program for calculating h-indices and more. (And yes, to preempt the grumpy academics, taking these measures seriously is clearly silly. But then again, from my perspective there ain’t much in the world that ain’t just plain silly 😉 )

Posted on

Scirate.com Not Just For Quantum Anymore

A few changes at Scirate.com, which I thought I’d mention. The website now supports all of the different arXives. Of course since the only people who read this silly blog are quantum people, I have no idea how much traction these other archives will have in the short term. Navigation to different days should now be easier with the handy-dandy floating navigation icons I’ve setup. Finally, international characters should be showing up correctly now….I hope! Stay tuned for lots of interesting upgrades (lots of ideas!)…err well, just as long as I can find some spare time!

Posted on

Factoring Bacteria

No sooner do I attack biologists as the common mortal enemy of computer scientists and physicists in my last post when along comes quant-ph/0702203. Yet another nomination, in that great cosmic contest: “best paper title ever!” (said with the comic book guy accent, of course.) quant-ph/0702203:

Purple bacteria and quantum Fourier transform
Author: Samir Lipovaca
Abstract: The LH-II of purple bacteria Rhodospirillum (Rs.) molischianum and Rhodopseudomonas (Rps.) acidophila adopts a highly symmetrical ring shape, with a radius of about 7 nm. In the case of Rps. acidophila the ring has a ninefold symmetry axis, and in LH-II from Rs. molischianum the ring has an eightfold symmetry axis. These rings are found to exibit two bands of excitons. A simplified mathematical description of the exciton states is given in Hu, X. & Schulten, K. (1997) Physics Today 50, 28-34. Using this description, we will show, by suitable labeling of the lowest energy (Qy) excited states of individual BChls, that the resulting exciton states are the quantum Fourier transform of the BChls excited states. For Rs. molischianum ring exciton states will be modeled as the four qubit quantum Fourier transform and the explicit circuit will be derived. Exciton states for Rps. acidophila ring cannot be modeled with an integer number of qubits. Both quantum Fourier transforms are instances of the hidden subgroup problem and this opens up a possibility that both purple bacteria implement an efficient quantum circuit for light harvesting.

Boy are we going to have mud on our face when we discover that Bacteria have beaten even D-wave towards the construction of a useful quantum computer 😉

Posted on

Welcome to the Feast, Tums Provided

Over at Shtetl-Optimized, Scott goes a little ballistic on criticism he’s received over the wording of his and Umesh Vazirani’s letters to the Economist. (As a side note, it is kind of sad to see such a poorly written article in the Economist: I know for a fact that an early Economist article on Shor’s algorithm drew a lot of great people into the field of quantum computing.) Part of Scott’s issue is with “physicists” insisting on rigor when they themselves are “the headmasters of handwaving.” So when Scott says

Today it is accepted that quantum computers could not solve NP-complete problems in a reasonable amount of time.

and he gets a lot of flack from physicists insisting that his statement might be interpreted as BQP not containing NP, he gets rather ticked off since those “headmasters of handwaving” themselves make all sorts of statements like this and don’t seem to mind. “Double standard!” shouts Da Optimizer!
Now one could take Scott’s rant and turn it into a great computer-science physics flamewar, but what fun would that be? And I’m a softy (or a Chinese restaurant placemat, depending on your perspective), so I’d like to take what Scott has said and turn it around. Therefore, let me declare the following Pontiffical edict:

Welcome to the headmasters of handwaving club, theoretical computer scientists! We’ve got a seat ready for you right here at our table, all full of delightful theorems and lemmas which you can eat….without having to give a proof of their validity. Our feasts our grand, our parties even wilder, and our nights filled with wonder and awe. Sure you may get a little indigestion, what with the unproven or even, dare I mention the word, wrong, theorems, tumbling around in your belly, but look at what you get in return! Did I mention the wild parties?

I guess in my mind, I actually think that computer science and physics have a lot more in common with each other than either side would ever dare admit. For example, researchers from both fields, it seems to me, can be placed (borrowing the terminology of physics only because of stuff in my past light-cone) neatly on a linear diagram from “experimentalist” to “theorist.” Just as “experimental computer scientists” complain to death about the lack of usefulness of the algorithms invented by “theoretical computer scientists”, “experimental physicists” spend vast hours complaining about the indigestability of the vast body of the “theoretical physics.” But every so often, in this tension, the theorist from both sides do something so remarkable and so practically important that the experimentalists get really excited and actually take the theory and put it to use. Similarly, theorists from both sides who don’t take heed of the experimental side of their field are, it seems to me, destined for obscurity. For example a theoretical physicist who ignores the fact that thier pet theory violates nearly every experiment ever performed, or a theoretical computer scientist who works with a model of computation so irrelevant to modern computation that no one notices (and no I don’t put the entire complexity zoo into this category: the reasons for studying the zoo go far beyond simply defining complexity classes so obscure as to be irrelevant…the beauty of the best complexity classes is exactly in their relevance to our real world computation questions.) both share a common destiny in the dustbin of irrelevant results.
So, rejoice, physicist and computer scientists! You masters of the twentieth century, makers of the grandest constructions in the world and in our minds, and find peace in fighting against your common rising enemy: those damn pesky biologists!

Posted on

Scirate.com

…
Dave, where have you been? Your posting has been almost nonexistent over the last few weeks. Why?
I’ve been busy.
Really? Academics are busy? I thought that they only taught one course per term. Sounds like you are a bunch of tax payer sponsored lazy bums to me.
Bah, you have no idea! Grumble, grumble. But more seriously I haven’t been blogging because I only have a certain small amount of free time and I’ve been dedicating all this time to a new project.
New project? Like your project to make an information theoretic transactional interpretation of quantum theory?
No, even more bizarre. A website.
A website? Come on, Dave, last time I created a website it took me like a few minutes. Are you really that slow?
I am slow. But that’s another issue. What took me so long was that I needed to learn php and a little javascript and extend my mastery of pyton to get the website working.
Ah, becoming a true computer scientist are you, Dave?
Hey, since Scott Aaronson can now claim to be “the second funniest physics blogger,” maybe with these skills I can claim to be “the second least funny computer science blogger!”
So what is this website of which you speak? I hope its not pornography related.
No, no pornography. The website is called scirate.com.
Scirate.com? Are you irate about science or something? I’m certainly irate about science…I hate how that damn thing called reality keeps dragging me down.
No, I love science. It doesn’t make me irate at all. Just filled with a deep calm. So take that! But anyway, scirate.com is a website inspired by digg.com, the arxiv, the open archives initiative, conversations I’ve had with Joe Renes, Michael Bremner, and a host of others, and my desire to have some fun.
Fun? So it IS pornography related.
No. No pornography. The idea came from the observation that while the arxiv is a amazing tool, one of the problems was that the volume of papers was high and, to put it bluntly, the quality of these papers was not necessarily so great. So the question became, how do I do something to filter out the arxiv? Now, of course, everyone will want a slightly different filter. One person’s noise might be indeed another persons operatic masterpeice. But there should be a way to produce at least “some” kind of filter based on the quality of the work. And certainly computers aren’t smart enough to do this filtering (okay that’s a challenge to all you AI people out there!) And using citations is too slow. But there is a group of experts out there who can do pretty good filtering…
Who?
You! And by “you” I mean the people who read the arxiv listings.
Me? What can I do?
Well, each day postings from the arxiv (actually only from quant-ph right now, see below) are listed onto scirate.com. If you are registered, you can then look through the listing and vote (or “Scite” as I call it) for the preprints. Then, when you display, or anyone else displays the page, the listing will be sorted by vote. So, with enough user participation, the hope is that the signal will “float” to the top. A noise filter!
Are you calling me a Butterworth filter?
Nothing of the sort. I’m calling you a useful!
Okay, but aren’t you worried about vote stuffing?
Certainly vote stuffing is possible. But I’m an optimist when it comes to others behavior. That being said, I have a few tricks for avoiding vote stuffing.
Fine, but aren’t you worried that this just adds another layer to the popularity contest of science. Aren’t you just adding another leg in the “publish or perish” beast?
No, I’m not worried. First of all to have an impact it must be used by more than a few crazies like those people who read this website. And if it is used by more than a few crazies, well then I think the site is worth it. Second of all, anyone who takes seriously citation data of any sort is setting themselves up for “the wrong kind of science.” Just because the reality of how academia works is a pain doesn’t mean that you have to buy into carrying about how cited your paper is. You should be doing science for the reasons of expanding knowledge.
Okay, maybe I’m a little interested. Oh wait, I’m a high energy theorist, but you only have quant-ph. Why?
Well right now I only have quant-ph. This is because quant-ph is what I read and I wanted to start somewhere familiar. Second, I do plan on extending it to the other arxiv’s and allowing you choose which arxiv’s to browse, etc. Third, the arxiv is moving to a new format for papers sometime soon and this will certainly break my oai harvester, so I will wait until they make that change before I attack the other arxivs.
Fair enough, but the site seems a little barebones, doesn’t it?
Yep. Mostly I’ve just been focusing on getting the barebones site up and running. Further improves will come if there is enough interest. And of course it would be great if users could tell me about problems their having or features they’d like to see. To do this I’ve set up a blog scirate.com/blog.
Why are the abstracts displayed in small font?
Click on them and find out.
I voted, but the paper didn’t change order.
Yes, right now you have to reload to get the new order. This will, eventually, be fixed.
Can’t you do something more sophisticated like feature X on digg.com?
Eventually there will be more features. Believe me I have a long list of ideas, but I’m always open to ideas. Again The Scirate Blog is a good place to post your ideas.
What software did you use to write the site? Why didn’t you use Pligg, the digg clone?
Php, mysql, javascript, some serverside ajax stuff, python. Doing things on your own is funner. Did I ever tell you about how I learned Calculus? I bought a book on quantum mechanics and on about page 12 came to an integral sign (the famous integral sign that Planck turned into a sum sign!) and didn’t know what it was. I took it to a teacher who knew it was an integral sign. So I went off and learned Calculus.
You really are obsessed with quantum theory, aren’t you?
Yes.
Well, Dave, I’ll see you later. I’ll see you at QIP right?
Um, did I mention I’m teaching this term?
You inserted that last sentence to make this blog post one big circle didn’t you?
…