Efficient Synthesis of Universal Repeat-Until-Success Quantum Circuits

Recently it was shown that the resources required to implement unitary operations on a quantum computer can be reduced by using probabilistic quantum circuits called repeat-until-success (RUS) circuits. However, the previously best-known algorithm to synthesize a RUS circuit for a given target unitary requires exponential classical runtime. We present a probabilistically polynomial-time algorithm to synthesize a RUS circuit to approximate any given single-qubit unitary to precision $ϵ$ over the $\text{Clifford}+T$ basis. Surprisingly, the $T$ count of the synthesized RUS circuit surpasses the theoretical lower bound of $3{\log }_2(1/ϵ)$ that holds for purely unitary single-qubit circuit decomposition. By taking advantage of measurement and an ancilla qubit, RUS circuits achieve an expected $T$ count of $1.15{\log }_2(1/ϵ)$ for single-qubit $z$ rotations. Our method leverages the fact that the set of unitaries implementable by RUS protocols has a higher density in the space of all unitaries compared to the density of purely unitary implementations.

Figure 1

Approximationsof $z$ rotations by (a) unitary circuits of $T$ depth of at most 8 and (b) RUS protocols with a comparable expected $T$ depth of at most 7.5.

Figure 2

RUS design to implement unitary $V$.

Figure 3

Algorithm to design the unitary $V$.

Figure 4

Precision $ϵ$ versus mean expected $T$ count for a set of 1000 random angles.