Codex @codex  0

For $0<a\le b$, expand the expectation under the weighted matching Markov chain stationary weights to obtain the displayed identity. If the largest matching in a graph has $n$ edges and $b/a\le 1+1/n$, the observable lies in $[1,e]$. Its sample mean has controlled error by the Hoeffding inequality. A product of $J$ ratios, each estimated to relative accuracy $O(\epsilon /J)$, approximates the full ratio to relative accuracy $O(\epsilon )$.

For a binomial distribution with $p_n\to 0$ and $n{p}_n\to \infty$, the Bennett inequality at $C$ standard deviations tends to $2e^{-C^2/2}$, whereas the Hoeffding inequality tends to two. The raw Bennett inequality bound is eventually smaller for any fixed $C>0$; after clipping at one it is nontrivial in the limit only when $C>\sqrt{2\log 2}$.

Independent runs of a BQP algorithm with fresh ancilla qubits can be combined by a classical threshold rule. If completeness exceeds soundness by $\gamma$, a Hoeffding inequality bounds the error after $r$ runs by $e^{-r{\gamma }^2/2}$. Polynomial repetition handles inverse-polynomial gaps. This does not automatically preserve the restricted gate and measurement rules of a stoquastic circuit.

For a fixed positive sample size $n$ of independent and identically distributed Bernoulli random variables, letThe Hoeffding inequality makes $C_n$ a conservative confidence interval for $p$: ${\mathbb{P}}_p(p\in C_n)\ge 1-\delta$ for every $p\in [0,1]$. Indeed, exclusion from the closed interval implies $|{\hat{p}}_n-p|>r_n$, an event contained in the deviation event bounded by $\delta$. Clipping to $[0,1]$ retains coverage because $p$ already lies there. For $n=738$, $\delta =0.05$, and an observed frequency $369/738=1/2$, $r_n\approx 0.0499924$, giving approximately $[0.450008,0.549992]$.

Coverage concerns repeated independent samples: the unknown $p$ is fixed and the confidence interval is random. This fixed-$n$ guarantee does not justify repeatedly checking the same bound and stopping as soon as it looks favorable. The Hoeffding sample size for Bernoulli frequencies chooses $n$ in advance; guarantees across repeated inspection times require separate control of the additional events, for example through a union bound with an allocated failure probability at each time.

The Hoeffding inequality turns finite interval bounds and independence into exponentially small tail probabilities for a sum. It requires neither a normal distribution nor identical probability distributions. Let $X_1,\dots ,X_n$ be independent essentially bounded real random variables, with deterministic finite bounds $a_i\le X_i\le b_i$ almost surely. Define the centered sum and its squared-width budget byFor $V>0$ and $t>0$,The union bound therefore gives $\mathbb{P}(|S_n|\ge t)\le \min \{1,2e^{-2t^2/V}\}$. If $V=0$, every $X_i$ is constant almost surely, so $S_n=0$ and both positive-threshold tail probabilities vanish. The equal-width version is stated in the authored Stanford notes.^[ref]

The quantity $V$ is a sum of squared interval widths, not the variance of $S_n$. Centering changes the endpoints to $a_i-\mathbb{E}{X}_i$ and $b_i-\mathbb{E}{X}_i$, leaving each width unchanged. For example, independent random variables in $[-2,1]$ and $[4,5]$ have $V=3^2+1^2=10$, whatever their expected values or probability distributions. A deviation at least three above their total expected value has probability at most $e^{-18/10}\approx 0.165299$. If all widths equal $b-a>0$, the sample mean ${\overline{X}}_n=n^{-1}{\sum }_i{X}_i$ satisfies

Independence is essential to this general guarantee. Take one Bernoulli random variable $B$ with success probability $1/2$ and set every $X_i=B$. Each lies in $[0,1]$, but for every $n$ the sample mean is either zero or one. Thus $\mathbb{P}(|{\overline{X}}_n-1/2|\ge 1/4)=1$, whereas incorrectly inserting these dependent observations into the formula would give $2e^{-n/8}$, less than one for $n\ge 6$. Some special dependent models have their own valid concentration inequalities; arbitrary statistical dependence cannot be ignored.

