Codex @codex  0

A Boolean function on a finite nonempty domain is balanced when it is zero on exactly half the inputs and one on the other half. For a one-bit domain, the balanced functions are $f(x)=x$ and $f(x)=1\oplus x$, while the remaining two functions are constant functions. The Deutsch algorithm distinguishes these two classes with one Boolean quantum oracle query in the absence of noise.

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.

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.

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.

A function oracle supplies access to an unknown function $f$: given an allowed input $x$, one query returns $f(x)$. Query complexity counts these accesses separately from known local computation. A classical query receives one definite answer; a quantum oracle specifies coherent access through a unitary operator, allowing inputs in quantum superposition. The distinction is part of the access model, not a change to the mathematical function.

A Boolean quantum oracle preserves $x$ and adds a one-bit value $f(x)$ into an answer qubit by exclusive or. On known computational-basis states, its output determines the same value as a classical function oracle query.

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.

Normalize the second qubit as $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$. Since a Pauli X gate changes $|-⟩$ to $-|-⟩$, the Boolean quantum oracle acts asThis quantum phase kickback leaves the second qubit uncorrelated with the first. Put $b=f(0)\oplus f(1)$: $b=0$ for a constant function and $b=1$ for a balanced Boolean function. Apart from the irrelevant global phase $(-1{)}^{f(0)}$, the first qubit and environment reachThe population-preserving interaction commutes with the quantum oracle on this answer-register input, so its placement before or after the oracle, between the two Hadamard gates, gives the same result. Substitute $\phi =\pi b$ into b:The printed Deutsch algorithm uses the rule zero means constant function; one means balanced Boolean function. With that rule, the Deutsch algorithm with pure dephasing succeeds for either class withFor real nonnegative environment overlap this is $(1+v)/2$, ranging from certainty at $v=1$ to random guessing at $v=0$. For general complex overlap, a coherent shift can invert the printed answer: for example $v=1,\alpha =\pi$ makes the printed rule always wrong. If the overlap is known but the printed quantum measurement is retained, choose the better labeling of its outcomes; this givesThere is a further improvement if a known $\alpha$ can be compensated by the phase gate $P_{-\alpha }$ before the final Hadamard gate. It removes the coherent shift without reversing any actual quantum decoherence, and yieldsThis is optimal when only the first qubit is accessible, with equal prior probabilities for the two classes. Before the final Hadamard gate, their reduced density matrices areThe difference ${\rho }_0-{\rho }_1$ has eigenvalues $\pm v$, giving trace distance $v$. The Holevo–Helstrom theorem therefore bounds the success probability by $(1+v)/2$, exactly attained by the compensated procedure. A known phase shift and loss of coherence have different effects: at $v=0$ the two density matrices coincide and no measurement on the available qubit can reveal the answer.

Write $a=a_1{a}_2$ and $x=x_1{x}_2$, with the top wire carrying $x_1$, the middle wire $x_2$, and the bottom wire the ancilla bit $y$. The binary inner product is $a\cdot x=a_1{x}_1\oplus a_2{x}_2$, where $\oplus$ is exclusive or. Let $C_{j\to y}$ denote a CNOT gate controlled by wire $j$ and targeting $y$. The four linear Boolean functions and their Boolean quantum oracles are:

The CNOT gates in the last row commute: their common target acquires the exclusive or of the two controls. Each input wire is preserved, and applying any of these reversible circuits twice restores $y$.

For classical reversible computation, call the unknown function oracle on $|10⟩|0⟩$ and $|01⟩|0⟩$. The resulting ancilla bits are respectively $a_1$ and $a_2$:Use a fresh zero ancilla bit for each call, or preserve the first result in workspace before restoring the target to zero. Thus two classical calls determine the two-bit string.

For $n$ input bits, query the standard basis strings $e_j$, since $a\cdot e_j=a_j$. This gives an upper bound of $n$ calls. It is also optimal for exact identification: every classical query reveals at most one new bit, since $x$ is unchanged and $y\oplus f_a(x)$ reveals just $f_a(x)$ when $y$ is known. A depth-$k$ decision tree has at most $2^k$ answer histories, but must distinguish $2^n$ possible hidden strings. Hence $k\ge n$, including adaptive strategies. The classical query complexity of linear Boolean function identification is therefore

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.

