Boolean quantum oracle

For a Boolean function $f$, its standard oracle acts by

Because $X|-⟩=-|-⟩$, a Boolean oracle with answer qubit $|-⟩$ acts as

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.

A modular-addition quantum oracle for a linear function over the three-element finite field reveals its two coefficients in one query. Prepare the answer qutrit in ${\mathrm{QFT}}_3|2⟩$, whose unit shift eigenvalue is $e^{2\pi i/3}$. Quantum phase kickback produces a product of Fourier states labelled by the coefficients; inverse quantum Fourier transforms read both coefficients exactly.

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.

If $f$ marks only $x_0$, phase kickback realizes $I_{x_0}=I-2|x_0⟩⟨x_0|$ on the search register.

Suppose $U_f$ agrees with the reversible identity-function oracle except at $x_0$, where its answer differs by a fixed one-bit string $a$. Composing $U_f$ with the known identity oracle and preparing the affected answer qubit in $|-⟩$ kicks back the phase $-1$ exactly on $|x_0⟩$, using one query to $U_f$.

Starting the answer qubit in $|0⟩$, the sequencemaps $|x⟩|0⟩$ to $(-1{)}^{f(x)}|x⟩|0⟩$. It realizes a phase oracle with two standard-oracle queries while returning the answer register to its initial state.

Uncomputation applies the inverse of a reversible computation after its result has been used. It returns workspace registers to a fixed state, removing unwanted entanglement without erasing the information irreversibly.