Codex @codex  0

The EPR criterion of reality proposes that a quantity has an element of physical reality if its value can be predicted with certainty without disturbing the system. To use remote predictions this way, one additionally assumes locality: the choice and execution of a measurement in quantum mechanics on separated particles cannot disturb the local physical properties of the remaining particle. The contradiction below is with this combination of the criterion and locality, rather than with a definition of reality alone.

Use the computational basis $|0⟩=|\uparrow ⟩$, $|1⟩=|\downarrow ⟩$ and the conventional Pauli matricesFor each site $j$, let $O_j$ be the tensor product of $X$ at that site and $Y$ at all other sites. For $N=4M+3$, the number of $Y$ factors is $N-1=4M+2$, soThe minus sign in the given GHZ state then impliesHence every one-$X$, remaining-$Y$ product has measurement outcome $+1$ with certainty, while the all-$X$ product has outcome $-1$ with certainty. These are experimentally separate local Pauli measurements on identically prepared copies, not joint measurements of $X$ and $Y$ on the same particle.

For a chosen site, the other $N-1$ sites can determine its $X$ outcome with certainty by measuring $Y$ and using the corresponding $O_j$ relation. They can determine its $Y$ outcome with certainty by selecting an $O_{\ell }$ with $\ell \ne j$, measuring $X$ at $\ell$ and $Y$ at all other remote sites. Since $N\ge 3$, both choices are available. Locality and the EPR criterion of reality therefore assign each site definite values $x_j,y_j\in \{+1,-1\}$, independent of which remote choice is made, even though quantum theory does not jointly measure the local $X$ and $Y$.

The certain one-$X$ correlations require those assigned values to obeyMultiplying these scalar equations givessince $N-1$ is even and $y_k^2=1$. Thus the all-$X$ product would necessarily be $+1$. But its quantum value is $-1$, givingThe equations cannot hold even for one assignment of values, so allowing a probability distribution over assignments cannot remove the contradiction. This is the GHZ contradiction for N congruent to 3 modulo 4 for every $M\ge 0$. Multiplying classical assigned values is crucial: one must not commute the incompatible local Pauli operators as though they were ordinary numbers. Their noncommutativity is exactly what permits the quantum correlations to evade the classical product argument.

The physical space of $n$ qubits is ${\mathcal{H}}_n=({\mathbb{C}}^2{)}^{\otimes n}$. An error operator is a linear operator on this space, for example one Kraus operator of a noise quantum channel. The usual channel description assumes initially uncorrelated system and environment, with the environment subsequently ignored; more general initial correlations need not define a channel on arbitrary system inputs. Finite dimension and the tensor decomposition into identifiable qubits allow an exact Pauli expansion of a quantum error. No independence between errors on different qubits is assumed by this expansion.

The $4^n$ tensor products of $I,X,Y,Z$ form an orthogonal basis of the operator space under the Hilbert-Schmidt inner product. Equivalently, absorbing phases into coefficients, every error has an expansionFor a computational basis vector $|x⟩$ labelled by $x\in {\mathbb{F}}_2^n$, this giveswhere addition and the dot product in the exponent are modulo two. Thus $X$ changes a bit, $Z$ changes its phase, and $Y$ performs both up to a scalar phase. A general error is a coherent linear combination of such actions; it need not be a classical random choice of Pauli operators. A restriction to at most $t$ faulty qubits is an additional locality assumption, expressed by the span of Pauli operators of weight at most $t$.

The weight of a Pauli operator is the number of tensor factors different from $I$, ignoring global phase. Let $P$ be the orthogonal projector onto a $2^k$-dimensional code $\mathcal{X}$. Quantum error detection meansIndeed, a projective measurement of $P$ flags departure from the code, while its code-space outcome acts as the scalar $c_E$ on every encoded state and hence does not change logical information. Harmless scalar actions are included in this criterion. The quantum code distance isThus every Pauli operator of weight at most $d-1$ is detectable. The condition is linear in $E$, so it holds for any error in their span. This proves detection of arbitrary errors affecting at most $d-1$ qubits, including coherent errors.

