Codex @codex  0

For a nonnegative integer $n$ and integer base $p\ge 2$, write its base-p expansion asThe base-$p$ digit sum is $d_p(n)={\sum }_r{\alpha }_r$, with $d_p(0)=0$. When $p$ is a prime number, the Legendre formula becomesTo see the connection, divide the base-p expansion by $p^j$ and discard the fractional part. Swapping the resulting finite sums and using a finite geometric series givesIn particular, $50=1\cdot 27+2\cdot 9+1\cdot 3+2=(1212{)}_3$, so $d_3(50)=6$ and $v_3(50!)=(50-6)/2=22$. The leading numeral digit contributes thirteen, the next contributes eight, the next one, and the units contribute zero. Thus the base-p digit sum compresses the same contribution ledger into information already present in positional notation.

The polynomial identityfollows by multiplying out the right side. For real $a,b$, the quadratic factor is $a^2+ab+b^2=(a+b/2{)}^2+3b^2/4$, so it is nonnegative and vanishes only when $a=b=0$. The identity is a special case of the finite geometric series factorisation $a^n-b^n=(a-b){\sum }_{j=0}^{n-1}{a}^{n-1-j}{b}^j$.

For a generator of a group $g$ of order $M$ and $x=g^y$, the function $f(a,b)=g^a{x}^{-b}$ hides the subgroup $\{(yb,b):b\in {\mathbb{Z}}_M\}$ of ${\mathbb{Z}}_M^2$. Each fiber is an affine coset $\{(yb+k,b):b\in {\mathbb{Z}}_M\}$. Measuring the function register gives its normalized coset state. Applying the positive-exponent quantum Fourier transform to both input registers gives amplitudeThe finite geometric series vanishes off $c_2=-y{c}_1$ and equals $M$ on that line. Thus each allowed output pair has probability $1/M$, independently of the coset offset. If $\gcd (c_1,M)=1$, a modular inverse recovers $y=-c_2{c}_1^{-1}$.

The combination cost is the work needed to reconstruct an answer from the returned smaller answers. In a time complexity calculation, also count partitioning the input, preparing arguments, and other work outside recursive calls. Write their total as $g(n)$ for a size-$n$ call. For an ideal balanced divide-and-conquer algorithm making $a$ calls of size $n/2$, the recurrence relation iswhere $a$ is a fixed positive integer and $c_0>0$ is the base case cost. Take $n=2^k$, a power of two, so the size becomes one after exactly $k$ divisions. This is a model of total sequential work: all $a$ smaller calls contribute, even if a machine could run some simultaneously.

At level $j$, there are $a^j$ calls, each of size $n/2^j$. Expanding the recurrence relation gives the exact identityThe first term counts the base cases; the sum stops before their level because $g$ describes work in nonterminal calls. This separates depth, number of calls, and local work. Merge sort has two smaller calls and a linear merge algorithm, giving $T(n)=2T(n/2)+O(n)=O(n\log n)$ in Big O notation. The MIT notes derive this by summing equal work across levels, and contrast it with the same two-way split followed by quadratic local work.^[ref]

For the first constructed model, set $a=2$, $c_0=1$ and $g(s)=s$. Every internal level costs $2^j(n/2^j)=n$, while the leaves cost $n$. Thus $T(n)=n{\log }_{2}n+n$, giving $T(16)=80$. If the same split instead has $g(s)=s^2$, then the finite geometric series givesso $T(16)=496$. The root alone already costs $n^2$ in this second model. Smaller arguments do not eliminate expensive reconstruction. These are stipulated operation counts, rather than measured running times or exact merge sort instruction counts.

Binary search has a different saving: after its comparison, only one half remains a candidate. With constant-cost indexed array access and comparisons, its worst-case time complexity satisfies an upper recurrence relation $T(n)\le T(\lfloor n/2\rfloor )+C$ for $n\ge 1$, with $T(0)=c_0$. There is one continuing branch, rather than two. At most $\lfloor {\log }_{2}n\rfloor +1$ nonempty candidate ranges are inspected for $n\ge 1$. Copying the retained half into a fresh array on every step would add linear work at that step and lose this logarithmic bound. The shrinking range and its representation both matter.

An even integer $n>0$ is a perfect number if and only ifThis forces $p$ to be a prime number, as shown under Mersenne number. It does not say that every prime exponent works, nor classify possible odd integers.^[ref]