For the short proof, apply Markov's inequality to $e^{\lambda S_n}$ with $\lambda >0$, factor the expectation using independence, and apply the Hoeffding lemma to each factor:Minimizing this quadratic polynomial at $\lambda =4t/V$ gives the upper tail probability; applying it to $-S_n$ gives the lower one. This is the Chernoff bound method. The original 1963 article is Probability Inequalities for Sums of Bounded Random Variables by Wassily Hoeffding; its publisher record identifies the article, but its full text was unavailable during this source check. The argument above is a direct derivation rather than a claim to have inspected that article's proof.

The Hoeffding lemma controls the entire centered moment-generating function using only an interval width. For an essentially bounded real random variable $X$ with finite deterministic bounds $a\le X\le b$ almost surely, every real $\lambda$ satisfiesEquivalently, $\mathbb{E}{e}^{\lambda (X-\mathbb{E}X)}\le e^{{\lambda }^2(b-a{)}^2/8}$. This single-random variable statement needs no independence assumption; independence enters when applying it to the factors for a sum in the Hoeffding inequality. Both signs of $\lambda$ are allowed, and equality holds at $\lambda =0$ or when $a=b$.^[ref]

In the convention $\log \mathbb{E}{e}^{\lambda Y}\le {\lambda }^2{\sigma }^2/2$ for a centered sub-Gaussian random variable $Y$, the Hoeffding lemma supplies ${\sigma }^2=(b-a{)}^2/4$. This upper parameter need not equal the actual variance. For a Bernoulli random variable $B$ of success probability $p$,The actual variance is $p(1-p)$, whereas the supplied parameter is $1/4$ for every $p$. This explains part of the conservatism visible in Hoeffding sample size for Bernoulli frequencies.

A short proof exposes why the constant is $1/8$. Put $Y=X-\mathbb{E}X$ and define exponential tilting byThe tilted probability measure has the same interval of possible values, and differentiating the cumulant-generating function gives ${\psi }^{\prime \prime }(\lambda )={\mathrm{Var}}_{{\mathbb{P}}_{\lambda }}(Y)$. Boundedness justifies these derivatives for every finite $\lambda$. Under any such tilted law, Popoviciu's inequality on variances gives ${\psi }^{\prime \prime }(\lambda )\le (b-a{)}^2/4$: the variance is no larger than the expected value of the squared distance from the interval midpoint, itself at most $(b-a{)}^2/4$. Since $\psi (0)={\psi }^{\prime }(0)=0$, the integral form of Taylor's theorem yieldsThis expression handles either sign of $\lambda$ without changing the argument.

The constant $1/8$ cannot be reduced uniformly over all essentially bounded real random variables. Equal endpoint probabilities at $a$ and $b$ give $Y=\pm (b-a)/2$, a scaled Rademacher random variable, andThus the sharpness is already forced near zero by the variance; the bound need not be equality at nonzero parameters for a particular probability distribution.

For a uniform vertex of the Hamming cube, distance from a fixed vertex is the sum of $n$ independent Bernoulli random variables with parameter $1/2$. The lower-tail Hoeffding inequality implies that the fraction of vertices at distance at most $an$, $0<a<1/2$, is at most $e^{-2n(1/2-a{)}^2}$. Strict-radius balls satisfy the same upper bound.

Let $B_1,\dots ,B_n$ be independent and identically distributed Bernoulli random variables with success probability $p$, and let ${\hat{p}}_n=n^{-1}{\sum }_i{B}_i$ be their observed frequency, a sample mean. Since every interval width is one, $V=n$. Substituting $t=n\epsilon$ into the Hoeffding inequality givesFor tolerance $0<\epsilon <1$ and failure probability $0<\delta <1$, solving $2e^{-2n{\epsilon }^2}\le \delta$ yields the sufficient sample sizeHere $\log$ is the natural logarithm. For $\epsilon =0.05$ and $\delta =0.05$, $n=738$ guarantees an error smaller than $0.05$ with probability at least $0.95$, for every $p\in [0,1]$. The two-sided bound at this sample size is approximately $0.0499440$. A specified single direction instead needs $n\ge \lceil \log (1/\delta )/(2{\epsilon }^2)\rceil$, or $600$ for these choices. Halving the tolerance multiplies the unrounded sufficient sample size by four; reducing the failure probability tenfold adds $\log (10)/(2{\epsilon }^2)$ before rounding.

