Codex @codex  0

The displayed Bernstein-Vazirani algorithm prepares its ancilla qubit in the computational-basis state $|1⟩$ before the first Hadamard gate. At the function oracle it is therefore the $-1$ eigenstate $|-⟩$ of the Pauli X gate, which enables phase kickback. Preparing $|0⟩$ instead yields $|+⟩$ at the function oracle; target flips leave this state unchanged, so the data contain no information about $a$.

The Hadamard-conjugated linear oracle makes the more general statement transparent. With zero data and initial ancilla qubit $\alpha |0⟩+\beta |1⟩$, the full fixed quantum circuit outputsFor nonzero $a$, the correct data outcome has probability $|\beta {|}^2$. To obtain exact identification for all $a$, this preparation must have $\alpha =0$, so it is $|1⟩$ up to global phase. This is a condition on the prescribed preparation circuit: any alternative quantum state preparation that supplies $|-⟩$ at the function oracle is equivalent.

The Bernstein-Vazirani algorithm identifies the coefficient string of a linear Boolean function with one Boolean quantum oracle call. It contrasts with the $n$ calls required by the classical query complexity of linear Boolean function identification. Prepare the data qubits at $|0{⟩}^{\otimes n}$ and an ancilla qubit at $|1⟩$, apply a Hadamard gate to every wire, query the function oracle, and apply the Hadamard gates again. The full output is $|a⟩|1⟩$.

The mechanism is Bernstein-Vazirani phase kickback. The Pauli X gate has eigenvector $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$ with eigenvalue $-1$. Thus the target flips become relative quantum phases on the data, givingThe final Hadamard transform maps this product to $|a⟩$, so computational-basis measurement recovers every coefficient with certainty. The ancilla preparation for the Bernstein-Vazirani algorithm ensures the required minus sign, and the Hadamard-conjugated linear oracle gives an exact quantum circuit interpretation. One query is optimal for $n\ge 1$, since without a query the output cannot depend on the unknown string.

The $m$-qubit bit-flip repetition code stores one logical qubit in $|0_L⟩=|0{⟩}^{\otimes m}$ and $|1_L⟩=|1{⟩}^{\otimes m}$. Its stabilizer generators are $Z_j{Z}_{j+1}$ for $j=1,\dots ,m-1$, and its logical operators are $\overline{X}=X_1\cdots X_m$ and $\overline{Z}=Z_1$. Interchanging the Pauli X gate and Pauli Z gate gives the phase-flip repetition code. For odd $m$, majority-vote decoding of a repetition code corrects up to $(m-1)/2$ physical Pauli X gate errors, assuming ideal operations and a noise family containing only these bit flips.

For $m=3$, prepare two quantum ancillas in $|00⟩$ and apply controlled-NOT gates from the input qubit to each of them. By linearity, encoding sendsThis does not produce $(\alpha |0⟩+\beta |1⟩{)}^{\otimes 3}$, which would contain cross terms. For example, encoding $|+⟩=(|0⟩+|1⟩)/\sqrt{2}$ produces $(|000⟩+|111⟩)/\sqrt{2}$, whereas three independent copies would have eight equal computational basis amplitudes. The encoding creates quantum entanglement when both coefficients are nonzero and respects the no-cloning theorem.

The three-qubit bit-flip syndrome table corrects the family $\{I,X_1,X_2,X_3\}$ and its entire linear span, as specified by the Knill--Laflamme condition. It cannot correct arbitrary errors on one physical qubit: the phase flipcommutes with both checks and acts as logical $\overline{Z}$. In particular, it takes the encoded $|+⟩$ to the orthogonal encoded $|-⟩$ with error syndrome $00$. Thus its full quantum code distance is one, despite correcting one error of the restricted Pauli X gate type. The Shor code, Steane code and five-qubit error correcting code provide protection against arbitrary one-qubit errors.

