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.

Charlie cannot send a bit to Alice with the stated preparation, fixed interaction and final local measurements. Write $V={\mathrm{CNOT}}_{B\to A}$ and $W={\mathrm{CNOT}}_{B\to C}$, so the complete gate is $U=WV$ with the rightmost gate acting first. Alice has finished interacting before the gate involving Charlie acts.

For arbitrary product input density matrices, put ${\tau }_{AB}=V({\rho }_A\otimes {\rho }_B)V^{†}$. The final reduced density matrix of Alice isThe equality follows because a unitary operator on the traced-out systems leaves the partial trace unchanged. The right-hand side is independent of Charlie's preparation. Therefore every outcome probability of every local measurement by Alice is independent of Charlie's message. Quantum no-signalling applies after Alice's last interaction, even though phase kickback can allow communication between the two qubits of an individual CNOT gate.

Reverse communication is also possible. Prepare Alice in $|+{⟩}_A$. Bob encodes $m=0$ as $|+{⟩}_B$ and $m=1$ as $|-{⟩}_B$. Since $X|\pm ⟩=\pm |\pm ⟩$, phase kickback giveswhere $|(-{)}^0⟩=|+⟩$ and $|(-{)}^1⟩=|-⟩$. Alice measures in the Hadamard basis: $+$ means zero and $-$ means one, deterministically.

The target's Pauli X gate eigenvalue becomes a relative phase on the control. This is the operational content of CNOT control reversal in the Hadamard basis; the computational basis control arrow alone does not determine every possible direction of communication.

Use the Hadamard basis states $|\pm ⟩=(|0⟩\pm |1⟩)/\sqrt{2}$. The Hadamard gate satisfies $H|0⟩=|+⟩$, $H|1⟩=|-⟩$, and $H^2=I$. After the first three Hadamard gates, the full quantum state isThe Pauli X gate obeys $X|-⟩=-|-⟩$. Consequently the Boolean quantum oracle produces phase kickback:Factoring out the ancilla qubit, the four states immediately after the function oracle areThe final Hadamard gates send $|+⟩$ to $|0⟩$ and $|-⟩$ to $|1⟩$. In particular, the printed quantum circuit includes a final Hadamard gate on the ancilla qubit too. Its full outputs, ordered as $x_1,x_2,y$, areThus one oracle call identifies $a$ with certainty: a computational-basis measurement of the first two qubits returns $a_1{a}_2$. The ancilla qubit returns to $|1⟩$ and carries no additional information about $a$. The Bernstein-Vazirani algorithm turns the pattern of relative quantum phases into a definite computational-basis state.

The required identity is CNOT control reversal in the Hadamard basis. To derive it using standard quantum circuit identities, let $\mathrm{CZ}$ be the Controlled-Z gate, which multiplies $|11⟩$ by $-1$ and fixes the other computational-basis states. Since $HXH=Z$,The Controlled-Z gate is symmetric in its two wires. Combining this symmetry with $H^2=I$ givesThis is an exact operator identity, including its global phase, and applies to arbitrary inputs. One can also check it directly from the orthogonal projectors $P_b=|b⟩⟨b|$: conjugating $C_{1\to 2}=P_0\otimes I+P_1\otimes X$ by $H\otimes H$ gives

For the three-wire quantum circuit, put $W=H^{\otimes 3}$. Conjugation distributes over products because $W^2=I$: $WABW=(WAW)(WBW)$. Each CNOT gate in $U_a$ therefore reverses direction, while the Hadamard gates on untouched wires cancel. The Hadamard-conjugated linear oracle isThese are the simplified quantum circuits in the figure: for $a=00$ there are no gates; for $a=01$ there is $C_{y\to 2}$; for $a=10$ there is $C_{y\to 1}$; and for $a=11$ there are both. The ancilla qubit becomes their common control. On every computational-basis state, the entire simplified circuit acts asStarting the data qubits at $|00⟩$, the prescribed computational basis preparation of the ancilla qubit must therefore be $|1⟩$: it activates the required flips and gives $|a⟩|1⟩$. Starting it at $|0⟩$ instead gives $|00⟩|0⟩$ for every $a$, so no information is obtained.

More generally, an initial ancilla qubit state $\alpha |0⟩+\beta |1⟩$ in this same fixed quantum circuit givesFor nonzero $a$, the desired data output has probability $|\beta {|}^2$, and exact identification for every $a$ requires $\alpha =0$. This condition refers to the displayed ancilla preparation for the Bernstein-Vazirani algorithm: the state entering the function oracle must be $|-⟩$, up to global phase. Other quantum state preparation procedures that deliver this same state are equivalent; $|1⟩$ is the prescribed input before the first Hadamard gate.

For arbitrary $n$, linearity of the linear Boolean function suppliesThis decomposition is for analysis: the Bernstein-Vazirani algorithm calls the unknown function oracle as one supplied operation. The common control starts at $1$, so the simplified quantum circuit takes $|0{⟩}^{\otimes n}|1⟩$ to $|a⟩|1⟩$. Equivalently, phase kickback gives a product statewhich the final Hadamard transform decodes to $|a⟩$. Thus one quantum oracle call suffices for every $n\ge 1$, compared with $n$ classical calls. This counts function oracle uses; the surrounding Hadamard gates and final computational-basis measurement still act on $n+1$ and $n$ qubits, respectively.

