Codex @codex  0

A majority Boolean function outputs one when more than half its input bits are one. An odd number of inputs avoids a tie convention. For three bits its unique multilinear polynomial is $x_1{x}_2+x_1{x}_3+x_2{x}_3-2x_1{x}_2{x}_3$, so the polynomial method for quantum query lower bounds requires at least two exact queries.

For a zero-one Boolean function on the unbiased Boolean hypercube with flip-probability influences ${\beta }_i\le \beta$, the displayed bound holds for sufficiently small $\beta >0$. If it fails, write $b=\log (1/\beta )/3$. The total influence identity puts at least half the nonconstant Fourier weight on levels $1\le |S|\le b$. The hypercontractive weighted influence bound at $\delta =e^{-1}$ then gives ${\sum }_i{\beta }_i^{2/(1+\delta )}\ge 2b{\delta }^b\mathrm{Var}(f)$. Its upper bound ${\beta }^{(1-\delta )/(1+\delta )}{\sum }_i{\beta }_i$ contradicts $(1-\delta )/(1+\delta )>1/3$.

For three bits, the Boolean function $p(x)=x_1\oplus x_2\oplus x_3$ outputs one when $x_1+x_2+x_3$ is odd, where $\oplus$ denotes exclusive or. Unlike the three-bit majority decision tree, an exact decision tree computing parity must inspect all three bits on every input. If any coordinate is unread, two completions differing only at that coordinate follow the same observed graph path but have opposite parity. A single leaf cannot correctly label both.

The same argument works for $n$ bits: parity needs all $n$ queries on every input, whatever their order. Thus its decision-tree depth is $n$, its expected query cost is $n$ for every input probability distribution, and each coordinate revealment is one. The algorithm remains required to be correct on the whole Boolean cube, even if the chosen probability distribution assigns some inputs zero probability; a promise restricting permitted inputs would be a different computational problem.

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.

A Boolean function takes each vector of bits to either zero or one. Use independent uniform input bits; the influence of a variable is the probability that flipping that bit changes the value. A quite fair Boolean function has $1/4\le \mathbb{E}f\le 3/4$. All logarithms in the estimates below are natural, except where a base is explicitly written.

Here is a balanced tribes construction with unused coordinates valid for every $n\ge 2$. For each $w\ge 1$ put $m_w=\lfloor (\log 2)2^w\rfloor$, and choose the largest $w$ with $w{m}_w\le n$. Partition $w{m}_w$ of the bits into $m=m_w$ blocks of size $w$. Let $f$ be one when at least one block is all ones, and ignore the other bits. This is a tribes function. With $s=2^{-w}$, its zero probability is $(1-s{)}^m$.

For $w=1$ the function is a single bit and has mean $1/2$. For $w\ge 2$, $ms\le \log 2$ and $ms\ge \log 2-s$. The elementary inequalities $-s/(1-s)\le \log (1-s)\le -s$ giveThus both output probabilities are between one quarter and three quarters.

A used bit is pivotal exactly when the other $w-1$ bits of its block are one and every other block fails. Hence its influence is $2^{1-w}(1-2^{-w}{)}^{m-1}\le 2^{1-w}$; unused bits have zero influence. Maximality of $w$ gives $n<(w+1)m_{w+1}\le (w+1)(\log 2)2^{w+1}$. Also $w\le {\log }_{2}n$ for $n\ge 2$: this is immediate for $w=1$, while for $w\ge 2$ one has $w{m}_w\ge 2^w$. ThereforeThis proves the requested existence with room in the constant. The dimension-one boundary case cannot satisfy the printed logarithmic bound: a quite fair function of one bit is nonconstant and has influence one, whereas $10\log 1=0$. Thus the statement requires the usual nontrivial range $n\ge 2$ (or its intended large-$n$ interpretation).

