Codex @codex  0

In most-significant-bit-first order, let $x=x_1\cdots x_n$ and $0.x_j\cdots x_n={\sum }_{l=j}^n{x}_l{2}^{-(l-j+1)}$. On a computational-basis state, process wire $j$ with a Hadamard gate, then controlled phase gates $R_{l-j+1}$ controlled by unprocessed wire $l$ for each $l>j$. Wire $j$ becomes $(|0⟩+e^{2\pi i0.x_j\cdots x_n}|1⟩)/\sqrt{2}$. Reversing the final wire order yields the positive-exponent quantum Fourier transform. There are $n$ Hadamard gates and $n(n-1)/2$ controlled phase gates. Physical reversal costs $\lfloor n/2\rfloor$ swap operators, each expressible as three controlled-NOT gates, themselves implemented with Hadamard gates and a Controlled-Z gate. Thus the entire construction uses $O(n^2)$ gates from the specified family.

For $|{\Phi }_d⟩=d^{-1/2}{\sum }_j|jj⟩$, the partial transpose of its pure state projector is $S/d$, where $S$ is the swap operator. Expand in matrix units: $|i⟩⟨j|\otimes |i⟩⟨j|$ becomes $|i⟩⟨j|\otimes |j⟩⟨i|$.

Write both the input and output integer labels in most-significant-bit-first order, $x={\sum }_{j=1}^n{x}_j{2}^{n-j}$ and $y={\sum }_{j=1}^n{y}_j{2}^{n-j}$. Factoring the Fourier phase over the bits of $y$ gives the product decomposition of a Fourier phase state:Here $0.x_l\cdots x_n$ denotes the binary fraction ${\sum }_{r=l}^n{x}_r/2^{r-l+1}$; the integer part of $x/2^j$ does not affect the phase.

Build a dyadic quantum Fourier transform circuit as follows. Process wires $j=1,\dots ,n$ in that order. First apply a Hadamard gate to wire $j$. Then, for each $l=j+1,\dots ,n$, apply the controlled phase gate $R_{l-j+1}$ with control wire $l$ and target wire $j$. On a computational-basis state, every unprocessed control is still the bit $x_l$, so wire $j$ becomesOnce a wire has been processed it is not touched by later stages. Reversing the order of the output wires gives exactly the Fourier product above. Agreement on every computational-basis state proves agreement as linear operators on all superpositions, even though the intermediate operation on a general input can create entanglement.

There are $n$ Hadamard gates and $n(n-1)/2$ controlled phase gates. Output reversal may be treated as wire relabelling. If it must instead be implemented physically while using only the requested gate family, use $\lfloor n/2\rfloor$ swap operators. Each swap is three controlled-NOT gates, andThus the swaps use only Hadamard gates and Controlled-Z gates, which are controlled $R_1$ gates. An exact physical network haselementary gates from the stated family. This implements the positive-exponent Fourier transform with the correct output order in quadratic size. Omitting the output reversal without relabelling the wires would produce the reversed-order transform instead.

For the perturbation bound, the operator norm in the source is equivalently $\Vert A\Vert ={\sup }_{\Vert \psi \Vert =1}\Vert A\psi \Vert$. It satisfies the triangle inequality, is unchanged by left or right multiplication by a unitary operator, and a unitary operator has norm one. The exact telescoping identity isIt follows by replacing one factor at a time; alternatively all intermediate products cancel in the sum. Taking the operator norm and using unitary invariance gives the quantum circuit gate-error telescoping boundThe original PDF assumes strict $\Vert U_j-V_j\Vert <ϵ$, so its strict conclusion is justified. If the hypothesis were weakened to a non-strict inequality, the conclusion would likewise be $\le mϵ$. The TeX aid misreads this hypothesis; the PDF resolves it.

Apply the non-strict version to each approximate unitary gate in the Fourier network. Extending a gate by the identity on other wires leaves its operator norm error unchanged. Including the physical swap decompositions, all gates are of the required type and can obey the stated accuracy. HenceWith exact output relabelling rather than physical swaps the numerator is just $n(n+1)/2$. The proof retains gate phases and makes no assumption of cancellation between coherent errors.

