Codex @codex  0

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.

A measurement in quantum mechanics with outcomes $m$ is specified, in the single-operator-per-outcome description, by linear operators $M_m$ satisfying ${\sum }_m{M}_m^{†}{M}_m=I$. Its effects $F_m=M_m^{†}{M}_m$ form a positive operator-valued measure. The two measurement postulates are the Born rule for outcomes and the conditional state update:For a density operator the corresponding formulas are $p_m=\mathrm{Tr}(M_m\rho M_m^{†})$ and ${\rho }_m=M_m\rho M_m^{†}/p_m$. More general quantum instruments have multiple operators for each outcome and sum these terms. For a projective measurement of an observable $A={\sum }_m{a}_m{P}_m$, take $M_m=P_m$; the outcome value is $a_m$ and the postmeasurement state lies in its eigenspace. A POVM alone specifies probabilities, whereas the measurement operators or instrument also specify the backaction.

For quantum teleportation, Alice and Bob initially share the Bell pair $|{\Phi }^{+}{⟩}_{AB}=(|00⟩+|11⟩)/\sqrt{2}$. Alice also holds the input $|\psi {⟩}_C=\alpha |0⟩+\beta |1⟩$, with $|\alpha {|}^2+|\beta {|}^2=1$. The shared entanglement is a resource; the two transmitted classical bits alone could not transfer an arbitrary unknown quantum state.

Alice applies a controlled-NOT gate with $C$ as control and $A$ as target, then a Hadamard gate to $C$. Starting from $|\psi {⟩}_C|{\Phi }^{+}{⟩}_{AB}$, direct expansion givesFor example, the four receiver vectors are $\alpha |0⟩+\beta |1⟩$, $\beta |0⟩+\alpha |1⟩$, $\alpha |0⟩-\beta |1⟩$, and $-\beta |0⟩+\alpha |1⟩$. Thus the gate calculation fixes the ordering of the Pauli corrections, including the last branch's sign.

Alice measures $C,A$ in the computational basis, obtaining $(a,b)$. The Born rule gives each outcome probability $1/4$, independent of the input amplitudes. Bob's normalized conditional state is $X^b{Z}^a|\psi ⟩$. Alice sends the two outcome bits. Bob applies the inverse, $Z^a{X}^b$, and henceThe same circuit is a Bell-basis measurement on Alice's two qubits, expressed using ordinary gates followed by computational-basis measurements. It restores the state without Alice or Bob knowing $\alpha ,\beta$.

By linearity, the calculation also holds when the input is entangled with a reference: each outcome has branch map $|\psi ⟩\mapsto X^b{Z}^a|\psi ⟩/2$, and after correction every branch is one-half of the identity map. Summing the four corrected density operators gives exactly the original input density operator, with all reference correlations preserved. This is teleportation as an identity channel on a reference. Without the two classical bits Bob must average the four uncorrected states, giving $\frac{1}{4}{\sum }_{a,b}{X}^b{Z}^a\rho Z^a{X}^b=I/2$, so the process cannot signal before the message arrives. The Bell pair is consumed and Alice retains no copy of the unknown state, in accordance with the no-cloning theorem.

Use the Hilbert-Schmidt inner product normalized by the dimension: $(A,B)=\frac{1}{2}\mathrm{Tr}(A^{†}B)$. The identity and the three Pauli matrices are Hermitian, each has square $I$, and each nonidentity Pauli matrix has zero trace. For distinct nonidentity indices, the Pauli matrix multiplication law gives ${\sigma }_j{\sigma }_k=i{\sum }_l{\epsilon }_{jkl}{\sigma }_l$, which is traceless. ThereforeThere are four such orthonormal operators, and the complex vector space of two-by-two matrices has dimension four. Hence they form an orthonormal basis. Taking the inner product of any $E$ with each basis element proves, for arbitrary complex $E$ and not just Hermitian ones,For example, if $E=\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)$, its four coefficients are $(a+d)/2$, $(b+c)/2$, $i(b-c)/2$, and $(a-d)/2$, respectively.