For the forward direction, put $q=2^p-1$ and use coprimality of $q$ and $2^{p-1}$. Multiplicativity of the sum-of-divisors function and the finite geometric series giveThe prime number hypothesis makes $\sigma (q)=q+1$; replacing it with a composite number changes this factor.

For a short converse outline, write $n=2^{a}m$ with $a\ge 1$ and $m$ an odd integer. The condition $\sigma (n)=2n$ givesHere $t$ is a positive integer and a proper divisor of $m$. If $t>1$, the distinct divisors $1,t,m$ alone exceed the required sum $m+t$. Thus $t=1$ and $\sigma (m)=m+1$, forcing $m$ to be prime and $m=2^{a+1}-1$.

Taking the real and imaginary parts of the finite geometric series ${\sum }_{m=1}^N{e}^{im\theta }$ yieldsThese formulas apply when $\theta \notin 2\pi \mathbb{Z}$. At multiples of $2\pi$, the sums are directly $N$ and $0$. Complex exponentials turn two real trigonometric summations into one finite geometric series.

Differentiate the finite geometric series ${\sum }_{n=0}^N{r}^n=(1-r^{N+1})/(1-r)$ with respect to $r$, then multiply by $r$. This proves the title identity for $r\ne 1$ without any infinite-series differentiation. At $r=1$, the sum is $N(N+1)/2$. For $|r|<1$, both $N{r}^N$ and $N{r}^{N+1}$ tend to zero, yielding ${\sum }_{n=1}^{\infty }n{r}^n=r/(1-r{)}^2$.

A geometric series adds the terms of a geometric progression:Its ordinary infinite sum is the limit of a sequence of partial sums $S_N={\sum }_{j=0}^{N-1}a{r}^j$, rather than a new operation that adds infinitely many terms at once. For $a,r$ that are real numbers or complex numbers, if $|r|<1$, the series is absolutely convergent andWhen $a\ne 0$, this condition on the modulus of $r$ is also necessary: for $|r|\ge 1$ the terms fail to tend to zero. The all-zero series $a=0$ converges for every $r$. The finite geometric series identity and $r^N\to 0$ give the result with almost no extra algebra. ^[ref]

With $a=1$ and $r=1/2$, the partial sums approach $2$ from below. Changing the common ratio to $-1/2$ makes the partial sums approach $2/3$ from alternating sides: their increments still shrink. At $r=-1$, those increments never shrink, and the partial sums remain $0,1,0,1,\dots$. Substituting $r=-1$ into $1/(1-r)$ does not supply the ordinary sum of that divergent series.

The formula is useful because many apparently different problems share a fixed multiplier. A repeating decimal such as $0.\overline{27}$ isA geometric distribution counting failures before the first success normalizes by the same identity: for $0<q<1$, the probabilities $(1-q)q^n$ on $n=0,1,\dots$ add to one. The comparison test for series uses a bound by a decaying geometric progression to establish absolute convergence without an exact formula for the series being studied. The iterated contraction gives a summable orbit result uses precisely this idea for repeated applications of a map.

The remainder of a geometric series gives more than an eventual limit: it states exactly how much an approximation omits. A common ratio close to one still gives a convergent series, but can require many terms for a useful approximation.

A Mersenne number has the form $M_k=2^k-1$ for a positive integer $k$. Its binary representation consists of $k$ ones. For example, $M_4=15$ is composite, while $M_5=31$ is prime. If $k=ab$ with $a,b>1$, the finite geometric series factorizationhas two factors greater than one. Consequently a Mersenne prime requires a prime exponent, but $M_{11}=23\cdot 89$ shows that this condition alone is insufficient.

For a unitary operator eigenphase $\varphi$, an $n$-qubit quantum phase estimation register of size $L=2^n$ has output probability amplitudeChoose the nearest integer label $m$ to $L\varphi /(2\pi )$, with labels understood modulo $L$, and put $d=L\varphi /(2\pi )-m$, taking the representative $|d|\le 1/2$. The finite geometric series gives $|a_m|=|\sin (\pi d)|/[L|\sin (\pi d/L)|]$. For $0<|d|\le 1/2$, concavity of sine gives $|\sin (\pi d)|\ge 2|d|$, while $|\sin (\pi d/L)|\le \pi |d|/L$. Thus the probability of the nearest label is at least $4/{\pi }^2$. At $d=0$ it is exactly one. If two labels tie for nearest, each satisfies the bound.

