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.
What: A quantum computing workshop sponsored by the CIAR (Canadian Institute for Advanced Research).
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?
Comment #1 May 30th, 2006 at 2:50 pm
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?
Comment #2 May 30th, 2006 at 3:30 pm
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.
Comment #3 May 31st, 2006 at 7:28 am
Sorry for posting off topic, but it could take centuries before Scott posts on technical subjects again :})
QC Programming Puzzler
R.R. Tucci
Comment #4 May 31st, 2006 at 7:08 pm
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.)
Comment #5 June 1st, 2006 at 12:14 pm
Now, now, Scott. Not so harsh. The posting clearly said that it was a puzzle, not a problem.
Comment #6 June 1st, 2006 at 12:34 pm
“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