For the joint error, regard the two prescribed basis outputs as the columns of an environment-valued linear map. Its coefficient array in the usual output-row, input-column convention isThe source's other array is arranged as a column of the images of basis kets; it must not be mistaken for this coefficient array acting on an amplitude column. Applying the just-proved Pauli matrix expansion componentwise in any environment orthonormal basis gives the Pauli decomposition of a qubit-environment isometry:To check the potentially delicate sign of the Pauli Y gate coefficient, use $Y|0⟩=i|1⟩$ and $Y|1⟩=-i|0⟩$. The four terms then giveLinearity proves the expansion for every input pure state. The environment coefficient vectors need not be normalized or mutually orthogonal. Consequently this expansion includes coherent combinations of Pauli errors, rather than asserting that every quantum channel is a probabilistic Pauli channel.

For the recovery probability, use the usual independent-use interpretation of the given phase-flip channel: each of the three transmitted qubits has a Pauli Z gate error independently with probability $q$. The phase-flip repetition code uses logical codewords $|+++⟩$ and $|---⟩$. The decoding Hadamard gates convert physical phase flips to bit flips because $HZH=X$. We can then analyze the two decoding controlled-NOT gates and the final Toffoli gate directly, rather than assuming a recovery rule.

Let $b_1,b_2,b_3$ be the error bits after this basis conversion. For a logical basis input $t\in \{0,1\}$, the three data bits before inverse encoding are $t\oplus b_1,t\oplus b_2,t\oplus b_3$. The two controlled-NOT gates produceThe Toffoli gate flips the first wire when both of the last two bits are one. Its residual error isThe last two wires carry an error syndrome independent of $t$. Thus this transformation preserves the amplitudes of an arbitrary superposition: zero or one phase error returns the original unknown qubit, while two or three phase errors leave the logical Pauli X gate applied to it. The probability of universally successful recovery is thereforeEquivalently, the decoded quantum channel is $\rho \mapsto (1-p_L)\rho +p_{L}X\rho X$, with logical failure of the three-qubit phase-flip repetition code $p_L=3q^2-2q^3$. For $0<q<1/2$, the failure probability is below $q$, since $q-p_L=q(1-q)(1-2q)>0$. A special input that is a Pauli X eigenstate is unchanged even by the residual logical error; this does not make the code correct that error on an unknown input. Its squared quantum fidelity with a particular pure input is $1-p_L+p_L|⟨\chi |X|\chi ⟩{|}^2$. If the errors on different channel uses are correlated, the marginal probability $q$ alone is insufficient: the general universal success probability is the probability of at most one error.

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.

Number the physical wires $1,\dots ,5$ from top to bottom and write a computational basis ket in that order. The first four are ancilla qubits and the fifth carries the input. It is enough to follow the basis input $|b⟩$, $b\in \{0,1\}$, because the encoding quantum circuit acts linearly.

The first fan-out consists of four controlled-NOT gates from wire 5 to wires 1–4. It sends $|0000b⟩$ to $|bbbbb⟩$. The three Hadamard gates then giveThe two Pauli X gates on wires 2 and 3, followed by a Controlled-Z gate and the same two X gates, restore the bits but contribute $(-1{)}^{(1-c)(1-d)}$: the sign is negative exactly when the original bits on both wires were zero. Finally, the right-hand controlled-NOT gates are $3\to 4$, $2\to 5$, $1\to 4$ and $1\to 5$. They leave the first three bits unchanged and turn the last two into $b\oplus a\oplus d$ and $b\oplus a\oplus c$. ThusExplicitly, the logical basis quantum states produced by the printed gates areEach has eight orthogonal terms of equal magnitude, and their supports are disjoint, so they are normalized and mutually orthogonal. The arbitrary input is therefore encoded asThis is a realization of the five-qubit error correcting code. The input amplitudes and their relative quantum phase are preserved in the logical subspace; the encoding is an entangled-state linear isometry, not five independent copies of the unknown input. The explicit signs and bit ordering above are fixed by this circuit, rather than by a convention for a different encoder.