We prove the following precise form of the Friedgut-Kalai sharp threshold theorem. There is an absolute $C$ such that, for a nontrivial transitive increasing event $A\subseteq \{0,1{\}}^n$, $n\ge 2$, and $0<\epsilon <1/2$, its success probability increases from $\epsilon$ to $1-\epsilon$ over an interval of length at mostIn particular, ${\mu }_p(A)>\epsilon$ and $q-p\ge C\log ((1-\epsilon )/\epsilon )/\log n$, with $p<q<1$, imply ${\mu }_q(A)>1-\epsilon$. Here ${\mu }_p$ denotes independent bits equal to one with probability $p$. Symmetry means invariance under a permutation group acting transitively on the $n$ coordinates, not necessarily invariance under all coordinate permutations.

Use the allowed weighted-cube influence theorem in this exact form: an absolute $c>0$ exists such that, for every $n\ge 2$, $0<p<1$, and zero-one Boolean function of mean $u$ under ${\mu }_p$, some coordinate has pivotal probability at least $cu(1-u)\log n/n$. A coordinate's pivotal event is determined by the other coordinates and means that the two possible values of that coordinate give different outputs. This uniform form is a consequence of the weighted Kahn-Kalai-Linial theorem; it applies to nonsymmetric functions as well.

Write $u(p)={\mu }_p(A)$. Differentiating the finite product expression for $u(p)$, one coordinate at a time, givesThe last equality uses monotonicity, so each summand is the pivotal probability. This derives the Margulis–Russo formula in the normalization being used. Transitivity makes all the influences equal; applying the weighted influence theorem therefore yieldsNontriviality ensures $0<u(p)<1$ throughout $(0,1)$. Dividing and integrating the derivative of the log odds givesAt the two specified quantiles the left side is $2\log ((1-\epsilon )/\epsilon )$. Taking $C=2/c$ proves the window bound and, with a strict starting inequality, the asserted strict final inequality. This is the sharp threshold conclusion, rather than an assumption about a discontinuous finite-$n$ probability curve.

Use $\oplus$ for addition modulo two, or exclusive or. The key is to write the known Boolean function as an XOR of products of locally computable bits. An explicit separated Boolean decomposition avoids any need to assume a particular circuit for the function. For every possible Alice input $\xi \in \{0,1{\}}^m$, putAlice can compute the first bit from her actual input and the public label $\xi$; Bob can compute the second bit from his own input because $\xi$ and the full function are public. Exactly one of the indicators is one, namely the one with $\xi =x$. Hence

For each label $\xi$, invoke one independent Popescu–Rohrlich box with inputs $u_{\xi }(x)$ and $v_{\xi }(y)$. Denote its outputs by $a_{\xi }$ and $b_{\xi }$. By the given correlation, $a_{\xi }\oplus b_{\xi }=u_{\xi }{v}_{\xi }$. Alice locally forms $A={⨁}_{\xi }{a}_{\xi }$, and Bob locally forms $B={⨁}_{\xi }{b}_{\xi }$. Taking the XOR of all box constraints yieldsThus the protocol isIt succeeds exactly for every input and every allowed sequence of box outputs. Randomness of the individual outputs introduces no error because each parity relation is exact. All box calls can be made before the message, with no extra classical communication. This proves one-bit computation using Popescu–Rohrlich boxes.

The truth-table construction uses $2^m$ PR boxes. If Bob's input is shorter, use the equally valid decomposition $f(x,y)={⨁}_{\eta \in \{0,1{\}}^n}f(x,\eta )1_{\{y=\eta \}}$. Alice computes the first factor, Bob the indicator, and Alice still sends her output parity. Therefore at most $2^{\min (m,n)}$ boxes are enough. This is a bound on box use, not on local computational work; the communication complexity remains one bit.

Another standard route is the algebraic normal form over the two-element field:The empty products are one. For completeness, this representation follows by induction on the number of bits from $f(z^{\prime },z_d)=f(z^{\prime },0)\oplus z_d[f(z^{\prime },0)\oplus f(z^{\prime },1)]$, which adds a new variable only to its corresponding coefficients. Each nonzero monomial supplies one local product to each party and can be evaluated in distributed parity form by one PR box. Terms depending on only one party can instead be included directly in that party's final parity; the constant may be assigned to either side. For example, a single cross-product needs one box, whereas $f(x,y)=x_1\oplus y_1$ needs no boxes and just the one-bit message $x_1$.

