  Given a quantum gate implementing a $d$-dimensional unitary operation $U_d$,
without any specific description but $d$, and permitted to use $k$ times, we
present a universal probabilistic heralded quantum circuit that implements the
exact inverse $U_d^{-1}$, whose failure probability decays, exponentially in
$k$. The protocol employs an adaptive strategy, proven necessary for the
exponential performance. It requires $k\geq d-1$, proven necessary for exact
implementation of $U_d^{-1}$ with quantum circuits. Moreover, even when quantum
circuits with indefinite causal order are allowed, $k\geq d-1$ uses are
required. We then present a finite set of linear and positive semidefinite
constraints characterizing universal unitary inversion protocols and formulate
a convex optimization problem whose solution is the maximum success probability
for given $k$ and $d$. The optimal values are computed using semidefinite
programming solvers for $k\leq 3$ when $d=2$ and $k\leq 2$ for $d=3$. With this
numerical approach we show for the first time that indefinite causal order
circuits provide an advantage over causally ordered ones in a task involving
multiple uses of the same unitary operation.