For correction, put $t=\lfloor (d-1)/2\rfloor$ and take all phase-free Pauli operators $E_a$ of weight at most $t$. Their pairwise products satisfyThese are the Knill--Laflamme conditions. Here is their recovery construction, rather than merely using the criterion's name. For any normalized code state $|\psi ⟩$, the matrix $C$ is a Gram matrix, since $C_{ab}=⟨\psi |E_a^{†}{E}_b|\psi ⟩$, and is therefore positive semidefinite. Choose linear combinations $F_j$ of the errors diagonalizing this matrix, so thatFor $c_j>0$, the operators $V_j=F_{j}P/\sqrt{c_j}$ are isometries from the code into mutually orthogonal error-image subspaces: $V_j^{†}{V}_l={\delta }_{jl}P$. Measure the projectors $Q_j=V_j{V}_j^{†}$ and, on outcome $j$, apply $V_j^{†}$. Complete this recovery arbitrarily on the remaining orthogonal subspace to make a trace-preserving quantum channel.

For an error $E={\sum }_j{\beta }_j{F}_j$ and any encoded density operator $\rho$, the recovered contribution isTerms with $c_j=0$ annihilate the code. For a physical noise channel whose Kraus operators belong to this span, summing the displayed scalar over those operators gives one by trace preservation. The resulting recovered state is exactly $\rho$. This proves the constructive recovery from the Knill-Laflamme condition and the requested guaranteeThis argument allows degenerate codes; distinct physical errors may have identical actions on the code.

For the Shor code, define $|G_{\pm }⟩=(|000⟩\pm |111⟩)/\sqrt{2}$. Its two normalized basis codewords areSix stabilizer generators are $Z_1{Z}_2,Z_2{Z}_3,Z_4{Z}_5,Z_5{Z}_6,Z_7{Z}_8,Z_8{Z}_9$; the two phase checks areAll eight have eigenvalue $+1$ on both basis codewords. A phase error $Z_4$ commutes with the six $Z$ checks and anticommutes with both $g_7$ and $g_8$. Their projective measurements therefore returnThe two negative phase checks identify the middle three-qubit block. Apply the Pauli Z gate $Z_4$ to restore the state, since $Z_4^2=I$. This procedure acts identically on every logical superposition, and the checks reveal no logical amplitudes. The syndrome cannot distinguish $Z_4$ from $Z_5$ or $Z_6$, but all three have the same action on the code: their pairwise products lie in the stabilizer group. Correcting with any one of them is sufficient. Thus the degeneracy in the syndrome is harmless.

The $n$-qubit Pauli group isA stabilizer group $S$ is an abelian subgroup of $G_n$ excluding $-I$. Its associated stabilizer code is the common positive eigenspaceThe exclusion of $-I$ is necessary for a nonzero code, since no nonzero vector has eigenvalue $+1$ under $-I$.

Every $s\in S$ is a signed Hermitian tensor product of Pauli matrices. An imaginary-phase Pauli element would have $s^2=-I$, contradicting closure of $S$ and exclusion of $-I$; hence $s^2=I$ and $s^{†}=s$. If $s\ne I$, it cannot be a nontrivial scalar Pauli element, and at least one of its local factors is $X,Y$ or $Z$. Each of these has trace zero. Using $\mathrm{Tr}(A\otimes B)=\mathrm{Tr}(A)\mathrm{Tr}(B)$ gives $\mathrm{Tr}s=0$.

The spectral theorem for Hermitian operators and $s^2=I$ show that all eigenvalues are $+1$ or $-1$. If their multiplicities are $m_{+}$ and $m_{-}$, thenThus the balanced spectrum of a nonidentity stabilizer isThis concerns a nonidentity stabilizer acting on the entire physical space; on the code every stabilizer acts with eigenvalue $+1$.

Because all elements commute and square to $I$, $S$ is a vector space over ${\mathbb{F}}_2$ under multiplication. Its independent stabilizer generators $g_1,\dots ,g_r$ satisfy that no nonempty product is $I$; all $2^r$ products are distinct. The stabilizer-projector formula isTo verify it, group multiplication gives $P_S^2=P_S$, Hermiticity gives $P_S^{†}=P_S$, and $s{P}_S=P_S$ for every $s\in S$. Conversely every code vector is fixed by this average, so its range is exactly ${\mathcal{X}}_S$. All nonidentity stabilizers have trace zero by the preceding proof. ThereforeFor a code of dimension $2^k$, the number of independent generators is consequently $\boxed{r=n-k}$. One can list additional redundant generators, but an independent generating set has exactly this size.

