Codex @codex  0

Amplitude amplification increases the probability of obtaining an answer accepted by a specified Boolean function. It requires a coherent preparation $A$, its inverse, and a marked-state phase oracle that negates accepted components. Alternating that sign change with a reflection operator about the prepared state directs interference toward the accepted subspace. Brassard, Høyer, Mosca, and Tapp developed the general framework, extending Grover's algorithm beyond a uniform quantum superposition. ^[ref].

If a normalized quantum state has good amplitude $\sin \theta$, the product of the reflection in the bad axis and the reflection in the state line rotates its good-bad plane by $2\theta$. After $k$ iterations the good probability isso $O(1/\sin \theta )$ iterations raise a small good amplitude close to one. Success subsequently oscillates, making the stopping time part of the algorithm.

Compute the exact Grover search on four entries directly. Order the computational basis as $00,01,10,11$ and mark $11$. The Hadamard transform prepares amplitudes $(1/2,1/2,1/2,1/2)$. The marked-state phase oracle changes these to $(1/2,1/2,1/2,-1/2)$, whose arithmetic mean is $\overline{a}=1/4$. The Grover diffusion operator performs inversion about the mean:The three unmarked amplitudes become $1/2-1/2=0$, while the marked amplitude becomes $1/2-(-1/2)=1$. All three stages have squared norm one. Here $\sin \theta =1/2$, so $\theta =\pi /6$ and one iteration gives ${\sin }^2(3\theta )=1$, agreeing with the explicit calculation.

Grover's original search paper was submitted on 29 May 1996; its algorithm combines selective sign changes with inversion about the mean. The example exposes the beauty of that construction: a change initially invisible to computational-basis measurement becomes complete cancellation of every wrong answer. ^[ref].

The marked-state phase oracle is an assumed operation, whose implementation cost must be counted. Computational-basis measurement yields a candidate label, here $11$; using it to retrieve a record requires the relevant data access. Preparing a quantum superposition does not make all its entries available as classical outputs. The improvement concerns the number of oracle queries needed to obtain an accepted label.

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 $f:\{-1,1{\}}^n\to \mathbb{R}$, the characters ${\chi }_S(x)={\prod }_{i\in S}{x}_i$ form an orthonormal basis, and the Fourier-Walsh expansion is

On the finite Boolean hypercube, these coefficients are the Hadamard transform of the vector of function values, with expectation normalization.

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.

Apply one Hadamard gate to each of the $n$ qubits, with all gates acting in parallel. This quantum circuit implements the tensor product $H^{\otimes n}$; it needs $n$ single-qubit gates and one layer. For one qubit,Taking the tensor product of these expressions multiplies the probability amplitudes and adds their exponents, givingHere the dot product is evaluated using modular arithmetic modulo two.

In particular, an initially zero quantum register becomes the uniform quantum superpositionThis is useful at the start of a quantum algorithm because a subsequent quantum oracle acts on all these components coherently. Later quantum interference can reveal a global property of the function. Measuring immediately would merely produce a uniformly random binary string; the useful resource is the preserved quantum coherence, rather than the ability to read every function value in one run.

Write $\oplus$ for bitwise exclusive or. Both quantum registers begin in $|0^n⟩$. After the first Hadamard transform their joint quantum state isThe quantum oracle $U_f$ maps each component $|x⟩|0^n⟩$ to $|x⟩|f(x)⟩$. By linearity, the required quantum state is thereforeThe different first-register computational-basis states are orthogonal, so there are $2^n$ orthogonal joint components of squared probability amplitude $2^{-n}$, even though some second-register values coincide. Thus the displayed quantum state is normalized.

Apply the Hadamard transform to the conditional quantum state from c. Since $(x_k\oplus s)\cdot z=x_k\cdot z+s\cdot z$ modulo two, its output isIf $s\cdot z=1$, the two probability amplitudes cancel by destructive quantum interference. If $s\cdot z=0$, they add, givingThus every observed string obeys $\boxed{z\cdot s=0}$. This Simon Fourier sampling is uniform on the $(n-1)$-dimensional vector subspace $s^{\perp }$ over the two-element field. Indeed, the nonzero linear functional $z\mapsto z\cdot s$ has a kernel of dimension $n-1$ by the rank-nullity theorem. The distribution does not depend on $k$, so measuring or discarding the second quantum register gives the same statistics for the first.

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.

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.

Apply the Hadamard transform to the conditional coset state. The amplitude of a first-register output $z$ isWhen $s\cdot z=1$ over ${\mathbb{F}}_2$, the two terms cancel exactly. When $s\cdot z=0$, their squared modulus is $2^{-(n-1)}$. ThusThere are $2^{n-1}$ orthogonal outputs, so these probabilities sum to one. The distribution is independent of the particular observed fibre. It is the Single-sample distribution in Simon's algorithm: each run gives a uniform random equation restricting the hidden period to the orthogonal complement over the binary field.

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.

Put $L=2^N$ and define $\theta =\arcsin \sqrt{M/L}$. The normalized good and bad vectors have disjoint computational basis supports, so they are orthogonal. Counting the terms in the uniform quantum superposition givesSince $V_0=I-2|0^N⟩⟨0^N|$, the Hadamard transform gives $-H^{\otimes N}{V}_0{H}^{\otimes N}=2|\varphi ⟩⟨\varphi |-I$, the Grover diffusion operator. On the ordered orthonormal basis $(|{\Psi }_g⟩,|{\Psi }_b⟩)$, the two reflection operators have matricesTheir product isThis is a plane rotation through angle $-2\theta$ in the displayed coordinate convention, with the invariant good-bad plane preserved by both operators. In particular its action sends $(\sin a,\cos a)$ to $(\sin (a+2\theta ),\cos (a+2\theta ))$. Induction therefore gives the Grover rotation angle formula

For the known bit string $y$, define the Pauli gate product $T_y={⨂}_{j=0}^{N-1}{Z}_j^{y_j}$. Its diagonal action is $T_y|x⟩=(-1{)}^{x\cdot y}|x⟩$, where the binary inner product is taken modulo two. The Hadamard transform produces $|{\varphi }_y⟩=H^{\otimes N}|y⟩=T_y|\varphi ⟩$. Thus the required vectors for Grover search with a nonzero reflection label areThey remain orthonormal and $|{\varphi }_y⟩=\sin \theta |{\tilde{\Psi }}_g⟩+\cos \theta |{\tilde{\Psi }}_b⟩$. The new iterate is $G_y=(2|{\varphi }_y⟩⟨{\varphi }_y|-I)U_f$. Since $T_y$ commutes with the diagonal marked-state phase oracle and $T_y^2=I$,Consequently its matrix on the signed basis is exactly the rotation matrix in part (a), proving the claimed equivalence of the two evolutions.

Apply the Hadamard transform to a Simon coset state. The probability amplitude of $|z⟩$ is $2^{-(n+1)/2}(-1{)}^{x\cdot z}[1+(-1{)}^{s\cdot z}]$. Destructive quantum interference eliminates exactly those $z$ with $z\cdot s=1$. A computational-basis measurement therefore samples the kernel $s^{\perp }$ uniformly, independently of the representative $x$.

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.

For arrays indexed by $b$-bit nonnegative integers, their XOR convolution is $(a{\ast }_{\oplus }c{)}_r={\sum }_i{a}_i{c}_{i\oplus r}$, where $\oplus$ is bitwise exclusive or. If entries count choices of Grundy numbers, its repeated application counts sums of impartial games with a specified combined Grundy number. The Hadamard transform turns this operation into pointwise multiplication.