Write $N=2k+1$ and abbreviate the Dicke states by $|D_j^n⟩=|{\Psi }_j^n⟩$. Alice's shared resource has decompositionFollow the actual circuit order: a controlled-NOT gate from the input to $q_0$, a Hadamard gate on the input and a Pauli X gate on $q_0$, followed by computational basis measurements. Just before measurement, the joint vector isThe Dicke states in each branch are orthogonal, so each branch has squared norm $1/4$. Conditioning on outcome $00$ and normalizing therefore gives the state of the other $N$ parties:This is the encoding used in Dicke-resource telecloning. The extra Pauli X gate on Alice's resource qubit is essential to the displayed ordering of the amplitudes.

Yes: use superdense coding, with a shared Bell state. Let the sender and receiver initially hold the first and second qubits of $|{\Phi }^{+}⟩=(|00⟩+|11⟩)/\sqrt{2}$. To encode bits $(a,b)$, the sender applies $Z^a{X}^b$ to her qubit. These Pauli operators produce four orthogonal states:She sends this qubit through the noiseless quantum channel. The receiver then possesses both qubits. He applies a controlled-NOT gate from the received qubit to his original qubit, followed by a Hadamard gate on the received qubit. This maps the four states in the table to $|ab⟩$. A measurement in the computational basis therefore recovers the two bits with certainty. No classical message is sent.

The resource assumption deserves care: one-qubit superdense coding needs a Bell pair already shared before encoding. If none is initially available, the sender can prepare a Bell pair locally and send one half through the same noiseless quantum channel in advance. The protocol then uses two transmitted qubits in total, including distribution of the entanglement, still with no classical communication. Alternatively, sending two computational basis qubits directly also communicates two bits. With a pre-shared Bell pair, one transmitted qubit suffices; without it, the entanglement-distribution cost must be counted. An unassisted single transmitted qubit cannot perfectly encode four classical messages: its Holevo bound is at most ${\log }_{2}2=1$ bit.

Number the three data qubits from top to bottom. It suffices initially to follow a pure input $|\psi ⟩=a|0⟩+b|1⟩$; linearity will extend the result to every density operator. The first two controlled-NOT gates create $a|000⟩+b|111⟩$. The first layer of Hadamard gates then encodes this asthe three-qubit phase-flip repetition code. Let $e_i$ indicate whether a Pauli Z gate occurred on data qubit $i$ during storage. The next layer of Hadamard gates uses $HZH=X$ and givesThe two initially zero syndrome quantum ancillas receive the adjacent parities. In the diagram's top-to-bottom order, their error syndrome isBoth terms of the logical superposition have these same parities, so the syndrome is independent of $a,b$. Measuring it reveals no logical-state information.

At the marked position of $R$ in the printed circuit, there has already been another layer of Hadamard gates on the data. There is also a layer immediately after $R$. Thus a desired correction $X_i$ in the parity-extraction frame must be implemented as $R=Z_i$ at the actual recovery location, since $H^{\otimes 3}{Z}_i{H}^{\otimes 3}=X_i$. Choose the recovery according toThe two patterns on each row share a syndrome because complementing all three bits does not change either parity. For a weight-zero or one error, the recovery removes the entire error in the parity-extraction frame. The remaining state is $a|000⟩+b|111⟩$, and the two final controlled-NOT gates give $|\psi ⟩|00⟩$.

For a weight-two or three error, minimum-weight recovery instead leaves all three bits flipped, giving $a|111⟩+b|000⟩$. The final controlled-NOT gates send this to $(a|1⟩+b|0⟩)|00⟩=X|\psi ⟩|00⟩$. Consequently, for every input density operator,The logical failure is a Pauli X gate after decoding, even though the stored physical errors were Pauli Z gates: $Z_1{Z}_2{Z}_3$ exchanges the two encoded codewords. This is the logical failure of the three-qubit phase-flip repetition code.

