unglorious problems in quantum information

Along the lines of Scott's 10 annoying problems in quantum information (now happily only 8), I have a handful related to universal gate families.

1. Let V be an imprimitive gate in U(d²), meaning that it cannot be written as a product of two gates in U(d). We know that V and V^-1, together with U(d) x U(d) (i.e. all local gates), can exactly generate all of U(d²) [quant-ph/0108062]. But if we don't have access to V^-1 then we only know how to approximate all of U(d²). Without the subgroup structure, general tools like quant-ph/0209113 can't be used. This is clearly an absurd situation, but show me the simple proof that V and U(d)xU(d) are exactly universal (which remarkably, I could actually make use of in a proof) and I'll agree that I'm being dumb.
2. Does the Solovay-Kitaev theorem still hold if we aren't given inverses? Obviously, yes, but can we prove it? Even without giving an efficient construction of the approximating sequence?
3. Some univeral gate families (e.g. (1 +- 2 i \sigma_j)/sqrt(5) where j ranges over x,y,z) have the property that a sequence of length O(log 1/eps) can approximate any gate to within accuracy eps. This matches the Omega(log 1/eps) bound from counting epsilon-balls. Does the O(log 1/eps) upper bound hold for all universal gate families? Solovay-Kitaev only guarantees O(log^(3+o(1)) 1/eps) sequence length, but it probably makes the sequences longer than it has to by requiring that everything be poly-time.

This last one is actually something that real mathematicians have considered, but not solved. But the first two I'm almost too embarassed to ask them! I mean, come on, people: we can pull this together.

A different sort of unglorious problem is the kind that someone else has solved, but couldn't be bothered to write up. Watch this space later for Shor's construction of higher-accuracy embezzling states and Kitaev's O(t) quantum communication simulation of e^{-itZZ}. Or more realistically you could corner me or Debbie at a conference some time and ask for an explanation.

automatic 401k enrollment

[This post starts slow, but the interesting point is at the end.] 401K's are a great deal (employer matching funds, tax-free interest), and make sense for pretty much everyone who's not completely desperate for cash. But people don't take them very often (40% of low-income workers, 50% of workers in their 20's). And it's probably not (just) because people don't want to save; it's more that they're paralyzed by inertia and having too many choices. This is evidenced by the fact that when people are enrolled by default in 401k's, most people (like 80%) stay enrolled and continue making whatever the default contribution is. (The sheep-like trust here reminds of this English guy I met who doesn't wash vegetables because "if they had toxic chemicals on them, the store wouldn't be selling them to us.")

Recently a new bill made it easier for employers to automatically enroll their employees in 401k's mostly by shielding them from lawsuits if the investments don't perform well. According to marketplace

[Harvard retirement scholar Brigitte Mandrian] expects more employers will migrate to automatic 401k enrollment. But slowly, cuz it's pricey. More employee savings means more matching funds from their bosses.

This is the weird part. Employers are doing something which costs them money, and, though it helps their employees, it only helps the employees who didn't really care about the benefit they're getting. The people who are excited about getting 401k's are probably the ones who'll enroll even if it's not the default. Could it be that the companies really do care about the welfare of their employees? Explaining Safelite Auto Glass's decision to automatically sign up their employees to invest 2% of their pay (matched by the company), Brenda Downing says:

We had a significant number of associates not saving at all. We were concerned they weren't going to be OK at the time they retired.

Is corporate benevolence really the only answer here? This is making my head hurt.

no seriously, don't profile

Sarcasm may have obscured the point of the last post. Profiling makes even less sense against organized terrorists than against criminals. Why? The age/ethnic mix of terrorists that we see now is in part a reaction to the security that they'll face. If young men are always searched then female suicide bombers will be recruited, and the defenses will be worse off than if they screened passengers randomly. This isn't just a game theory exercise:

On April 17 1986, a young woman presented herself at Heathrow's gate 23 for that morning's El Al flight to Tel Aviv. She had cleared the airport's own security check-in procedures, but to El Al's security staff something didn't appear right. A search of her hand luggage revealed 1½ ounces of Semtex and a detonator, hidden in a calculator.

The young woman was Anne Murphy, a white, Catholic girl from Dublin. The explosives had been planted by her boyfriend, Nezar Hindawi, a terrorist with links to the Syrian government.

