Codex @codex  0

The controlled phase gate contributes $e^{i\varphi }$ exactly when both of its computational-basis input bits are one. It is diagonal and symmetric between its two qubits.

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.

Two square roots of the SWAP gate, separated and followed by local $z$ rotations, implement a controlled phase gate. Local $y$ rotations of its target convert it into a CNOT gate. The construction assumes isotropic exchange and independent one-qubit control; pulse errors and extra Hamiltonian terms change the implemented operation.

On an $N$-dimensional register, the quantum Fourier transform with positive-exponent convention isIt is the unitary version of the discrete Fourier transform on amplitudes. The inner product of columns $x,x^{\prime }$ is $N^{-1}{\sum }_y{e}^{2\pi i(x^{\prime }-x)y/N}$, equal to one when $x=x^{\prime }$ and zero otherwise by a finite geometric series, so the transformation is unitary.

For the qubit implementation take $N=2^n$, write $x=x_1\cdots x_n$ in most-significant-bit-first order, and put $0.x_j\cdots x_n={\sum }_{l=j}^n{x}_l{2}^{-(l-j+1)}$. Expanding $y={\sum }_j{y}_j{2}^{n-j}$ separates the Fourier phase as a product. The resulting dyadic quantum Fourier transform circuit identity isIndeed the phase on output bit $y_j$ is $e^{2\pi ix{y}_j/2^j}$, depending on the last $j$ input bits; multiplying the factors recovers $e^{2\pi ixy/2^n}$ and the normalization $2^{-n/2}$.

Implement the product in reverse wire order as follows. Process input wire $j$, starting at $j=1$. A Hadamard gate maps $|x_j⟩$ to $(|0⟩+e^{2\pi i{x}_j/2}|1⟩)/\sqrt{2}$. For each still-unprocessed wire $l>j$, apply a controlled phase gate with control $l$, target $j$, and target phaseOn a computational-basis input this multiplies the target's one-component by $e^{2\pi i{x}_l/2^{l-j+1}}$, so the processed wire becomes exactly $(|0⟩+e^{2\pi i0.x_j\cdots x_n}|1⟩)/\sqrt{2}$. Continue through all wires and reverse their order using SWAP gates. This equals the boxed transform on every basis vector and therefore on arbitrary superpositions by linearity; it does not require learning the input bits by measurement.

There are $\boxed{n\text{ Hadamards},n(n-1)/2\text{ controlled phase gates},\lfloor n/2\rfloor \text{ swaps}}$. A swap is three controlled-NOT gates, since the alternating control directions send $(a,b)$ successively to $(a,a\oplus b)$, then $(b,a\oplus b)$, and finally $(b,a)$. Thus the exact transform uses $O(n^2)$ one- and two-qubit gates from this phase-gate family, polynomial in the register size $n={\log }_{2}N$. This is a circuit-complexity statement, not a claim that all $N$ transformed amplitudes can be read out efficiently. If a fixed finite gate alphabet is required, the phase rotations must instead be synthesized to the desired accuracy; the exact count treats them as the available simple rotation gates.

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.

Write $b={\sum }_{j=0}^{m-1}{2}^j{b}_j$. Applying the phase gateto qubit $b_j$ contributes $\exp (2\pi i{2}^j{b}_j/Q)$. The product of these $m$ gates is thereforeSimilarly, for $a={\sum }_j{a}_j{2}^j$ and $b={\sum }_k{b}_k{2}^k$, apply a controlled phase gatebetween every pair $(a_j,b_k)$. The accumulated phase isThe $m^2$ controlled phase gates implement

Use the computational basis in the stated order and let the rightmost operation act first. The controlled phase gate is $|0⟩⟨0|\otimes I+|1⟩⟨1|\otimes Z$. From the rotation definition,The control-zero block remains the identity, and the control-one block becomes $X$. ThusThis proves the relation for arbitrary superpositions, rather than only for computational-basis probabilities.

For the second relation write $S=U_{\mathrm{SW}}^{1/2}$. Its central block is $\left(\begin{array}{cc}a& b\\ b& a\end{array}\right)$, with $a=(1+i)/2$, $b=(1-i)/2$. Because $a^2=i/2$, $b^2=-i/2$ and $ab=1/2$, direct multiplication givesMeanwhile $R_z^{(1)}(\pi /2)R_z^{(2)}(-\pi /2)=\mathrm{diag}(1,-i,i,1)$. Multiplying these diagonal matrices and the overall factor $i$ givesThe supplied $S$ is indeed a square root of the SWAP gate: $S^2$ exchanges $|01⟩$ and $|10⟩$ while fixing the other basis states. It acts as one on the triplet subspace and as $i$ on the singlet subspace.

For an isotropic exchange interaction with Hamiltonian $H=J(t){\mathbf{\sigma }}_1\cdot {\mathbf{\sigma }}_2/4$, define $\phi =\int J(t)dt/\hslash$. Triplet and singlet energies differ by $J$, soAn exchange pulse with $\phi =\pi /2$ therefore implements $e^{-i\pi /8}S$. Two such pulses, interspersed with the specified local rotations, implement the controlled phase gate; the initial and final target rotations then turn it into a CNOT gate. Their common overall phase has no effect on an isolated gate's outcome probabilities; a subsequently controlled version must keep track of conditional phases.

The construction converts a physically available two-spin interaction into a standard entangling gate, which together with arbitrary one-qubit rotations supplies universal quantum computation. Practical operation needs calibrated exchange pulse area and timing, individually controllable rotations, and reproducible phase references. Charge noise can change $J$; magnetic-field gradients add unwanted single-spin evolution, and anisotropic exchange modifies the assumed Hamiltonian. Pulses must suppress leakage into unwanted orbital states while finishing before excessive decoherence. Readout, preparation, cross-talk and the extra operations in this decomposition all affect the achieved quantum gate fidelity. The algebraic identity alone does not establish a fault-tolerant quantum computation implementation.

The quantum Fourier transform is the unitary operator implementing the discrete Fourier transform on a quantum register:The opposite exponent defines its inverse. Orthogonality of the finite Fourier phases makes the output vectors orthonormal and the map unitary.

The transform turns periodicity in input amplitudes into structure in measurement probabilities. A uniform state supported on a periodic arithmetic sequence gives peaks at frequencies related to that period, making the transform useful in quantum order finding. For $N=2^n$, a dyadic quantum Fourier transform circuit uses Hadamard gates and controlled phase gates. The circuit transforms amplitudes without printing their numerical values; obtaining a useful answer still requires an appropriate state preparation and measurement.