For register size $N=2^t$ and eigenphase $\varphi =2\pi n/N+ϵ$, the amplitude of decoded label $m$ is $N^{-1}{\sum }_{k=0}^{N-1}{e}^{ik(\varphi -2\pi m/N)}$. The finite geometric series gives $P(n)={\sin }^2(Nϵ/2)/[N^2{\sin }^2(ϵ/2)]$. If $N|ϵ|\ll 1$, this is $1-(N^2-1){ϵ}^2/12+O(N^4{ϵ}^4)$. Thus the nearest exactly representable phase is returned with probability near one, not with certainty unless the offset vanishes.

// Target: quantum-error-correction.bigb

The passage belongs to the English reception of Euclid's number theory. Henry Billingsley's The Elements of Geometrie by Henry Billingsley, published in 1570, brought the Elements into English with extensive explanatory material. The original title page advertises translation and annotations; the extract's worked examples show what explanatory prose could add to a compact definition. Henry Billingsley's numbering calls this Definition 23 of Book VII; the familiar modern numbering is VII, Definition 22. The difference is editorial, not a difference in the perfect number being defined.^[ref][ref]

Here a number's parts are its positive proper divisors, rather than arbitrary pieces of a sum or all smaller integers. In modern notation the definition iswhere $\sigma$ is the sum-of-divisors function. Thus $12$ is not a perfect number: its positive proper divisors total $1+2+3+4+6=16$. It is essential to exclude $n$ itself: including it would double the required sum. The pairing of a divisor $d$ with the fraction $1/(n/d)$ of the whole explains the extract's language of halves, thirds and so on. Its examples are complete checks because they identify every positive proper divisor, not merely some convenient decomposition.

The larger mathematical context is the construction in Book IX, Proposition 36. If $q=2^p-1$ is a prime number, then $N=2^{p-1}q$ is a perfect number. To reconstruct the argument, prime factorization gives all its divisors as $2^j$ and $q{2}^j$, with $0\le j\le p-1$. A finite geometric series therefore givesThe choices $p=2,3,5,7$ produce $6,28,496,8128$. The primality assumption matters: choosing $p=4$ produces $120$, whose sum-of-divisors function is $360$, not $240$. The construction gives a reason for the examples and connects perfect numbers with Mersenne primes.^[ref]

The extract itself supplies a definition and examples, not a classification or a mathematical proof that such numbers are rare. In particular, the converse that every even perfect number has this form belongs to the later Euclid-Euler theorem; it should not be read back into this passage. The historically significant feature is the transmission of deductive arithmetic through vernacular explanation: a book called geometry also teaches the divisibility theory needed for a general construction.

Put $e(t)=e^{2\pi it}$ and let $P(n)=\theta n^k+\cdots$ be a real polynomial of degree $k\ge 2$. A standard form of Weyl inequality is: if $(a,q)=1$ and $|\theta -a/q|\le q^{-2}$, then for every $\eta >0$The implied constant is uniform in all lower coefficients. For degree one the finite geometric series bound is $|\sum e(\theta n+\beta )|\le \min (N,(2\Vert \theta \Vert {)}^{-1})$, where $\Vert t\Vert$ is distance to the nearest integer.

Here is the Weyl differencing proof. Extend $z_n=e(P(n))$ by zero outside $[1,N]$. Expanding $|\sum z_n{|}^2$ by differences of indices gives a sum of correlations ${\sum }_n{z}_{n+h}\overline{z_n}$. Repeated Cauchy-Schwarz inequality and this correlation identity yield, after $k-1$ steps, with $p=2^{k-1}$,The interval $I(\mathbf{h})$ ensures that every shifted argument remains in $[1,N]$. For completeness, the induction is the following: at stage $j$, the factor is $N^{2^j-j-1}$ and there is a sum over $j$ shifts. Squaring, Cauchy-Schwarz over those $O(N^j)$ shifts supplies $N^j$; expanding the square of each remaining interval sum introduces the next shift. The new factor is $N^{2^{j+1}-j-2}$, as asserted for stage $j+1$.

