Efficient synthesis of probabilistic quantum circuits with fallback

Repeat-until-success (RUS) circuits can approximate a given single-qubit unitary with an expected number of $T$ gates of about $\frac{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 multiqubit unitaries followed by measurements. In contrast to RUS protocols, the presented PQF protocols are guaranteed to 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\{ln[ln(1/\varepsilon )]\}$, where $b$ is a quantity related to the expansion property of the underlying universal gate set.

Figure 1

PQF protocol to implement a unitary gate $G$.

Figure 2

Markov chains for the implementation of a target unitary transformation $G$. Shown are state transitions for (a) repeat-until-success (RUS) protocols and (b) probabilistic circuits with fallback (PQF) protocols.

Figure 3

Overview of compilation flow for one round of the PQF circuit. If a number of rounds $k$ strictly larger than one is intended, stages 1–4 need to be repeated for modified target angles as described in the text.

Figure 4

Algorithm to find a probability modifier $r$.

Figure 5

Precision $\varepsilon$ versus mean expected $T$ count of PQF circuits over Clifford + $T$ for set of random angles.

Figure 6

Precision $\varepsilon$ versus mean expected $K$ count of PQF circuits over Clifford + $\frac{\pi }{12}$ for set of random angles.

Figure 7

Precision $\varepsilon$ versus mean expected $V$ count of PQF circuits over Clifford + $V$ for set of random angles.