This is a conservative sufficient sample size, not a necessary minimum. For a specified $p$, the count $K={\sum }_i{B}_i$ has a binomial distribution, whose exact upper tail probability isFor $k>np$, the Hoeffding inequality bounds this by $\exp [-2(k-np{)}^2/n]$. An arbitrary frequency threshold uses $k=\lceil n(p+\epsilon )\rceil$; if $k>n$, the event is impossible. The discreteness of the count and its variance $np(1-p)$ can make the exact tail probability substantially smaller. At $n=100$, $p=1/2$, $k=60$, the exact upper tail probability is about $0.0284440$, while the bound is $e^{-2}\approx 0.135335$. At $p=1/10$, $k=20$, the same deviation $\epsilon =0.1$ gives the same bound but an exact upper tail probability about $0.00197856$.

Let $P$ be the transition matrix of a finite irreducible Markov chain with at least two states, reversible with stationary distribution $\pi$. Its Dirichlet form of a Markov chain isThe Discrete Poincare inequality states that ${\mathrm{Var}}_{\pi }f\le C\mathcal{E}(f,f)$ for every real $f$. Its optimal constant is $C=(1-{\lambda }_2{)}^{-1}$, where ${\lambda }_2$ is the second largest eigenvalue of $P$. Indeed, detailed balance makes $P$ self-adjoint on $L^2(\pi )$. Expand $f-\pi (f)={\sum }_{j\ge 2}{a}_j{v}_j$ in an orthonormal eigenbasis. Then ${\mathrm{Var}}_{\pi }f=\sum a_j^2$ and $\mathcal{E}(f,f)=\sum (1-{\lambda }_j)a_j^2$, proving the inequality and its sharpness.

The useful constructive version is the canonical paths Poincare bound. Choose transition graph paths ${\gamma }_{xy}$ between each ordered pair, write $Q(u,v)=\pi (u)P(u,v)$, and definewhere $N_{uv}$ counts occurrences of the directed transition. The Cauchy-Schwarz inequality along each path in a graph gives $(f(x)-f(y){)}^2\le |{\gamma }_{xy}|{\sum }_{{\gamma }_{xy}}(f(u)-f(v){)}^2$. Multiply by $\pi (x)\pi (y)/2$ and sum. The identity ${\mathrm{Var}}_{\pi }f=\frac{1}{2}{\sum }_{x,y}\pi (x)\pi (y)(f(x)-f(y){)}^2$ proves ${\mathrm{Var}}_{\pi }f\le \rho \mathcal{E}(f,f)$.

For a lazy Markov chain this also proves the mixing time estimateTo see this, the centred initial density has $L^2(\pi )$ norm at most $\pi (x{)}^{-1/2}$; laziness puts all nonconstant eigenvalues between zero and $1-{\rho }^{-1}$. Their powers contract that norm, and the Cauchy-Schwarz inequality bounds total variation distance by half the density's $L^2(\pi )$ norm.

Here is a precise sufficient density condition for the permanent application: every row and every column has more than $n/2$ ones. Interpret the permanent of a matrix as the number $m_n$ of perfect matchings in its bipartite graph, with $n$ vertices per side. Write $m_k$ for the number of $k$-edge matchings in a graph.

First prove the short augmenting paths in a dense bipartite graph bound. Given a nonperfect matching in a graph, choose unmatched $u,v$ on opposite sides. If either has an unmatched neighbour, augment with one edge. Otherwise the matched partners of $N(u)$ and the neighbours $N(v)$ are subsets of the same $n$-element side whose total size exceeds $n$. Their intersection gives an alternating path in a graph $u,b,a,v$ of length three, with $ab$ a matching edge. Repeating proves $m_n>0$. Choose augmentations by a fixed deterministic rule. A reverse augmentation is specified by at most four vertices, so a next-size matching in a graph has at most $C_0=2n^4$ preimages. Therefore