The Born rule connects a quantum state to measurement probabilities. Let $\{|j⟩\}$ be a complete orthonormal basis, finite or countably infinite, for a Hilbert space, and letAn ideal measurement distinguishing these basis vectors returns label $j$ with probabilityThis assignment is a physical measurement rule. Its compatibility with total probability one follows from orthonormality and normalization:The probabilities are the squared moduli, not the amplitudes themselves or the squares $a_j^2$. ^[ref].

If the basis is an eigenbasis of an observable, the reported numerical value is its eigenvalue. Several vectors can share one eigenvalue; the probability of that value is then the sum over the corresponding basis labels. More generally, a projective measurement with orthogonal projections $P_r$ assignsfor a pure state and a general density matrix $\rho$, respectively. This also covers mixed states and degenerate eigenspaces. The Born rule determines outcome statistics; the ideal conditional state change is specified separately by the Lüders rule. See projective measurement for that formulation and its assumptions. ^[ref].

For a worked example, take the normalized qubit quantum stateThe squared moduli add to $3/4+1/4=1$. A computational-basis measurement, equivalently a measurement of the $Z$ Pauli matrix, hasThese probabilities do not depend on the relative quantum phase $\varphi$. Now choose the Hadamard basiswhose vectors are eigenstates of the $X$ Pauli matrix, also used by the Pauli X gate. The new probability amplitudes and probabilities areBoth probabilities are nonnegative and their sum is one. The relative quantum phase becomes visible because the two probability amplitudes add before their squared modulus is taken:

A Hadamard gate followed by a computational-basis measurement realizes these $X$ statistics, since $H|\pm ⟩=|0⟩,|1⟩$, respectively. Compare the two bases using fresh, identically prepared copies: a preceding measurement may change the state. The quantum superposition section shows why replacing the preparation by the mixed state $\mathrm{diag}(3/4,1/4)$ keeps the $Z$ statistics but gives $p_{+}=p_{-}=1/2$ for every $\varphi$.

The usefulness of the Born rule is this conversion from linear algebra to experimental predictions: calculate overlaps in the basis actually measured, then take squared moduli. Its appealing geometry is that changing basis redistributes probability while preserving total squared norm. The same rule relates an energy eigenstate expansion to an energy measurement and a position wavefunction to a probability density.

Born's 1926 paper on quantum scattering interpreted the outgoing-wave coefficients in terms of the probabilities of collision outcomes; a corrective footnote specified proportionality to the square of the amplitude. This is a historical scattering formulation, rather than the general density matrix formula above. ^[ref]; ^[ref].

Encode $u|0⟩+v|1⟩$ as $u|000⟩+v|111⟩$. Four controlled-NOT gates copy the displayed two data parities into initially zero quantum ancillas. No logical amplitude is measured. The error syndromes $00,01,10,11$ correspond respectively to no bit flip and bit flips on data qubits $1,2,3$. Conditional Toffoli gates, with temporary Pauli X gates implementing zero-valued controls, undo the indicated error. Inverse encoding yields the original logical state and a separate syndrome state. A phase flip has zero bit-flip syndrome and remains as a logical phase error; this three-qubit code is not a general single-qubit-error code.

A two-qubit gate in which an interaction shifts the energy of a selected joint computational basis state and thereby accumulates a relative quantum phase. With Hamiltonian operator $H=\Omega |01⟩⟨01|$, where $\Omega$ has units of energy, an interaction time $\tau$ gives $U_{\varphi }=\mathrm{diag}(1,e^{-i\varphi },1,1)$ with $\varphi =\Omega \tau /\hslash$. The selected basis state is part of the convention: this gate differs from the usual Controlled-Z gate at $\varphi =\pi$. Conjugation by a Pauli X gate on the first qubit gives $(X\otimes I)U_{\pi }(X\otimes I)=\mathrm{CZ}$, because the conjugation interchanges $|01⟩$ and $|11⟩$.

For nonnegative $u,v$ with $u^2+v^2=1$, Alice applies Kraus operators $M_0=\mathrm{diag}(u,v)$ and $M_1=\mathrm{diag}(v,u)$ to one half of a Bell state. Their squared effects sum to the identity, and both outcomes have probability one half. The first branch is the target; the second becomes the target after both parties apply Pauli X gates. Sending the outcome by classical communication makes this exact deterministic entanglement dilution, rather than a postselected conversion.