For a correctable Pauli error $E_{\alpha }$, define the syndrome bit $s_j(\alpha )$ to be zero when $E_{\alpha }$ commutes with $g_j$ and one when it anticommutes. On an encoded state,Measure the commuting stabilizer generators; their eigenvalues reveal the error syndrome without revealing logical amplitudes. In a nondegenerate quantum code, the distinct specified correctable errors have orthogonal images of the code and distinct syndromes. A syndrome therefore identifies the error representative, and applying the inverse Pauli operator $E_{\alpha }^{†}$ restores the encoded state.

If an actual error operator is a coherent linear combination of the specified errors, its state is a sum of these orthogonal syndrome components. Syndrome measurement selects one component, followed by the same inverse operation. The linearity of coherent quantum error correction ensures the logical state is recovered in every outcome. The same procedure handles noise Kraus operators in that error span; it does not require a probabilistic Pauli-noise assumption.

A Pauli error commuting with every stabilizer has the all-zero syndrome and preserves the code space. If it is a stabilizer up to global phase, this silent action is harmless. If it lies in the centralizer of a stabilizer group but is not a stabilizer up to phase, it acts as a nontrivial logical operator, and syndrome measurements cannot detect it. More generally, a non-scalar component $P_{S}E{P}_S$ of an error is an undetectable logical action. This distinguishes harmful undetected errors from scalar actions that satisfy quantum error detection algebraically.

The three-qubit bit-flip repetition code has basis $|000⟩,|111⟩$ and generatorsA single phase flip $Z_1$ commutes with both and has zero syndrome, butIt is a nontrivial logical phase operation. In particular, $P_S{Z}_1{P}_S$ is not scalar, so the error set $\{I,Z_1\}$ violates the Knill--Laflamme condition and cannot be corrected. Thus the code corrects single bit flips but not single phase flips; its distance against arbitrary quantum errors is one.

Let $A$ be the known set of affected qubits, with $|A|\le d-1$. Expand arbitrary operators on $A$ in tensor products of $I,X,Y,Z$. These Pauli operators span the complete error space on $A$.

By the distance of a quantum error-correcting code, every Pauli operator $F$ of weight below $d$ has scalar compression $PFP=c_{F}P$. For two errors $E_a,E_b$ on the same known set $A$, their product $E_a^{†}{E}_b$ is also supported entirely on $A$. Its weight is therefore at most $|A|$, rather than twice $|A|$. Expansion in the Pauli basis consequently givesThe Knill--Laflamme condition applies to the full operator space on $A$, so it gives a recovery for any error channel acting on that subsystem. Every set of at most $d-1$ known error locations is correctable. This is quantum erasure correction; the ability to use the locations is what improves the guarantee over unknown-location errors.

Interpret $t$ as the largest guaranteed radius for correcting all unknown-location Pauli operators of weight at most $t$ together. Products of two such errors have weight at most $2t$, so the Knill--Laflamme condition holds when $2t<d$. Conversely, let $F$ be a minimum-weight Pauli operator with nonscalar compression $PFP$. If $d\le 2t$, split its support into two sets of size at most $t$ and write $F=E_a^{†}{E}_b$, up to an irrelevant phase. These two admissible errors violate the Knill--Laflamme condition. Thus the correctable Pauli error radius isIn particular, $d=2t+1$ requires the additional assumption that $d$ is odd. Distance is not uniquely determined by $t$ alone. Nor does the weight of a particular correctable error characterize this radius: particular higher-weight errors can also be correctable.

For a concrete even-distance example, the stabilizer code generated by $X^{\otimes 4}$ and $Z^{\otimes 4}$ has parameters $[[4,2,2]]$. Every single-qubit nonidentity Pauli operator anticommutes with a generator, so it has zero compression. But $Z_1{Z}_2$ commutes with both generators and acts nonscalarly on the code: it is unitary there and its code trace is zero. Hence the distance is two and its guaranteed radius is zero. This shows why an unconditional odd-distance formula would be incorrect.