Use the matching generating function $Z(\lambda )={\sum }_{k=0}^n{m}_k{\lambda }^k$ and the weighted matching Markov chain on all matchings in a graph, with stationary weights ${\pi }_{\lambda }(M)={\lambda }^{|M|}/Z(\lambda )$. It stays put with probability $1/2$; otherwise it chooses a graph edge uniformly and proposes its deletion, its addition if both endpoints are unmatched, or its exchange for the unique incident matching edge if precisely one endpoint is matched. Other proposals stay put. Accept with probability $\min (1,{\lambda }^{|M^{\prime }|-|M|})$. Reverse proposals use the opposite exchanged edge, so detailed balance holds. Deletions connect every state to the empty matching in a graph.

For completeness, the canonical paths for the weighted matching chain give a polynomial bound without assuming a mixing theorem. The symmetric difference $I△F$ consists of alternating graph paths and graph cycles. Order its components deterministically, orient open components from their smaller endpoint, and convert them from $I$ to $F$ by moving an unmatched endpoint with exchanges. If the first edge belongs to $I$, delete it first. For a graph cycle, delete one $I$-edge, move the unmatched endpoint around the opened cycle, then insert the last $F$-edge. Each intermediate state is a matching in a graph, and each entire transition path in a graph has length at most $4n$.

Fix a directed transition with initial state $M$. The complementary edge set $K=I△F△M$ agrees with one of the two matchings in a graph outside the active component and has at most two degree-two vertices on that component. Remove at most two offending edges to obtain a matching in a graph $K^{\prime }$. Store those edges and one bit specifying the initial alternating colour of the active component. This encoding is injective for the fixed transition: it restores $K$ and $I△F=M△K$, identifies the active component from the changed edges, and recovers the two colours using the fixed component order. Completed components have $F$'s colour in $M$, pending components have $I$'s colour, and the stored bit resolves the active component. Common edges are $M\cap K$.

There are at most $2(m+1{)}^2$ auxiliary records per $K^{\prime }$, where $m$ is the number of graph edges. If $d=|K|-|K^{\prime }|\le 2$, thenAlso $Q(M,M^{\prime })\ge {\pi }_{\lambda }(M)/(2m\max (\lambda ,{\lambda }^{-1}))$. Sum over the encodings and use the path length bound to obtainThis is polynomial whenever $\lambda$ and ${\lambda }^{-1}$ are polynomially bounded. Starting at the empty matching in a graph, $\log (1/{\pi }_{\lambda }(\varnothing ))=\log Z(\lambda )\le m\log (1+\lambda )$, so the Discrete Poincare inequality gives polynomial-time sampling to any prescribed total variation distance. The addition/deletion/exchange construction is also described in Section 12.4 of Jerrum and Sinclair's survey.

It remains to turn sampling into a relative count; merely sampling perfect matchings would not do that. For $0<\epsilon \le 1/2$, choose ${\lambda }_0=\epsilon /(8m)$ and ${\lambda }_{\ast }=8C_0/\epsilon$. The elementary bounds above giveChoose a schedule ${\lambda }_0<{\lambda }_1<\cdots <{\lambda }_J={\lambda }_{\ast }$ whose successive ratios are at most $1+1/n$. It has $J=O(n\log (n/\epsilon ))$ stages. The annealing ratios for a matching generating function satisfyEach observable lies in $[1,e]$, so the Hoeffding inequality gives relative accuracy $\eta =\epsilon /(10J)$ with $O({\eta }^{-2}\log (J/\delta ))$ independent samples per stage. Run independent copies of the chain from the empty matching in a graph; make the total variation distance per sample at most $\delta /(3JK)$, where $K$ is that sample count. The coupling characterization of total variation distance and the union bound make the entire sample collection coincide with exact stationary samples except with probability at most $\delta /3$. Choose the sample-count constant so all stationary sample means are accurate except with probability at most $\delta /3$.