A two-query network begins in $|0{⟩}_x|0{⟩}_y$, calls $U_f$, flips the input with $X_x$, calls $U_f$ again, and measures the answer wire in Z. The successive states areThe measured answer is zero for constant functions and one for balanced functions. The circuit is drawn in i.

Explicit oracle circuits follow from the form $f(x)=a\oplus bx$:Thus the four circuits, respectively for the truth tables in i, are the identity on both wires; a NOT on the answer wire; a CNOT from input to answer; and a CNOT together with an answer NOT. The latter commute, so their order is immaterial. These circuits leave the input wire unchanged and XOR precisely $f(x)$ into the answer.

Let $a,b$ be as in i. Insert the explicit oracle from ii between the two pairs of Hadamard gates. The network identitiesturn the entire network intoThis is the last simplified circuit in i. On the designated input $|0{⟩}_x|1{⟩}_y$, its reversed control is certainly one, soThe global phase is unobservable. Measuring the first wire therefore determines the function class with certainty after one oracle query, while the second wire returns to $|1⟩$. These circuit identities are the network form of quantum phase kickback: the answer state between the Hadamards is the $X$ eigenstate $|-⟩$, on which an XOR acts as a phase.

Take the Hadamard gate to be $H=2^{-1/2}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$ and the phase gate to be $P(\varphi )=\mathrm{diag}(1,e^{i\varphi })$. This fixes the sign convention for the interference phase.

For the coherent quantum circuit, the successive quantum states areThe Born rule therefore gives the concise answer

With the stated quantum decoherence after the phase gate, the joint pure state before the last Hadamard gate isAfter that Hadamard gate, its environment coefficient at output zero is $(|e_0⟩+e^{i\varphi }|e_1⟩)/2$. Squaring its norm sums over every unobserved environment outcome, soThe Cauchy-Schwarz inequality gives $0\le v\le 1$. In this single-qubit interference with conditional environment states, $v$ is the interference visibility: orthogonal environment states erase the fringe, while a unit-modulus overlap shifts its phase without reducing visibility. The plus sign in $\varphi +\alpha$ follows from the specified overlap $⟨e_0|e_1⟩$, rather than its complex conjugate.

If the same quantum decoherence occurs before the phase gate, the joint pure state is first $(|0⟩|e_0⟩+|1⟩|e_1⟩)/\sqrt{2}$. The phase gate then produces exactly the same state used above. Equivalently, the controlled environment interaction commutes with the diagonal phase gate. The probability is unchanged.

For the Deutsch algorithm, use the reversible Boolean quantum oracleThe algebraic oracle map printed in the source has its arguments misplaced: taken literally, it sends two distinct answer inputs to the same output for constant $f$, so it cannot be a unitary operator. The corrected map above agrees with the diagram's input-control, answer-target arrangement. Put the answer qubit in $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$. Since the Pauli X gate satisfies $X|-⟩=-|-⟩$, quantum phase kickback givesWrite $b=f(0)\oplus f(1)$. Up to the irrelevant global phase $(-1{)}^{f(0)}$, the input qubit acquires relative phase $(-1{)}^b$, so its ideal final computational-basis measurement returns $b$: zero for a constant function and one for a balanced function.

Let the specified quantum decoherence occur in the interference portion between the two Hadamard gates. It commutes with the oracle's effective diagonal phase on the input, so the same analysis applies whether it occurs just before or just after the query. The two likelihoods areThus the diagram's usual zero-for-constant decision rule hasThis is the reliability for either promised class separately, with no prior needed. For equally likely classes, if $v\cos \alpha$ is known to be negative, reversing the interpretation gives $(1+|v\cos \alpha |)/2$. A known environment phase can instead be compensated by the phase gate $P(-\alpha )$ before the final Hadamard gate, giving success probability $(1+v)/2$. In particular, $v=0$ gives no information and $v=1$ permits certainty after phase compensation. These refinements distinguish a shifted fringe from lost quantum coherence; with the unmodified diagram a phase shift alone can reverse the apparent answer. Quantum decoherence after the final Hadamard gate leaves its computational populations unchanged, so that different placement would not spoil the measured answer.

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.

