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.

For the binary phase representation of a Pauli string, these local rules implement $P\mapsto U^{†}PU$ for the Hadamard gate and the phase gate $S=\mathrm{diag}(1,i)$. In particular $S^{†}XS=-iXZ$, so the phase update differs in sign from forward conjugation. Use the old input bits, and reduce $s$ modulo four.

With two Hadamard gates as mixers, an unobstructed zero-phase arm gives only port 0 for upper-port incidence. An ideal absorber in arm 1 acts on the intermediate superposition $(|0⟩+|1⟩)/\sqrt{2}$. It absorbs with probability $1/2$; its no-absorption branch is the unnormalized state $|0⟩/\sqrt{2}$. Recombination gives amplitude $1/2$ at each surviving output, so the dark-port success probability is $1/4$. The result assumes a calibrated transparent alternative and an ideal absorber; a dark-port event alone does not establish those apparatus assumptions.

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.

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 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].

The controlled-Z gate is $CP(\pi )=\mathrm{diag}(1,1,1,-1)$. Conjugating the target of a controlled-NOT gate by Hadamard gates turns controlled-NOT into controlled-Z.

The one-input Deutsch algorithm determines whether a Boolean function is constant or balanced using one Boolean quantum oracle call. Initialize the input qubit in $|+⟩$ and the answer qubit in $|-⟩$. Quantum phase kickback changes the input to $(-1{)}^{f(0)}(|0⟩+(-1{)}^{f(0)\oplus f(1)}|1⟩)/\sqrt{2}$. A Hadamard gate and computational-basis measurement therefore return the parity $f(0)\oplus f(1)$ with certainty.

If the input qubit of the Deutsch algorithm acquires conditional environment states with overlap $⟨e_0|e_1⟩=v{e}^{i\alpha }$ between its two Hadamard gates, its fixed zero-for-constant, one-for-balanced rule succeeds with probability $(1+v\cos \alpha )/2$. A known phase can be compensated before the last Hadamard gate, raising the success probability to $(1+v)/2$. An orthogonal pair of environment states gives $v=0$ and destroys all information in the input qubit about the answer; unit overlap modulus preserves coherence up to a known phase.

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.

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.

Share a Bell state meter pair, apply local system-to-meter CNOT gates, and measure each meter in the computational basis. The parity of the local meter records measures system $Z_A{Z}_B$ while preserving all coherence within either parity sector. The complete tuple of local records has Kraus operator $P_{u\oplus v}/\sqrt{2}$. Each local record is uniform, and the nonlocal result requires local operations and classical communication to compare records. A local Hadamard gate conjugation supplies the corresponding $X_A{X}_B$ measurement.

Share a GHZ state on $A,B,C$ and let the unknown input $Q$ be $|\chi ⟩$. Alice applies CNOT from $Q$ to $A$, then a Hadamard gate to $Q$, and measures $Q,A$ computationally, giving $s,t$. Charlie measures $C$ in the Hadamard basis, giving $c$. Bob's conditional state isup to a global phase. Alice's two bits and Charlie's one bit therefore specify Bob's inverse correction $Z^{s\oplus c}{X}^t$.

To prove the phase rule, write $|\chi ⟩=\alpha |0⟩+\beta |1⟩$. After Alice's result, $BC$ is $\alpha |tt⟩+(-1{)}^s\beta |(1\oplus t)(1\oplus t)⟩$. Taking Charlie's Hadamard basis partial inner product multiplies its second term relative to its first by $(-1{)}^c$. The remaining common phase is $(-1{)}^{ct}$, which is physically irrelevant. All eight result triples have probability $1/8$. Charlie's record localizes a known-phase Bell pair, allowing the standard Bell-basis teleportation identity to complete the transfer.

For $n\ge 2$, apply a Hadamard gate to one qubit, then controlled-NOTs from it to all others. Replacing each controlled-NOT gate by a target Hadamard, a Controlled-Z gate, and another target Hadamard uses $1+3(n-1)$ allowed gates. Each one-qubit reduced state is $I/2$, proving entanglement across each qubit-versus-rest bipartition.

Multiplying a target unitary operator by $e^{i\varphi }$ changes the controlled operation by a relative quantum phase on its control-one branch. Substitution in $C(V)=|0⟩⟨0|\otimes I+|1⟩⟨1|\otimes V$ proves the displayed identity. In particular, $C(-I)=Z\otimes I$ rather than the identity operator. Preparing the control at $|+⟩$ and applying a final Hadamard gate distinguishes $C(I)$ from $C(-I)$ with certainty, independently of the target quantum state. The global phase of an uncontrolled quantum gate is unobservable, but a specified controlled unitary gate provides a branch relative to which that phase can be measured.

