  Compilation of unitaries into a sequence of physical quantum gates is a
critical prerequisite for execution of quantum algorithms. This work introduces
STOQ, a stochastic search protocol for approximate unitary compilation into a
sequence of gates from an arbitrary gate alphabet. We demonstrate STOQ by
comparing its performance to existing product-formula compilation techniques
for time-evolution unitaries on system sizes up to eight qubits. The
compilations generated by STOQ are less accurate than those from
product-formula techniques, but they are similar in runtime and traverse
significantly different paths in state space. We also use STOQ to generate
compilations of randomly-generated unitaries, and we observe its ability to
generate approximately-equivalent compilations of unitaries corresponding to
shallow random circuits. Finally, we discuss the applicability of STOQ to tasks
such as characterization of near-term quantum devices.
