(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!