12.10 How accurate is accurate enough?

We have seen that finite sets of gates can be used to approximate any unitary operation with any prescribed accuracy. But how accurate is accurate enough? Of course, the answer depends on what we want to achieve.

Suppose we come up with a cool quantum algorithm, represented by a circuit composed of $t$ gates, and it solves an interesting decision problem with probability $\frac{1}{2}+\delta$ . The value of $\delta$ might be tiny, so not much can be inferred from a single run, but as long as we can repeat the computation $r$ times and take the majority answer as the “right” answer, the Chernoff bound²⁵² tells us that the probability of error is bounded above by $e^{-2r\delta^2}$ . We now want to physically implement this circuit using our preferred universal set of gates, say $\{H,T,\texttt{c-NOT}\}$ . If we can implement each gate with accuracy $\varepsilon/t$ , then we can approximate the circuit with accuracy $\varepsilon$ , which means that the probability of success will be $\frac{1}{2}+\delta\pm\varepsilon$ . So, at the very least, we want $\varepsilon<\delta/2$ .

Recall Exercise 1.11.10.↩︎