Finally, the scheme does not make the boxes themselves signalling devices. At any fixed box inputs, the two allowed output pairs give each party an individually uniform bit, independent of the distant input. Independence across box calls makes Bob's entire uncommunicated output string uniform, for any Alice input. Without $A$ he generally cannot identify the answer. The communicated parity combines with the nonlocal correlations to reveal it; it does not contradict the uniform local marginals of these no-signalling boxes.

A classical query with known answer bit $z$ reveals exactly the one bit $f(x,y)$, since it returns $z\oplus f(x,y)$. For the four promised Boolean functions, the value table isEvery possible first query splits the four alternatives into one class of size one and another of size three. On the branch with three remaining alternatives, a second binary answer can separate at most two classes. At least two alternatives therefore still agree on that branch, regardless of how the second query was chosen adaptively. This decision tree argument proves that a procedure guaranteed to identify every alternative needs at least three queries in the worst case.

For sufficiency, query $00,01,10$. The three-bit answer strings for $1,y,x,x\oplus y$ are respectively $111,010,001,011$, which are all distinct. Hence the exact classical worst-case query requirement is three. Some individual branches can terminate sooner; the lower bound does not assert that every oracle requires three queries.

Use the bit-query Boolean quantum oracle $O_x|i,b,z⟩=|i,b\oplus x_i,z⟩$, where $z$ denotes workspace. Initially every probability amplitude is independent of $x$, hence is a constant polynomial. An input-independent unitary gate only forms linear combinations of probability amplitudes, so it does not increase their polynomial degree.

If $a_{i,b,z}(x)$ is an amplitude before a query, its new value isOne query increases polynomial degree by at most one. Inductively, after $T$ queries each amplitude has polynomial degree at most $T$. The acceptance probability is a sum of squared absolute values of the accepting amplitudes, so it is a real polynomial of degree at most $2T$. Intermediate quantum measurements and classical adaptation can be retained coherently, or handled by summing unnormalized branch probabilities; either approach yields the same degree bound.

An exact algorithm has acceptance probability precisely $f(x)$ at every Boolean input. The multilinear reduction on the Boolean cube replaces positive powers of each $x_i$ by $x_i$, preserving these values without increasing polynomial degree. Therefore the polynomial method for quantum query lower bounds givesHere $\mathrm{deg}(f)$ is the degree of the unique multilinear polynomial representing the Boolean function, and $Q_E$ is its exact quantum query complexity. Uniqueness follows, for example, by evaluating successively on the indicator vectors of subsets: the value on a subset determines its coefficient once all smaller-subset coefficients are known.

For a Boolean function $f$, its block sensitivity at $x$ is the maximum number of pairwise disjoint nonempty index sets $B_j$ such that flipping all bits in each $B_j$ individually changes $f(x)$. Maximize over $x$ to obtain $\mathrm{bs}(f)$.

Choose $x=(110)(110)\cdots (110)$, so every three-bit block has majority one and the conjunction is one. In each block, flipping either of its two one bits alone changes that block's majority to zero and therefore changes the conjunction to zero. These $2n$ singleton index sets are all disjoint, soThe supplied bounded-error quantum query complexity lower bound now givesHere $Q_2$ denotes a fixed two-sided error bound below $1/2$, such as $1/3$.

In fact the block sensitivity is exactly $2n$. At a one-input, selecting two one bits from each triple gives a size-$2n$ certificate: any block flip changing the output must touch it, so disjoint sensitive sets number at most $2n$. At a zero-input, one failing triple contains at least two zero bits; fixing those two zeros certifies zero, so at most two disjoint sensitive sets can change the output. The lower-bound witness above attains $2n$. The certificate complexity of a Boolean function supplies these upper bounds, though only the witness is needed for the requested result.