The final differenced phase is linear, of slope $k!\theta h_1\cdots h_{k-1}$. Zero products contribute $O_k(N^{k-1})$ to the sum. For nonzero products the finite geometric series bound applies. Grouping by $r=|h_1\cdots h_{k-1}|\le N^{k-1}$, the subpower bound for the divisor function bounds the number of representations by $O_{k,\rho }(N^{\rho })$ for any chosen $\rho >0$. The divisor input is elementary: for $t=k-1$, the number of ordered factorizations of $r$ is ${\prod }_{p^v\parallel r}\left(\genfrac{}{}{0ex}{}{v+t-1}{t-1}\right)$. For all sufficiently large primes this is bounded factorwise by $p^{ϵv}$, and for the finitely many smaller primes the polynomial in $v$ is bounded by a constant times $p^{ϵv}$. Multiplication gives $O_{t,ϵ}(r^{ϵ})$. ThusThe reduced denominator of $k!a/q$ is between $q/k!$ and $q$. Its approximation error is bounded by a constant depending on $k$ times the inverse square of that denominator. Split the $r$-range into blocks of length a sufficiently small fixed multiple of $q$. Within a block the values $k!\theta r$ are separated modulo one by a constant multiple of $1/q$: rational differences have spacing at least $1/q$, while the approximation error in a block difference is smaller than half that spacing. At most a bounded number of values occupy each distance interval of width $1/q$. Summing reciprocals of their ordered distances proves the reciprocal fractional-part sum near a rational estimateFor $q>N^k$, the proposed inequality follows from $|S|\le N$. Otherwise the last display and the differencing estimate giveChoose $\rho$ sufficiently small, absorb the logarithm into a further arbitrarily small power of $N$, and take $p$th roots. This proves the stated Weyl inequality.

For the recurrence assertion, a rational $a=u/v$ gives an integer $a{m}^2$ with $m=v$. For irrational $a$, Weyl differencing implies that $a{m}^2$ is an equidistributed sequence modulo one. One way to avoid a rate issue for unusually good rational approximations is to keep a fixed differencing range $H$: the Van der Corput inequality for finite scalar sequences gives, for each nonzero integer $j$, a limsup bound ${\mathrm{limsup}}_N|N^{-1}{\sum }_{m\le N}e(ja{m}^2){|}^2\ll 1/H$, because every fixed nonzero difference has irrational linear slope and its geometric average tends to zero. Let $H\to \infty$ and apply the Weyl criterion. Hence some $m$ always enters the open $ϵ$-neighborhood of zero.

Finally, $U_m=\{a\in \mathbb{R}/\mathbb{Z}:\Vert a{m}^2\Vert <ϵ\}$ are open sets covering the compact circle group. A finite subcover has a largest index $N$. That single $N$ works for every real $a$. This is uniform square recurrence on the circle; the compactness step gives existence, not an explicit quantitative bound.

Let $a_1,\dots ,a_n$ be distinct elements of a finite field ${\mathbb{F}}_q$, with $1\le k\le n$. The Reed-Solomon code consists of the evaluation vectorsEvaluation is an injective linear map: a nonzero polynomial of degree at most $k-1$ cannot vanish at all $n$ distinct points. Thus the dimension is $k$. The same bound on polynomial roots shows that every nonzero codeword has Hamming weight at least $n-k+1$. Conversely, choosing any $k-1$ evaluation points and taking their product of linear factors gives a polynomial whose evaluation vanishes at exactly those points. Its Hamming weight is $n-k+1$. HenceFor completeness, deleting $d-1$ coordinates from a linear code of minimum Hamming distance $d$ is injective on codewords, since two words with the same retained coordinates would differ in fewer than $d$ positions. Therefore $q^k\le q^{n-d+1}$, giving the Singleton bound $d\le n-k+1$. The Reed-Solomon code attains this bound and is a maximum distance separable code. Multiplying individual coordinates by nonzero field elements changes neither the dimension nor the Hamming weight, so the same proof applies to a generalized Reed-Solomon code.

To specify the generator polynomials of a cyclic code unambiguously, use the primitive cyclic Reed-Solomon code convention. Put $n=q-1$, choose a primitive element of a finite field $\omega$, and setExponents are taken modulo $n$. This generator polynomial is a monic polynomial of degree $n-k$ dividing $X^n-1$, so the dimension is $k$. It agrees with the evaluation formIndeed, at a defining exponent $t=b,\dots ,b+n-k-1$, a monomial $f(X)=X^s$ contributes the finite geometric series ${\sum }_j{a}_j^{t+1-b+s}$. Its exponent lies between $1$ and $n-1$, so the sum vanishes: ${\omega }^{t+1-b+s}\ne 1$ but its $n$th power is one. Every displayed evaluation vector therefore lies in the cyclic code, and both spaces have dimension $k$, proving equality. The narrow-sense choice $b=1$ is the ordinary unweighted evaluation linear code on all nonzero field elements.

