Exact Oracle Algorithms

By [F1], $(-1{)}^{x\cdot z}={\prod }_{i<n}(-1{)}^{x_i{z}_i}$, since the exponent parity is the sum of the coordinate products modulo two. Distributivity over the finite Cartesian product gives ${\sum }_{x\in \{0,1{\}}^n}(-1{)}^{x\cdot z}={\prod }_{i<n}(1+(-1{)}^{z_i})\mathrm{.}$ Each factor is $2$ when $z_i=0$ and $0$ when $z_i=1$. Thus the product is $2^n$ when all coordinates of $z$ vanish and is $0$ otherwise.

By [F2], on each factor $H\mathrm{\mid }{x}_i⟩=2^{-1\mathrm{/}2}{\sum }_{y_i\in \{0,1\}}(-1{)}^{x_i{y}_i}\mathrm{\mid }{y}_i⟩$. Applying [F5] to the ordered product basis [F3] gives a coefficient $2^{-n\mathrm{/}2}{\prod }_{i<n}(-1{)}^{x_i{y}_i}=2^{-n\mathrm{/}2}(-1{)}^{x\cdot y}$ at $\mathrm{\mid }y⟩$, by [F1]. Summing these coefficients proves the tensor-Hadamard formula in the Statement.

Writing the two function values in order gives exactly the four strings $00,01,10,11$. By the Definition, $00$ and $11$ are in $Y$, while $01$ and $10$ are in $N$. These two sets are disjoint and cover all four possible tables, so the promised output is well-defined.

The totality in [F2] makes both evaluations $f(0)$ and $f(1)$ available. Equality gives the constant case and inequality gives the balanced case by the two disjoint rows of the table in step 1.1.

Since $n\ge 1$, $N=2^n$ is even and $1\le N\mathrm{/}2<N$. A constant function has either $0$ or $N$ addresses with value $1$, whereas a balanced function has $N\mathrm{/}2$ such addresses. These counts differ, so the YES and NO sets are disjoint.

Both promise classes are nonempty: the zero function is constant, and the function $f(x)=x_0$ has exactly $N\mathrm{/}2$ inputs with each value because flipping its first bit pairs a zero-output address with a one-output address. Thus the stated promise is meaningful for every $n\ge 1$.

For every $x\in \{0,1{\}}^n$, [F3] is a finite XOR of bits, hence defines one bit; therefore $f_a$ is a total Boolean function and satisfies the query-instance requirement [F2].

For each coordinate $i<n$, let $e_i$ be the string with a single $1$ at position $i$. Then $f_a(e_i)=a_i$ by [F3]. If $f_a=f_b$, evaluation at every $e_i$ gives $a_i=b_i$, so $a=b$. Thus the secret is uniquely determined by the function table.

Fix a deterministic one-query procedure and let $q$ be its queried address. The constant-zero function $f_0$ and the balanced function $g$ defined by $g(q)=0$, $g(1-q)=1$ give the same reply. The procedure therefore has the same transcript and output on two functions requiring different answers, so it cannot be exact.

Querying both addresses reveals the entire truth table; equal replies identify a constant and unequal replies identify a balanced function. Thus two queries suffice exactly, and step 1.1 proves the deterministic exact query complexity is two.

Fix a random tape of an algorithm that makes at most one query. If it makes no query, its one output is correct on at most two of the four truth tables. If it queries address $q$, then for each possible reply $b\in \{0,1\}$ there are exactly two promised functions with $f(q)=b$: one constant and one balanced. The fixed tape gives the same output for both, so it is correct on at most one of each such pair, hence on at most two of the four functions. There are finitely many deterministic one-query strategies on two addresses with binary outputs. The random-tape algorithm induces a probability weight on this finite strategy set by grouping tapes according to their resulting strategy. Averaging the fixed-strategy bound over that finite distribution and over the four functions preserves the bound $1\mathrm{/}2$; by [F3] some promised input has success at most $1\mathrm{/}2$.

