How is the size of the circuit derived, in proving the threshold theorem?

Question

In chapter 10.6.1 in Nielsen and Chuang, the section on concatenated codes and the threshold theorem (pages 480-481) states:

The size of the simulating circuit goes as $d^k$ times the size of the original circuit, where $d$ is a constant representing the maximum number of operations used in a fault-tolerant procedure to do an encoded gate and error correction.

It is further explained that if we wish to achieve a final accuracy of $\epsilon$, we are required to concatenate the simulating circuit $k$ times such that:

$$ \frac{(cp)^{2^k}}{c} \leq \frac{\epsilon}{p(n)} \tag{10.113} $$

where $p(n)$ is the number of gates in the simulating circuit and $\frac{(cp)^{2^k}}{c}$ is the failure probability for a procedure at the highest level.

After this, the size of the circuit is to achieve this accuracy is then given as:

$$ d^k = \left(\frac{\log{(p(n)/c\epsilon)}}{\log(1/pc)}\right)^{\log{d}} \tag{10.114} $$

My question is, how is the size of the circuit derived in Eq(10.114)? It is closely related to Eq(10.113) after some rearranging, but I cannot see exactly how to get Eq(10.114).

Answer 1

From Eq(10.113) we can work out the size a simulating circuit must be to achieve the desired accuracy of $\epsilon/p(n)$. Rearranging Eq(10.113), we see $1/(cp)^{2^k} = p(n)/c\epsilon$. Taking the logarithm (base 2, as per @ChrisD) of both sides and rearranging \begin{equation} 2^k = \frac{\log(p(n)/c\epsilon)}{\log(1/cp)} \end{equation} Raising both sides to the power $\log(d)$ and noting $(2^k)^{\log{d}} = d^k$ (as per @ChrisD, again), we can express the size of our circuit as \begin{equation} d^k = \left(\frac{\log\left(p(n)/c\epsilon\right)}{\log\left(1/pc\right)}\right)^{\log{d}} \end{equation} The expression for $d^k$ suggests that the size of the simulating circuit scales as \begin{equation} O\left(\text{poly}(\log p(n)/\epsilon)\right) \end{equation} i.e. the size of the circuit grows no faster than some polynomial function of $\log p(n)/\epsilon$.