Paper we finished long ago, in my prior life, and now finally available on the arxiv tubes: Adiabatic Quantum Transistors. My coauthors are saints for their patience.
To Catch Terrorists, Think Quantum Mechanically?
[latexpage]
An interesting paper in PNAS from a few years back that I missed, “Strong profiling is not mathematically optimal for discovering rare malfeasors” by William H. Press.
Suppose you have a large population of people and a single bad guy who you want to catch. You could look through the entire population to find the bad guy, or you could set up checkpoints (err I mean airline security screening areas) to look for people, sampling only some small fraction of the population that goes through the checkpoint. Now, if you don’t know anything about the population you’re sampling, you might as well just sample them randomly until you find your baddie, since you don’t have any other information that could help you.
But suppose that you are able to come up with some prior probabilities for different people to be the bad guy. I.e. you’ve developed a model for what makes someone more likely to be a bad guy, and further assume that this model is really pretty accurate. To each person you can assign a probability $p_i$ that the person is indeed the bad guy. Now you could continue to sample uniformly, but you have this great model that you want to use to help catch the bad guy. What do you do?
It turns out that the wrong thing to do is to sample in proportion to the probability $p_i$. To figure out the correct strategy, suppose that you sample from the population with probability $q_i$. Then if $k$ is your man, the probability that you get him in one sample is $q_k$. Or, another way to say it is that the mean number of screenings you’ll need to find the baddie is $1/q_k$. Assuming your model is correct, the mean number of people you will have to sample is $sum_i p_i/q_i$. So now to calculate the optimum we need to minimize this expression for $q_i$ subject to the constraint that $sum_i q_i =1$.
To calculate this optimum, you use a Lagrange multiplier
$${partial over partial q_j} left[ sum_i {p_i over q_i} + lambda (sum_i q_i -1)right]=0$$
or
$$ – {p_j over q_j^2} + lambda = 0$$
Which, in order to satisfy our contraints (and also positive probabilities) gives us the answer for the optimum of
$$ q_j = { sqrt{p_j} over sum_i sqrt{p_i}}$$
Or, in other words, you should sample proportional to the square root of the probabilities. Pretty cool, a nice easy, yet surprising answer.
Even more awesome is that we got some square roots of probabilities in there. Quantum probability amplitudes are, of course, like square roots of probabilities. Now if only we could massage this into insight into quantum theory. Do it. Or the terrorist win.
Higgs rumors
Some good links:
- rumors via Peter Woit
- Tevatron releases 2.9 sigma analysis, see vista.org
- Intrade at 80 percent odds it will be found
- Nature leaks rumors of 125 GeV
- Nice short answer to consequences of Higgs at 125GeV for minimal supersymmetric models
- The seminar is scheduled for midnight between July 3/4 PST.
Exciting to see what they’ve found, but also what hints about compatibility with the standard model, Whoever named that model was a prophet 🙂
Update 1:14am PST July 4: CERN press release Discovery!
My Voice
What is my voice? Lacking one, I choose pseudo-plagiary (the original, far more illuminating, can be found here):
The other one, the one called Dave Bacon, is the one things happen to. I walk through the halls of Google Seattle and stop for a moment, perhaps mechanically now, to look at the green glow of code from flat screens, and the blocks and arrows on the whiteboard; I know of Dave Bacon from his email and see his name on a list of (former) professors or in another person’s blog. I like Borges, mountains, omphaloskepsis, the taste of chiles and the prose of Pynchon; he shares these preferences, but in a vain way that turns them histrionic. It would be an exaggeration to say that ours is a hostile relationship; I live, let myself go on living, so that Dave Bacon may have contrived his theories, and these theories justifies me. It is no effort for me to confess that he has achieved some valid pages (or more accurately he had great co-authors), but those pages cannot save me, perhaps because what is good belongs to no one, not even to him, but rather to the science and to experiment. Besides, I am destined to perish, definitively, and only some bits of information about myself can survive in him. Little by little, I am giving over everything to him, though I am quite aware of his perverse custom of flipping certain important bits about himself.
Feynman knew that all things change; the electron exchanges a photon with another electron, scattering to a new state. I shall remain in Dave Bacon, not scattered to another person (if it is true that my evolution is unitary), but I recognize myself less in his papers than in many others or in the laborious strumming of a guitar. Years ago I tried to free myself from him and went from the foundations of quantum theory to games correcting quantum computing machines, but those games belong to Dave Bacon now, and I shall have to imagine other things. Thus my life is a flight and I lose everything and everything belongs to oblivion, or to him.
I do not know which of us has written this webpage.
1yr
One year since I left the tower and joined Google. I think it may be time to start blogging again.
IDE Tools for Reading Research Papers?
It’s been over six months I made the jump from quantum computing theory professor at the University of Washington to software engineer at Google. When I hear from my friends back in quantum computing, the second question they ask is, “what’s it like?” (the first question is whether Google wants to build a quantum computer.) There are lots of answers to this question, but what I think is really interesting is not how I feel about the ins and outs of this new career, but what I found the most surprising about the similarities between my new jobs and my old job. And, for me, hands down, the most surprising similarity is between reading papers and reading other peoples code.
Reading a a paper in a new subject area was definitely one of the favorite parts of my old job (and a central skill to being a good researcher.) You’d start out, often, with only a small clue about the subject of the paper. Often you were led to the paper by a search that hit a few keywords, and an abstract that seemed interesting. But after a few pages it often becomes clear that there are all sorts of terms and ideas that you just haven’t seen before. And so you often have to spend some time doing some reading of other papers that contain the terms you don’t understand and see if they help. Mostly they don’t, but sometimes they do and then you can backtrack and figure out some of what the first paper said. This sort of jumping around, at least for me, occurred quite a bit as I’d try to parse a paper, interspread with periods of logical thought and pen and paper verification of calculations.
Reading other peoples code is very similar. At first you start looking at some class, say, and you have some vague idea what it does. Documentation and implicit documentation through naming gives you some idea of what is going on, but quickly you often see the code start calling code that you don’t know how it works or what it exactly does, and so you have to go track down that other class, and then figure it out, and then backtrack. Of course this is often interspread with bits of following the logic of the code. Today, with modern IDE tools, this sort of jumping back and forth becomes a quick habit and makes the process of figuring out someone else’s code significantly easier.
Which got me thinking. Why aren’t there modern tools for reading research documents that provide some of the functionality that is found in IDEs such as Eclipse? Certainly some authors are gracious enough to compile their LaTeX such that their citation data is a link, but this is a long way from having PDFs where you can click on citations in the text and then you get immediately transported to the other paper, maybe even to the particular location in the paper that is relevant. I think the technical challenge here is providing hooks between the documents: how do I make a citation that is more than just citing the full paper (wouldn’t it be nice if you specified the set of ranges of relevant lines in the paper?) There are certainly very cool tools out there now for storing and parsing your scientific papers, but while the implicit linking between these papers is complex, most of this complexity is buried in the [12] citation pater. But maybe solutions for this are already out there? Thoughts?
The Wolf That Cried Education Bubble
“Foster, You’re Dead!” is a Philip K. Dick short story published in 1955 describing the struggle of a young boy, Mike Foster, whose father refuses to purchase his family a bomb shelter. The story describes a classically Dickian society: paranoia over nuclear war so consumes everyone that the purchase of a bomb shelter and participation in a financial plan to provide protection from nuclear war are basic actions that every member of the society is assumed to have to participate in. Mike’s father, who refuses to participate in this hyper-consumeristic cross with the military industrial complex is labeled an “anti-P” and, without giving away too much, the story provides a strikingly empathetic description of Mike and his father’s struggles around their ostracized state. The story is in Second Variety (The Collected Stories of Philip K. Dick, Vol. 3)
One day I saw a newspaper headline reporting that the President suggested that if Americans had to buy their bomb shelters, rather than being provided with them by the government, they’d take better care of them, an idea which made me furious. Logically, each of us should own a submarine, a jet fighter, and so forth.
Which is what got me thinking about tuition.
You see, in a former, quantized life, the rhythms of my life were centered squarely on the academic world. And if you’re in the world of academia in the United States, you most certainly know that college tuition prices have risen over the last few decades at a rate greatly exceeding that of inflation. These rising tuition costs have led to an increasing indebtedness are the part of students, causing some not very famous people and some very famous people to speculate that there is a higher education bubble. Since I made those impetuous comments about there being a higher education bubble, however, I’ve had time to dig around and see what actual data I could find on the subject.
Enter the treasure trove of reports from the delta cost project (for those who want to investigate the bias of this report note it is in part sponsored by the Lumina foundation who has a mission to increase higher education in the United States, along with an interesting enough story behind its founding to set off all you tin hat conspiracy theorists. That’s right you Sn-hatters…set off for somewhere else to post your canned responses!) First off the full reports are a data lovers delight: there’s some good stuff here!
But what I found most interesting, highlighted particularly in the 2009 report, was a question I’ve often wondered about: cost shifting. While it is true that tuition costs are rising, this does not, of course, mean that universities themselves have spending increasing at the same rates. For example at the in the sate of Washington, tuition hikes have been directly tied not to spending costs, per se, but to a declining state revenue. So are spending costs increasing? Page 34 of the report has a great graphic of spending per degree across different kinds of higher education institution:
This shows pretty strikingly that spending has actually remained fairly constant….except at private research institutions. And even more remarkably is the question of how much tuition costs are the result of increased spending:
The primary cause of tuition increases in public institutions is not increased spending, but rather cost shifting to replace losses in state appropriations and other revenues. In public research institutions, 92 percent of revenues from tuition increases since 2002 have resulted from shifts in costs. In other public institutions, costs are declining even as prices are increasing. Private institutions are both raising tuition and increasing spending. Only about 30 percent of revenues from tuition increases in the private research universities can be attributed to cost shifts, though in private master’s and bachelor’s institutions, about 85 percent of tuition are from cost shifts rather than spending increases
Which brings me back to good old Philip K. Dick. Let me get this straight: spending per degree has been basically flat…except among the private institutions. Tuition costs, which everyone is yelling about, have been entirely due to shifting funding at public institutions, while private institutions have increased tuition and spending. So yeah, I do believe Dick had every right to pissed off at his president asking him to shoulder the costs of bomb shelters because people would “take better care of them” if they owned them themselves. As do we have a right to be pissed off at the reckless abandonment of higher education by our state governments, which has led to the regressive burden of tuition increases. Except by the private institutions. Who, if anyone, will once again be responsible for riding the boom that is the bubble of expanded public leverage (and yes I know the private institutions here are mostly “nonprofits”, but having gone to both public and private research universities of some caliber, you can bet your horse I’ve seen which can lay claim to being more egalitarian.)
Now if only I could figure out how to turn this into a short story….
The Wolf That Cried Education Bubble
“Foster, You’re Dead!” is a Philip K. Dick short story published in 1955 describing the struggle of a young boy, Mike Foster, whose father refuses to purchase his family a bomb shelter. The story describes a classically Dickian society: paranoia over nuclear war so consumes everyone that the purchase of a bomb shelter and participation in a financial plan to provide protection from nuclear war are basic actions that every member of the society is assumed to have to participate in. Mike’s father, who refuses to participate in this hyper-consumeristic cross with the military industrial complex is labeled an “anti-P” and, without giving away too much, the story provides a strikingly empathetic description of Mike and his father’s struggles around their ostracized state. The story is in Second Variety (The Collected Stories of Philip K. Dick, Vol. 3)
One day I saw a newspaper headline reporting that the President suggested that if Americans had to buy their bomb shelters, rather than being provided with them by the government, they’d take better care of them, an idea which made me furious. Logically, each of us should own a submarine, a jet fighter, and so forth.
Which is what got me thinking about tuition.
You see, in a former, quantized life, the rhythms of my life were centered squarely on the academic world. And if you’re in the world of academia in the United States, you most certainly know that college tuition prices have risen over the last few decades at a rate greatly exceeding that of inflation. These rising tuition costs have led to an increasing indebtedness are the part of students, causing some not very famous people and some very famous people to speculate that there is a higher education bubble. Since I made those impetuous comments about there being a higher education bubble, however, I’ve had time to dig around and see what actual data I could find on the subject.
Enter the treasure trove of reports from the delta cost project (for those who want to investigate the bias of this report note it is in part sponsored by the Lumina foundation who has a mission to increase higher education in the United States, along with an interesting enough story behind its founding to set off all you tin hat conspiracy theorists. That’s right you Sn-hatters…set off for somewhere else to post your canned responses!) First off the full reports are a data lovers delight: there’s some good stuff here!
But what I found most interesting, highlighted particularly in the 2009 report, was a question I’ve often wondered about: cost shifting. While it is true that tuition costs are rising, this does not, of course, mean that universities themselves have spending increasing at the same rates. For example at the in the sate of Washington, tuition hikes have been directly tied not to spending costs, per se, but to a declining state revenue. So are spending costs increasing? Page 34 of the report has a great graphic of spending per degree across different kinds of higher education institution:
This shows pretty strikingly that spending has actually remained fairly constant….except at private research institutions. And even more remarkably is the question of how much tuition costs are the result of increased spending:
The primary cause of tuition increases in public institutions is not increased spending, but rather cost shifting to replace losses in state appropriations and other revenues. In public research institutions, 92 percent of revenues from tuition increases since 2002 have resulted from shifts in costs. In other public institutions, costs are declining even as prices are increasing. Private institutions are both raising tuition and increasing spending. Only about 30 percent of revenues from tuition increases in the private research universities can be attributed to cost shifts, though in private master’s and bachelor’s institutions, about 85 percent of tuition are from cost shifts rather than spending increases
Which brings me back to good old Philip K. Dick. Let me get this straight: spending per degree has been basically flat…except among the private institutions. Tuition costs, which everyone is yelling about, have been entirely due to shifting funding at public institutions, while private institutions have increased tuition and spending. So yeah, I do believe Dick had every right to pissed off at his president asking him to shoulder the costs of bomb shelters because people would “take better care of them” if they owned them themselves. As do we have a right to be pissed off at the reckless abandonment of higher education by our state governments, which has led to the regressive burden of tuition increases. Except by the private institutions. Who, if anyone, will once again be responsible for riding the boom that is the bubble of expanded public leverage (and yes I know the private institutions here are mostly “nonprofits”, but having gone to both public and private research universities of some caliber, you can bet your horse I’ve seen which can lay claim to being more egalitarian.)
Now if only I could figure out how to turn this into a short story….
A New Start
“Nothing endures but change” – Heraclitus
Pork Tenderloin, Carmelized Pears, Pear-Brandy Sauce
Recipe originally from Epicurious
Ingredients:
- 1 1/4 pounds pork tenderloin, trimmed, cut crosswise into 1-inch-thick slices
- 1/2 stick butter
- 4 firm but ripe large Anjou pears, peeled, halved, cored, cut into 1/3-inch-thick wedges. So far other pears that I’ve made this with don’t work as well as Anjou (Cornice)
- 1 teaspoon sugar
- 1/2 cup chopped shallots
- 1 1/4 teaspoons dried thyme
- 1/4 cup pear eau-de-vie (clear pear brandy)
- 1 cup whipping cream
- 1/3 cup pear nectar
Place pork slices between plastic wrap and pound with mallet to 1/4-inch thick.
Melt 2 tablespoons butter in large nonstick skillet over high heat. Add pears and sugar; sauté until pears are tender and deep golden, about 8 minutes.
Melt 1 tablespoon butter in another large nonstick skillet over high heat. Season pork with salt and pepper. Working in batches, add pork to skillet; sauté just until cooked through, about 2 minutes per side. Transfer to plate. Cover. Reduce heat to medium. Melt 1 tablespoon butter in same skillet. Add shallots and thyme; sauté 2 minutes. Add eau-de-vie; boil until reduced to glaze, scraping up any browned bits, about 2 minutes. Add cream and pear nectar; boil until thickened to sauce consistency, about 5 minutes. Season with salt and pepper.
Reheat pears if necessary. Spoon into center of platter. Arrange pork around pears. Pour sauce over pork.