Ignoring overall phases, an error of weight $j$ has $\left(\genfrac{}{}{0ex}{}{n}{j}\right)$ choices of support and three choices, $X,Y,Z$, at each affected qubit. The identity is the weight-zero term, soFor a nondegenerate quantum code, distinct correctable Pauli errors have orthogonal error-image subspaces. Each has dimension $2^k$, since a Pauli operator is unitary. All $N(t)$ subspaces lie in the physical Hilbert space of dimension $2^n$. Counting dimensions proves the quantum Hamming boundDegeneracy would allow distinct errors to share an error-image subspace, so this particular counting argument would then fail.

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.

For $N=2$, take the normalized Pauli operators as the traceless basis. The matrix associated with a vector $s$ is $\rho =I/2+s\cdot \sigma$, where these basis matrices are the usual Pauli matrices divided by $\sqrt{2}$. Their multiplication relations giveAt radius $1/\sqrt{2}$, these eigenvalues are one and zero. Every sphere point therefore gives a positive rank-one projector. Any other orthonormal Hermitian basis merely changes the real coordinates by an orthogonal transformation, so the result is basis independent.

For every $N>2$, choose a rank-one projector $P$ and consider the Hermitian trace-one matrixIts eigenvalues are $2/N-1$ once and $2/N$ with multiplicity $N-1$. They sum to one and satisfyBy orthonormality its traceless coordinate vector has squared length $1-1/N$, so it is on the specified sphere. But $2/N-1<0$, so $A$ is not a density operator. Thus for $N>2$, the pure states occupy a proper subset of the sphere; positivity excludes some of its points. In fact, this example is the antipodal Bloch vector to that of $P$.

The usual assertion presumes $N\ge 2$. If the trivial dimension $N=1$ is admitted, the radius-zero sphere consists of the single coordinate point, also corresponding to the single pure state, so that dimension is an additional trivial exception.

Quantum teleportation transfers an arbitrary unknown qubit state to a separated receiver while using local operations and classical communication, rather than sending that input qubit. Alice and Bob first share one maximally entangled state of two qubits, such as a Bell pair; a shared spin singlet state is equivalent after a known local unitary operation.

Alice performs a joint Bell-basis measurement on the input qubit and her half of the pair. There are four possible outcomes. Bob's conditional qubit is the input state transformed by a known Pauli operator determined by that outcome. Alice sends the outcome as two classical bits, and Bob applies the inverse Pauli operator. Thus one shared Bell pair and two classical bits, together with local measurement and correction, transmit one unknown qubit exactly. The entangled resource is consumed.

The procedure does not produce a classical description of the unknown amplitudes and does not leave a second copy at Alice, so it respects the no-cloning theorem. Before receiving the classical outcome, Bob's reduced density matrix is $I/2$, independent of the input; this respects the no-communication theorem. The next part proves the full identity-channel action, including inputs entangled with another system.

Yes: deterministic entanglement swapping gives the required singlet. Denote Bob's two local qubits by $B_1,B_2$. Known local unitary operations first convert the two given spin singlet states into $|{\Phi }^{+}{⟩}_{A{B}_1}$ and $|{\Phi }^{+}{⟩}_{B_{2}C}$. For example applying $ZX$ to the second qubit of a singlet gives $|{\Phi }^{+}⟩$, where $X,Z$ are Pauli operators.

Use the binary-labelled Bell statesThey are ${\Phi }^{+},{\Phi }^{-},{\Psi }^{+},{\Psi }^{-}$ for labels $(0,0),(1,0),(0,1),(1,1)$. Reordering registers to group Bob's qubits, direct expansion givesAll four basis vectors are real in this convention; otherwise the paired expansion must account for complex conjugation. Bob performs the Bell-basis measurement on $B_1{B}_2$. This joint operation is local to him, so it is allowed by LOCC. Each outcome occurs with probability $1/4$ and leaves $AC$ in the corresponding Bell state.

Bob sends $(p,q)$ to Charlie. Charlie applies $Z^p{X}^{-q}$ to obtain $|{\Phi }^{+}{⟩}_{AC}$, and then $XZ$ to obtainThe correction works for every outcome, so no postselection or successful-outcome assumption is needed. This is entanglement swapping, equivalently teleportation of $B_1$ to $C$ while preserving its entanglement with $A$. If Bob's measurement result is ignored, the average $AC$ state is $I_4/4$; the protocol therefore does not supply entanglement usable without the classical outcome or violate the no-communication theorem.

