  We present an algorithm for compiling arbitrary unitaries into a sequence of
gates native to a quantum processor. As accurate CNOT gates are hard for the
foreseeable Noisy- Intermediate-Scale Quantum devices era, our A* inspired
algorithm attempts to minimize their count, while accounting for connectivity.
We discuss the search strategy together with metrics to expand the solution
frontier. For a workload of circuits with complexity appropriate for the NISQ
era, we produce solutions well within the best upper bounds published in
literature and match or exceed hand tuned implementations, as well as other
existing synthesis alternatives. In particular, when comparing against
state-of-the-art available synthesis packages we show 2.4x average (up to 5.3x)
reduction in CNOT count. We also show how to re-target the algorithm for a
different chip topology and native gate set, while obtaining similar quality
results. We believe that empirical tools like ours can facilitate algorithmic
exploration, gate set discovery for quantum processor designers, as well as
providing useful optimization blocks within the quantum compilation tool-chain.