Suppose a deterministic procedure makes at most $N\mathrm{/}2$ queries in the worst case. Run it on the constant-zero function and let $S$ be the set of distinct queried addresses. Write $s=\mathrm{\mid }S\mathrm{\mid }\le N\mathrm{/}2$ and list the complement $C$ in lexicographic order, with $c=\mathrm{\mid }C\mathrm{\mid }$. Concatenating the lexicographic lists of $S$ and $C$ lists every address exactly once: the sets are disjoint and cover the domain. Indexing this concatenated list gives a bijection from $\{0,\dots ,s+c-1\}$ to the $N$-element address set, so $s+c=N$ by [F3]. Thus $c=N-s\ge N\mathrm{/}2$. Choose $T$ to be the first $N\mathrm{/}2$ addresses of $C$ and define $g$ to be $1$ on $T$ and $0$ elsewhere. Then $g$ is balanced and agrees with the constant-zero function on every address in $S$. Inductively, each adaptive query and reply in the two executions is the same, so the final outputs agree despite the different correct answers. Thus no such procedure is exact.

Query any fixed set of $N\mathrm{/}2+1$ distinct addresses. If all replies are equal, the function cannot be balanced because each value occurs only $N\mathrm{/}2$ times in a balanced function, so it is constant. If the replies are not all equal, the function is not constant and is balanced by the promise. This gives an exact procedure using $N\mathrm{/}2+1$ queries; combined with step 1.1 the exact complexity is $N\mathrm{/}2+1$.

For a constant function, all three replies agree, so the procedure outputs constant correctly with probability one. For a balanced function write $m=N\mathrm{/}2$. The ordered sample space has $N(N-1)(N-2)$ triples. If $m=2$, no three distinct samples can have the same reply, so the error probability is zero. If $m\ge 3$, the error event consists of an ordered triple all drawn from the zero class or all from the one class; its probability is $\frac{2m(m-1)(m-2)}{(2m)(2m-1)(2m-2)}=\frac{m-2}{2(2m-1)}=\frac{N-4}{4(N-1)}\mathrm{.}$ This is at most $1\mathrm{/}4$, since $N-4\le N-1$.

The without-replacement experiment has success at least $3\mathrm{/}4$ by step 1.1. For an implementation in the finite fair-bit model, take three independent blocks of $n$ fair bits as addresses, allowing repetitions. On a balanced input the three replies are independent fair bits, so they all agree with probability $2(1\mathrm{/}2{)}^3=1\mathrm{/}4$; on a constant input they always agree. Thus this algorithm uses exactly $3n$ random bits and three value queries and has success at least $3\mathrm{/}4$. When $n=1$, the domain has two addresses and querying both returns the full truth table, which classifies exactly. The claim concerns bounded-error upper cost and leaves the deterministic exact lower bound as a separate query measure.

Fix a random tape. The algorithm is a deterministic adaptive binary decision tree of depth at most $q$, since each query reply is one bit by [F2]. A binary tree of depth at most $q$ has at most $2^q$ leaves: this holds at depth zero, and at each added level every prior leaf creates at most two children. Each leaf outputs one candidate secret, so at most one of the $2^n$ secrets reaching that leaf can be correctly recovered. Hence success averaged uniformly over secrets is at most $2^q\mathrm{/}{2}^n=2^{q-n}$.

For fixed $n$ and $q$, there are finitely many deterministic depth-at-most-$q$ decision trees on the finite address set, with output labels in $\{0,1{\}}^n$. The random-tape algorithm induces weights on this finite strategy set by grouping tapes according to their tree. Averaging step 1.1 over this finite distribution leaves average success at most $2^{q-n}$. If worst-case success is at least $2\mathrm{/}3$ on every secret, its average under the uniform secret law is at least $2\mathrm{/}3$. For $q\le n-1$, the upper bound is at most $1\mathrm{/}2<2\mathrm{/}3$, a contradiction; therefore $q\ge n$.

For each coordinate $i<n$, query $e_i$, the string with one at $i$ and zeros elsewhere. By [F2], the reply is $f_a(e_i)=a_i$. These $n$ replies give the entire secret, so $n$ queries suffice exactly.

By [F1], the address is initially $\mathrm{\mid }+⟩=2^{-1\mathrm{/}2}{\sum }_{x\in \{0,1\}}\mathrm{\mid }x⟩$ and the target is $\mathrm{\mid }-⟩$. By [F3], after the query and final address Hadamard, the output amplitude at $y\in \{0,1\}$ is ${\alpha }_y=\frac{1}{2}{\sum }_{x\in \{0,1\}}(-1{)}^{f(x)+xy}\mathrm{.}$ The target remains the same unit vector [F3].