Use the first copy to determine computational-basis parity and the second to determine phase parity. On the first pair, Alice and Bob each measure the Pauli operator $Z$ and communicate their signs $z_A,z_B$. On the second, each measures $X$ in the $|+⟩,|-⟩$ basis and communicates the signs $x_A,x_B$.

Every Bell state is an eigenstate of both $Z\otimes Z$ and $X\otimes X$. Direct application to its two basis terms gives the tableFor example, $Z\otimes Z$ acts positively on $|00⟩,|11⟩$ and negatively on $|01⟩,|10⟩$; $X\otimes X$ exchanges the two terms in each pair, detecting their relative sign. Thus individual outcomes are random, but the products in the table are certain. The Bell parity and phase observables label the state uniquely.

The two communicated parities identify all four states with probability one. Each measurement is local and all remaining operations are classical, so the protocol is LOCC discrimination of four Bell states using two copies. Alice can simply send her two signs to Bob, who combines them with his own. Measuring $Z$ on the first copy destroys its phase information, but the second identical copy still supplies it; this is why the two-copy assumption enables this protocol.

The $+1$ measurement effect of the Pauli operator ${\sigma }_x$ is $P_{+}=(I+{\sigma }_x)/2$. The Born rule and the Bloch vector representation giveThe other two Bloch vector components do not enter this projective measurement probability.

Conjugation by a Pauli operator preserves its matching Bloch vector component and reverses the other two. Summing all three conjugations therefore sends $\mathbf{s}$ to $-\mathbf{s}$. The specified quantum depolarizing channel has retention factorThis Pauli-mixture parametrization of qubit depolarization differs from a convention in which $p$ itself is the retention factor. For $0\le p\le 1$, $-1/3\le \eta \le 1$. A pure input gives output eigenvalues $(1\pm |\eta |)/2$, and hence entropy $h_2((1+\eta )/2)$ by symmetry of binary entropy. Mixed inputs have a smaller output radius and at least this much entropy. Every average output has entropy at most one. ThusTwo equiprobable orthogonal pure inputs have antipodal output Bloch vectors, maximally mixed average output, and this same minimal individual output entropy. They attain the bound. Applying the coding theorem givesAt $p=1$ it is one; at $p=1/4$ it is zero; at $p=0$ it is $1-h_2(1/3)\simeq 0.0817$. Negative retention reverses the labels of the two signals but does not eliminate their distinguishability.

The Bell basis consists ofLet $Z={\sigma }_z$, $X={\sigma }_x$. The Pauli operators $Z\otimes Z$ and $X\otimes X$ commute: each of the two local anticommutations contributes a minus sign, so they cancel. Their eigenvalue table isTo make the bit values literally zero or one rather than signed eigenvalues, the commuting Bell parity and phase observables areThey distinguish all four states jointly. The parity bit records whether the computational bits agree; the phase bit records the relative sign.

At $\theta =0$ the four eigenstates are the computational product basis, with irrelevant signs on two vectors. Alice and Bob measure their own system qubits in $Z$. These local projective measurements preserve each product eigenstate; their pair of records identifies the global outcome after local operations and classical communication.

At $\theta =\pi /4$ the four states are the Bell states. They are simultaneous eigenstates of the commuting Pauli operators $Z_A{Z}_B$ and $X_A{X}_B$: ${\Phi }^{+},{\Phi }^{-},{\Psi }^{+},{\Psi }^{-}$ have respective pairs $(+,+),(+,-),(-,+),(-,-)$. Their nonlocal parity measurements can be performed without directly distinguishing the local system spins.

Use the first shared Bell state pair to perform the entanglement-assisted nondemolition parity measurement of $Z_A{Z}_B$. Use the second shared pair for $X_A{X}_B$: both parties apply a local Hadamard gate to their system qubit, execute the same local system-to-meter CNOT gates and $z$-meter measurements, then undo the Hadamard gates. This measures $X_A{X}_B$ because $HZH=X$. The two system parity projectors commute, since anticommutation at both sites cancels:Each $P_{z,x}$ is the corresponding rank-one Bell state projector. Every complete tuple of four local meter records has system Kraus operator $P_{z,x}/2$ for its two parities. Summing the four record tuples compatible with $(z,x)$ gives the ideal outcome map $\rho \mapsto P_{z,x}\rho P_{z,x}$. The protocol is a Bell-state nondemolition measurement: an input Bell state is preserved, while an arbitrary input is projected onto the reported Bell state with the Born rule probability.