Number the wires from top to bottom as $1,\dots ,5$. The first two controlled-NOT gates encode $|\psi ⟩=u|0⟩+v|1⟩$ into the bit-flip repetition codeon data wires $1,2,3$. The lower two zero ancillas store an error syndrome. Reading the PDF's four detection CNOTs givesThe syndrome and the data qubit to be flipped are thereforeThis is coherent syndrome extraction for the three-qubit repetition code. The recovery Toffoli gates implement these conditions; the intervening Pauli X gates temporarily turn zero-valued controls into one-valued controls and then restore the syndrome wires. Finally, inverse encoding returns the logical state to the top wire and resets data wires 2 and 3 to zero.

For the specified error $X_1$, the encoded data becomes $u|100⟩+v|011⟩$. Both terms have syndrome $01$, so detection factors out $|01{⟩}_{45}$ without revealing the logical amplitudes. Recovery flips data wire 1, restoring $u|000⟩+v|111⟩$, and decoding yieldsThe lower four wires need not all return to zero: their syndrome record is independent of the logical state, which is what the correction requirement needs.

Apply a Hadamard gate to qubit $A$, followed by a controlled-NOT gate with $A$ controlling $B$. The resulting Bell-basis conversion circuit is $U=\mathrm{CNOT}(H\otimes I)$ and givesThus $00,01,10,11$ map respectively to ${\Phi }^{+},{\Psi }^{+},{\Phi }^{-},{\Psi }^{-}$. The first input bit becomes the phase bit and the second becomes the parity bit.

Both gates are self-inverse, but inversion of their product reverses the order:So the same two gates convert the Bell basis back to the computational basis when applied in reverse order: first the controlled-NOT, then the Hadamard. Using the forward order twice does not generally work, since these gates do not commute. For example, $U|{\Phi }^{+}⟩=(|00⟩+|01⟩-|10⟩+|11⟩)/2$, which is not a computational-basis state.

Use GHZ preparation with Hadamard and controlled-Z gates for $n\ge 2$. Apply a Hadamard gate to the first qubit, then a controlled-NOT gate from that qubit to each of the other $n-1$ qubits. Every controlled-NOT can be written in the allowed gate set asIndeed conjugating the target $Z$ by $H$ makes the controlled phase into a controlled $X$. The rightmost gate acts first. Consequently the Clifford circuit uses $1+3(n-1)$ allowed gates and givesFor every chosen qubit $j$, tracing out the other qubits yields ${\rho }_j=\frac{1}{2}(|0⟩⟨0|+|1⟩⟨1|)=I/2$. Equivalently, across that qubit versus the rest, the displayed state is a Schmidt decomposition with two nonzero coefficients $1/\sqrt{2}$. It is therefore entangled across every such bipartition.

Entanglement does not prevent the polynomial single-output simulation from part (iii). The simulation follows the measured observable rather than claiming that the intermediate states remain product states. When $n=1$, there is no remaining subsystem and the requested entanglement is impossible; the construction and claim require $n\ge 2$.

For $|\psi ⟩=a|0⟩+b|1⟩$, the Controlled-NOT gate givesA cloned product would instead beEquality up to a physically irrelevant global phase requires $ab=0$. ThusFor a genuine superposition it creates quantum entanglement instead of two independent copies.

Let $|\alpha ⟩=a|0⟩+b|1⟩$ be Alice's unknown qubit, and label her half of the shared Bell state by $A$ and Bob's by $B$. Alice applies a Controlled-NOT gate from the unknown qubit to $A$, then a Hadamard gate to the unknown qubit. The three-qubit state becomesAlice measures her two qubits in the computational basis and sends the two classical outcomes $(j,k)$ to Bob. Bob applies $Z^j{X}^k$, recovering $|\alpha ⟩$ with certainty. This is quantum teleportation; Alice never needs to know the state.

For the shared GHZ state, Charlie first applies a Hadamard gate to his qubit. ThenCharlie measures in the computational basis. Outcome $0$ leaves Alice and Bob with $|{\varphi }^{+}⟩$; outcome $1$ leaves $|{\varphi }^{-}⟩$, which either party converts to $|{\varphi }^{+}⟩$ by applying $Z$ after Charlie reports the outcome. Thus

Quantum no-signalling says that, without communicating a measurement outcome, any local trace-preserving operation performed on subsystem $A$ leaves all outcome probabilities for measurements on subsystem $B$ unchanged; equivalently, it leaves the reduced density matrix ${\rho }_B$ unchanged.

