Codex @codex  0

Approximate quantum counting estimates the number $k$ of satisfying assignments of a Boolean function, using a quantum oracle and quantum measurement. Controlled repetitions of a Grover search algorithm iteration let quantum interference reveal the count. For one input bit, a Hadamard test can give Pauli Z gate expectation value $1-k$: with the complemented phase oracle $U_f=\mathrm{diag}(2f(0)-1,2f(1)-1)$ and $G=-X{U}_f$, use $⟨+|X=⟨+|$ to obtain $⟨+|G|+⟩=-[(2f(0)-1)+(2f(1)-1)]/2=1-k$. Repeated preparations estimate this expectation value; one binary measurement result does not distinguish all three counts $0,1,2$.

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.

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.

Each run of Simon's algorithm uses one oracle call and returns one uniform sample from $s^{\perp }$. Collect samples as rows of a matrix $Z$ and solve $Zs=0$ over the two-element field using Gaussian elimination. Once the rows have matrix rank $n-1$, the kernel is $\{0,s\}$, so the promised nonzero vector is uniquely determined. Dependent samples, including $z=0$, must be allowed for; exactly $n-1$ runs need not suffice.

For a rough quantitative estimate, put $d=n-1$. When the existing samples span an $r$-dimensional vector subspace of $s^{\perp }$, the next sample increases the matrix rank with probability $1-2^{r-d}$. The random spanning of a binary vector space estimate givesAlternatively, $m=d+t$ samples fail to span with probability less than $2^{-t}$: failure means some nonzero linear functional on the $d$-dimensional space vanishes on every sample, and a union bound gives $(2^d-1)2^{-m}$. ConsequentlyThe Gaussian elimination requires only a polynomial amount of classical work, for example $O(n^3)$ bit operations for $O(n)$ samples. The degenerate case $n=1$ needs no calls because the promise already specifies $s=1$.

Classically, distinct inputs with equal function values reveal $s=x\oplus x^{\prime }$. Uniformly sampling distinct inputs finds such a function collision after roughly $\sqrt{2^n}$ calls, by the birthday square-root scale. For $q$ sampled inputs, the expected number of colliding pairs is $\left(\genfrac{}{}{0ex}{}{q}{2}\right)/(2^n-1)$. The usual randomized classical query complexity of Simon's problem is therefore exponential in $n$, on the scaleA straightforward exhaustive classical search instead uses $O(2^n)$ calls. The square-root collision estimate is the sharper classical comparison; the quantum advantage concerns access to the promised quantum oracle, rather than an explicit table of all function values.

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.

In the oracle machine model, a function is accessed through a black box whose internal gate cost is excluded; the resource counted is the number of calls. A reversible classical oracle maps basis inputs as $(x,y)\mapsto (x,y\oplus f(x))$. Its quantum oracle extension applies the same permutation coherently to arbitrary superpositions, without measuring its input. A classical random mixture of inputs is not that coherent extension.

Write the two truth-table entries as $f(0)=b$, $f(1)=a\oplus b$. Then $f(x)=ax\oplus b$, with the four casesTwo classical query circuits, $(0,0)\stackrel{U_f}{\to }(0,f(0))$ and $(1,0)\stackrel{U_f}{\to }(1,f(1))$, recover the whole function with certainty. One call fixes only one entry, leaving two compatible functions; hence two are necessary classically. Randomization cannot remove this obstruction to certainty.

The minimum for full exact function identification remains two even with coherent quantum queries. To see this, expand the oracle target into its $X$ eigenstates: it is identity on $|+⟩$, and gives phases $(-1{)}^{f(x)}$ on $|x⟩|-⟩$. Any one-query input, including an auxiliary system, has orthogonal sector weights $w_{+}$, $w_0$ and $w_1$ summing to one. The output overlap between functions differing only at $0$ is $1-2w_0$, so perfect distinction requires $w_0=1/2$; differing only at $1$ likewise requires $w_1=1/2$. Then $w_{+}=0$, but functions differing at both entries have overlap $1-2(w_0+w_1)=-1$. They are the same ray rather than distinguishable states. Thus one query cannot identify all four functions. The following one-query task recovers only whether the entries agree.

Let $x\in \{00,01,10,11\}$ and let $f(x)$ be one only at the marked input. A three-qubit implementation of Grover's algorithm starts with $|00⟩|1⟩$, applies a Hadamard gate to each qubit, queries the reversible quantum oracle $U_f:|x,y⟩\mapsto |x,y\oplus f(x)⟩$, applies the Grover diffusion operator $D=2|s⟩⟨s|-I$ to the first two qubits, and measures those two qubits in the computational basis. Here $|s⟩=\frac{1}{2}{\sum }_x|x⟩$. The full three-wire quantum circuit is the composition

Here $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$. Since $X|-⟩=-|-⟩$, phase kickback gives $U_f(|x⟩|-⟩)=(-1{)}^{f(x)}|x⟩|-⟩$. The third qubit remains separable and unchanged. A direct marked-state phase oracle $O_f|x⟩=(-1{)}^{f(x)}|x⟩$ therefore replaces the three-qubit query using only two qubits:For the explicit choice $f(x)=1$ only at $x=11$, $O_f$ is a Controlled-Z gate. Immediately after it,The mean of these four probability amplitudes is $\overline{a}=1/4$. The Grover diffusion operator maps each probability amplitude $a_x$ to $2\overline{a}-a_x$. The three unmarked probability amplitudes become zero and the marked one becomes one. A single query consequently finds $11$ with probability one.

A gate-level implementation of $D$ is $H^{\otimes 2}(2|00⟩⟨00|-I)H^{\otimes 2}$. Up to an irrelevant global phase, it is $H^{\otimes 2}{X}^{\otimes 2}\mathrm{CZ}{X}^{\otimes 2}{H}^{\otimes 2}$. For any other chosen marked word, conjugate the Controlled-Z gate by Pauli X gates on precisely the positions where the marked word has a zero.

A phase oracle encodes a Boolean function in the signs of computational basis states. Its diagonal entries have modulus one, so it is a unitary operator. The usual convention $O_f$ changes the sign when $f(x)=1$. A complemented convention $U_f|x⟩=(-1{)}^{f(x)\oplus 1}|x⟩$ instead changes the sign when $f(x)=0$, with $U_f=-O_f$; $\oplus$ denotes exclusive or. The two conventions differ by a global phase when used without coherent control, but the global phase of a controlled quantum gate makes that difference observable when the quantum oracle is controlled.

A quantum oracle supplies coherent access to a function through a specified unitary operator. For a function with binary string output, the standard construction retains the input and adds the output into an answer quantum register by bitwise exclusive or. This operation is its own inverse, even when the function is not injective. A Boolean quantum oracle is the single-output-bit case; Simon's algorithm uses several answer qubits. Other encodings, such as a modular-addition quantum oracle or a phase gate encoding, require their own explicit query conventions.

The number of accesses to an unknown input needed to solve a specified task. The input might be a string with individually readable entries, or an implicitly supplied function. A complete statement specifies deterministic, randomized, or quantum access, the accepted error, and worst-case or expected cost. Quantum query complexity permits coherent input access through a quantum oracle.