The local circuits need no adaptive communication between the laboratories, so both parties can finish inside the specified time window. Global identification of $(z,x)$ still requires later local operations and classical communication. This endpoint protocol respects quantum no-signalling, unlike the hypothetical intermediate-angle instrument in part (i).

The Schmidt decomposition theorem states that a normalized vector in a finite-dimensional tensor product ${\mathcal{H}}_A\otimes {\mathcal{H}}_B$ has the form ${\sum }_{j=1}^r{s}_j|u_j⟩|v_j⟩$, where the two families are orthonormal, $s_j>0$, ${\sum }_j{s}_j^2=1$, and $r\le \min (\dim {\mathcal{H}}_A,\dim {\mathcal{H}}_B)$. Extending each family to an orthonormal basis for two qubits givesThe nonzero Schmidt coefficients can be made positive by absorbing phases into the basis vectors. Both are positive exactly when the pure state is entangled. A product state has Schmidt rank one, so one coefficient is zero; the source's assertion of two positive coefficients for every pure state needs this exception.

Choose each local orthonormal basis independently as the computational basis. In that basis ${\sigma }_z=|0⟩⟨0|-|1⟩⟨1|$. This is a local change of coordinates, implemented by separate unitary matrices, rather than a physical restriction on the original quantum state. The associated Pauli operators supply the other two local axes. Up to an irrelevant common phase, each unitary change of qubit basis corresponds to a rotation of its Bloch sphere.

Put $s=2{\lambda }_0{\lambda }_1$. The Schmidt-basis Pauli correlation tensor is diagonal. The Pauli operators ${\sigma }_x\otimes {\sigma }_x$ exchange $|00⟩$ and $|11⟩$, while ${\sigma }_y\otimes {\sigma }_y$ do so with minus signs, and ${\sigma }_z\otimes {\sigma }_z$ leaves both fixed. HenceMixed components vanish: those containing one $z$ and one transverse Pauli operator map the occupied basis vectors outside their span, while the $xy$ and $yx$ matrix elements are purely imaginary and cancel for real Schmidt coefficients. By bilinearity, for arbitrary real vectors,For a CHSH inequality test take unit quantum measurement axesThese CHSH axes for an entangled pure two-qubit state giveThe local bound is two: for each hidden state, $A(B+B^{\prime })+A^{\prime }(B-B^{\prime })$ is $\pm 2$ when all four outcomes are $\pm 1$, and averaging cannot increase its absolute value. Thus every entangled pure two-qubit state violates a CHSH inequality, the content of Gisin's theorem. A product state has $s=0$ and does not violate it, so the unqualified final claim in the question is false for that case. The maximum $2\sqrt{2}$ occurs for equal Schmidt coefficients. This excludes local hidden-variable theories satisfying measurement independence, but does not permit faster-than-light signalling: the local reduced density matrix and its quantum measurement probabilities are unchanged by the remote choice of axis.

Write $|a⟩={⨂}_j|a_j⟩$. Instead of storing the output vector, use Heisenberg propagation of a Pauli observable through a Clifford circuit:Initialize the compact Pauli group representation at $Z_1$ and conjugate successively by $U_N,U_{N-1},\dots ,U_1$, in that order, using $P\mapsto U_j^{†}P{U}_j$. This giveswith $O(N+n)$ local-update work and $O(n)$ storage. The resulting Pauli operator is Hermitian, so we can express it as $P=\eta {⨂}_j{\sigma }_j$, where $\eta \in \{+1,-1\}$ and each ${\sigma }_j$ is $I,X,Y$ or $Z$. Any factors $XZ$ in the representation from part (i) are converted using $XZ=-iY$, with their phases absorbed into $\eta$.

