Month: February 2005

Note: Please pass word of this program on to anyone you think may be interested:
http://www.qinfo.org/people/nielsen/blog/archive/000180.html

The theoretical Quantum Information Science group at the University of Queensland is inviting expressions of interest from graduate students and early career researchers (up to eight years out of PhD) interested in visiting the group for 3-5 weeks during 2005.

About the group: The Quantum Information Science group currently has four faculty members (Andrew Doherty, Gerard Milburn, Michael Nielsen, Tim Ralph), 5 postdocs, and 14 PhD students. Group members collaborate closely with the experimental groups of Andrew White (quantum technology lab) and Halina Rubinsztein-Dunlop (BEC and quantum dots), the theoretical condensed matter group of Ross McKenzie, and the Queensland node of the Centre of Excellence for Quantum and Atom Optics. Fellows will be encouraged to interact broadly during their visit.

Duration: Fellowships will normally last for three to five weeks.

Background of Fellows

Graduate Students: Fellows will be currently working towards a PhD in quantum information science or a closely related field.

Early Career Researchers: Fellows should have a strong interest in quantum information science, but in some instances their background may be primarily in other areas of science, e.g., control theory, pure mathematics, theoretical computer science, condensed matter physics, quantum optics, high-energy physics, or other fields with a potential to contribute to the group.

We encourage applications from potential Fellows in all areas of science (computer science, mathematics, physics, engineering, chemistry) relevant to quantum information science.

Time: We aim to spread the Fellows out during 2005. For this reason, we ask that applicants think seriously about what dates they would be available to take up the Fellowship, and indicate those dates on the expression of interest.

Number: Up to 20 Fellowships will be awarded in 2005, 10 to graduate students, and 10 to early career researchers. The initial round of applications will be due March 18; depending on the quality and number of applications a further round may be held later in the year.

Benefits: The Fellowship will cover: the cost of a return economy class airfare by the most direct route from the recipient’s home institution to Brisbane, Australia; the cost of accommodation while in Brisbane; and the cost of transport to and from the airport. Please note that no salary or stipend will be provided.

Research seminar: Fellows will be asked to present a 40 minute whiteboard seminar about their ongoing research.

Tutorial lectures: Fellows will be asked to present a series of 2-4 tutorial lectures on some topic they nominate, for presentation at an informal whiteboard seminar series. These could come from a very wide range of areas, and would not be restricted to quantum information science. The following list of examples is simply meant to be suggestive: applicants should ask themselves what specialist knowledge they have that might be of interest to others.

• Computer science: The status of the P versus NP problem; pseudorandom generators; derandomization; expander graphs; Markov chain Monte Carlo; PCP.
• Control theory: open loop control; feedback control; complete controllability; Pontryagin maximum principle; Bellman equation.
• Mathematics: topics in advanced linear algebra; Lie groups; Hopf algebras; quantum groups.
• Complex systems: small worlds; network theory; self-organized criticality; information markets.
• Condensed matter physics: quantum Hall effect; Bose-Einstein condensation; Mott insulater phase transition; superfluidity; superconductivity; high-temperature superconductivity; quantum phase transitions in general.
• Other area: Virtually any well-presented topic in any area of fundamental interest in computer science, mathematics and physics will be well-received.

Expression of interest

Please cut and paste the following into email, fill it out, and send to Michael Nielsen at: nielsen at physics dot uq dot edu dot au with the subject “Visiting Fellowship application”. Applications must be received by March 18 to be eligible; late applications will not be accepted.

Name:

Current position:

Supervisor (for grad student):

Thesis topic (for grad student):

Institution:

Current interests:

Past interests:

List up to three papers you’ve published in the past three years:

Desired duration of visit (3-5 weeks):

Dates you would able to visit (between April 15 and December 31, 2005):

Examples of three topics you’d be willing to give a short series (2-4) of tutorial seminars on. Note that this list is not binding; it’s simply meant to indicate the range of your expertise:

The quantum information group at the University of Queensland has a new website, developed by Peter Rohde. One of the features of the site is to mix a blog format with more traditional static content, to reflect both what’s currently going on (seminars, visitors, workshops) with more timeless information about the group.

