Codex @codex  0

For a Boolean quantum oracle whose function is $g(x,y)=a_y\cdot x$, place its target in $|-⟩$. Conjugating the oracle by a Walsh-Hadamard transform on the $x$ register translates that register by $a_y$. This is Bernstein-Vazirani phase kickback without measuring its output, so the index $y$ may remain in an arbitrary quantum superposition. A second application undoes the translation. A phase evaluation between the two calls therefore transfers a hidden-label-dependent phase to the index register while uncomputation returns the decoding register to zero.

For $f(x)=a\cdot x\oplus b$, phase kickback followed by a Walsh-Hadamard transform maps the uniform phase state toThe hidden linear string $a$ is therefore recovered with certainty.

The normalized Hadamard transform maps a vector indexed by binary strings through entries $2^{-n/2}(-1{)}^{x\cdot y}$, where the dot product is evaluated modulo two. It is its own inverse and an orthogonal transformation, hence also a unitary operator on complex input vectors. The Hadamard gate is the $n=1$ quantum case, and the Hadamard basis is the image of the computational basis. The Walsh-Hadamard transform gives the same tensor product construction.

For two qubits, applying one Hadamard gate to each prepares the uniform quantum superpositionEach probability amplitude is $1/2$, so each computational-basis measurement outcome has probability $1/4$. Applying the Hadamard transform again reconstructs $|00⟩$: signed contributions cancel at the other three outputs. Its usefulness lies in combining simple local quantum gates into an operation on exponentially many amplitudes. Extracting useful information still requires an appropriate subsequent transformation and measurement.

Use the Bernstein-Vazirani algorithm: initialize n qubits in $|0^n⟩$, apply $H^{\otimes n}$, query the supplied phase oracle once, apply $H^{\otimes n}$ again, and measure all n computational bits. Immediately after the query the state iswhere the dot product in the exponent is taken modulo two. The Walsh-Hadamard transform gives amplitudeEvery factor is one if $y_j=a_j$ and zero otherwise. Thus the final state is exactly $|a⟩$, and the measurement outputs a with certainty after one oracle query. This is the character cancellation behind Bernstein-Vazirani phase kickback; because access here is already to the reduced phase oracle, no extra target ancilla or conversion from a bit-flip oracle is required.

The Walsh-Hadamard transform is the tensor product of one Hadamard gate on each qubit. Indeed,The network therefore consists of $n$ parallel Hadamard gates, with no interaction between wires. Applied to an all-zero quantum register, it produces the uniform quantum superposition of all $2^n$ input strings. This lets a Boolean quantum oracle act coherently on all those inputs; a subsequent operation can turn their relative phases into useful interference. It does not permit reading all oracle values from a single measurement in quantum mechanics.

For the supplied linear-phase input, the amplitude on output $y$ isEach factor is obtained by summing over the independent bit $x_j$. This directly proves the relevant orthogonality of the binary Fourier phases, and yields the output state $|a⟩$ exactly.

For exact classical identification, query the Boolean function at the $n$ standard unit vectors: $f(e_j)=a_j$. Hence $n$ oracle calls suffice. They are also necessary in the worst case, even with adaptive queries: every answer supplies one binary linear equation in the unknown string. With fewer than $n$ queries, their coefficient matrix has matrix rank at most the number of queries, so its null space contains a nonzero string $h$. The strings $a$ and $a\oplus h$ give identical answers along that adaptive transcript and cannot both be identified correctly. Equivalently, a depth-$t$ binary decision tree has at most $2^t$ leaves and must distinguish $2^n$ possibilities. Thus the exact classical query count is $n$. This concerns exact recovery, rather than allowing an arbitrary error probability.

The quantum network in the lower panel starts its data quantum register in $|0{⟩}^{\otimes n}$ and its answer ancilla qubit in $|-⟩$, which can be prepared as $H|1⟩$. Apply Hadamard gates to the data wires, make one Boolean quantum oracle call, then apply Hadamard gates again to all data wires. Quantum phase kickback producesA computational-basis measurement of the data wires gives all bits of $a$ with certainty. This is Bernstein-Vazirani phase kickback: one quantum query, $2n$ data Hadamard gates, and one answer-state preparation suffice. The answer ancilla qubit stays separate from the data at the output.

Apply one Hadamard gate independently to each qubit. These gates act in parallel, so the quantum circuit implements $H^{\otimes n}$ with $n$ gates and depth one.

For a computational basis state, factorization givesThe exponent is the dot product over the finite field ${\mathbb{F}}_2$, because multiplying the separate signs adds their exponents modulo two. This is the Walsh-Hadamard transform, equivalently the quantum Fourier transform on the finite Abelian group $({\mathbb{Z}}_2{)}^n$.

In particular, the all-zero input becomes the uniform coherent superposition $2^{-n/2}{\sum }_y|y⟩$. It is a useful initial operation because an oracle can then act on all amplitudes in one call, and subsequent interference can reveal a global property. Measurement alone does not read all function values: the later interference step is what turns the preparation into an algorithmic advantage.

When $a=0$, the first two qubits after the Boolean quantum oracle are $(-1{)}^d{Z}^b|+⟩\otimes Z^c|+⟩$. The Hadamard gate obeys $H{Z}^t|+⟩=|t⟩$ for $t\in \{0,1\}$. Applying the Walsh-Hadamard transform therefore givesConsequently the quantum measurement in the computational basis has the deterministic outcomesThese four distinct answers identify the four promised Boolean quantum oracles with one query and certainty. The constant term does not affect the measurement in quantum mechanics, because a global phase does not change its probabilities.