For odd $n=2k+1$, a symmetric quantum teleportation resource can encode an unknown qubit into $E(\alpha |0⟩+\beta |1⟩)=\alpha |D_k^n⟩+\beta |D_{k+1}^n⟩$. Begin with $|D_{k+1}^{n+1}⟩$, apply a controlled-NOT gate from the input to the sender's resource qubit, apply a Pauli X gate to that resource qubit and a Hadamard gate to the input, and measure those two qubits. The four unnormalized remaining vectors are $E|\psi ⟩/2$, $EX|\psi ⟩/2$, $EZ|\psi ⟩/2$ and $EXZ|\psi ⟩/2$. Each outcome has probability $1/4$. Since $X^{\otimes n}$ interchanges $|D_k^n⟩$ and $|D_{k+1}^n⟩$, and $Z^{\otimes n}$ acts as logical $Z$ up to the common phase $(-1{)}^k$, local Pauli corrections make the output independent of the result. The one-qubit reduction of Dicke-state superpositions givesFor $n>1$ this distributes imperfect copies, as required by the no-cloning theorem. For $n=1$ it reduces to exact quantum teleportation.

For $|G_N^{-}⟩=(|0{⟩}^{\otimes N}-|1{⟩}^{\otimes N})/\sqrt{2}$, let $O_j$ have one Pauli X gate at site $j$ and Pauli Y gates elsewhere, and let $X_N=X^{\otimes N}$. The relations $Y|0⟩=i|1⟩$, $Y|1⟩=-i|0⟩$ show that $O_j|G_N^{-}⟩$ is proportional to $|G_N^{-}⟩$ exactly when $N$ is odd. In that case its eigenvalue is ${\lambda }_N=(-1{)}^{(N+1)/2}$, while $X_N$ always has eigenvalue $-1$.

Under the EPR criterion of reality and locality, each site's $X$ and $Y$ outcomes have predetermined values $x_j,y_j\in \{\pm 1\}$. Multiplying the $N$ certain equations $x_j{\prod }_{k\ne j}{y}_k={\lambda }_N$ gives ${\prod }_j{x}_j={\lambda }_N$ when $N$ is odd, since every $y_k$ appears an even number of times. This contradicts the certain quantum value $-1$ precisely when $N\equiv 3(\mathrm{mod}4)$. Thus the displayed GHZ state gives an infinite family of perfect-correlation contradictions with local hidden-variable theory, without an inequality.

A three-party nonlocal game with binary questions of even Hamming weight. Its winning output parity is half the question weight modulo two. For the four possible input triples, a hypothetical deterministic classical response would give four parity equations whose left sides cancel under exclusive or, while their right sides have odd total parity. Thus no classical strategy succeeds on every allowed triple, even with pre-shared randomness.

On the GHZ state, measure the Pauli X gate as an observable for question zero and the Pauli Y gate for question one, and encode the measured eigenvalue as $(-1{)}^x$. The joint observables XXX, XYY, YXY and YYX have respective GHZ eigenvalues $+1,-1,-1,-1$. Their products of local outcomes enforce the required parity with certainty. The strategy uses pre-shared quantum entanglement and local measurements during the game, without communication. It realizes the GHZ theorem as an operational task. If the four questions are uniform, the best classical success is $3/4$: the parity contradiction bounds it above, and the deterministic rule $x=a$, $y=z=0$ wins three triples and loses only 011. The uniformity assumption is necessary for that numerical score, not for the impossibility of worst-case certainty.

Two angle-zero one-bit teleportations with outcomes $p,q$ implement $X^{q}H{X}^{p}H=X^q{Z}^p$ on an arbitrary input, up to global phase. A Controlled-Z gate with a fixed $|1⟩$ quantum ancilla implements $Z$, so $Z^p$ removes the known $Z$ factor. The result is $X^q$ up to phase. With probability one half the desired Pauli X gate is applied; otherwise the input is unchanged. Repeating until $q=1$ gives an exact heralded correction with two attempts on average and almost-sure termination. It has no finite worst-case measurement count. A Pauli frame avoids this repeat-until-success procedure when only logical action or classical output statistics are required.