The duality of primitive cyclic Reed-Solomon codes now follows directly. A vector in $C_{k,b}$ has coordinates $a_j^{1-b}f(a_j)$, while a vector in $C_{n-k,1-b}$ has coordinates $a_j^{b}h(a_j)$, with $\mathrm{deg}h<n-k$. Their dot product is ${\sum }_j{a}_{j}f(a_j)h(a_j)$. Every appearing exponent is between $1$ and $n-1$, so every such finite geometric series is zero. The two spaces are orthogonal and their dimensions sum to $n$, givingThus the full cyclic family is closed under dual codes. The offset matters: the dual code of the narrow-sense linear code generally has offset zero, rather than one.

For arbitrary evaluation points, the precise statement is closure of generalized Reed-Solomon codes under duality. If $C={\mathrm{GRS}}_k(a,v)$, put $P(X)={\prod }_i(X-a_i)$ and $u_i=(v_i{P}^{\prime }(a_i){)}^{-1}$. Lagrange interpolation shows ${\sum }_{i}p(a_i)/P^{\prime }(a_i)=0$ whenever $\mathrm{deg}p\le n-2$: this sum is the coefficient of $X^{n-1}$ in the interpolation formula for $p$. Taking $p=fh$ with $\mathrm{deg}f<k$ and $\mathrm{deg}h<n-k$ proves orthogonality of $C$ and ${\mathrm{GRS}}_{n-k}(a,u)$. Comparing dimensions gives equality with $C^{\perp }$. An unweighted evaluation linear code at arbitrary points need not have an unweighted evaluation dual at the same points; the multiplier form and the cyclic offset formula resolve that convention issue.

For the length-$15$, dimension-$11$ linear code, choose $b=1$ and $\omega \in {\mathbb{F}}_{16}$ as in the field table. Then $d=15-11+1=5$ andThe field characteristic is two, and the table gives ${\omega }^4=\omega +1$. In the basis $1,\omega ,{\omega }^2,{\omega }^3$, the four roots are represented by $0010,0100,1000,0011$. Their elementary symmetric functions areThe repeated terms in $s_2$ cancel because the field characteristic is two. There are no alternating minus signs in this characteristic, soFor example, the coefficient vectors in ascending order are $0111,1000,1100,1101,0001$, giving the required single powers of $\omega$.

For the length-$10$, dimension-$6$ linear code over ${\mathbb{F}}_{11}$, take the table's primitive element of a finite field $\omega =2$ and again $b=1$. The four roots are $2,4,8,5$. Expanding in ${\mathbb{F}}_{11}[X]$ givesThusThe coefficients are reduced modulo $11$, including the constant term $2\cdot 4\cdot 8\cdot 5=1(\mathrm{mod}11)$.

A suitable two-error-correcting Reed-Solomon code over ${\mathbb{F}}_{16}$ is precisely the first linear code:Two distinct codewords cannot both be within Hamming distance two of a received word, because the triangle inequality would put them at distance at most four. Thus this linear code corrects any two symbol errors. Its generator polynomial has four consecutive defining zeros of a cyclic code, and its dimension and exact minimum Hamming distance have already been proved.

Let $U$ be a unitary operator and suppose initially that the target is an eigenstate $|u⟩$ with $U|u⟩=e^{2\pi i\varphi }|u⟩$, $0\le \varphi <1$. Use $t$ control qubits, so $L=2^t$. Hadamard gates prepare the uniform superposition $L^{-1/2}{\sum }_{a=0}^{L-1}|a⟩$. For each binary control position $j$, apply the controlled unitary gate $U^{2^j}$. The resulting state isApply the inverse quantum Fourier transform, with convention ${\mathrm{QFT}}_L|j⟩=L^{-1/2}{\sum }_a{e}^{2\pi iaj/L}|a⟩$, and measure the control. The exact amplitude and probability areFor an exactly representable phase $\varphi =j_0/L$, orthogonality of roots of unity makes the outcome $j_0$ certain. Otherwise the finite geometric series givesThe estimate is $j/L$, with phases interpreted modulo one.

