Freeriding on the Back of a Giant While Slapping the Giant Upside the Face

Somedays I just simply can’t take it anymore and would like to see nothing more than the banning of all my anti-science bretheren from using all of the benefits which science has brought to the world. Don’t believe in science, FINE, don’t use anything science helps discover. I’ll be happy to take the other side of the coin and agree to not benefit from any drug invented by some evolution doubting creationist or other such creature.
In the local UW rag: “The Daily”

Is intelligent design that scary?
As Jared Silvia states in “So what if we are monkeys?” (May 5) we indeed are “truly special.”
We are special enough to understand, as legislators in Kansas have grasped, that evolution is not the end-all it proposes to be. These legislators have realized since science will never be able to prove or disprove the evolutionary process, there must be another pertinent argument out there.
Contrary to what Silvia says, the theory of evolution is easy to wrap one’s mind around. It’s easy to look at dinosaurs, fossils and apes and draw conclusions that we are the apex of a long chain of evolution. What is hard is proving this fact. Where are the laws of science (the second law of thermodynamics), the DNA sequences, or the evidence of transitionary species (like the humans with no eyes) that prove evolution is the truth?
The Kansas legislators must have come to the same conclusions a lot of astronomers have come to recently when looking at the galaxies of the universe. These things may have been created by intelligent design.
Science can neither prove nor disprove evolution, so let’s stop the scientific and educational community from favoring only the theory of evolution. Is it such a bad thing to juxtapose one “theory” with another to facilitate a balanced discussion, as we will hopefully see during the future in Kansas?
John Messner, senior, history

When I see dribble like this I always think of my favorite theory which explain the universe. It involves lots of pink elephants, psycho grandmothers, gay sex, and arguments that Jesus was an athiest. And of course, it’s a possible explanation for all the experimental data (you really don’t want me to give the full theory do you? I’ll bet anyone I can turn any set of four items into an alternative explanation of the theory of evolution.) So please, Mr. Messner, let me teach my theory to all those young little minds and I’ll be glad to teach your intelligent design theory.
And then, to make my day even brighter, I find in Nature:

Academics stress licence threat to US science
Geoff Brumfiel, Washington
Alarms ring over rules for foreign nationals and ‘sensitive’ equipment.
Proposed changes to an obscure set of export rules could derail US research, say academic and industrial groups, who are now frantically trying to raise the alarm among scientists.
The modified rules would require academic researchers from countries including China and India to obtain a government licence before operating a wide range of lab equipment in the United States. In a 22 April letter to university department chairs, Judy Franz, executive officer of the American Physical Society, warned that the changes constitute a “potential threat to research”. And this week, the National Academies are convening a special workshop to inform scientists of the proposed changes.
At issue is a set of rules governing the export of sensitive technologies. Known as the Export Administration Regulations, the rules are meant to limit the transfer of equipment that could advance the military might of ‘countries of concern’ — a list that includes China, India, Pakistan and Russia. The regulations also require researchers from these countries working with some items of equipment to obtain a licence from the US Department of Commerce.
Traditionally, universities have thought themselves exempt from the regulations. But a March 2004 report from the Department of Commerce’s Office of Inspector General, an independent watchdog, argued that the regulations do apply to academic labs. The report also proposed expanding the criteria under which a licence would be required for using controlled equipment, and applying the rules by country of birth rather than country of citizenship (see Nature 431, 615; 2004).
The 45-page equipment list includes common lab apparatus such as lasers and sealed glove boxes for handling hazardous material. Getting a licence for each potential user would overwhelm lab supervisors, warns Dan Mote, president of the University of Maryland, who is scheduled to talk at a National Academies workshop. “This really is potentially devastating,” he says. “It’s quite conceivable that this would just bring work to a halt.”
Industry is also concerned, according to Cynthia Johnson, director of government relations for Texas Instruments, a major US semiconductor manufacturer. Although industrial labs already have to comply with the rules, the proposal to base the regulations on a researcher’s country of birth rather than citizenship could alienate fresh talent, she says.
Department of Commerce officials stress that they are still far from making a final decision about how to modify the rules. “What we are doing is seeking input,” says Peter Lichtenbaum, assistant secretary for export administration.
That is why it is important for researchers to weigh in with their objections, says Arthur Bienenstock, a physicist and dean of research and graduate policy at Stanford University in California. “What the Department of Commerce needs is an honest assessment of what it would mean if the inspector-general’s rules were implemented,” he says. The comment period closes on 27 May
Nature 435, 4 (5 May 2005).

Yeah! Let’s demolish the research universities! Yeah!
And of course, today, in Kansas, even Todo is spinning in his grave as the Kansas State Board of Education seems to be unaware that there are vast legions of scientists out there who are extending their lives by developing drugs whose validity across species is explicitly searched for using the theory of evolution. Instead they choose to call hearings which are boycotted by scientists and say such amazing things as

“It’s intellectually stimulating,” said board Chairman Steve Abrams, of Arkansas City, one of the three presiding members. “It’s good information.”