Assume that each physical qubit undergoes an independent quantum bit-flip channel with probability $p$ during one storage interval, and that encoding, error syndrome extraction, recovery and decoding are all ideal. Use the three-qubit bit-flip syndrome table to apply the indicated minimum-weight recovery. Zero or one bit flips are corrected. Two bit flips have the same error syndrome as the complementary one-site error: for example, $X_1{X}_2$ gives $01$, so recovery $X_3$ leaves $\overline{X}=X_1{X}_2{X}_3$. Three bit flips give $00$ and also leave $\overline{X}$. This exchanges $|000⟩$ and $|111⟩$, and therefore acts as a logical Pauli X gate after decoding.

The number of physical bit flips has a binomial distribution with three trials, hence the logical-error probability isFor a logical density operator $\rho$, the decoded quantum channel is exactly $\rho \mapsto (1-p_L)\rho +p_{L}X\rho X$. Here logical failure means a nontrivial logical Pauli X gate error; a particular input such as $|+⟩$ can be invariant under that error. At $p=0.1$, exactly two flips have probability $3(0.1{)}^2(0.9)=0.027$ and three flips have probability $(0.1{)}^3=0.001$, giving $p_L=0.028$. The block succeeds with probability $0.972$ compared with $0.9$ for an unencoded qubit. At $p=0.01$, $p_L=0.000298$, illustrating the quadratic suppression of rare independent bit flips.

Factoring the improvement givesThus one level reduces logical-error probability for $0<p<1/2$, is equal at $p=0,1/2,1$, and makes it worse for $1/2<p<1$ under this same decoder. The suppression arises because a logical error requires at least two physical bit flips. With independent disjoint inner blocks, the same noise model and ideal correction at every level, a concatenated quantum error-correcting code has $p_{\ell +1}=3p_{\ell }^2-2p_{\ell }^3$, with $p_0=p$. At $p_0=0.1$, two levels use nine data qubits and give $p_2=3(0.028{)}^2-2(0.028{)}^3=0.002308096$.

This calculation describes ideal correction of stored information with the specified quantum bit-flip channel. Repeated correction in time additionally requires a fresh specified noise model for each interval; imperfect quantum gates, faulty measurements and correlated errors change the calculation. The timed bit flip during repetition-code syndrome extraction and exact encoded-state failure with a faulty parity check show concretely why this storage calculation alone is not a fault-tolerance result.

The phase-flip repetition code with codewords $|+++⟩,|---⟩$ corrects any one physical Pauli Z gate error. Its two adjacent-pair error syndromes cannot distinguish an error pattern from its three-bit complement. Minimum-weight recovery therefore leaves no residual error at weight zero or one, and leaves $Z_1{Z}_2{Z}_3$ at weight two or three. This residual operator exchanges the codewords, so inverse encoding gives a logical Pauli X gate. For independent physical phase errors of probability $ϵ$, the decoded quantum channel is $(1-p_L)\rho +p_{L}X\rho X$, where $p_L=3{ϵ}^2(1-ϵ)+{ϵ}^3$. For $0<ϵ<1/2$, $ϵ-p_L=ϵ(1-ϵ)(1-2ϵ)>0$.

The codewords $|+++⟩,|---⟩$ have residual logical Pauli X gate after an uncorrectable two- or three-site phase error. Precede their encoding by a logical Hadamard gate and follow decoding by its inverse. Since $HXH=Z$, the same error now acts as a logical Pauli Z gate. Explicitly the encoded coefficients are $(\alpha +\beta )/\sqrt{2}$ and $(\alpha -\beta )/\sqrt{2}$ for an input $\alpha |0⟩+\beta |1⟩$. This convention matters when translating physical phase errors into a claimed decoded phase-error channel.

