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

]]>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.)

]]>QC Programming Puzzler

R.R. Tucci

]]>Yes.

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

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

]]>