For $y=0$, ${\alpha }_0=((-1{)}^{f(0)}+(-1{)}^{f(1)})\mathrm{/}2$; for $y=1$, ${\alpha }_1=((-1{)}^{f(0)}-(-1{)}^{f(1)})\mathrm{/}2$. If $f(0)=f(1)$, these are respectively $\pm 1$ and $0$; if they differ, they are $0$ and $\pm 1$, by [F2].

In each case the address amplitudes have squared moduli $1$ at the correct output and $0$ at the other. Since the terminal state is the product of that address vector and the unit target $\mathrm{\mid }-⟩$, [F5] and [F7] sum the target's two squared coordinate moduli to one and give exactly the same address output law. Thus the measured output is correct with probability one.

The procedure [F1] contains one oracle invocation. Its target preparation has one $X$ and one $H$, and its address has $1$ Hadamard gates before and $1$ after the query. Thus [F8] gives exactly one query and one $X$ and three $H$ gates, totaling four one-qubit gates; the terminal measurement is counted separately.

By [F1] and [F3], after the oracle and final Hadamards the amplitude at address $y$ is ${\alpha }_y=2^{-n}{\sum }_{x\in \{0,1{\}}^n}(-1{)}^{f(x)+x\cdot y}\mathrm{.}$ For constant $f(x)=c$, factor out $(-1{)}^c$ and apply [F4] with $z=y$: ${\alpha }_y=(-1{)}^c$ if $y=0^n$ and $0$ otherwise.

For balanced $f$, [F2] gives equally many $+1$ and $-1$ terms in ${\alpha }_{0^n}$, so ${\alpha }_{0^n}=0$. For every $y$, the terminal output weight is $\mathrm{\mid }{\alpha }_y{\mathrm{\mid }}^2$ after summing the target coordinates: the state is ${\sum }_y{\alpha }_y\mathrm{\mid }y⟩\otimes \mathrm{\mid }-⟩$, the target has squared coordinate moduli $1\mathrm{/}2,1\mathrm{/}2$ by [F3]. Its unit-vector projector is a density operator by [F6], and [F5] and [F7] give the stated marginal. Thus the constant case outputs $0^n$ surely, while in the balanced case the probability of $0^n$ is zero.

The output weights sum to one by [F5]. Hence, when $f$ is balanced, all output probability is on strings other than $0^n$, which the output rule of [F1] labels balanced; in the constant case step 1.1 places all probability at $0^n$.

The procedure [F1] contains one oracle invocation. Its target preparation has one $X$ and one $H$, and its address has $n$ Hadamard gates before and $n$ after the query. Thus [F8] gives exactly one query and one $X$ and $2n+1$ $H$ gates, totaling $2n+2$ one-qubit gates; the terminal measurement is counted separately.

By [F1]–[F3], after phase kickback and the final address Hadamards the amplitude at $y$ is ${\alpha }_y=2^{-n}{\sum }_{x\in \{0,1{\}}^n}(-1{)}^{a\cdot x+x\cdot y}=2^{-n}{\sum }_x(-1{)}^{x\cdot (a\oplus y)},$ where $\oplus$ is coordinatewise addition modulo two; the parity formula in [F2] gives the exponent identity coordinate by coordinate.

By [F4], ${\alpha }_y=1$ for $y=a$ and $0$ for $y\mathrm{\ne }a$. The target remains the unit vector $\mathrm{\mid }-⟩$ by [F3], so [F5]–[F7] give output weight $\mathrm{\mid }{\alpha }_y{\mathrm{\mid }}^2$ at each measured address. Therefore the output distribution is concentrated at $a$.

The procedure [F1] contains one oracle invocation. Its target preparation has one $X$ and one $H$, and its address has $n$ Hadamard gates before and $n$ after the query. Thus [F8] gives exactly one query and one $X$ and $2n+1$ $H$ gates, totaling $2n+2$ one-qubit gates; the terminal measurement is counted separately.