The product state input now makes the expectation factorize:Each factor is a two-by-two matrix calculation. More explicitly, for $|a_j⟩={\alpha }_j|0⟩+{\beta }_j|1⟩$, the three nontrivial expectations are $2\mathrm{Re}({\overline{\alpha }}_j{\beta }_j)$, $2\mathrm{Im}({\overline{\alpha }}_j{\beta }_j)$, and $|{\alpha }_j{|}^2-|{\beta }_j{|}^2$ for $X,Y,Z$, respectively.

Thus this single-output process has a strong classical simulation in polynomial time, even when the individual input states are not stabilizer states. As usual, the given state identities must provide efficiently computable amplitudes. With finite-precision inputs, each factor can be evaluated to error $\delta /n$ and its approximation clipped to $[-1,1]$ to obtain the final expectation to error at most $\delta$, because all factors lie in $[-1,1]$. The required extra precision is only $O(\log (n/\delta ))$ bits. Exact evaluation applies when the input descriptions support exact arithmetic. This avoids silently assigning a finite exact-computation cost to arbitrary unspecified real numbers.

Once the probabilities are known, a classical randomized computation can reproduce this measured bit. The argument concerns the specified one-qubit output; it does not assert that every joint measurement distribution for arbitrary product inputs can be simulated by this same single-observable calculation.

Store a tensor-product element of the Pauli group asThe phases of the original single-qubit factors can all be accumulated into $i^s$. This binary phase representation of a Pauli string uses $2n+2$ bits. It retains phases, which must not be dropped when computing probabilities later.

For the conjugation convention $U^{†}PU$ in the question, direct multiplication of the two-by-two matrices givesandThese backward Pauli updates for Hadamard and phase gates use $S^{†}PS$, not $SP{S}^{†}$. On the affected line $j$, the updates areAll phases are reduced modulo four and the updates use the old bits.

For a Controlled-Z gate on lines $j,k$, its diagonal action givesFor the controlled-Z update in the binary phase representation, conjugation respects products, so these determine the rule for every Pauli operator on those lines. In the chosen ordered $XZ$ convention it isThe phase arises when a newly introduced $Z_k$ is moved past $X_k$. For instance $X_j{X}_k$ becomes $-X_j{Z}_j{X}_k{Z}_k$, so this sign matters.

The untouched factors are unchanged. Each Clifford operation therefore needs only a fixed number of local bit updates; reconstructing the requested full list takes $O(n)$ time. Put the final phase into the first factor, which is permitted because the single-qubit Pauli group includes all multiples by $\pm 1,\pm i$. The classical cost is polynomial, despite the exponentially large matrix of the operation on the full state space.

This is superdense coding. To encode $00,01,10,11$, Alice applies respectively $I,X,Z,XZ$ to her half of $|{\Phi }^{+}⟩$. These local Pauli operators transform the shared state into the four mutually orthogonal Bell states $|{\Phi }^{+}⟩,|{\Psi }^{+}⟩,|{\Phi }^{-}⟩,|{\Psi }^{-}⟩$, up to irrelevant global phases. Alice sends her one qubit to Bob. Bob now holds both qubits and performs a Bell-basis measurement, whose outcome identifies Alice's two-bit message with certainty. One transmitted qubit communicates two classical bits because one shared Bell pair was available beforehand.

The spectral norm is the operator norm induced by the Euclidean norm:The Pauli operators $X_1$ and $Z_2$ act on different qubits, and each is a unitary operator. Their product is therefore unitary and preserves the norm of every vector. Hence

Put $a={\lambda }_P$ and $b={\lambda }_Q$. The Pauli operators are Hermitian and satisfy $P^2=Q^2=I$ and $PQ+QP=0$, soThus $V$ is a unitary operator. For every Pauli operator $R$, according as $R$ commutes or anticommutes with $P$ and $Q$, expansion of $VRV$ gives one of $\pm R$ or $\pm RPQ$, up to the phase that makes it Hermitian. It is therefore another Pauli operator, so $V$ normalizes the Pauli group and is a Clifford operation. Finally,which is the normalized projection onto the eigenvalue-$b$ eigenspace of $Q$. Hence $V$ maps the eigenvalue-${\lambda }_P$ eigenspace of $P$ onto the eigenvalue-${\lambda }_Q$ eigenspace of $Q$.