Where even the sun pulls all-nighters

Who: From left, Ashwin Nayak, Debbie Leung, Mike Mosca, your humble squinting blogger, Andris Ambainis with coffee, Patrick Hayden.

Where: Haines Junction (population 789), Yukon Territory, 100 miles east of Alaska. One of the furthest outposts of civilization, surrounded by one of the last pristine wilderness areas on Earth.

When: We arrived here last night, after flying to Whitehorse and then battling heavy traffic (i.e., at least two other cars) for several hours on the Alaska Highway.

Why: I dunno, I guess the CIAR has more money than it knows what to do with.

How: You thought they wouldn’t have WiFi here?

6 Responses to “Where even the sun pulls all-nighters”

1. Anonymous Says:

so umm are you technically out in the middle of nowhere? and why would ciac host such a thing out in the middle of nowhere?

2. Scott Says:

so umm are you technically out in the middle of nowhere?

Yes.

and why would ciac host such a thing out in the middle of nowhere?

I don’t know. But I’m not complaining.

3. Anonymous Says:

Sorry for posting off topic, but it could take centuries before Scott posts on technical subjects again :})
QC Programming Puzzler

R.R. Tucci

4. Scott Says:

R.R.: Your post inspired me to lay down a new rule: if you want to use my comments section to advertise your open problems, then you must state your problems at a reasonable level of generality (i.e., not for just 2 or 3 qubits). 🙂

Speaking of which, here are some problems you might enjoy:

Is there an efficient algorithm that, given a circuit of CNOT gates, finds an equivalent such circuit of approximately minimum size? (Presumably the answer is no, but I have no idea how to prove that based on any standard hardness assumption.)

Is there a set of “local transformation rules” by which any circuit consisting of CNOT, Hadamard, and pi/4 phase gates can be converted into any equivalent such circuit? (Iwama et al. gave such a set for the case of CNOT gates only. See my paper with Daniel Gottesman for a start on this question.)

5. Wim van Dam Says:

Now, now, Scott. Not so harsh. The posting clearly said that it was a puzzle, not a problem.

6. Anonymous Says:

“R.R.: Your post inspired me to lay down a new rule: if you want to use my comments section to advertise your open problems, then you must state your problems at a reasonable level of generality (i.e., not for just 2 or 3 qubits). :-)”

Oh but that rule is too onerous for a fun Puzzler. A Puzzler doesn’t have to be a Field’s medal problem. I’m planning to give the answer in a week. I don’t want to pose a problem for which I don’t already know the answer myself. That rules out Field’s medal material. I don’t want to induce a paroxysm of thinking in the reader unless I have an antidote at hand, in case he wants it.

Hey, you and Gottesman (I’ve never met the chap but I’ve heard from someone, I forget who, that he is the most serious person in the world) should write some Puzzler’s and post them for the community to enjoy. I’m sure you two could do a much better job than I can.

I’m very interested in the subject of finding equivalent circuits (and approximate equivalent circuit), and have written some papers about it, so I will definitely take a look at your work with Gottesman.

R.R.Tucci