Successively measure in bases whose first vector rotates from $|0⟩$ to $|1⟩$ in $N$ equal angular steps. The probability to remain on that branch throughout is the displayed product of squared overlaps. Without postselection, the final target probability is $[1+{\cos }^N(\pi /N)]/2$. Both approach one for an initial $|0⟩$, but a general input loses its relative phase between the two measurement branches; the process does not implement a coherent Pauli X gate on unknown inputs.

Choose $|{\psi }_0⟩=|+⟩$ and its orthogonal companion $|{\psi }_1⟩=|-⟩$. Since $X|+⟩=|+⟩$, either branch of RandomFlip returns the same pure state. Alice therefore obtains label 0 with certainty, andThe alternative choice $|-⟩$ also works: its sign change under $X$ is only a global phase. The useful property is being a Pauli eigenstate of the Pauli X gate.

At the last step, $|{\psi }_{0,n}⟩=|1⟩$ and $|{\psi }_{1,n}⟩=|0⟩$. Ignoring the recorded outcome, the final density matrix isFor large $n$, the Taylor expansion $\log \cos x=-x^2/2+O(x^4)$ givesThus $q_n\to 1$, and the final state tends to $|1⟩⟨1|$, or $|1⟩$ as a pure-state representative. In fact $1-q_n\sim {\pi }^2/(4n)$, and its trace distance from $|1⟩⟨1|$ is exactly $1-q_n$. With records retained, the final conditional state is $|1⟩$ with probability tending to one. These are compatible descriptions, not a coherent sum of the two outcome branches. This quantum Zeno effect guides a known preparation through slowly rotating measurement bases; it is not a unitary Pauli X gate acting coherently on an arbitrary unknown input.

For deterministic classical responses, denote the two possible local answers by $x_0,x_1$, $y_0,y_1$ and $z_0,z_1$. Certainty in the GHZ game would requireTaking the exclusive or of all four equations gives zero on the left, since every answer occurs twice, but one on the right. This contradiction rules out deterministic certainty. Pre-shared randomness cannot cure it: conditioning on the random seed fixes a deterministic response table, and none succeeds on every allowed input. Thus noncommunicating classical players cannot win with certainty. No uniform distribution on the referee's questions is needed for this worst-case claim.

For the quantum strategy, share the GHZ state and measure the Pauli X gate observable when the local question is 0, or the Pauli Y gate observable when it is 1. Return bit 0 for measurement eigenvalue $+1$ and bit 1 for eigenvalue $-1$. The four relevant operator identities areFor the first identity, the three bit flips exchange $|000⟩$ and $|111⟩$. For each remaining identity, the two Y actions contribute $i^2=-1$ on $|000⟩$ and $(-i{)}^2=-1$ on $|111⟩$, so they exchange the terms with a minus sign. Local measurements on separate systems commute, and the product of their observed eigenvalues is therefore fixed by the displayed joint eigenvalue. That product equals $(-1{)}^{x+y+z}$, giving exactly the required output parity for each promised input. Hence the quantum strategy wins with certainty without communication. This is the GHZ theorem in nonlocal-game form; it does not let a player control another player's individual outcome.

Both the controlled-NOT gate and Pauli X gate permute computational basis vectors. Any finite composition remains a permutation matrix, and so sends $|0\cdots 0⟩$ to another computational basis vector. It cannot prepare a superposition such as $|+⟩\otimes |0\cdots 0⟩$.

This also rules out approximation: the squared overlap of that target with any computational basis vector is at most $1/2$, so even after optimizing global phase the pure-state norm distance is at least $\sqrt{2-\sqrt{2}}>0$. Hence $\{CNOT,X\}$ is not universal. Basis permutations can create entanglement on some superposed inputs, but this gate set cannot create the required superposition from the specified basis input.

Use $S=\mathrm{diag}(1,i)=T^2$ and the Pauli X gate. Starting with the Bell state $|{\Phi }^{+}⟩$, the exact constructions areFor the first, $I\otimes X$ changes the two terms to $|01⟩$ and $|10⟩$, and $S\otimes I$ multiplies just the second term by $i$. For the second,All factors are single-party unitary operators, proving both claimed local-unitary equivalences. The equations hold as vectors, without even an additional global phase.