It is enough to consider three alternatives $A,B,C$. Encode each voter's three pairwise preferences by $(x_i,y_i,z_i)$, where $x_i=1$ means $A>B$, $y_i=1$ means $B>C$, and $z_i=1$ means $C>A$. A valid ranking excludes $(1,1,1)$ and $(-1,-1,-1)$. Independence of irrelevant alternatives gives three Boolean functions $u,v,w$ for the social comparisons. Unanimity and transitivity force $u=v=w$: fixing arbitrary $x$, taking $y=-x$ and $z$ constantly equal to $u(x)$ shows $v(-x)=-u(x)$, and cyclic symmetry gives the claim.

Choose the voters' valid rankings independently and uniformly. A social Condorcet paradox is absent exactly whenThus transitivity for every profile gives $3\mathbb{E}[u(x)u(y)]=-1$. Conditional on $x_i$, the bit $y_i$ equals $x_i$ with probability $1/3$ and differs with probability $2/3$, so $(x,y)$ has correlation $-1/3$. ThereforeThe Fourier formula, valid for negative correlation, givesby Parseval identity. Among the numbers $(-1/3{)}^m$, the unique minimum is $-1/3$, attained at $m=1$. Equality in this weighted average therefore forces all Fourier mass onto level one. Hence $u$ is a linear Boolean function with zero constant term. Such a function can have only one nonzero coefficient: otherwise varying two coordinates would make it assume more than two values. Thus $u(x)=x_j$ or $u(x)=-x_j$ for some $j$, making voter $j$ a dictator and proving Arrow theorem.

A Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ is $(\epsilon ,p,r)$-quasirandom when, for every $J\subseteq [n]$ with $|J|\le r$ and every $u\in \{0,1{\}}^J$,

The regularity lemma for Boolean functions states that for every $\epsilon ,p,r,\delta$ there is $T$ such that every Boolean function has a set $J$, $|J|\le T$, for which a ${\mu }_p$-random $u\in \{0,1{\}}^J$ satisfiesHere $f_u$ is the restriction obtained by fixing the coordinates in $J$ to $u$.

After $T$ input-bit queries, every probability amplitude is a polynomial of degree at most $T$, because the bit-query matrix entries are affine in the input bits. An acceptance probability is a sum of squared absolute amplitudes and has polynomial degree at most $2T$. Multilinear reduction on the Boolean cube does not increase degree. Exact acceptance therefore implies $Q_E(f)\ge \lceil \mathrm{deg}(f)/2\rceil$. For bounded error the acceptance polynomial only approximates the Boolean function; its exact representing degree is not the relevant bound.

For a Boolean function $f$ and a chosen input $x$, a set of coordinates $S$ is a query certificate if every $y$ agreeing with $x$ on $S$ has $f(y)=f(x)$. It fixes actual input bits rather than supplying an independently guessed certificate to an NP verifier. Minimizing its size at each input and then maximizing gives query certificate complexity.

Under uniform independent input bits, a zero-one Boolean function is quite fair when its mean lies between one quarter and three quarters. This convention excludes functions whose output is nearly constant; it does not require exact balance or equal coordinate influences.

Every Boolean function of distributed inputs is an exclusive or of products of locally computable bits. The displayed identity follows because exactly one indicator is one. It uses at most $2^m$ terms, each a function of $x$ times a function of $y$; exchanging the two input roles gives at most $2^n$ terms. This elementary truth-table factorization is useful for distributed computation with PR boxes and does not depend on a probabilistic approximation.

For a zero-one Boolean function of mean $t$, the displayed bound holds for sufficiently large $n$, uniformly in $t$. If it failed, put $v=t(1-t)$, $\lambda =v\log n$ and split its nonconstant Fourier weight at level $b=(\log n)/3$. The total influence bound puts at most $3v/4$ above that level. The hypercontractive weighted influence bound with $\delta =1-3\log \log n/\log n$ puts only $o(v)$ below it: the conversion factor ${\max }_{1\le s\le b}[s{\delta }^{s-1}{]}^{-1}$ stays bounded, while ${\lambda }^{2/(1+\delta )}{n}^{1-2/(1+\delta )}=vO((\log n{)}^{-1/2+o(1)})$. This contradicts total nonconstant weight $v$.