There�s been a lot of fuss within the blogosphere and the US media about comments made by Harvard President Larry Summers, about women and academia.

I�m not going to comment directly on that here, as all that I have to say has been said much better elsewhere. In particular, Sean Caroll has an excellent post (scroll down to the post “Sex and Science!”) on the subject.

What I want to talk about in this post is a pitfall in the way much of the broader online discussion has been framed.

In describing this pitfall I am to a large extent preaching to the choir� I expect most of my readers understand perfectly well what I�m about to say. I�m writing it, then, simply because I think it is relevant both to the Summers incident, and to many other public discussions, and because it�s evident that too many of the people involved in public debate either aren�t aware of this problem, or have simply forgotten it.

(A secondary reason, as with much of my writing, is to clarify the thoughts in my own head!)

A lot of the discussion about the Summers incident has focused on the question �Are women intrinsically better / worse than men in academic job roles?�, and variants thereof.

Now what exactly does that question mean?

In fact, it can mean many different things to different people. My guess is that when most people say that, they�re thinking (at least vaguely) in terms of some simple underlying model.

Let me give an example of what I mean by an �underlying model�. It�s a mathematical model, but it�s a very simple one, so even if you�re not mathematically inclined, please bear with me: the point will (I hope) be clear anyways.

In this model each person has an �intrinsic ability for academia�, a point score (between 1 and 100, say).

The Male population has some distribution (say, Gaussian) with a mean M and a standard deviation S.

The Female population has some distribution (again, Gaussian) with a mean F and the same standard deviation S.

What I think many people implicitly have in mind when they use phrases like �men are better suited than women for academic jobs� is that M > F, i.e., that men are on average better than women.

When phrased in these quantitative terms, though, you quickly see a problem.

The problem arises when you make the model just a tiny bit more complicated � and probably more realistic.

Let�s suppose in the revised model we still have Gaussian distributions, with the male mean M = 50 and the female mean F = 48, so men are �better� (on average) than women.

(Disclaimer: I�ve chosen those numbers ad hoc as representative of the hypothesis many people have put forward online, not because I believe that men are on average better than women.)

But suppose the standard deviations for the two populations are not the same. Suppose instead that the male standard deviation is 10 points, and the female standard deviation is 12.

If the median Harvard Faculty member needs a score of 80 points, then there will be many more women with the requisite ability than men, even though, on average, men have a higher points score.

It gets more complicated.

Suppose instead that you consider a local community college, where the median Faculty score is (say) 58. In that case, more men than women will have the ability to be on the Faculty at the community college, but more women than men will have the ability to be on the Faculty at Harvard.

All of a sudden whether you say �men are more suited than women to academia� depends an awful lot on how you define �academia�. More importantly, the conclusions you draw about policy may depend on other value judgements that you might have thought were unrelated to the original question: like whether it�s more important to foster community colleges or elite research Universities like Harvard.

In fact, it�s even worse than that. Both my models are ridiculously oversimplified � even though I�ve argued that my second model is probably a good bit better than what some people are using. You can�t quantify this kind of thing with a single score, we don�t have Gaussian populations, and so on. Real life will be much more complicated than even my second model suggests.

The problem I�m pointing out is several-fold, and it applied to lots of public discussion, not just of intrinsic differences between men and women, but of other topics.

First, underlying many such discussions are implicit models which are rarely if ever articulated. Indeed, people often don�t realize that they�re working off such implicit models � usually vaguely defined, vastly oversimplified models � rather than reality. This can lead to all sorts of mistakes and omissions.

Second, there tends to be a lot of variation in what models different people believe. This can lead even parties of good faith to have trouble understanding one another (much less coming to agreement), especially if they don�t understand that such differences are possible. People (and I’m certainly guilty)have a disturbing tendency to confuse their models with reality.

What�s the point of all this? It isn�t that every time some question like this comes up, we should all spend our time writing down mathematical models, comparing their various merits, and so on, or that the key is to have the “right model” or anything like that.

The point is simply to remember that public discussion is carried on using implicit models of this type. Unless we are aware of the existence of those models, and the difficulties they can cause, both due to miscommunication and due to mistakes arising from confusing models with reality, having a productive substantive discussion about any contentious issue is extremely difficult.