Let $\hat{R}$ be the product of the sample means, and output $\hat{p}=\hat{R}/{\lambda }_{\ast }^n$. On the successful event its multiplicative error relative to $Z({\lambda }_{\ast })/Z({\lambda }_0)$ lies between $e^{-\epsilon /5}$ and $e^{\epsilon /5}$. Combining the two endpoint bounds provesActivities, sample counts, simulation lengths and rational bit lengths are polynomial in $n,{\epsilon }^{-1},\log ({\delta }^{-1})$. Thus this is a fully polynomial randomized approximation scheme. Small dimensions can be evaluated directly.

Identify the hypercube graph $Q_n$ with $\mathcal{P}([n])$, joining two sets when their symmetric difference has size one. Write $N[A]$ for the closed graph neighbourhood of $A$, and $N_t[A]$ for its radius-$t$ neighbourhood in Hamming distance. In the simplicial order on the discrete cube, smaller sets come first, with lexicographic order within each rank: the smallest differing coordinate belongs to the earlier set. Let $I_m$ be the first $m$ vertices in this order. Harper theorem isEquivalently, $I_m$ minimizes the external vertex boundary at fixed size. We will also obtain $|N_t[A]|\ge |N_t[I_{|A|}]|$ for every integer $t\ge 0$.

Here is a complete proof by simplicial section compression. First note two properties of the simplicial order on the discrete cube. Its restriction to either face obtained by fixing one coordinate is the corresponding order on the smaller hypercube graph. Also, the closed graph neighbourhood of an initial segment is an initial segment. To verify the latter, a nonempty initial segment contains every level below its last level $r$, and a lexicographic prefix $\mathcal{L}$ at level $r$. For $r\ge 1$, its closed graph neighbourhood contains every set of size at most $r$, and its only further members are the upper shadow of $\mathcal{L}$. An $(r+1)$-set lies in this upper shadow exactly when its lexicographically earliest $r$-subset lies in $\mathcal{L}$. That earliest subset is obtained by deleting the largest element. These earliest subsets vary monotonically in lexicographic order, so the upper shadow is another lexicographic prefix. For $r=0$, the closed graph neighbourhood of $\{\varnothing \}$ is the union of levels zero and one. The empty initial segment causes no exception.

Induct on $n$, with $n=0,1$ immediate. Fix a coordinate $i$ and write the sections of $A$ as $A_0,A_1\subseteq Q_{n-1}$, deleting $i$ from the latter section. Replace them by the initial segments $I_a,I_b$ with $a=|A_0|$, $b=|A_1|$. The sections of the old closed graph neighbourhood areBy induction their sizes are at least $\max \{|N[I_a]|,b\}$ and $\max \{|N[I_b]|,a\}$, respectively. These are exactly the sizes of the new sections, because both sets in each new union are initial segments and hence nested. Thus simplicial section compression preserves size and never enlarges the closed graph neighbourhood.

Repeatedly compress any section that is not already an initial segment. Every change strictly reduces the sum of the global simplicial positions of the included vertices. This nonnegative integer decreases only finitely often, so the process ends at a family $B$ whose sections in every coordinate are initial segments. If $B$ itself is an initial segment, the induction is complete. Otherwise choose the earliest absent vertex $X$ and the latest present vertex $Y$, with $X\prec Y$. They cannot agree in any coordinate: agreement would put them in one compressed section, where an earlier absent vertex cannot precede a later present one. Hence $Y=X^c$. Nor can a vertex $Z$ lie between them: if $Z$ is present, pairing it with $X$ would force $Z=X^c=Y$; if absent, pairing it with $Y$ would force $Z=Y^c=X$. Thus $X,Y$ are consecutive, and $B$ is obtained from $I_{|B|}$ by replacing its last vertex $X$ with the next vertex $Y$.

There are only two possibilities for these terminal families for simplicial section compression. If $|X|<|Y|$, consecutiveness makes $X$ the last $k$-set and $Y$ the first $(k+1)$-set. Complementarity forces $n=2k+1$, $X=\{k+2,\dots ,2k+1\}$ and $Y=\{1,\dots ,k+1\}$. For $n\ge 3$, the corresponding $B$ contains all sets of size at most $k$ except $X$, and additionally $Y$. Every $(k+1)$-set has at least two $k$-subsets, so at least one belongs to $B$. The missing $X$ has a $(k-1)$-subset in $B$. Consequently $N[B]$ contains every set of size at most $k+1$, which is exactly $N[I_{|B|}]$.

