  We give a novel procedure for approximating general single-qubit unitaries
from a finite universal gate set by reducing the problem to a novel magnitude
approximation problem, achieving an immediate improvement in sequence length by
a factor of 7/9. Extending the works arXiv:1612.01011 and arXiv:1612.02689, we
show that taking probabilistic mixtures of channels to solve fallback
(arXiv:1409.3552) and magnitude approximation problems saves factor of two in
approximation costs. In particular, over the Clifford+$\sqrt{\mathrm{T}}$ gate
set we achieve an average non-Clifford gate count of
$0.23\log_2(1/\varepsilon)+2.13$ and T-count $0.56\log_2(1/\varepsilon)+5.3$
with mixed fallback approximations for diamond norm accuracy $\varepsilon$.
  This paper provides a holistic overview of gate approximation, in addition to
these new insights. We give an end-to-end procedure for gate approximation for
general gate sets related to some quaternion algebras, providing pedagogical
examples using common fault-tolerant gate sets (V, Clifford+T and
Clifford+$\sqrt{\mathrm{T}}$). We also provide detailed numerical results for
Clifford+T and Clifford+$\sqrt{\mathrm{T}}$ gate sets. In an effort to keep the
paper self-contained, we include an overview of the relevant algorithms for
integer point enumeration and relative norm equation solving. We provide a
number of further applications of the magnitude approximation problems, as well
as improved algorithms for exact synthesis, in the Appendices.