To prove an error bound, choose a nearest label $j_0$ to $L\varphi$ on the circular grid and put $d=L\varphi -j_0$ in the interval $[-1/2,1/2]$. For $d\ne 0$, concavity of sine on $[0,\pi /2]$ gives $|\sin \pi d|\ge 2|d|$, while $L|\sin (\pi d/L)|\le \pi |d|$. Therefore the nearest-integer success bound for quantum phase estimation isHere $\Vert x{\Vert }_{\mathbb{R}/\mathbb{Z}}={\min }_{k\in \mathbb{Z}}|x-k|$. At an exact grid point the probability is one. If two nearest labels tie, either one separately has the displayed lower bound.

For high confidence one can prove a stronger quantum phase estimation tail bound. Let $d_j$ be the centered distance between $j$ and $L\varphi$, chosen with $|d_j|\le L/2$. The denominator estimate $|\sin (\pi d_j/L)|\ge 2|d_j|/L$ implies $p_j\le 1/(4d_j^2)$ away from the exact-phase case. A label at circular integer distance $\ell$ from $j_0$ has $|d_j|\ge \ell -1/2$, and there are at most two labels at each such distance. For $m\ge 2$, summing the tails givesOn the complementary event the circular phase error is at most $(m-1/2)/L$. Thus, for $b$ desired bits of accuracy, take $t=b+u$ with $u\ge 1$ and $m=2^u$ to obtainTaking $u=\lceil {\log }_2(1+1/(2\epsilon ))\rceil$ makes the right side at most $\epsilon$. This adds only $O(\log (1/\epsilon ))$ control qubits. Efficient QFT is not by itself a guarantee of efficient controlled powers of an arbitrary $U$: implementing them by repeated oracle calls uses $L-1$ calls. The modular-arithmetic application has efficient powers, as follows.

Assume $n>1$ and $\gcd (x,n)=1$, and let $r$ be the multiplicative order of $x$ modulo $n$. Define the unitary operator $U_x|y⟩=|xy\mathrm{mod}n⟩$ on $0\le y<n$, and extend it as the identity on unused computational-basis labels of the binary register. Coprimality makes multiplication a permutation, so this extension really is unitary. The orbit of $|1⟩$ consists of the $r$ distinct states $|x^j\mathrm{mod}n⟩$. Its modular multiplication eigenstates areThe last relation follows by shifting the index $j$ cyclically; orthogonality follows from the finite Fourier sum. We do not need to know $r$ to prepare one of these eigenstates: the readily prepared target obeysRunning quantum phase estimation on this state produces the mixture of the $r$ eigenphase distributions, each with weight $1/r$, because the target eigenstates are orthogonal. Thus it samples a uniformly random phase label $s$ and estimates $s/r$ with the bounds just proved. Equivalently the state before the inverse QFT is $L^{-1/2}{\sum }_a|a⟩|x^a\mathrm{mod}n⟩$, which is obtained by quantum modular exponentiation directly.

The controlled power $U_x^{2^j}$ multiplies by $x^{2^j}\mathrm{mod}n$, whose constant is computed by repeated squaring. Under the assumed efficient modular exponentiation, these controlled multiplications and the QFT use a number of gates polynomial in the register lengths. Taking $L>n^2$ requires only $O(\log n)$ phase qubits. The nearest-label event has probability at least $4/{\pi }^2$ and yields an estimate within $1/(2L)<1/(2r^2)$ of $s/r$. Since $r<n$, continued-fraction recovery in quantum order finding then identifies the reduced fraction $s/r$. The denominator is $r/\gcd (s,r)$, not necessarily $r$: when $s$ and $r$ are coprime it is the desired order, and when they are not it is only a divisor. One may test candidate denominators using modular exponentiation and repeat with fresh samples; denominators from successful samples can also be combined by a least common multiple. The probability of a nearest-label sample with $s$ coprime to $r$ is at least $(4/{\pi }^2)\phi (r)/r$. These qualifications explain exactly what the phase estimate yields without falsely assuming that the unknown order or an eigenstate was available at the start.

Use the integer norm lower bound for rational approximation to a quadratic irrational. The integer $2q^2-a^2$ is nonzero, since $\sqrt{2}$ is irrational. If $a/q<2$, thenbecause $\sqrt{2}+a/q<\sqrt{2}+2<4$. If $a/q\ge 2$, the difference is at least $2-\sqrt{2}>1/4\ge 1/(4q^2)$. ThusIn particular, $\sqrt{2}$ is a badly approximable number.