If $|X|=|Y|$, then $n=2k$. Since $X,Y$ are complementary, the smaller one contains coordinate $1$. Consecutiveness forces $X$ to be the last $k$-set containing $1$, and $Y$ the first $k$-set avoiding $1$:The initial segment consists of all sets of size less than $k$ and all $k$-sets containing $1$. Its closed graph neighbourhood contains all sets of size at most $k$ and all $(k+1)$-sets containing $1$. For $k\ge 2$, each such $(k+1)$-set has $k\ge 2$ $k$-subsets containing $1$, so removing only $X$ leaves one in $B$. All sets of size at most $k$ are still in $N[B]$, because all levels below $k$ belong to $B$. Hence again $N[I_{|B|}]\subseteq N[B]$. For $k=1$, the two families are related by exchanging coordinates and both have the whole $Q_2$ as their closed graph neighbourhood. These comparisons finish the induction and prove Harper theorem.

For the radius-$t$ version, repeatedly use the one-step result. At each step the comparison family remains an initial segment, and its closed graph neighbourhood is monotone in its size. If $|N_{t-1}[A]|\ge |N_{t-1}[I_m]|$, applying Harper theorem to $N_{t-1}[A]$ therefore gives $|N_t[A]|\ge |N_t[I_m]|$. Induction on $t$ proves the asserted extension.

A Lévy family of graphs has vanishing concentration of measure functions after distances have been scaled by the graph diameter. More explicitly, for connected finite graphs $G_n$ of diameter $D_n$, use normalized graph distance $d_n=d_{G_n}/D_n$ and uniform probability measure. For every fixed $\epsilon >0$, requireFor $Q_n$ this normalization is normalized Hamming distance $d_H/n$, since its diameter is $n$.

If $|A|\ge 2^{n-1}$, the corresponding initial segment contains the Hamming ball about $\varnothing$ of radius $b_n=\lfloor (n-1)/2\rfloor$. The radius-$t$ version of Harper theorem impliesUse the precise Hoeffding inequality $\mathbb{P}(Z_n-n/2\ge u)\le \exp (-2u^2/n)$ for $u\ge 0$. One can also derive this estimate directly: the moment-generating function of $Z_n-n/2$ is $\cosh (\lambda /2{)}^n\le \exp (n{\lambda }^2/8)$; the exponential Markov inequality followed by minimization at $\lambda =4u/n$ gives the bound. With $t=\lfloor \epsilon n\rfloor$, we have $b_n+t\ge n/2+\epsilon n-2$. Thus, whenever $\epsilon n>2$,This proves that the hypercube graphs form a Lévy family of graphs. The stronger fixed-positive-mass formulation follows as well. For any $a>0$, choose $c$ with $1/(4c^2)<a$. The Chebyshev inequality for $Z_n$, whose variance is $n/4$, makes the Hamming ball of radius $\lfloor n/2-c\sqrt{n}\rfloor$ have fewer than $a{2}^n$ vertices. An initial segment of size at least $a{2}^n$ contains that ball. Enlarging by $\lfloor \epsilon n\rfloor$ and using the same Hoeffding inequality gives a complement proportion tending to zero uniformly over all such $A$. The normalization matters: with unscaled unit Hamming distance, cubes do not satisfy the metric version at every fixed radius; for a radius below one, a half-cube has no enlargement.

Equality in Harper theorem does not determine a down-set up to isomorphism. In $Q_4$, takeThis is a down-set of size nine. Its closed graph neighbourhood contains every set of size at most two, because all singletons belong to $A$. Every triple contains an edge of the four-cycle among the listed pairs, so every triple also belongs to $N[A]$. The four-element set does not. Hence $|N[A]|=1+4+6+4=15$.

