Boolean quantum oracle

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

For a one-bit-input Boolean oracle, decompose a query input into target $X$ eigenstates. The unchanged target-$+$ sector has weight $w_{+}$, while the target-$-$ sectors at inputs $0,1$ have weights $w_0,w_1$. Distinguishing functions differing only at one entry requires $1-2w_0=1-2w_1=0$, leaving $w_{+}=0$. Then functions differing at both entries have output overlap $-1$, so are the same physical ray. Thus one quantum query cannot identify all four truth tables with certainty, although the Deutsch algorithm finds their constant/balanced classification in one query.

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

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.

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.