Approximate Compilation

Until now we have demanded that a compiled circuit reproduce the target unitary exactly (up to global phase). On noisy hardware that demand is often counter-productive. An exact decomposition may need many gates, and every gate adds physical error; a slightly inexact circuit with far fewer gates can yield a more accurate result in practice. Approximate compilation deliberately trades a small unitary error for a large gate-count saving.

The error budget

Suppose each two-qubit gate has error rate $p$ and your compiled circuit uses $g$ of them. To leading order the circuit's error from noise is roughly $g \cdot p$ . If you accept an approximation error $\varepsilon$ in the unitary in exchange for cutting the gate count from $g$ to $g'$ , the total error becomes about

\varepsilon_{\text{total}} \approx \varepsilon + g' p,

and this can be smaller than the exact circuit's $g p$ whenever the gates saved outweigh the approximation introduced. The compiler's job is to spend an error budget wisely across these two sources.

Where the savings come from

Discrete synthesis tolerance. Solovay–Kitaev and Ross–Selinger synthesis are inherently approximate: requesting accuracy $\varepsilon$ rather than machine precision shortens the gate sequence (roughly $\sim 3\log_2(1/\varepsilon)$ T gates per rotation). Loosening $\varepsilon$ buys shorter sequences.
Small-angle pruning. A rotation $R_z(\theta)$ with $|\theta|$ below a threshold is close to the identity and can be dropped, at the cost of an error $O(\theta)$ .
Approximate resynthesis. A whole sub-block can be replaced by a lower-depth unitary that is close in operator norm but not equal — a numerical optimization minimizing distance subject to a gate budget.

Noise-aware compilation

Pushed further, the compiler uses a model of the device's actual noise — gate error rates, qubit $T_1/T_2$ times, crosstalk — to decide where approximation pays off. It might route through a higher-fidelity qubit even at the cost of an extra swap, or accept a coarser rotation on a fast-decohering qubit. The optimum is no longer "fewest gates" but "lowest expected end-to-end error," which depends on the hardware as much as the algorithm.

The takeaway

Exact compilation is the right target for a perfect machine; real machines reward approximation. By treating accuracy as a budget to be allocated between unitary approximation error and accumulated gate noise, approximate and noise-aware compilation can produce circuits that are shorter, shallower, and — on today's hardware — more accurate than their exact counterparts.