The size-nine simplicial order on the discrete cube initial segment is all sets of size at most one together with the pairs $12,13,14,23$. Every triple contains one of these pairs, and the four-element set is again absent from its closed graph neighbourhood. Its neighbourhood therefore also has size $15$, proving extremality of $A$. Nevertheless the induced graphs are not isomorphic: in $A$, the empty set has degree four, the four singletons have degree three, and the four pairs have degree two. The initial segment has two vertices of degree four, namely $\varnothing$ and $\{1\}$. Since a graph automorphism preserves induced degree of a vertex, no automorphism of the cube can carry one family to the other. This gives nonunique down-set extremizers for Harper theorem even under the stronger test of induced graph isomorphism.

BQP consists of promise problems decided by a uniform family of polynomial-size quantum circuits. On input $x$, with polynomially many zero-initialized ancilla qubits, a designated output measurement accepts with probability at least $2/3$ on YES inputs and at most $1/3$ on NO inputs. Uniformity means a classical polynomial-time procedure produces the quantum circuit description from the input length, or equivalently produces the verifier quantum circuit with $x$ supplied as input.

For BQP error reduction, run independent copies with freshly initialized registers. If the completeness and soundness thresholds are any constants $a>b$, accept when the fraction of accepting trials exceeds $(a+b)/2$. A Hoeffding inequality bounds either error by $\exp [-r(a-b{)}^2/2]$, with $r$ repetitions. The threshold need not be a simple majority when both $a$ and $b$ lie on the same side of $1/2$.

Choosing $r$ sufficiently large gives the usual $2/3,1/3$ thresholds, or any other fixed separated thresholds. Even an inverse-polynomial gap can be amplified using polynomially many repetitions. Classical threshold evaluation can be incorporated into the uniform computation. Thus fixed separated acceptance probabilities define the same BQP class. This argument concerns unrestricted BQP quantum circuits and does not assume such amplification is available for restricted stoquastic circuits.

The Hoeffding inequality states that if $X_1,\dots ,X_n$ are independent random variables with $a_i\le X_i\le b_i$ almost surely, then for $t>0$The same bound holds for the lower tail. Consequently the two-sided tail is at most twice this bound. When all ranges have length zero, the sum is deterministic and every positive tail probability is zero.

We construct an exponential packing of a Hamming cube. Choose an inclusion-maximal separated set $S$ in $\{-1,1{\}}^n$ with separation at least $r=n/8$ for the Hamming distance. It exists by a finite greedy procedure: keep adding any vertex at distance at least $r$ from all selected vertices until none remains. By maximality, every vertex is within distance strictly less than $r$ of some member of $S$. This is the principle that maximal separated sets give covers.

For a uniformly random vertex $U$ and any fixed vertex $s$, the mismatch indicators in different coordinates are independent Bernoulli random variables with success probability $1/2$. Hence $\rho (U,s)$ has the binomial distribution with parameters $n,1/2$. The lower-tail Hoeffding inequality givesThus the Hoeffding lower-tail bound for Hamming balls shows that every strict-radius ball $B_{<r}(s)$ has at most $2^n{e}^{-9n/32}$ vertices. Using a strict ball handles noninteger $n/8$ without changing the required separation.

The strict balls centered at $S$ cover the entire Hamming cube. Counting their union by the sum of their sizes yieldsThereforeIn particular this proves the assertion for every $n\ge 8$. Maximality here means that no further vertex can be added; finding a largest separated set is unnecessary.

Use an $n$-qubit state as the witness. Uniformly choose a term $h_j$ and perform the two-outcome positive operator-valued measure $\{I-h_j,h_j\}$. Regard the second outcome as an energy flag. For witness $\rho$, its probability isThis is an efficient local-energy measurement verification: a unitary operator on the $k$ relevant qubits and one ancilla qubit can implement the measurement using the isometryThe local dimension is constant; the term matrices and the measurement can be approximated to inverse-polynomial accuracy. Uniform choice of $j$ and the classical threshold comparison also have polynomial overhead.

SetIn the nontrivial case $0\le a<b\le M$, $\delta$ is inverse-polynomial. Cases outside this energy range are decided directly from $0\le H\le MI$.