Let $U_a|x⟩|b⟩=|x⟩|b\oplus (a\cdot x)⟩$ be the Boolean quantum oracle for a linear Boolean function, and put $W=H^{\otimes (n+1)}$. The CNOT gates $C_{j\to y}^{a_j}$ implement $U_a$, where the data wires control the ancilla qubit. CNOT control reversal in the Hadamard basis and $W^2=I$ imply the exact unitary operator identityHere $\oplus$ on strings is bitwise exclusive or. To conjugate a product, insert $W^2=I$ between its factors; each factor reverses its control and target, and the unused Hadamard gates cancel. The global phase is exactly $1$. In particular, the identity holds on arbitrary quantum superpositions, not only on the initialized inputs of the Bernstein-Vazirani algorithm.

For a controlled unitary gate $C(V)=|0⟩⟨0|\otimes I+|1⟩⟨1|\otimes V$, Hadamard gates on the target before and after the gate produce $C(HVH)$. Proof: the control-zero branch applies $HIH=I$, while the control-one branch applies $HVH$. Linearity extends the identity to arbitrary quantum states. Since $C(H)C(V)C(H)=C(HVH)$ too, a pair of controlled Hadamard gates surrounding the same target operation can be replaced by ordinary target Hadamard gates. No single controlled Hadamard gate is thereby identified with an ordinary one.

The Hadamard gate is the unitary operatorwhere $I$ is the identity operator. It maps the computational basis to the Hadamard basis:

These outputs have equal computational-basis measurement probabilities, but their relative quantum phase differs. Applying another Hadamard gate sends them to different definite outputs. Calling this gate a classical coin toss would discard precisely the information that makes this possible. ^[ref].

Starting from $|0⟩$, compare two quantum circuits, reading matrix products from right to left:Here $Z$ is the Pauli Z gate. After the first Hadamard gate, the probability amplitudes are $(1/\sqrt{2},1/\sqrt{2})$. Inserting $Z$ changes them to $(1/\sqrt{2},-1/\sqrt{2})$ without changing their squared magnitudes. At the final gate, the contributions to output zero cancel and those to output one add. Without $Z$, cancellation occurs at output one instead. This is controlled interference, with the quantum phase determining which answer emerges.

The same calculation works for any phase gate $P_{\varphi }=\mathrm{diag}(1,e^{i\varphi })$:For example, $\varphi =\pi /3$ gives $P(1)=1/4$, while $\varphi =\pi /2$ gives $P(1)=1/2$. The output-one amplitude at $\varphi =\pi /2$ is $(1-i)/2$: its two complex contributions add before the Born rule is applied. A phase gate alone leaves the populations unchanged; recombination converts its relative quantum phase into observable probabilities.

If quantum decoherence completely removes the computational basis coherence between the gates, the intermediate density matrix becomes $I/2$. Both the phase gate and final Hadamard gate leave $I/2$ unchanged, so $P(1)=1/2$ for every $\varphi$. The disappearing fringe explains why preserving quantum coherence matters: it enables the gate sequence to carry phase information into the final measurement.

For $|\pm i⟩=(|0⟩\pm i|1⟩)/\sqrt{2}$, direct matrix multiplication by the Hadamard gate gives coefficients $(1\pm i,1\mp i)/2$, proving the displayed identities. This exchanges the two Pauli eigenstates of the Pauli Y gate and agrees with $HYH=-Y$. The phases in the formula are global phases for each separate state; the relative phase inside each state is essential.

In a Hadamard gate, phase gate, Hadamard gate sequence starting from $|0⟩$, let a population-preserving interaction correlate $|j⟩$ with a normalized environment state $|e_j⟩$ between the two Hadamard gates. Use $P_{\phi }=\mathrm{diag}(1,e^{i\phi })$ and $⟨e_0|e_1⟩=v{e}^{i\alpha }$. The environment-valued output-zero coefficient is $(|e_0⟩+e^{i\phi }|e_1⟩)/2$, whose squared norm is the displayed probability. The modulus $v$ controls contrast, while $\alpha$ shifts the quantum interference fringe. For $v=1$ there is no mixing; a deterministic relative quantum phase accounts for the shift.