One final comment. It’s hard not to give the impression in this post that �of course, I�d never do such a silly thing�. Of course, I would, although I hope I�d catch myself at least some of the time. However, if you want an amusing (and sobering) example along similar lines, involving a physicist and an economist, see the first few pages of Dietrich Dorner�s excellent book “The Logic of Failure”. You can actually read the passage in question by using amazon.com�s �Search Inside this Book� feature, and searching for �physicist�; you�ll find an entry point to the Front matter, which is where you want to be. More generally, Dorner�s book makes a pretty compelling case that we all make mistakes like this all the time, even in very simple cases.

My major scientific interest for the past few months has been in using ideas from differential geometry to develop insight into quantum computation. I’ve just posted a paper (pdf) at the preprint archive on the subject. This post is a somewhat technical overview of what’s done in the paper. The post will, I hope, make a fair bit of sense to people who know something about the technical details of quantum computation, but latter parts will be hard going for other people.

I’ve also posted a talk (Powerpoint) I gave a couple of weeks ago on the subject.

Update (2005/02/19): Some typos in my talk fixed, with thanks to Wim van Dam.

One of the most notoriously difficult problems in computation, either quantum or classical, is to figure out the minimal circuit that can be used to compute some function.

Even the easier problem of proving a lower bound on the size of the minimal circuit seems to be intractable for most interesting functions – this is why famous problems like P vs. NP are so hard.

Inspired by geometric control theory and ideas from Riemannian and Finsler geometry, I’ve been spendng my time trying to develop a general approach to the proof of lower bounds on circuit size.

The technical details are lengthy, but the basic motivating ideas are fairly simple.

The starting point is the observation that what we’re really trying to do is minimize a function (number of gates) over the space of quantum circuits computing the desired function.

As any high school maths student can tell you, minimizing a discrete function like “number of gates” is a heck of a lot harder than minimizing a smooth function, since we can use the powerful tools of the differential calculus to solve the latter problem.

The first thing done in the paper is therefore to replace the discrete problem of finding a minimizing quantum circuit by a more smoothly formulated problem, which I call the Hamiltonian control problem. Basically, we embed the (discrete) circuit optimization problem inside a smoothed version which lets us use the tools of the calculus.

This smoothed problem turns out to be essentially a problem of finding “shortest paths” on some suitable geometric space, in this case, the space of n-qubit unitary operations.

The upshot is that we can get a lower bound on the minimal circuit size by computing the length of the minimal geodesic between the desired unitary quantm computation, U, and the identity operation, I, where length is defined by some suitable metric structure.

(An interesting technical point is that the right type of metric structure to use is a so-called Finsler metric structure, which generalizes the Riemannian metrics familiar to physicists by replacing quadratic forms by a more general norm function.)

Now the calculus comes into play. By using the calculus of variations, it’s possible to derive a second order differential equation (the “geodesic equation”) describing the geodesics of the metric. Because the geodesic equation is second order, once an initial position and velocity are set, the remainder of the geodesic is completely determined.

This is in sharp contrast with the usual case in circuit design, either classical or quantum, where being given part of an optimal circuit does not obviously assist in the design of the rest of the circuit.

This contrast makes me think this approach is really worth pursuing as an approach to quantum circuit lower bounds.

That’s the broad conceptual picture of the program. I’ve also made some technical progress on implementing the program, which I won’t try to describe here, beyond quoting the second half of the abstract:

In this paper we construct several Finsler metrics whose minimal length geodesics provide lower bounds on quantum circuit size, and give a procedure to compute the corresponding geodesic equation. We also construct a large class of solutions to the geodesic equation, which we call Pauli geodesics, since they arise from isometries generated by the Pauli group. For any unitary U diagonal in the computational basis, we show that: (a) provided the minimal length geodesic is unique, it must be a Pauli geodesic; (b) finding the length of the minimal Pauli geodesic passing from I to U is equivalent to solving an exponential size instance of the closest vector in a lattice problem (CVP); and (c) all but a doubly exponentially small fraction of such unitaries have minimal Pauli geodesics of exponential length.

