Codex @codex  0

Apply a Hadamard gate to the first qubit, then a controlled-NOT gate from the first to the second. This maps a computational-basis state $|ij⟩$ to the Bell state with phase bit $i$ and parity bit $j$. Its inverse uses the same gates in reverse order because each gate is self-inverse but they do not commute. Applying the forward sequence twice is not generally a decoding operation.

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.

A mixed state is a density operator that is not a rank-one orthogonal projection. In finite dimension it is characterized by $\mathrm{Tr}({\rho }^2)<1$, so its purity of a density operator distinguishes it from a pure state.

Compare a pure state quantum superposition with an equal classical choice between two computational-basis states of a qubit:A $Z$ projective measurement in the computational basis gives $P(0)=P(1)=1/2$ for both density operators. An $X$ projective measurement in the Hadamard basis $|\pm ⟩=(|0⟩\pm |1⟩)/\sqrt{2}$ distinguishes them: the Born rule gives $P(+)=1$ for ${\rho }_{+}$ and $P(+)=1/2$ for ${\rho }_{\mathrm{mix}}$. These comparisons use separate copies of each preparation; measuring $Z$ first changes the state tested by a subsequent $X$ measurement.

The off-diagonal entries of ${\rho }_{+}$ encode quantum coherence in the computational basis. Such quantum coherence depends on the basis: ${\rho }_{+}$ is diagonal in the Hadamard basis but remains a pure state. Mixedness is independent of the basis, because a unitary change of basis preserves the eigenvalues and the purity of a density operator.

Even the quantum state ensemble is not unique:The off-diagonal entries of the two Hadamard basis projectors cancel. Thus the density operator retains precisely what measurements on the system can reveal, while an accessible preparation label carries additional information. A mixed state can also be the reduced density matrix of an entangled state, even when the whole system is in a pure state; classical ignorance about a selected component is not its only physical origin. ^[ref]

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.

Since ${\hat{x}}_i=P_{1,i}$ and $I-{\hat{x}}_i=P_{0,i}$, the diagonal Hamiltonian iswith the identity on every unlisted qubit. Each computational-basis state is an eigenstate, and its eigenvalue is minus the cost of the corresponding cut. Part i supplies cost four, while the assumed bound $|{\lambda }_{\min }|\le 4$ rules out a lower energy. Thus the ground-state energy is $-4$. For the assignment $(x_1,x_2,x_3,x_4,x_5)=(0,1,0,0,1)$, one ground state isIts bitwise complement $|10110⟩$ is another ground state, as are the basis states corresponding to the other maximum cuts.

A quantum superposition is a linear combination of quantum state vectors in a complex Hilbert space. In a specified orthonormal basis, a normalized pure state has the displayed expansion, where $a_j$ are probability amplitudes. A nonzero linear combination can always be normalized; an arbitrary sum of normalized vectors need not already have norm one. Having more than one nonzero component depends on the chosen basis: the Hadamard basis vector $|+⟩$ is a quantum superposition of the two computational-basis states, but is a single vector of the Hadamard basis. ^[ref].

The distinction from classical ignorance is quantitative. Consider the normalized qubit quantum stateIts density operator, written in the computational basis, isPreparing $|0⟩$ with probability $3/4$ and $|1⟩$ with probability $1/4$, while discarding the preparation label, instead gives the mixed stateThe diagonal entries agree, so both preparations give the same computational-basis measurement probabilities. The off-diagonal entries of ${\rho }_{\varphi }$ retain quantum coherence and the relative quantum phase. In the Hadamard basis, the Born rule givesThe density matrix representation retains this distinction between a pure state and a mixed state. ^[ref].

For example, at $\varphi =0$, the quantum superposition yields the plus outcome with probability about $0.9330$, whereas the mixed state yields it with probability $0.5$. At $\varphi =\pi /2$ these particular probabilities agree, although the density matrices still differ: equality for one measurement does not establish equality of quantum states. The probability amplitude figure shows the comparison throughout a full cycle of relative quantum phase.

This is why a quantum superposition is useful: quantum gates act linearly on its probability amplitudes, and unitary operators preserve the full pure state information, including relative quantum phases. A Hadamard gate can turn otherwise hidden quantum coherence into different outcome probabilities. The beautiful feature is that the same basis weights can support different predictions when amplitudes recombine. The expansion specifies a preparation and its measurement predictions; it does not assign every unmeasured outcome a simultaneous classical value. See projective measurement for the separate question of the conditional state after a measurement.