Oh, and one more thing. If I see the theory of evolution called the theory of the origin of life one more time, I’m simply, well, I’m simply going to explode.

The History of My Brain

The brain is a remarkable computational device (not material? bah. get your faith out of my office.) A rough estimate of the computational power needed to simulate the brain’s neural power is around a billion MIPs (millions of instructions per second.) When I was growing up, I was fascinated by the possibilities of artificial intelligence. In fact, this forms the basis of my three ways to do theoretical physics:

  1. Do it yourself. This requires lots of work and the ego to believe you can actually figure things out. The benefit is that you can perhaps contribute now. Unfortunately, I don’t believe that this is a long term solution to doing theoretical physics (see 2 and 3)
  2. Build a computer to do it for you. Or build a computer to speed up certain functions in your brain. How long before we can build computers with vastly greater ability than our mushy brains? Are our brains really operating at some optimal limit for computation? For number crunching tasks, most definitely not. This solution seems to me the much more realistic long term way to contribute to theoretical physics. Of course, you may not get the credit for any of this. The computer that did all the work will surely the lions share of the credit. Can a computer win the Nobel prize?
  3. Join the Search for Extraterrestrial Intelligence (SETI). The theory here is that if we discover intelligent alliens they will more than likely be more advanced that we are. Thus they will have used 1 and 2 to have learned vastly more about theoretical physics than we currently know. So if you join SETI and SETI succeeds, you will just be able to ask the aliens about advanced theoretical physics. Of course, this assumes that the aliens are nice and not bug-like (because as every fan of sci-fi knows, bug-like aliens are all about killing fleshy humans.)

But back to the topic at hand: simulating the human brain. One problem with an analysis that just looks at the raw computational speed of the human brain is that it disregards the computational complexity inherit in the structure of the brain itself. In particular, the brain is the product of 500 million plus years of evolution (I want to start counting from at least some ancestor which had some sort of nervous system). So the question I’ve always found fascinating is how large this overhead of so many years of evolution costs in producing the structure of the brain? Do we need to simulate all 500 million plus years of evolution, yielding a computational power far beyond even our best projections of the computational power of the brain? This is particularly troublesome when you think about the power of evolution: our ancestors have been roaming around the landscape of possible brains for a long long time. A counter to this is the idea that we don’t need to simulate all of the evolution, but only the developemental biology which leads to a full grown human. This later point of view seems less computationally challenging, but still daunting. And I’ll bet that this is the computational hangup for simulating human intelligence: not the raw power of the brain, the but the power to reproduce the developement of the brain. I wonder if anyone has done any rough calculations on the computatonal power needed for this latter task.
As I said, when I was growing up, I was fascinated by the possibility of advanced computer intelligences. I can still remember the frustration of not being able to produce intelligence on my TRS-80 Color Computer II. So I left those dreams behind me, but I promised myself that if I ever thought computers were powerful enough to really start producing intelligence I would return to the field. I guess you shouldn’t be surprised, then, if in thirty years you find me hacking away in some dark basement beside a machine named “Newton.”

The Return of Speed

In Santa Fe, there was nothing quite so painful as going to get a croissant and coffee in the morning only to watch as fifteen minutes was forever lost from my life. Even after I learned that giving exact change would shorten my wait by at least two minutes, the sheer slowness was pretty painful. Which is why it is so wonderful to be back in a university town. Especially a university town in a city. Because the beautiful thing about both of these two settings is the absolute speed with which getting my morning breakfast is achieved. Wam! Bam! Here’s your food! I love it! I’ve even noticed that I’m out of shape in getting my money ready so fast. I’d better practice getting my wallet out faster. Ahhhh….life among the young’uns makes me happy.

Unconventional Convention

Via the Preposterous Universe (must resist bad words about the University of Chicago for denying Sean Carroll tenure) comes the announcement of The Time Traveler Convention to be held at MIT. If anyone sees me there, could they please send me an email and tell me about it? Because I’m in Seattle, and if I do show up at MIT, then this clear means that I invented a time machine. And if this is true, I’ve got a lot of thinking to do about flux capacitors.

Did We Overgeneralize to the Hidden Subgroup Problem?