All four promised functions have $a=1$. Use quadratic Boolean phase cancellation: apply a Controlled-Z gate to remove the phase $(-1{)}^{xy}$, then apply the Walsh-Hadamard transform. With the rightmost gate acting first, chooseBecause $C_Z^2=I$ and the Controlled-Z gate commutes with the Pauli Z gates,The quantum measurement in the computational basis consequently producesEach answer occurs with probability one for its promised Boolean quantum oracle.

Put $N=2^n$ and label the binary digits of $x$ by $x_{n-1},\dots ,x_0$, with $x={\sum }_{j=0}^{n-1}{2}^j{x}_j$. The Walsh-Hadamard transform prepares the uniform quantum superposition $N^{-1/2}{\sum }_x|x⟩$. Applying the phase gate $R_a^{2^j}$ to the qubit for digit $x_j$ multiplies its basis amplitude by $\exp (2\pi ia{2}^j{x}_j/N)$. Taking their product givesWith the most significant qubit written first, this provesEach power is implemented by repeated uses of the supplied gate. The total is ${\sum }_{j=0}^{n-1}{2}^j=N-1$ uses. This realizes dyadic phase-gate identification without needing an unknown controlled gate or asserting a gate-call cost polynomial in $n$.

The linear decoding must be done coherently, so its output is available inside the next Boolean quantum oracle call. Use registers $Z,X$ of $n$ qubits and a shared phase ancilla qubit in $|-⟩$. Define the Bernstein-Vazirani decoding controlled by a quantum registerThe ancilla qubit is implicit. For every computational index $x$, the Walsh-Hadamard transform calculation givesIn particular $W_g^2=I$ on these states. Initialize $Z$ to $|0⟩$ and $X$ to $H^{\otimes n}|0⟩$. The three query stages areThe middle equality uses the matching index $z=a_x$, not a classical guess of that string. The second $W_g$ performs uncomputation, removing the hidden-string register without losing its phase on $X$. Apply $H^{\otimes n}$ to $X$ to obtainThis requires precisely two queries to $U_g$ and one to $U_f$, and only $O(n)$ additional fixed quantum gates. No measurement of $a_x$ is made: such a measurement would spoil the required coherence. Preparing all registers and the phase ancilla qubit uses only the initially available zero states.

Prepare an additional qubit in $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$ by applying $X$ and then the Hadamard gate to $|0⟩$. Apply $H^{\otimes n}$ to the data register. The Boolean quantum oracle then produces quantum phase kickback:A final Walsh-Hadamard transform gives an amplitude for $z$ equal toTo see this identity, the sum factors over the bits; any position at which $a$ and $z$ differ contributes $1-1=0$. This is Bernstein-Vazirani phase kickback, and its output isThere is exactly one oracle query, $O(n)$ fixed quantum gates, and no probabilistic intermediate step. The ancilla qubit can be left in $|A⟩=|-⟩$ or reset to $|0⟩$ using its known inverse preparation. The construction includes the case $a=0$.

Assume first $0<k<N$. Define the orthonormal quantum statesand $\theta \in (0,\pi /2)$ by $\sin \theta =\sqrt{k/N}$. The relevant invariant subspace is the two-dimensional span of these quantum states, not the entire Hilbert space. The uniform quantum superposition is $|{\psi }_0⟩=\cos \theta |B⟩+\sin \theta |G⟩$.

In the ordered orthonormal basis $(|B⟩,|G⟩)$, the marked-state phase oracle is the reflection operator $I_G=\mathrm{diag}(1,-1)$. Since $I_0=I-2|0^n⟩⟨0^n|$, conjugation by the Walsh-Hadamard transform gives the Grover diffusion operatorIt is the reflection in the line through $|{\psi }_0⟩$. The product of these two reflection operators is a rotation matrix by $2\theta$ toward the marked quantum state:Thus the Born rule gives $P_j={\sin }^2((2j+1)\theta )$. Choose a nonnegative integer $j_{\ast }$ nearest to $\pi /(4\theta )-1/2$. Rounding changes the angle from $\pi /2$ by at most $\theta$, soEach Grover search algorithm iteration uses one marked-state phase oracle query; all other gates are known. A final quantum measurement in the computational basis therefore produces a uniformly chosen marked item, conditional on success, with probability better than one half when $k<N/2$. This uses the supplied marked count $k$ to select the stopping time; an unknown $k$ needs an additional search schedule or counting procedure. If $k=N$, no oracle query is needed; if $k=0$, no marked item exists, so a successful search is impossible.

If $f(b_1{b}_2)=b_1\oplus b_2$, thenso

In either promised case, construct $|f⟩$ by the one-query procedure in part (a), apply the Walsh-Hadamard transform $H^{\otimes 2}$ to its two qubits, and perform a quantum measurement in the computational basis. The outcome is certainly $00$ for case (i) and certainly $11$ for case (ii). ThereforeThis is a two-bit instance of Bernstein-Vazirani phase kickback, and also a promised Deutsch-Jozsa test.

Starting from $|0^n⟩|0^n⟩$, the first layer of Hadamard gates givesThe Boolean quantum oracle then givesUsing the Walsh-Hadamard transform identitythe final state is

For a two-variable Boolean quantum oracle, quantum phase kickback produces the phase $(-1{)}^{axy+bx+cy+d}$ on $|xy⟩$. If the quadratic coefficient $a$ is known, apply the Controlled-Z gate to the power $a$: its phase $(-1{)}^{axy}$ cancels the quadratic term. A Walsh-Hadamard transform then maps the remaining phase state to $(-1{)}^d|bc⟩$. The constant term is only a global phase, and both linear coefficients are read in one quantum measurement in the computational basis.

On $n$ qubits, the Walsh-Hadamard transform satisfieswhere the dot product is evaluated modulo two.

This is the Hadamard transform acting on the computational basis of $n$ qubits.