To estimate the prime-weighted exponential sum, let $Q=\lfloor N^{1/2}\rfloor$. The Dirichlet approximation theorem gives a reduced fraction $a/q$ withCombining this with the lower bound gives $q>Q/4$. Thus $q\asymp N^{1/2}$; the approximation cannot have a small denominator.

The relevant analytic input is the prime exponential-sum estimate from Vaughan identity:Here is the structure behind that estimate. With Dirichlet convolution and cutoffs $U,V$, the Vaughan identity isIt follows from $\Lambda =\mu \ast \log$, $\log =\Lambda \ast 1$, and $\mu \ast 1={\delta }_1$. The first two Dirichlet convolution terms become type I sums with one short factor; the last becomes a bilinear type II sum with both factors bounded below. Split these sums into dyadic blocks and use $U=V=N^{2/5}$. For the type I sums, the inner finite geometric series has bound $\min (L,(2\Vert \alpha m\Vert {)}^{-1})$. For the type II sums, the Cauchy-Schwarz inequality followed by expansion introduces analogous sums in differences of indices. Rational approximation separates the phases into blocks of length comparable to $q$, bounding these reciprocal-distance sums. The Dirichlet convolution coefficients are divisor-bounded, producing the logarithmic factors. These steps give the displayed estimate; no unproved cancellation of arbitrary weighted sums is being assumed.

With $\alpha =\sqrt{2}$ and $q\asymp N^{1/2}$, the two denominator-dependent terms are $O(N^{3/4})$. ConsequentlyThe final passage absorbs the logarithm using the positive exponent margin $9/10-4/5=1/10$.

Write $\varphi =2\pi n/N+ϵ$, with $|ϵ|\le \delta \ll 2\pi /N$. Decode the measured bits as above. The probability amplitude of label $m$ isUsing the finite geometric series,Interpret removable singularities by continuity. In particular, near-grid quantum phase estimation returns the nearby exact label $n\mathrm{mod}N$ with probabilityThis is near one under the stated small-offset assumption, but not exactly one when $ϵ\ne 0$.

There is also a rigorous error bound. Taking the squared modulus of the sum giveswhere $1-\cos x\le x^2/2$ and the elementary sums of $k$ and $k^2$ evaluate the last expression. HenceOn that event the circular quantum phase error is at most $\delta$. For other labels, the exact probabilities areTheir total is $1-P(n)=O(N^2{\delta }^2)$, describing the leakage from the perfect solution. The physical output bit string remains reversed in the printed circuit; this changes its decoding, not these probabilities.

Put $N=2^t$ and write $U|u⟩=e^{i\varphi }|u⟩$, with $|u⟩$ normalized. The Hadamard gates prepare the control register in $N^{-1/2}{\sum }_{k=0}^{N-1}|k⟩$. Controlled powers of the unitary operator then give quantum phase kickback:Thus the register quantum state is $N^{-1/2}{\sum }_k{e}^{ik\varphi }|k⟩$, while the target remains $|u⟩$. Define the quantum Fourier transform by $F_N|m⟩=N^{-1/2}{\sum }_k{e}^{2\pi ikm/N}|k⟩$. Its inverse givesWhen $\varphi =2\pi n/N$, the inner finite geometric series equals $N$ if $m\equiv n(\mathrm{mod}N)$ and zero otherwise. Therefore exact quantum phase estimation givesThe quantum phase, rather than an unrestricted integer $n$, is recovered modulo $2\pi$.

The printed circuit has no bit-reversal swaps. Its top control uses $U^{2^{t-1}}$, and its measured top wire gives the least significant output bit. Write $n\mathrm{mod}N={\sum }_{j=0}^{t-1}{2}^j{b}_j$. Before the top wire's final Hadamard gate, its relative quantum phase is $2^{t-1}\varphi =\pi n$, so that gate produces $b_0$. The controlled inverse quantum phase gates then subtract its contribution from lower wires. More generally, before the final Hadamard gate on wire $j$, the relative quantum phase isso that wire gives $b_j$ deterministically. For the three-wire drawing, the correct interpretation isEquivalently, its Fourier-inversion circuit is $R{F}_N^{†}$, where $R$ reverses the register bits. Relabeling the measured bits or appending swaps gives the usual integer output. This bit convention matters, for example, when quantum phase $\pi$ produces top-to-bottom bits $001$, representing the label four rather than one.