The first Hadamard transform prepares a uniform superposition in the first register while the second stays zero. The Boolean quantum oracle, now with an $n$-bit output register and bitwise addition, therefore givesThis state is normalized because distinct $x$ labels are orthogonal, even when their oracle outputs coincide. Addition in the oracle is bitwise exclusive-or, making the oracle reversible; replacing the first register by $f(x)$ would not define a unitary gate for a two-to-one function.

For the later recovery steps we use the intended nonzero hidden-period promise $s\ne 0$. Then two-to-one behavior and $f(x+s)=f(x)$ force each fibre to be exactly $\{x,x+s\}$. The printed allowance $s\in \{0,1{\}}^n$ does not explicitly exclude zero. If zero were allowed without a nonzero-period promise, the displayed identity would hold trivially for every function and would not specify Simon's problem. That distinction is addressed again in the query count.

An oracle can recognize a solution without disclosing it in advance. If an efficiently evaluable or black-box predicate has the promised unique marked input, write $f(x)=1$ exactly for that input. A Boolean quantum oracle computes this predicate reversibly asIts diagonal projector on the search register is ${\sum }_{x}f(x)|x⟩⟨x|=|w⟩⟨w|$. To implement a selectable phase, compute $f(x)$ into a zero quantum ancilla, apply a known phase to its $1$ component, and uncompute. The search register then undergoesThis requires evaluation access to the predicate, not classical knowledge of which input passes it. The $P_{\psi }$ term is known from the Hadamard transform. With Hamiltonian-oracle access, or by controlled short-time simulations of the two terms, their sum can realize continuous-time quantum search.

The unknown projector is supplied through an oracle or a physically encoded recognition rule. It cannot be manufactured for an arbitrary hidden $w$ with no such input-dependent resource. The oracle assumption and the fixed energy scale $\Delta$ are essential when interpreting the square-root search time as a computational advantage.

The answer qubit enters the Boolean quantum oracle in $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$, because the Pauli X gate followed by the Hadamard gate maps $|0⟩$ to $|-⟩$. Since $X|-⟩=-|-⟩$, quantum phase kickback multiplies the $|xy⟩$ component by $(-1{)}^{f(x,y)}$ and leaves the answer qubit unchanged. The two input qubits enter in the uniform quantum superposition $|++⟩$. ThusEquivalently, using the Controlled-Z gate and the Pauli Z gate,Here the exponent in the phase may be evaluated as an ordinary integer, since its parity agrees with the exclusive or expression. In particular, $d$ contributes only a global phase.

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.

Write $N=2^n$ and $|s⟩=N^{-1/2}{\sum }_{x=0}^{N-1}|x⟩$. The initial Hadamard gates prepare $|s⟩$ in the search register and $|-⟩$ in the final quantum ancilla. Since the Pauli X gate satisfies $X|-⟩=-|-⟩$, the Boolean quantum oracle acts by quantum phase kickback:For a single marked entry this is the marked-state phase oracle $O_a=I-2|a⟩⟨a|$ on the search register. The ancilla stays separate and unchanged throughout.

The Grover diffusion operator is $V=2|s⟩⟨s|-I$, because $H^{\otimes n}|0^n⟩=|s⟩$. The PDF circuit places one diffusion after each oracle call, so the state before measurement isIn the supplied amplitude amplification theorem, take $|\psi ⟩=|s⟩$ and $|\varphi ⟩=|a⟩$. Their overlap has modulus $1/\sqrt{N}$, so the Grover rotation angle is $\theta =\arcsin (N^{-1/2})$. A quantum measurement in the computational basis therefore givesThe inverse sine here is applied to the overlap of the two different states. The converted TeX's self-overlap in the angle definition is a transcription error; the original PDF has $|⟨\varphi |\psi ⟩|$.

If there is no marked entry, the Boolean quantum oracle is the identity. The uniform superposition state is a positive eigenstate of the Grover diffusion operator:Thus every iteration leaves the full state $|s⟩\otimes |-⟩$ unchanged. The measured search bits have the uniform distributionOnly the first $n$ qubits are measured in the printed circuit. If the untouched ancilla were also measured in the computational basis, its bit would be an independent fair bit, giving probability $1/(2N)$ for each joint outcome.