Improved version of an earlier post, which received lots of excellent feedback. Thanks in particular to commenters Wim van Dam, Gonzalo Frasca, Nick Gray, Aram Harrow, and blogger Susan Mernit for their thoughts, which have helped inspire the present update.

Optimizing travel 2.0

Most researchers travel a lot, and I�m no exception. Recently, I�ve been collecting tips to optimize my travel. Nothing incredibly insightful, but the gradual accumulation of small but consistently applied habits has made a big difference to my travel.

I�ve collected the tips here as a way of forcing myself to systematize them, in the hope of providing something useful to other people, and in the hope of hearing some other tips in comments!

Many of the tips are obvious. Frankly, some probably appear pedantic or obsessive, but I�m of the opinion that every little thing you can do to improve travel is worth doing. I should also admit that I don�t (yet) do all of these things consistently, but I�m getting pretty close; since I started on this, I�ve greatly reduced the effects of jetlag, and am generally a happier traveler.

Your mileage may, of course, vary.

The original motivation that got me to think systematically about this was a particularly bad trip I had in August of 2004. On that trip I was jetlagged for an entire weeklong conference, which I may as well not have attended, since I spent most of the conference time sleeping in my hotel room. This was a particular pity, as the relatively few talks I did manage to attend were unusually good.

At home

Buy at least one large or extra battery to enable longer laptop use on the plane.

Buy a collection of travel adaptors which will enable you to plug in anywhere.

Put together a travel drawer at home. This contains foreign money collected on earlier trips (one envelope per currency), passport, travel adaptors so I can plug in my laptop elsewhere, phone line, ethernet cable, remote mouse for presentations, the checklists mentioned below, and any other specialized equipment � it�s handy to buy miniature versions of various things (toothpaste, laptop adaptor, and so on), in order to minimize luggage.

Try out some different types of earplugs, and when you�ve found some you like, buy a large supply of high quality earplugs. I find these extremely helpful for sleeping on planes. (Some people like noise-cancelling headphones. I find them okay, but prefer earplugs.)

Join the Qantas club or equivalent. This provides access to Qantas and partner lounges all over the world. Most significantly, this means access to showers and good quality chairs while connecting, as well as faster checkin. It�s usually not available, but some lounges will have a massage service, which I find helps significantly with recovery at the end of the flight.

Booking flights

Construct a list of standard routes and flight times that work best for you, and request those. To be effective, you need to either memorize the list, or file it in a location very easily accessible (< 30 seconds) from where you or your assistant make travel bookings. Have a list of preferred carriers you specifically request. Mine are Qantas, American, and British Airways. I fly Qantas mostly, and American and BA give me frequent flyer points on Qantas, which helps me upgrade to business class. Another advantage is that most carriers (Qantas included) have different classes of frequent flyer (bronze, silver, gold and platinum, in Qantas� case), and all sorts of nice effects start to kick in as you move up the classes. My preferred seats are forward in the plane, on the right hand side (get off faster), window seat (people don�t climb over you when you�re asleep), exit row or bulkhead. Having exit row or bulkhead seats is particularly important, as most aeroplane seats are sufficiently small that it�s very difficult to use a laptop onboard unless you�re in an exit or bulkhead (or business). The exception seems to be American Airlines, who have extra legroom, which is another reason I prefer them. (Unfortunately, their checkin service in LA is appalling, which counts heavily against them.) Frequent flyers can set up seating preferences which are then applied automatically to every trip.

Preparing for the trip

Create a checklist for choosing a hotel, and make sure it is easily available (< 30 seconds) from wherever you (or your assistant) expects to be making bookings from. Here�s mine:

• Is the hotel near the conference venue?
• Is there a supermarket nearby, so one can purchase good food to eat during the day?
• Are there kitchen facilities in the hotel rooms?
• Do the hotel rooms have high quality internet access, preferably free wireless?
• Do the hotel rooms have a restaurant on premises? Does it do breakfast?
• Do the hotel rooms have a laundry service?
• Do the hotel rooms have heating and cooling?

  For beating jetlag, I find one of the most important things is to be relaxed. A corollary is that if I�m to speak publicly on a trip, I prefer to speak as early as possible. No matter how well prepared I am, I find anticipation of a public talk creates a little nervous tension. It�s best to get it out of the way, so I can relax. I haven�t done it yet, but in future when speaking at a conference where I expect a lot of jetlag, I plan to ask the organizers if they�d mind scheduling my talk for early on.

  Packing

  Have a checklist. For me this is: passport, tickets, do a ticket check (am I going at the right time?), laptop, pda, keys, remote mouse, phone line, ethernet cable, a generous supply of clothing (I usually find I need more changes than I think � something always gets spilled, or ripped, or whatever), toiletries, mini-umbrella, 4 zip-lock bags, and 4 large plastic bags for dirty laundry and miscellaneous use.

  It�s useful to have an appendix to your checklist where you note additional items that may be required when traveling to specific countries or parts of the world.

  Make sure you can carry all luggage onboard, especially on long flights. It makes it less likely that you�ll miss connections, you won�t lose your luggage, and you�re not carrying huge quantities of stuff around. Most importantly, you�re likely to save about half an hour per connection in waiting time. That doesn�t sound like a lot, but when you�re traveling for 20 or 30 hours, every bit counts.

  If you can�t carry all your luggage onboard, for long flights or flights with multiple connections, make sure you carry at least one change of clothes and some toiletries onboard. That way you can shower and change en route, and even if your luggage gets lost, you�ll be in a much better position at the end of your flight.

  In addition to your one piece of carry-on baggage, most airlines will let you carry on a computer bag of some sort, provided you�re not carrying a handbag; stuff it in your other baggage if you are. Take advantage of this, as it can help substantially in meeting the goal of carrying onboard all your luggage.

  A computer bag also provides an excellent place to store a set of items you�d like easy access to on the plane. They can be stuffed into the seatback in front of you, or, if you�re at a bulkhead, you can put your entire computer bag on the ground beside your feet.

  Departing at the airport

  Buy some water. You�re rarely served enough onboard.

  Buy some healthy snacks to eat onboard.

  Get some foreign currency. It�s tempting not to, as you can usually get by without it, but it�s usually useful to have at least a couple of hundred dollars for emergencies.

  En route

  When you get on the plane, get rid of all the material out of the seat pockets in front of you, unless you plan to use it. Shove it in the overhead bin, instead. This is particularly useful if, like me, you have long legs, but even for the shorter-limbed, it�s nice to have that space available to store your own stuff.

  If I�m traveling internationally, I try to get a seat forward on the plane, and I make sure I get quickly to immigration, so at most a few people are ahead of me. With no luggage, I can then go immediately through customs. This sounds like a small thing, but it can save half an hour or more of carrying stuff around, waiting in lines and so on. Your posture (and, in my case, my back) and your temper can fray quite a bit during that time, so it�s well worth the little bit of extra effort.

  Onsite

  Take walks in the morning sun to reset your body clock, and relax.

  Treat yourself well. As tempting as it is to go out late and party, or drink lots, you just make yourself sick, and increase the effects of jetlag. All things in moderation and all that.

  If you�re staying at a hotel that provides complimentary toiletries, collect up any usefull-looking unused items and take them home with you, to store in your travel drawer for use on future trips. After all, the complimentary toiletries come in sizes that are much more convenient for travel than the usual sizes sold in stores.

Comments should be functioning properly again.

Via Lance Fortnow, I learn that Christie’s is auctioning off a bunch of historical documents relating to the history of computing.

One of those documents is a report by von Neumann, Burks and Goldstine on the concept of the computer. It’s expected to fetch up to about 40,000 US dollars.

In 1997 or 1998 I spent a few hours helping clean out some old trailers at the University of New Mexico Physics Department. One of the things I found while doing this was a copy of von Neumann, Burks and Goldstine – a rather ratty old copy, but (I believed) a true reprint of the report, or whatever the correct term was in those days.

I don’t remember what I did with it any more, but I haven’t seen it in many years. I almost certainly threw it out when I moved to Caltech in 1998, figuring that there must be millions of copies floating around…