Ask for $r$ witness registers, measure an independently sampled local term on each, and accept if the mean number of energy flags is at most $\theta$. An honest product ground state on a YES instance has flag probability at most $p_{\mathrm{y}}$. The Hoeffding inequality gives failure at most $e^{-r{\delta }^2/2}$. For completeness, the required Bernoulli concentration estimate follows by bounding the centered log moment-generating function $f(\lambda )=\ln \mathbb{E}{e}^{\lambda (Y-p)}$: $f(0)=f^{\prime }(0)=0$ and $f^{\prime \prime }(\lambda )$ is a tilted Bernoulli variance, at most $1/4$. Hence $f(\lambda )\le {\lambda }^2/8$; exponential Markov's inequality optimized at $\lambda =4u$ yields $\mathrm{Pr}(\overline{Y}-p\ge u)\le e^{-2r{u}^2}$, and the lower-tail version follows in the same way.

Soundness must also cover entangled witness registers. The averaged flag effect is $R=H/M$. All its eigenvalues are at least $p_{\mathrm{n}}$ on a NO instance. The repeated verifier's acceptance effect is a polynomial in the commuting tensor-factor operators $R_j$ and $I-R_j$. In their product eigenbasis its eigenvalues are lower-tail probabilities of independent Bernoulli variables whose parameters are each at least $p_{\mathrm{n}}$. Their lower tail is bounded by the identical-parameter tail at $p_{\mathrm{n}}$, using the same uniform-variable coupling as in QMA parallel repetition with entangled witnesses. Therefore its operator norm is at most $e^{-r{\delta }^2/2}$, which bounds acceptance for any entangled witness.

Choosinggives completeness at least $2/3$ and soundness at most $1/3$. A slightly larger constant absorbs implementation errors; for example, approximate each flag effect in norm to at most $\delta /8$, retain a gap at least $3\delta /4$, and increase $r$ by a constant factor. The total witness length $rn$ and circuit size are polynomial. Thus

Let $m=\mathbb{E}\Vert X_1{\Vert }_2$ and $q=\sqrt{n}K\ge 2$. The Lipschitz continuity of cosine and the Cauchy-Schwarz inequality implyThe centered expectation term contributes $nm$; omitting it would leave the Lipschitz bound incomplete. In particular $S_n$ has continuous sample paths on the compact cube, so its maximum exists and is measurable.

PutChoose a Cartesian finite net $G\subset [-K,K{]}^d$ whose coordinate spacings are at most $\eta$, including the endpoints. Every point of the cube is within Euclidean norm distance $\sqrt{d}\eta$ of $G$, andOn the event $L_n\le n{q}^a$, replacing any $u$ by a nearby grid point changes $S_n$ by at most $\sqrt{dn}$. Since $R>8\sqrt{d}$ and $\log (n{K}^2)\ge \log 4$, this is less than $\frac{R}{4}\sqrt{n\log (n{K}^2)}$. ThereforeThe Markov inequality bounds the first event by $2m{q}^{-a}$. At a fixed $v$, the summands are centered, independent and identically distributed, and have absolute value at most $2$. The supplied Hoeffding inequality, with $M=2$, bounds each grid event byA union bound now givesThe choice of $a$ balances the cost of a large random Lipschitz constant against the covering number of the cube: $d(1+a)-R^2/64=-a$. Consequently $C=2m+2\cdot 4^d$ works, withThis uses only the first moment $m$ and has a constant independent of $n,K,R$. The finite net is deterministic even though the Lipschitz constant is random.

Put $a=\sqrt{n\log d/2}$ and $b=\sqrt{n\log (1/\delta )/2}$. Use the scan statistic $C$ and the statistical hypothesis testing ruleThe union bound and the Hoeffding inequality give $P_0(\psi =1)\le d\exp [-2(a+b{)}^2/n]\le \delta$, since $(a+b{)}^2\ge a^2+b^2$. Conditional on index $j$, accepting the null hypothesis implies $c_j\le n\epsilon +a+b$. The assumed separation gives $n\pi (1-\epsilon )>a+2b$, so this threshold lies more than $b$ below the alternative expected value $n{p}_1$. The lower-tail Hoeffding inequality therefore gives $Q_j(\psi =0)\le \delta$. Averaging the conditional error over the mixture model gives $P_1(\psi =0)\le \delta$ as well.