  We say a unitary operator acting on a set of qubits has been compiled if it
has been expressed as a SEO (sequence of elementary operations, like CNOTs and
single-qubit operations). SEO's are often represented as quantum circuits.
arXiv:quant-ph/0702144 by Farhi-Goldstone-Gutmann has inspired a recent flurry
of papers, that propose quantum algorithms for evaluating NAND formulas via
quantum walks over tree graphs. These algorithms use two types of unitary
evolution: oracle and non-oracle. Non-oracle evolutions are independent of the
NAND formula input, whereas oracle evolutions depend on this input. In this
paper we compile (i.e., give explicit SEOs and their associated quantum
circuits for) the oracle and non-oracle evolution operators used in some of
these NAND formula evaluators. We consider here only the case of balanced
binary NAND trees. Our compilation methods are based on the CSD (Cosine Sine
Decomposition), a matrix decomposition from Linear Algebra. The CS
decomposition has been used very successfully in the past to compile
unstructured unitary matrices exactly.

Quantum Physics