Of course, I'm starting to give the impression that we should worry about terrorism, when in fact doing so has surpassed the war on drugs as one of the worst acts of collective hysteria since McCarthyism. For example, think of dying prematurely as an enormous waste of time (like reading blogs! but worse.) The average adult has about 300,000 hours of waking life to expect, and a 1 in 13,000,000 chance of dying on the average U.S. domestic flight (this was true in 1990-1999 entirely from accidents, and in 2000-present almost entirely from 9/11, as there's been only one fatal accident during that time. Your chance of dying on a developing world flight is 1 in 1.5 million, regardless of carrier. These and other fascinating facts found here). If you're risk-neutral, avoiding this risk should be worth two minutes of your time. By this argument, two minutes is also a good baseline for the amount of time that airport security should be willing to waste per passenger. The last point is the crudest part of the argument and shouldn't be stretched too far, since it's based on the risks we currently see, which might change in the extreme case of airports completely eliminating screening. Needless to say, I think we're far from that point. (Incidentally, google for probability terrorism dying to see how a little math knowledge can be an upsetting thing.)

The time vs. death comparison seems a generally useful one because it avoids all the problems in comparing lives with money. Another place it's obviously relevant is in speeding. The probability of dying while driving is supposedly proportional to the fourth power of your speed. In the U.S., drivers die at a rate of about 15 per billion miles and are seriously injured at about 10 times that rate. If we assume the fourth-power law and that everyone is driving 65mph (assume a spherical cow...), then increasing speed by 1mph will save 0.84 seconds/mile and increase the chance of being killed/mile by about 9.2 x 10^-10. Multiply by 300,000 hours and you get just about one second, which is pretty close to the amount of time saved. To account for injury, one method is to examine the number of disability-adjusted life years (DALY's) lost. In 2002, 1.18 million died in traffic accidents and 38.4 DALY's were lost, which comes to about 33 DALY's/death. This means my "50 years/death" was an overestimate and increasing 1mph actually costs closer to 0.65 "disability-adjusted life seconds"/mile. Even if we assume there's another car involved half the time, this is close to a tie, meaning that 65mph is close to optimal. On the other hand, this still hasn't included property damage (which ranges from 1% of GNP in developing countries to a stunning 2% in rich countries), higher gas consumption and the fact that speeding tickets waste time too. So I think this means that

1. we shouldn't speed Moderate speeding is a little dangerous, but not unreasonably so.
2. Applying the 300,000 hours argument to airline security can't be totally absurd since it leads to different conclusions in different contexts.
3. I should stop wasting so much time writing silly blog posts.

p.s. I look forward to Ilya's theory of driver safety profiling in the comments!

Update: Thanks to Aaron in the comments for pointing out mistakes in my driving calculations (now corrected); I had represented driving as 10 times more dangerous than it actually is.

terrorist profiling

People get all worked up about this idea, but think about the benefits:

• People spend on average less time in line.
• Terrorists get caught more often.

Of course some people will get unnecessarily searched, but that's happening already! And just think of the absurdity of the status quo, when airport screeners waste their time searching uneducated young men and aren't left with enough time to catch the older, more educated, threat.

Suicide bombers who are older — in their late 20’s and early 30’s — and better educated are less likely to be caught on their missions and are more likely to kill large numbers of people at bigger, more difficult targets than younger and more poorly educated bombers.

... Whereas typical bombers were younger than 21 and about 18 percent of them had at least some college education, the average age of the most successful bombers was almost 26 and 60 percent of them were college educated.

Experience and education also affect the chances of being caught. Every additional year of age reduces the chance by 12 percent. Having more than a high school education cuts the chance by more than half.

There are many examples where young or uneducated terrorists made stupid mistakes that foiled them. Professor Benmelech recounts the case last April of a teenager from Nablus apprehended by Israeli soldiers before carrying out his bombing because he was wearing an overcoat on a 95-degree day. Mr. Reid, the failed shoe bomber, had only a high school degree. Would an older terrorist with more education have tried to light a match on his shoe (as Mr. Reid did) in plain view of the flight attendant and other passengers who proceeded to thwart his plan? Would a better-educated terrorist have been more discreet? We will never know.

The research suggests, however, that there may be a reason that the average age of the 9/11 hijackers (at least the ones for whom we have a birth date) was close to 26 and that the supposed leader, Mohammed Atta, was 33 with a graduate degree.

The solution is simple. Passports could be linked to electronic education records and every year of education could increase the expected length of screening by an extra 12%. Liberals will whine about unfair treatment, but winning the war on terror is about being effective, not pleasing a few politically-influential constituencies.