The two Bell states are orthogonal. Applying the inverse Bell-state preparation circuit, namely a Controlled-NOT gate from $A$ to $B$ followed by a Hadamard gate on $A$, givesA computational-basis measurement therefore distinguishes them perfectly, soIf only $B$ is accessible, however,Every measurement on $B$ consequently has the same outcome distribution under both hypotheses. With equal prior probabilities no information is available, andthe error probability of a random guess.

The printed sum contains $Z_n$ although the stated labels end at $n-1$. We use the natural periodic convention $Z_n=Z_0$, with $n\ge 3$. If an open chain was intended, omitting the final term gives the same asymptotic bound.

Set $H_j=X_{j-1}{Z}_j$, with indices modulo $n$, and implement the product-formula Hamiltonian simulationEach factor acts on two qubits, so it is a two-qubit unitary operator. More explicitly, if $a=j-1$, $b=j$, and $C_{a\to b}$ is a controlled-NOT gate,where ${\mathsf{H}}_a$ is a Hadamard gate. This gives a constant number of one-qubit and two-qubit gates per factor; one-qubit gates can also be viewed as two-qubit gates tensored with the identity.

The spectral norm obeys the triangle inequality, submultiplicativity of the operator norm, and invariance under multiplication by unitary operators. In particular, the telescoping bound for products of operators gives $\Vert V^k-W^k\Vert \le k\Vert V-W\Vert$ for unitary $V,W$. The first-order unitary product-formula error bound consequently yieldsOnly neighboring terms can have a nonzero commutator, because all other supports are disjoint. There are $n$ neighboring unordered pairs, and $\Vert [H_j,H_l]\Vert \le 2\Vert H_j\Vert \Vert H_l\Vert =2$. Thus $\Vert U-\tilde{U}\Vert \le n/k$. Choosing $k>n/\epsilon$ givesThe coarser bound that counts all $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairs also proves the often-used $O(n^3/\epsilon )$ construction. Locality improves that cubic estimate to the quadratic bound above; neither assertion is a lower bound on the best possible circuit.

The controlled-NOT gate sends $|0x⟩$ to $|0x⟩$ and $|1\bar{x}⟩$ to $|1x⟩$. HenceSince the Hadamard gate satisfies $H^2=I$,

The three controlled-NOT gates have directions $1\to 2$, $2\to 1$, and $1\to 2$. On computational basis bits they act asBy linearity, the whole quantum circuit is the SWAP gate. Thereforeso $|\alpha ⟩=|\varphi ⟩$ and $|\beta ⟩=|\psi ⟩$.

Prepare an ancilla qubit in $|0⟩$. To measure $X\otimes X$, apply a Hadamard gate to each data qubit, apply a controlled-NOT gate from each data qubit to the ancilla, measure the ancilla in the computational basis, and apply a Hadamard gate to each data qubit again. The ancilla records the parity of the two rotated computational-basis bits, so outcome $0$ corresponds to eigenvalue $+1$ and outcome $1$ to eigenvalue $-1$. The data register is projected by $[I+(-1{)}^{s}X\otimes X]/2$, so its complete post-measurement state is retained. For $Z\otimes X$, perform the same ancilla-assisted Pauli measurement but apply the basis-changing Hadamard gates only to the second data qubit.

Use $n$ controlled-NOT gates in parallel. For each $j=1,\dots ,n$, the $j$th input qubit is the control and the $j$th output-register qubit is the target. Their combined action iswhich is exactly

For the controlled-NOT gate $U={\mathrm{CNOT}}_{12}$, propagation of the Pauli generators givesThus an $X$ on the control propagates forward to the target, while a $Z$ on the target propagates backward to the control.

Suppose $\tilde{V}$ has the same four conjugation rules and put $W=U^{†}\tilde{V}$. Then $W$ commutes with $X_1,X_2,Z_1,Z_2$. These generators span the full two-qubit operator algebra, so its commutant consists only of scalar multiples of the identity. Hence $W=e^{i\varphi }I$ and