A constant function has $f(0)=f(1)$, whereas a balanced one has one zero and one one, so $f(0)\ne f(1)$. The four oracles require only the following circuits:Prepare $|0⟩|1⟩$, apply a Hadamard gate to each qubit, apply the oracle once, apply another Hadamard gate to the first qubit, and measure that first wire in the computational basis. Immediately before the oracle the state is $|+⟩|-⟩$. The identity $X|-⟩=-|-⟩$ gives phase kickback:The output is certainly zero for constant and one for balanced. In circuit terms the target $X$ contributes only a global sign, and a controlled $X$ with target $|-⟩$ acts as $Z$ on the control; $HZH=X$ then turns that phase into a measured bit. These identities prove the network for all four explicit oracles. The unused sign contains $f(0)$ only as a global phase, consistent with the full-identification lower bound.

The Hadamard gate H and T gate $T=\mathrm{diag}(1,e^{i\pi /4})$ form a universal quantum gate set for single-qubit operations: finite sequences approximate any target single-qubit unitary arbitrarily well, up to a physically irrelevant global phase. Universality is not a claim that every arbitrary rotation has a finite exact H,T word. With products acting right to left, exact Pauli constructions areIndeed $T^2=S$, $T^6=S^{†}$, and $SX{S}^{†}=Y$.

Initialize the search register in $|00⟩$ and the output qubit in $|1⟩$, then apply H to all three. The search state becomes $|s⟩=(|00⟩+|01⟩+|10⟩+|11⟩)/2$, and the output becomes $|-⟩$. The oracle obeysThis phase kickback leaves the output qubit factored out, so subsequent analysis can use the phase oracle $O_f$ on the two search qubits alone. Apply one Grover diffusion operator $D=2|s⟩⟨s|-I$, then measure the search register.

A promise restricts which Boolean functions may be supplied. For the exact one-iteration four-entry search here, promise exactly one marked input. The four functions are $f_{jk}(x)=1$ precisely when $x=jk$, for $jk\in \{00,01,10,11\}$. Other known numbers of marked entries require a correspondingly chosen iteration count; uniqueness is the promise for this particular exact circuit.

In basis order $00,01,10,11$, the requested explicit calculation isThus the promised marked entry is found with probability one.

For two weakly coupled spin-half nuclei in nuclear magnetic resonance, a useful rotating-frame Hamiltonian iswhere $J$ is in hertz and $I_z=Z_1/2$, $S_z=Z_2/2$. Resonant pulses and refocusing separate local rotations from the scalar coupling. For positive $J$, evolution for $t=1/(2J)$ supplies $e^{-i\pi Z_1{Z}_2/4}$. Combining it with local Z phases gives the phase oracleThe scalar global phase is immaterial. Local $\pi$ pulses interchange zero and one, soThis implements the desired change of marked input without an additional output qubit.

Let $x\in \{00,01,10,11\}$ and let $f(x)$ be one only at the marked input. A three-qubit implementation of Grover's algorithm starts with $|00⟩|1⟩$, applies a Hadamard gate to each qubit, queries the reversible quantum oracle $U_f:|x,y⟩\mapsto |x,y\oplus f(x)⟩$, applies the Grover diffusion operator $D=2|s⟩⟨s|-I$ to the first two qubits, and measures those two qubits in the computational basis. Here $|s⟩=\frac{1}{2}{\sum }_x|x⟩$. The full three-wire quantum circuit is the composition

Here $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$. Since $X|-⟩=-|-⟩$, phase kickback gives $U_f(|x⟩|-⟩)=(-1{)}^{f(x)}|x⟩|-⟩$. The third qubit remains separable and unchanged. A direct marked-state phase oracle $O_f|x⟩=(-1{)}^{f(x)}|x⟩$ therefore replaces the three-qubit query using only two qubits:For the explicit choice $f(x)=1$ only at $x=11$, $O_f$ is a Controlled-Z gate. Immediately after it,The mean of these four probability amplitudes is $\overline{a}=1/4$. The Grover diffusion operator maps each probability amplitude $a_x$ to $2\overline{a}-a_x$. The three unmarked probability amplitudes become zero and the marked one becomes one. A single query consequently finds $11$ with probability one.

A gate-level implementation of $D$ is $H^{\otimes 2}(2|00⟩⟨00|-I)H^{\otimes 2}$. Up to an irrelevant global phase, it is $H^{\otimes 2}{X}^{\otimes 2}\mathrm{CZ}{X}^{\otimes 2}{H}^{\otimes 2}$. For any other chosen marked word, conjugate the Controlled-Z gate by Pauli X gates on precisely the positions where the marked word has a zero.

Let $U={\sum }_b{U}_b^A\otimes |b⟩⟨b{|}_B\otimes V_b^C$, where the conditional target operators are unitary. For product input ${\rho }_A\otimes {\rho }_B\otimes {\rho }_C$,Tracing over $B$ removes cross terms with unequal control labels. Tracing over $A$ leaves $\mathrm{Tr}(U_b{\rho }_A{U}_b^{†})=1$, proving the formula and its independence of ${\rho }_A$. Exchanging $A$ and $C$ proves the corresponding reverse independence. Thus the two targets cannot signal to each other through this fixed common-control interaction, despite phase kickback allowing a target to affect its control.

Two controlled-NOT gates with a common control and distinct targets are an example. They commute; their chronological order can be exchanged, giving an equivalent causal proof. Intervening control rotations or additional interactions can change the conclusion.