Making sense of the terms Polynomial and Exponential Precision in a Quantum Circuit

Question

The quantum circuit construction of the quantum Fourier transform apparently requires gates of exponential precision in the number of qubits used. However, such precision is never required in any quantum circuit of polynomial size. For example, let $U$ be the ideal quantum Fourier transform on $n$ qubits, and $V$ be the transform which results if the controlled-$R_k$ gates are performed to a precision $Δ=1/p(n)$ for some polynomial $p(n)$. Show that the error $E(U, V )≡\max_{|\psi\rangle}(U−V)|\psi\rangle$ scales as $O(n^2 /p(n))$, and thus polynomial precision in each gate is sufficient to guarantee polynomial accuracy in the output state.

This is Exercise $5.6$ in Quantum Computation and Quantum Information by Nielsen and Chuang

We have a quantum circuit of $n$ qubit QFT which requires $n$ Hadamard gates, $n(n+1)/2$ controlled-$R_k$ gates and at most $n/2$ swap gates.

$$ E(R_2^1R_3^1\cdots R_n^1\cdots R_2^{n-1},\mathcal{R}_2^1\mathcal{R}_3^1\cdots \mathcal{R}_n^1\cdots \mathcal{R}_2^{n-1})\leq E(R_2^1,\mathcal{R}_2^1)+E(R_3^1,\mathcal{R}_3^1)+\cdots+E(R_n^1,\mathcal{R}_n^1)+\cdots+E(R_2^{n-1},\mathcal{R}_2^{n-1})\\ =\Delta+\Delta+\cdots+\Delta+\cdots+\Delta=\frac{n(n+1)}{2}\Delta=\frac{n(n+1)}{2p(n)}=O(n^2/p(n)) $$

This is clear.

What does it mean to say that The quantum circuit construction of the quantum Fourier transform apparently requires gates of exponential precision in the number of qubits used ?

What is a quantum circuit with polynomial size ?

I am also confused by the terms polynomial precision and polynomial accuracy ?

Answer 1

Let's say you want to perform the (inverse?) quantum Fourier Transform on $n$ qubits. We measure how hard everything is to do relative to $n$, making a division between polynomial scaling (relatively easy) and exponential scaling (hard).

Now, of the various gates used to build the QFT, there are controlled-phase gates of various phases: $\pi$, $\pi/2$, $\pi/4$, $\ldots \pi/2^{n-1}$. You need to be able to implement all of these and it certainly suggests that you're going to need an accuracy of at least $O(2^{-n})$, i.e. exponential accuracy, or you won't be able to tell the difference between some of those different gates!