(by R.R. Tucci, May 2006)
Thanks to a 2003 paper by Vidal and Dawson, we know that ANY 2-qubit circuit can be expressed as a circuit with JUST 3 CNOTs (single-qubit gates are also allowed). But when can a circuit with 3-CNOTs be expressed with fewer than 3 CNOTs? Find simple-to-check necessary and sufficient conditions for when a 2-qubit circuit can be expressed with 2, 1, or 0 CNOTs (a zero CNOT circuit is just local operations). But wait! There is more. You also get.....to show how to construct such a fewer-CNOT circuit, if one exists. And while you are at it, why not write some software that constructs the fewer-CNOT circuit from the original one. After all, you are not a pusillanimous Theorist: an earthbound, armchair traveler observing the spectacle from the confines of Mission Control in Houston. You are an elite QC Programmer, made of the right stuff, destined to break the heavy bonds of earth, and ride a plume of code and fire into unknown worlds of quantum computing. To infinity and beyond!