Finite universal-gate compilation cost for the truncated QFT

If $m<n$, then $2^m\ge 4\pi n\mathrm{/}\eta$, so [F2] gives truncation error at most $\eta \mathrm{/}2$. If $m=n$, the truncated circuit is exact by [F2]. Thus in either case the ideal truncated unitary is within $\eta \mathrm{/}2$ of the exact QFT.

There are $L$ retained one- or two-qubit blocks. For $m\ge 1$, each summand in $L$ is at most $n$, hence $L\le n+n(m-1)=nm$. The final reversal uses $\lfloor n\mathrm{/}2\rfloor$ swaps, or $3\lfloor n\mathrm{/}2\rfloor =O(n)$ exact CNOTs by [F15] and the resource convention [A2].

For any factor $U\in U(2)$, [F10] gives $\mathrm{\mid }\det U\mathrm{\mid }=1$. Choose $\lambda \in \mathbb{C}$ with ${\lambda }^2=\det U$ by [F11]. Then [F12] gives $\mathrm{\mid }\lambda {\mathrm{\mid }}^2=\mathrm{\mid }\det U\mathrm{\mid }=1$, so $\mathrm{\mid }\lambda \mathrm{\mid }=1$. The matrix $S={\lambda }^{-1}U$ is unitary and has determinant $1$, hence $S\in SU(2)$. By [F7]–[F9] and $0<\delta \le \kappa \le {\eta }_0$, compile $S$ to a word $W$ with $\mathrm{\parallel }S-W\mathrm{\parallel }\le \delta$ and $O({\log }^{3.97}(1\mathrm{/}\delta ))$ gates. Thus $\mathrm{\parallel }U-\lambda W\mathrm{\parallel }\le \delta$. The local error lifts to the full register with the same operator norm by [F13]. By [F14], the embedded scalar $\lambda$ remains one scalar on the entire standalone circuit.

Apply [A1] to each retained block: use one gate for a Hadamard and, for $C(P_{\theta })$, the three target gates $A,B,C$ and one control phase gate from the controlled-unitary proof, with its two exact CNOTs. The phase gate is retained, so this is the complete controlled phase. These lists prove the uniform bound with $c=4$, independently of the angle. For any chosen lists bounded by $c$ as in the statement, the total number $K$ of one-qubit factors obeys $K\le cL$, and at most $cL$ CNOTs occur. Keep the Hadamards as one-gate lists, so $K\ge n\ge 1$. No ancilla or unproved QSD optimization is used.

By the circuit denotation interface [A3], compose the compiled factors in chronological order, leaving every decomposition CNOT exact. The global embeddings act on their specified wires by [F16]. The exact-minus-compiled product telescopes with one local difference per one-qubit factor. Every surrounding factor is unitary and has norm one by [F6]; [F5] bounds the norm of the sum by the sum of local errors, at most $K\delta \le cL\delta \le \eta \mathrm{/}2$. The product of the $K$ scalars from step 1.3 is one scalar for the whole standalone circuit.

Let $C$ be the compiled circuit and let $\lambda$ be the total scalar from step 3.1. The triangle inequality, step 1.1 and step 3.1 give $\mathrm{\parallel }{\mathrm{QFT}}_{2^n}-\lambda C\mathrm{\parallel }\le \eta$. By the max-over-unit-vectors definition in [F5], operator-norm homogeneity gives $\mathrm{\parallel }C-\bar{\lambda }{\mathrm{QFT}}_{2^n}\mathrm{\parallel }=\mathrm{\parallel }\bar{\lambda }({\mathrm{QFT}}_{2^n}-\lambda C)\mathrm{\parallel }=\mathrm{\parallel }{\mathrm{QFT}}_{2^n}-\lambda C\mathrm{\parallel }\le \eta$; the first vectors differ by the scalar $-1$, and $\mathrm{\mid }\lambda \mathrm{\mid }=1$. Choosing $\bar{\lambda }$ in the defining infimum proves $d_{\mathrm{p}\mathrm{r}}(C,{\mathrm{QFT}}_{2^n})\le \eta$. Applying [F4] gives the asserted total-variation bound for every unit input.

The scalar in step 3.1 is harmless for this standalone output law because the conclusion uses projective distance and [F4]. It cannot be silently discarded if this entire compiled block is placed under outer control, by [A4]; no outer-controlled compilation claim is made.

By [F8], the $K\le cL$ compiled one-qubit factors use $O(cL{\log }^{3.97}(1\mathrm{/}\delta ))$ gates. The decomposition CNOTs contribute at most $cL$ and the final SWAP expansion contributes $3\lfloor n\mathrm{/}2\rfloor$ exact CNOTs by [A2,F15]. Since $L\le nm$ and $1\mathrm{/}\delta =\max \{2cL\mathrm{/}\eta ,1\mathrm{/}\kappa \}$ with fixed $c,\kappa$, $\log (1\mathrm{/}\delta )=O(\log (2nm\mathrm{/}\eta ))$. Therefore the total is $O(nm{\log }^{3.97}(2nm\mathrm{/}\eta ))$. No step bounds the classical bit-time for target-angle descriptions.