  Recently it has been shown that Repeat-Until-Success (RUS) circuits can
approximate a given single-qubit unitary with an expected number of $T$ gates
of about $1/3$ of what is required by optimal, deterministic, ancilla-free
decompositions over the Clifford+$T$ gate set. In this work, we introduce a
more general and conceptually simpler circuit decomposition method that allows
for synthesis into protocols that probabilistically implement quantum circuits
over several universal gate sets including, but not restricted to, the
Clifford+$T$ gate set. The protocol, which we call Probabilistic Quantum
Circuits with Fallback (PQF), implements a walk on a discrete Markov chain in
which the target unitary is an absorbing state and in which transitions are
induced by multi-qubit unitaries followed by measurements. In contrast to RUS
protocols, the presented PQF protocols terminate after a finite number of
steps. Specifically, we apply our method to the Clifford+$T$, Clifford+$V$, and
Clifford+$\pi/12$ gate sets to achieve decompositions with expected gate counts
of $\log_b(1/\varepsilon)+O(\log(\log(1/\varepsilon)))$, where $b$ is a
quantity related to the expansion property of the underlying universal gate
set.