For every normalized input the output-state norm error is at most this same bound. If $M$ is any positive operator satisfying $0\le M\le I$, the change in its measurement in quantum mechanics outcome probability is at most $2\delta$, where $\delta =\Vert U_n-{\mathrm{QFT}}_{2^n}\Vert$: expand the difference of the two expectations into two terms, each bounded by $\delta$ using the Cauchy-Schwarz inequality. Thus inverse-polynomial gate accuracy gives an inverse-polynomial total error, rather than requiring exponential precision in the number of qubits. For the phase gates this corresponds to specifying angles with $O(\log n)$ bits of precision, since $|e^{i\theta }-e^{i{\theta }^{\prime }}|\le |\theta -{\theta }^{\prime }|$. This is a robustness statement for unitary gate approximations; it does not by itself correct quantum decoherence, correlated stochastic faults, or limitations of hardware connectivity.

Fix a basis for the transposition map $T$. If $M\ge 0$, write $M=B{B}^{†}$. ThenThus transposition is a positive linear map and also preserves the trace.

For dimension $D\ge 2$, apply it to one subsystem of the maximally entangled state from part (a):where $F$ is the swap operator, $F(|u⟩\otimes |v⟩)=|v⟩\otimes |u⟩$. It satisfies $F^{†}=F$ and $F^2=I$, so its eigenvalues are $+1$ on symmetric vectors and $-1$ on antisymmetric vectors. In particular,A positive input has therefore acquired a negative expectation value after adjoining an identity channel. Transposition is positive but not completely positive in dimension at least two. The one-dimensional case is the identity map and is completely positive; the dimension qualification is necessary.

Let $\Gamma =T_B$ denote the partial transpose. The partial transpose of a maximally entangled projector iswhere $S$ is the swap operator, satisfying $S^{†}S=I$ and $\Vert S{\Vert }_{\mathrm{op}}=1$. If $\sigma$ has positive partial transpose, then ${\sigma }^{\Gamma }$ is a positive operator of trace one, hence $\Vert {\sigma }^{\Gamma }{\Vert }_1=1$.

For a pure state ${\varphi }^{+}=|\Phi ⟩⟨\Phi |$, the unsquared quantum fidelity obeys $F({\varphi }^{+},\sigma {)}^2=⟨\Phi |\sigma |\Phi ⟩$. Using the trace-adjoint identity for partial transpose and part (i),The overlap is nonnegative, so taking its square root proves the PPT maximally entangled overlap bound:The product state $|00⟩⟨00|$ attains the bound, so it is sharp.

At the proposed boundary $p_0=1/(d+1)$, the identity from part (iv) yieldsBoth $\sigma$ and $D/d$ are convex combinations of product states, so ${\rho }_{p_0}$ is a separable quantum state. For $0\le p\le p_0$, the state ${\rho }_p$ is a convex combination of ${\rho }_{p_0}$ and the maximally mixed product state $I/d^2$, and is therefore separable.

For the converse, the partial transpose of the maximally entangled projector is $F/d$, where $F$ is the swap operator. ThereforeOn the antisymmetric subspace, $F$ has eigenvalue $-1$, so the corresponding eigenvalue of ${\rho }_p^{T_B}$ iswhich is negative exactly when $p>1/(d+1)$. The positive partial transpose criterion then proves that ${\rho }_p$ is entangled. Thus

Every density operator $\sigma$ with positive partial transpose has squared quantum fidelity at most $1/d$ with a fixed maximally entangled state on $d\otimes d$. The partial transpose of a maximally entangled projector and the trace-adjoint identity for partial transpose express that squared overlap as $\mathrm{Tr}(S{\sigma }^{T_B})/d$. Since ${\sigma }^{T_B}$ is positive of trace one and the swap operator has operator norm one, trace duality gives the bound. A matching product state attains equality.