The most famous problem in quantum computing is the hidden subgroup problem. In the hidden subgroup problem you are given access to an oracle which computers a function f. This function is a function from a group G to some set with a promise on the function. The promise is that f is constant and distinct on left cosets of some subgroup H of G. The goal of the hidden subgroup problem is, by querring the function, to determine a generating set for the subgroup H. We say that an algorithm for the hidden subgroup problem is efficient if it uses resources proportional to a polynomial in the logarithm of the size of the group.
The reason the hidden subgroup problem is famous is threefold. The first reason is that when G is Abelian, efficiently solving the hidden subgroup problem leads to an efficient algorithm for factoring integers and for the discrete logarithm problem, i.e. to Shor’s algorithm(s). The second reason is that efficiently solving the hidden subgroup problem when G is the symmetric group would lead to an efficient algorithm for the graph isomorphism problem. The third reason is that efficiently solving the hidden subgroup problem when G is the dihedral group would lead to an efficient algorithm for certain shortest vector in a lattice problems. The first of these reasons is a concrete reason: a quantum algorithm worked! But for the second and third, no efficient quantum algorithm is known.
Now what I find interesting, is that for the second of these reasons, for graph isomorphism, one can get by with solving a much more restricted version of the hidden subgroup problem than the full hidden subgroup problem over the symmetric group. The way to do this is to modify the problem to a problem I call the hidden subgroup conjugacy problem. Call two subgroups, H and K conjugate to each other if there exists an element g of the group G such that gHg^{-1}=K. In the hidden subgroup conjugacy problem, instead of identifying the subgroup (by returning a set of generators, for example) we require that you only identify which conjugacy the subgroup belongs to, i.e. the setup is the same: you are given an f which hides a subgroup H, but now instead of identifying the subgroup you only want to know which conjugacy class the subgroup belongs to. It is easy to see that for the Ableian case, this reduces to the hidden subgroup problem: gHg^{-1}=H for all g in this case. For graph isomorphism, the standard reduction to the hidden subgroup problem reduces to distinguishing between the subgroup being a trivial subgroup and the subgroup being a order two subgroup. So efficiently solving the hidden subgroup conjugacy problem would lead to an efficient algorithm for graph isomorphism. Interesting, the same does not seem to be true for the reduction from the hidden subgroup to certain shortest vector in a lattice problems, although I haven’t thought hard about this.
So the question I ask is, did we overgeneralize the hidden subgroup problem? Did we generalize ourselves into a problem which is just too hard, while efficiently solving a smaller variant would lead to interesting new quantum algorithms? I leave history to judge.

Seattlite

Sounds a bit like “satellite”, doesn’t it? Well, I made it to the big city of Seattle. My original route had to take a bit of a detour because I-80 was shut down in Wyoming due to snow storms. So instead I had to detour through Colorado where it snowed on me. Not that I got out of the car, except at gas stations.

Adios

Goodbye Santa Fe.
Tomorrow I head for the hills. Well actually I go around the hills at first and then over some hills and then over some more hills, and, well you get the picture.
I will miss green chiles, the “speculation” section at Borders, crystals with magical magical powers, the high mountain air, the aspin groves in fall, the good scientists at the Santa Fe Institute, tea time at the Institute, the convenient and terrific skiing, and the beautiful vistas of New Mexico.
I will not miss the running of red lights, the roads, crystals with magical magical powers, the hour long drive to 7a.m. flights in Albuquerque, and most of all, the fact that every metalic object I touch in this state gives me a nasty shock.

Bound Secrecy

One of the most fascinating early endeavours in quantum information theory was the discovery that pure bipartite quantum entanglement is a quantifiable resource. Thus, for instance, one can take many copies of the standard currency for bipartite pure entanglement, the singlet state, and create many copies of any other non-maximally entangled bipartite pure state. Similarly one can take many copies of a non-maximally entangled bipartite pure state and distill out copies of a singlet. The rates of these conversion processes is quantified by the Shannon entropy of one half of the non-maximally entangled state.
The situation, however, for mixed states is different. Here we find that there are states for which no pure entanglement can be distilled, but these mixed states are in fact entangled. These states are called bound entangled states because they require some pure entanglement in order to create them (thus the entanglement is bound into the mixed state.) Bound entangled states are strange beasts, being entangled, and yet not being able to be converted back to any sort of pure state entanglement currency.
One interesting use of a standard currency for bipartite pure state entanglement is in key generation. In these protocols, Alice and Bob distill noisy quantum states to obtain pure entangled states of some standard currency which can then be used to share a private key. Since an essential part of these protocols has been to distill pure entangled states, it seems, when you first think about it, that bound entangled states would not be useful for private key generation. However, this turns out to not be correct! Karol Horodecki, Michal Horodecki, Pawel Horodecki and Jonathan Oppenheim have shown (PRL 094, 160502 (2005), quant-ph/0309110) that one can obtain a secure key from bound entangled states! So, while bound entangled states often don’t like your standard non-bound entangled states, it turns out that for secret key generation, they are useful.

Talks

I’m beginning the process of putting my powerpoint talks online in powerpoint and html format. The first one is up and can be accessed by clicking on the cute little talks tab above. Or by clicking here

Weekend Wedding

Last weekend I went to a wedding in Redondo Beach for my friends Mel and West who I’ve known since my days back at Caltech. As you can guess, the maturity level of a group of Techers is very high:
Idiots
Here we see my friend Lon and I playing with our food. Note that I grabbed an orange, while Lon grabbed a lemon. Poor Lon.
Here is a picture of my rental car being towed because I lost the key to the car.
Dave Is An Idiot
Note that during that Bachelor party for this wedding I lost my cell phone and my drivers license.
If you decide to stop reading this blog because of the above damning information, I don’t blame you.