Rigorous Statements and Proofs of the Lemmas in Simon's Algorithm for the Dihedral Coset Problem and Their Underlying Hypothesis

Rigorous Statements and Proofs of the Lemmas in Simon’s Algorithm for the Dihedral Coset Problem and Their Underlying Hypothesis Yuchen Guo

1, ∗

and Shuo Yang

1, 2, 3, †

1

arXiv:2608.16598v1 [cs.CR] 17 Aug 2026

State Key Laboratory of Low Dimensional Quantum Physics and Department of Physics, Tsinghua University, Beijing 100084, China 2 Frontier Science Center for Quantum Information, Beijing 100084, China 3 Hefei National Laboratory, Hefei 230088, China (Dated: August 18, 2026) In a recent preprint, Simon proposed a polynomial-time quantum algorithm for the Dihedral Coset Problem and rested the analysis on four lemmas. Three of them carry only proof sketches, and this paper gives each of those three a statement that admits a single reading together with a complete proof. Lemma 1 follows from an exact second-moment computation for the subset-sum counts, and it holds with probability tending to one in place of the constant originally claimed. The amplitude bound of Lemma 3 follows from an exact Parseval identity on the cube of measurement outcomes and holds at every threshold with no well-behavedness hypothesis, so that predicate leaves the argument entirely. For Lemma 4, we compute both balls-in-bins covariances exactly and find that the second carries a term a fixed ball count leaves out. The assumption that the distinguished group contains no faulty samples can also be dropped. The two branch amplitudes share a signed prefactor, so the counting estimates control their difference and not the ratio the lemma states. We prove the additive form and show that the closing argument consumes nothing more than that. A single hypothesis survives all of this. It asks that the partition into the two sides be fixed independently of the measured string, and the rule the algorithm gives for choosing that partition does not supply it. Establishing these four lemmas therefore does not by itself establish the correctness of the algorithm.

I.

INTRODUCTION

The Dihedral Coset Problem asks for a hidden shift. One is given a supply of two-term superpositions |0, ξ⟩ + |1, ξ + d⟩ with ξ uniform on ZN and d fixed, and the task is to recover d. It is the hidden subgroup problem for the dihedral group, and the standard Fourier method that solves the abelian cases in Shor’s algorithm does not carry over [5, 14]. Ettinger and Høyer showed that polynomially many samples already determine d information-theoretically, so the whole difficulty lies in reading d out in polynomial time [6]. The best known algorithms are the subexponential sieves of Kuperberg [7, 8] and Regev [12]. Bacon, Childs and van Dam identified the optimal measurement for the problem and reduced its implementation to a classical subset-sum question [2]. Much of the interest in the problem comes from lattices. Ajtai’s worst-case to average-case reduction placed lattice problems at the foundation of a family of cryptosystems [1]. Regev showed that a polynomial-time solver would give a polynomial-time quantum algorithm for the unique shortest vector problem [11], and Brakerski, Kirshanova, Stehlé and Wen extended the reduction to Learning with Errors at polynomial approximation factors [3, 13]. The complexity of the Dihedral Coset Problem therefore sits directly beneath a large part of lattice-based cryptography, including the key-encapsulation scheme now being standardised [9]. A claim of a polynomial-time quantum

∗ guo-yc23@mails.tsinghua.edu.cn † shuoyang@tsinghua.edu.cn

algorithm in this area invites close reading, and the recent lattice algorithm of Chen received exactly that before a step in it was found not to work [4]. Simon has recently posted a preliminary draft giving a polynomial-time quantum algorithm for the problem [15]. It works on Q samples at once and sorts the Q bits into groups of m. The groups whose measurement outcome is all zero then build an unsigned count that both branches of the final interference share. The analysis rests on four lemmas. Lemma 2 is exact and carries a complete two-line proof, while the other three are marked Proof (Sketch). This paper supplies statements for those three that admit a single reading, together with complete proofs. Lemma 1 asserts that enough all-zero groups are collected. Section III computes the first and second moments of their number exactly by means of two Fourier transforms, one on the cube of measurement outcomes and one on the group ZN of subset sums. The correlation between two groups turns out to be exponentially small, and Chebyshev then gives probability tending to one in place of the constant [15] asks for. Lemma 3 bounds the individual amplitudes. Section IV obtains the bound from an exact Parseval identity, which needs no independence property of the signs and no wellbehavedness property either. The bound holds at every threshold, and the probabilities are taken directly on the distribution of records. These proofs ask for the A/B partition to be fixed independently of the measured string, which we state as Hypothesis (U) in Section IV. Lemma 4 compares the two branch amplitudes, and its proof works on the counts that feed them. The skeleton is a pair of balls-in-bins estimates, and Section V computes the covariance of each one exactly. The first comes

2 out with the exponent and the failure probability [15] displays, while the second works with a random number of surviving states that the algorithm imposes. We also remove the assumption that the distinguished group ga contains no faulty samples. Carrying the counts back up to the amplitudes raises a question of form. The two amplitudes of a pair share one signed prefactor, so the counting estimates deliver a bound on their difference while the lemma asks for their ratio. That turns out to cost nothing, because the closing argument only ever adds up differences. Section V E therefore proves the weaker statement and reaches the same exponent from it. Table I summarizes where each is treated. The rule [15] gives for choosing A does not supply Hypothesis (U), so establishing these lemmas does not by itself establish the correctness of the algorithm. Results proved here are lettered, so a numbered lemma is always one of [15]. TABLE I. The four lemmas of [15] and where each is treated below. In [15]

What it asserts

Here

Lemma 1 Enough all-zero groups are collected C Lemma 2 The B side contributes a common factor §II Lemma 3 Individual amplitudes are bounded E, E′ Lemma 4 The two branch amplitudes are nearly equal G, H

II. A.

SETUP

Problem setup

with ξ uniform and unknown and d fixed. With probability 1/(c′ log n) for a constant c′ , a sample is faulty and is an (n + 1)-bit classical string instead. Faulty samples play no role before Section V. Applying the ZN Fourier transform to the second register and measuring it returns a value y that is uniform on ZN and known to us, and it collapses the first register to |0⟩ + ω yd |1⟩. Taking Q samples and writing Y = (y1 , . . . , yQ ) for the measured weights, the tensor product of the Q qubits expands into X |Ψ⟩ ∝ ω d z(ϕ) |ϕ⟩, (2) ϕ∈{0,1}Q Q X

ϕi yi mod N.

h∈{0,1}

′ ϕ∈Zh

Zh′ = ϕ : z(ϕ) = z ′ + 2n−1 h . 

(5)

Here h(ϕ) is a function of ϕ and not a free register, and we write Z ′ = Z0′ ⊔ Z1′ for the set of all ϕ compatible with the measured z ′ . The bit dn now sits in the relative phase of |h⟩. If the register |h⟩ stood alone, one Hadamard and one measurement would return dn with certainty, and a recursion on the remaining bits of d would finish the problem. However, the two branches are attached to disjoint sets of ϕ, so they occupy orthogonal subspaces and cannot interfere. Regev’s way out is to erase the ϕ register with a subset-sum oracle [11]. Simon’s way out is to change basis, and the seven steps below carry that out.

B.

The algorithm in seven steps

Throughout this paper the ket holds the registers still in superposition and the record holds the classical numbers already measured. The record is (Y, z ′ , ϕ′ , S, W ′ , h′ ), and any of its entries may be substituted into a formula. Table II tracks both.

Write N = 2n and ω = e2πi/N , and let the unknown value be d = d1 d2 · · · dn with least significant bit dn . A sample is the state
√1 |0, ξ⟩ + |1, ξ + d mod N ⟩ , (1) 2

z(ϕ) =

Computing z(ϕ) into an ancilla and measuring its low n − 1 bits returns a value z ′ and leaves the top bit h = msb(z) in superposition, where msb denotes the most n−1 significant bit. Since ω d·2 = (−1)dn , the surviving state is X  X |Ψ⟩ ∝ (−1)h dn |ϕ⟩ |h⟩, (4)

(3)

i=1

Every basis state carries the same modulus, so all of the information sits in the phase, and that phase depends on ϕ only through the weighted sum z(ϕ).

TABLE II. What survives each step. Erasures are reversible and produce no record. After In the ket

New classical data

Step 1 ϕ Y = (y1 , . . . , yQ ) Step 2 ϕ, h z ′ , the low n − 1 bits of z Step 3 ϕ, h, s1 · · · sG none Step 4 h, s1 · · · sG ϕ′ , and ϕ is gone Step 5 h, s1 · · · sa S = (σj′ )j∈B ∗ Step 6 h, h W ′ = (s1 , . . . , sa−1 , ls∗ ) ∗ Step 7 h h′ = h ⊕ h∗ , and h is erased Final none the Hadamard measurement of h∗

Steps 1 and 2 are the constructions of Section II A, which produce the record entries Y and z ′ and leave the ket in the state displayed there. Step 3, the group sums. Partition {1, . . . , Q} into G = Q/m groups g1 , . . . , gG of m = c log n bits each, and write rj (ϕ) =

X

ϕi yi mod N,

sj (ϕ) = top rj (ϕ)

(6)

i∈gj

for the sum within group j and its top L = log n bits. Each sj is computed reversibly into its own L-bit register,

3 5. Measure W = (s1 , . . . , sa−1 , ls∗ ), obtaining W ′ .

giving |Ψ3 ⟩ ∝

X

(−1)h(ϕ)dn |ϕ⟩ |h(ϕ)⟩ |s1 (ϕ) · · · sG (ϕ)⟩. (7)

ϕ∈Z ′

These registers survive the disappearance of ϕ at the next step, which keeps only the top L bits of each rj . Step 4, the change of basis. Apply a Hadamard to all Q bits and measure, obtaining a classical string ϕ′ = ϕ′1 · · · ϕ′G , written in blocks by group. The ϕ register is gone, and the amplitude of a surviving label (h, ⃗s ) becomes a signed count of the ϕ compatible with that ′ label, each one weighted by the sign (−1)ϕ·ϕ , X |Ψ4 ⟩ ∝ E[h, ⃗s ] |h, ⃗s ⟩, (8) h,⃗ s

X

E[h, ⃗s ] = (−1)hdn

′

(−1)ϕ·ϕ .

(9)

The ket now holds (h, h∗ ). ∗ Step 7, transferring n−1 P the phase. Write∗z̃ for the ′lown−1 ∗ bits of z and zB = i∈B ϕi yi . From z +zB ≡ z +2 h and −2n−1 ≡ 2n−1 (mod 2n ), zB ≡ (z ′ − z̃ ∗ ) + 2n−1 h′ ,

′

′

′

(10)

Measure sj for every j ∈ B, obtaining S = (σj′ )j∈B , and the ket retains (h, s1 · · · sa ). Step 6, manufacturing h∗ . Here we introduce a new register that represents the top bit of the A-side partial sum. Write X z ∗ (ϕ) = ϕi yi mod N, h∗ = msb(z ∗ ) (11) i∈A

for the A-side partial sum and its top bit. This step turns h∗ into an explicit register in five moves. P L into a fresh L-bit 1. Compute s∗ = j∈A sj mod 2 register. ∗

2. P Erase sa , which is now redundant, being s − L j<a sj mod 2 . 3. Compute a check bit ls∗ that equals 1 exactly when positions 2 through log L of s∗ are all 1, and postselect on ls∗ = 0. This prohibits the carry from the bottom bits and makes msb(s∗ ) = msb(z ∗ ) = h∗ . The post-selection succeeds with probability about 1 − 2/ log n. ∗

∗

∗

(−1)hdn = (−1)h dn (−1)h dn

Step 5, the A/B split. A group whose measured block ϕ′j is the all-zero string contributes no sign, since (−1)ϕj ·0 = 1. Let A consist of the first a = n/ log n such groups and let B hold the rest. Lemma 1 of [15] asserts that there are at least a all-zero groups, and Section III treats that claim. The A side holds am = cn sample bits. Write ϕ = (ϕA , ϕB ) and ϕ′ = (ϕ′A , ϕ′B ) for the strings cut into their A and B parts, so that ϕ′A = 0 by construction and

∗

4. Split s into its top bit h and its low L − 1 bits s̄ , Hadamard s̄∗ , measure, and post-select on the allzero outcome. This succeeds with probability about 2/n and keeps all n/2 values of s̄∗ in the sum with coefficient +1. The bit h∗ itself is never measured, since we read it at the end.

(12)

The two top bits reach the B-side constraint only through h′ . Compute h′ with one CNOT, measure it, and use h′ together with h∗ to erase h reversibly. Once h′ is a measured constant the B side no longer sees h∗ , and the two branches share one B-side factor. This is Lemma 2 of [15], and it is the only one of the four with a complete published proof. The phase survives the substitution, since

ϕ∈Z ′ : h(ϕ)=h sj (ϕ)=sj ∀j

(−1)ϕ·ϕ = (−1)ϕB ·ϕB .

h′ = h ⊕ h∗ .

(13)

and the first factor is a global constant once h′ is known. The surviving state is X ∗ |Ψ7 ⟩ ∝ (−1)h dn Eh∗ |h∗ ⟩, (14) h∗ ∈{0,1}

where Eh∗ is the signed count of the ϕ compatible with the whole record and with that value of h∗ . The final step. Hadamard h∗ and measure. For a state E0 |0⟩ + (−1)dn E1 |1⟩ the outcome equals dn with probability p =

(E0 + E1 )2 1 = , 2(E02 + E12 ) 1 + q2

q =

|E0 − E1 | , (15) |E0 + E1 |

so the whole algorithm reduces to showing that E0 and E1 are close. Once p exceeds 1/2 by a non-negligible amount, polynomially many repetitions and a majority vote return dn , and a recursion on the remaining bits of d finishes the problem. C.

The coefficient reduces to convolution

Two families of sets record how the constraints tighten as the measurements accumulate, one family on each side of the partition. The two base members are fixed by the data known just after Step 4, namely the measured z ′ together with a value of the index z ∗ that ranges over ZN as a summation variable and is never a measurement outcome, n o X Az∗ = ϕA : ϕi yi = z ∗ , (16) i∈A

n o X B(z′ ,z∗ ),h = ϕB : z ∗ + ϕi yi = z ′ + 2n−1 h .

(17)

i∈B

Each later measurement discards some of the strings that remain, and the notation records this by growing a subscript. A prime marks the member that carries

4 TABLE III. The set families. Within each side, every entry carries the constraints of the entry above it together with the one shown. Set Fixed after Constraint added The A side, where no sign is carried Az ∗ Step 4 z ∗ (ϕA ) = z ∗ ′ Az∗ ,W ′ Step 6 sj (ϕA ) = Wj′ for j < a, together with ls∗ (ϕA ) = 0 The B side, which carries every sign B(z′ ,z∗ ),h Step 4 zB (ϕB ) = z ′ + 2n−1 h − z ∗ B(z′ ,z∗ ),S,h Step 5 sj (ϕB ) = σj′ for j ∈ B ′ B(z′ ,z̃∗ ),S,h′ Step 7 h replaced by the measured h′ , so that by Eq. (12) the index z ∗ collapses to z̃ ∗

everything the record fixes. On the A side that member is A′z∗ ,W ′ , which collects the ϕA with z ∗ (ϕA ) = z ∗ that also match the top blocks recorded in W ′ at Step 6 and satisfy ′ the post-selection ls∗ = 0. On the B side it is B(z ′ ,z ∗ ),S,h′ , which collects the ϕB that match the blocks S measured at Step 5 and obey Eq. (12) with the measured h′ . Table III collects all five members with the constraint each one adds. The A-side member is indexed by the whole of z ∗ , while the B-side member is indexed by its low n−1 bits z̃ ∗ alone. ′ ′ That collapse B(z ′ ,z ∗ ),S,h′ → B(z ′ ,z̃ ∗ ),S,h′ is Lemma 2. By Eq. (12) the B side is constrained by (z ′ − z̃ ∗ ) and h′ , so two values of z ∗ differing only in the top bit h∗ give the same set of ϕB , and therefore the same signed count. The B-side signed count and the normalised per-index amplitude are X ′ C(z′ ,z̃∗ ),S,h′ = (−1)ϕB ·ϕB , (18) ′ ϕB ∈B(z ′ ,z̃ ∗ ),S,h′

αz∗ = λ4 A′z∗ ,W ′

C(z′ ,z̃∗ ),S,h′ ,

(19)

where λ4 = (E02 + E12 )−1/2 normalises the two branches at the end of Step 7. The unnormalised amplitude of the branch h∗ is X Eh∗ = A′(h∗ ,z̃∗ ),W ′ C(z′ ,z̃∗ ),S,h′ . (20) z̃ ∗ ∈{0,1}n−1

The A-side factor is an unsigned count and every sign in the problem has been packed into C. We write Êh∗ = λ4 Eh∗ for the normalised branch amplitude, so that Ê02 + P Ê12 = 1 and z∗ : msb(z∗ )=h∗ αz∗ = Êh∗ . Equation (15) may be read with either pair, since q is a ratio. The unnormalised Eh∗ is kept in what follows, since the weight of a record is proportional to E02 + E12 and that quantity is identically 1 in the hatted variables. Subtracting the two branches gives the one line [15] reduces to,  X A′(0,z̃∗ ),W ′ − A′(1,z̃∗ ),W ′ · C(z′ ,z̃∗ ),S,h′ . E0 − E1 = z̃ ∗

(21) Each lemma guards one feature of Eq. (21). Lemma 2 allows for the common factor C outside the bracket. Lemma 4 bounds the relative difference of the two counts,

TABLE IV. Parameters. The sample count constant is written K, where [15] writes k, so that k stays free for Fourier frequencies. Symbol

Meaning

Value

n bit length c group size constant K sample count constant Q number of samples m bits per group G number of groups a number of A groups L width of sj ν length of one top block QB sample bits on the B side 1/(c′ log n) faulty sample rate

N = 2n ≥ 12 >c Knc+1 c log n Q/m n/ log n log n 2 n−L (G − a)m c′ constant

once they are aggregated over the low bits of z ∗ , by O(n−((c−1)/2−1) ). Lemma 3 bounds each product αz∗ on its own, so that a small relative difference implies a small absolute one.

D.

Parameters

Table IV lists the parameters that are fixed throughout our proof. Our ϕ is written b1 · · · bQ in [15], and our ϕ′ is written D. nj [r] counts the configurations of group j whose subset sum equals r,  P nj [r] = # ϕj ∈ {0, 1}m : i∈gj ϕi yi ≡ r . (22)

E.

The probability space

One run produces the record (Y, z ′ , ϕ′ , S, W ′ , h′ ), with Y drawn at Step 1 and the rest supplied by the measurements of Steps 2 to 7. Every probability below lives in the joint law of these. The results about the samples, including Lemma F, Theorem G and Lemma H, are proved with Y uniform on ZNQ . Theorem E and Theorem E′ concern

5 the measured string and are proved with the rest of the record held fixed and ϕ′B varying. The bound they give is the same number for every value of the rest. A bound holding under every conditioning holds under the joint law as well, so the failure probabilities of the two kinds live in one space and may be added. The second kind deserves a warning, since ϕ′ fixes the partition and the partition belongs to the record. Holding the rest of the record fixed therefore already restricts which ϕ′B remain available. Letting ϕ′B range over the whole cube is exactly Hypothesis (U) of Section IV, and Theorem E and Theorem E′ are stated under it. III.

LEMMA 1

Lemma 1 [15]. If k > c, then with constant probability, the measured value of D = b′1 . . . b′Q will have at least n/ log n groups that consist of all zeroes. Here k is our K and D is our ϕ′ . This section proves the lemma in the stronger form that the probability tends to one. The route is a direct moment computation on the number of all-zero groups, and the two transforms it needs are recorded first. The argument in [15] runs in two stages. The first stage shows that zero blocks of ϕ′ are at least as common as one blocks. The second maps the records carrying fewer than a all-zero groups into the records carrying at least a, by exchanging positions inside ϕ′ and exchanging the low n − 2 log n bits of the corresponding weights yi . Those low bits are taken to be distinct across the sample, which makes the map invertible. Comparing the two probabilities asks for more than P invertibility. Moving ′ the low bits alone changes i ϕi yi , so the set ZY of ′ strings compatible with the measured z is not carried onto its image counterpart. The moment computation below reaches the conclusion without any such map.

The second follows by expanding both sides and P identity ′ using N1 k ω k(r −r) = δrr′ . P We also write ⟨f ⟩k = N1 k f (k) and Vark (f ) = ⟨f 2 ⟩k − ⟨f ⟩2k . These measure the shape of a function on the frequency line and are not probabilistic quantities.

B.

One group

Immediately after Step 4 the record consists of (Y, z ′ , ϕ′ ) and the basis states are labelled (h, s1 · · · sG ). The amP ′ plitude at such a label is γ ϕ∈P (−1)ϕ·ϕ for a recordindependent γ, where the consistency class is  P(z, ⃗s) = ϕ ∈ {0, 1}Q : z(ϕ) = z, si (ϕ) = si ∀i , (26) where z = z ′ + 2n−1 h. Every ϕ lies P in exactly one class, so the classes partition the cube and P |P| = 2Q . Writing 1P (ϕ) for the indicator function of a class ( 1, ϕ ∈ P, 1P [ϕ] = (27) 0, otherwise, we have Pr[ϕ′ ; ϕ ∈ P] = γ 2

X

′

(−1)ϕ·ϕ

2

′ 2 = γ 2 1c P (ϕ ) . (28)

ϕ∈P

Lemma A. For every group j, every Y , and every fixed outcome of the earlier measurements, Pr[ϕ′j = 0 | ϕ ∈ P] ≥ 2−m . Summing over the classes, which removes the constraints imposed by z ′ , h and ⃗s, X Pr[ϕ′j = 0 | Y ] = 2−2m nj [r]2 . (29) r

Proof. Expanding the square gives X
′ ′ 2 = (−1)(ϕ⊕ψ)·ϕ . 1c P (ϕ )

(30)

ϕ,ψ∈P

A.

Two Fourier transforms

Two different transforms appear below. On the cube of measurement outcomes we use the Walsh–Hadamard transform [10], X ′ Fb(ϕ′ ) = F [ϕ] (−1)ϕ·ϕ , (23) ϕ∈{0,1}Q

and on the group ZN of subset sums we use X fˆ(k) = f [r] ω −kr ,

(24)

Summing over all ϕ′ leaves only the terms with ϕ ⊕ ψ = 0, so X Pr[ϕ ∈ P] = Pr[ϕ′ , ϕ ∈ P] = γ 2 2Q |P|. (31) ϕ′

Summing instead over the 2 Q−m strings with ϕ′j = 0 leaves the terms whose difference is supported inside gj , which means that X Pr[ϕ′j = 0; ϕ ∈ P] = Pr[ϕ′ ; ϕ ∈ P] = γ 2 2 Q−m AP , ϕ′ : ϕ′j =0

r∈ZN

(32) satisfying that X r

f [r] g[r] =

1 Xˆ f (k) ĝ(k). N k

where (25)

 AP = # (ϕ, ψ) ∈ P 2 : ϕ ⊕ ψ supported in gj .

(33)

6 where we define

Dividing gives Pr[ϕ′j = 0 | ϕ ∈ P] = 2−m AP /|P|,

(34)

which is at least 2−m because the diagonal ϕ = ψ already contributes |P|. Now let us sum over the classes. Suppose ϕ and ψ lie in the same class, so that z(ϕ) = z(ψ), and suppose they also agree outside gj . Then z(ϕ) − z(ψ) = rj (ϕ) − rj (ψ), so rj (ϕ) = rj (ψ). The constraint on sj is then satisfied automatically. Choosing the bits outside gj freely, X X AP = |2 Q−m nj [r]2 , (35) {z } × r P bits outside gj | {z } rj (ϕj )=rj (ψj )

and dividing by

Q P |P| = 2 gives the stated form.

P

C.

where (s)

ŵj (k)

2

(37)

s (s)

and wj [r] = nj [r] 1[top(r) = s] being the restriction of nj to one top block. Proof. The character sum of Lemma A applies with {ϕ′j = 0} replaced by {ϕ′j = ϕ′j ′ = 0}. There are 2 Q−2m such strings, therefore P (2)   A Pr ϕ′j = ϕ′j ′ = 0 | Y = 2−2m · P Q P , (38) 2 where  (2) AP = # (ϕ, ψ) ∈ P 2 : ϕ ⊕ ψ supported in gj ∪ gj ′ . (39) Let ϕ and ψ agree outside gj ∪ gj ′ . Every si with i ̸= j, j ′ then agrees automatically, and     z(ϕ) − z(ψ) = rj (ϕ) − rj (ψ) + rj ′ (ϕ) − rj ′ (ψ) . (40) So the pair lies in one class exactly when rj + rj ′ is preserved (from z) and top(rj ) and top(rj ′ ) are each preserved (from sj and sj ′ ). In this case, the two groups may trade a common offset δ := rj (ϕ) − rj (ψ) = r (ψ) − r (ϕ). j′

(43)

P

δ∈ZN

=2

X

Q−2m

(44) Rj [δ] Rj ′ [δ],

δ∈ZN

because R is even. Finally, we use the fact that XX f[ ⋆ f (k) = f [r]f [r − δ] ω −kδ δ

r

r ′ =r−δ

X

′

f [r]f [r′ ] ω −k(r−r )

(45)

r,r ′

k

X

f [r]f [r − δ].

Pulling out the 2 Q−2m choices of the bits outside the two groups and sorting the rest by δ, we obtain X (2) X AP = 2 Q−2m Rj [δ] Rj ′ [−δ]

Two groups

Tj (k) =

X r

=

Lemma B. For j ̸= j ′ and every Y ,   1 X Pr ϕ′j = ϕ′j ′ = 0 | Y = 2−4m Tj (k) Tj ′ (k), (36) N

j′

(41)

Define the autocorrelation X X (s) (s)
Rj [δ] = nj [r] nj [r′ ] = wj ⋆ wj [δ], r,r ′ : r−r ′ =δ top(r)=top(r ′ )

(f ⋆ f )[δ] =

s

(42)

2 = fˆ(k) ,

cj (k) = Tj (k), and the Tj (k) of Lemma B is the Fourier so R transform of the autocorrelation Rj [δ]. PThe Parseval P identity then turns δ Rj [δ]Rj ′ [δ] into N1 k Tj (k)Tj ′ (k) and finishes the proof. Since Tj is the Fourier transform P of Rj , the inverse transform at δ = 0 gives ⟨Tj ⟩k = r nj [r]2 . Lemma A therefore also reads Pr[ϕ′j = 0 | Y ] = 2−2m ⟨Tj ⟩k , and the two lemmas have the same shape.

D.

Averaging over the weights

Every probability written so far has been conditional on one fixed Y , with the Hadamard measurement of Step 4 supplying the only randomness. The weights are produced by the algorithm itself at Step 1, where the Fourier measurement on the second register of a sample returns a yi uniform on ZN . The Q samples are prepared independently, so
Y = (y1 , . . . , yQ ) ∼ Unif ZNQ . (46) Theorem C below is a statement about a run of the whole algorithm, so its probability space carries Y as well, and from here on E denotes that average. Now we calculate the expected second moment of a single group’s subset-sum count. Write β =

2m − 1 N

(47)

for the chance that a fixed nonempty subset of one group hits a fixed value. The result is  
E nj [r] nj [r′ ] = 1[r=r′ =0] + β 1[r=0] + 1[r′ =0] (48) 4m − 3 · 2m + 2 + β δrr′ + , 2 N

7 whose four terms come from the pairs where both subsets are empty, where exactly one is, where the two coincide and are nonempty, and where they differ and neither is empty (Appendix A). Carrying Eq. (48) through Tj (k) = P P ′ −k(r−r ′ ) gives s r,r ′ ∈s nj [r]nj [r ] ω m

ET (k) = 2 + β2 Dν (k) + β1 Re 1̂B0 (k), β1 = 2β,

β2 =

(4m − 3 · 2m + 2) 2L , N2

(49)

where B0 = {0, 1, . . . , ν − 1} is the bottom top-block (i.e., those with zero top bits) and Dν (k) = |1̂B0 (k)|2 is the Fejér kernel of order ν. Two averages of that kernel are also computed there 2

ν(2ν + 1) ≤ ν3. 3

⟨Dν2 ⟩k =

⟨Dν ⟩k = ν,

(50)

PG Theorem C. Let Z = j=1 1[ϕ′j = 0] be the number of all-zero groups. Under the hypothesis K > c of [15], Pr[Z ≥ a] → 1. This is Lemma 1 of [15] with probability tending to one in place of a constant. Proof. We take five steps. Step 1. Lemmas A and B hold for each fixed Y , so Pr[ϕ′j = 0 | Y ] = 2−2m ⟨Tj ⟩k ,

(51)

Pr[ϕ′j = ϕ′j ′ = 0 | Y ] = 2−4m ⟨Tj Tj ′ ⟩k .

(52)

Different groups use disjoint weights and all weights are independent, so E[Tj Tj ′ ](k) = ETj (k) ETj ′ (k) pointwise in k. The groups are identically distributed, so writing ET for the common value p1 := Pr[ϕ′j = 0] = 2−2m ⟨ET ⟩k ,

(53)

p2 := Pr[ϕ′j = ϕ′j ′ = 0] = 2−4m ⟨(ET )2 ⟩k .

(54)

Step 2. In general ⟨(ET )2 ⟩k ̸= ⟨ET ⟩2k , and the difference measures the correlation between two groups p2 − p21 = 2−4m Vark (ET ),

(55)

p2 − p21 Vark (ET ) η := = , p21 ⟨ET ⟩2k

(56)

where η is the normalised correlation coefficient of two groups being simultaneously all-zero. In this sense, a question about probabilistic independence has become a question about the shape of one function. Step 3. Write Zj = 1[ϕ′j = 0] for the indicator of group j. Each Zj is Bernoulli with parameter p1 and every pair has covariance p21 η, so Var[Z] =

X

Var[Zj ] +

Cov(Zj , Zj ′ )

j̸=j ′

j

|

X

{z

Gp1 (1−p1 )

}

|

≤ Gp1 + G2 p21 η.

{z

G(G−1)p21 η

}

(57)

Since E[Z] = Gp1 , dividing by E[Z]2 gives Var[Z] 1 ≤ + η. 2 E[Z] E[Z]

(58)

The first is the Poisson fluctuation of G nearly independent coins, and the second is the excess contributed by their dependence. Step 4. It remains to bound η. In Eq. (49) the term 2m is constant in k, and Vark is invariant under adding a constant, so only the two bumps contribute. From (x + y)2 ≤ 2x2 + 2y 2 and Vark ≤ ⟨ ·2 ⟩k , we have Vark (ET ) ≤ 2β22 ⟨Dν2 ⟩k + 2β12 (Re 1̂B0 )2 k .

(59)

By Eq. (50) the first average is at most ν 3 , and the second is at most ⟨|1̂B0 |2 ⟩k = ν. Using β2 ≤ 4m 2L /N 2 , β1 = 2β ≤ 2·2m /N and ν = N/2L , we bound the variance as 16m 4 · 4m , β12 ν ≤ , L N2 N 2L 2 · 16m + 8 · 4m Vark (ET ) ≤ . N 2L β22 ν 3 ≤

so

(60)

For the denominator, ⟨ET ⟩k ≥ 2m gives ⟨ET ⟩2k ≥ 4m . This gives 2n2c + 8 2 · 4m + 8 = L N2 n 2n 2c−1 2n +8 ≤ = 2−n+O(log n) , n 2

η ≤

(61)

using 2m = nc , 2L = n and N = 2n . The correlation between two groups is therefore exponentially small. Step 5. By Lemma A, E[Z] ≥ G2−m = (K/c)a, so a ≤ (c/K)E[Z] with c/K < 1. Chebyshev’s inequality together with Eq. (58) gives h
i Pr[Z ≤ a] ≤ Pr Z − EZ ≥ 1 − Kc EZ (62)   c −2  c ≤ 1− +η , K Ka where the last step also uses 1/E[Z] ≤ c/(Ka). Here c and K are constants, a = n/ log n → ∞, and η → 0 exponentially, so the right side tends to zero. Therefore, Lemma 1 holds with a conclusion stronger than [15] claimed.

IV.

LEMMA 3

Definition 1 [15]. For a given measured z ′ , and a resulting superposition ψ of values of h∗ at the end of step 7, let M be the set of values (Y, D, W ′ , S, h′ ) measured (apart from + − z ′ ) during the algorithm, let TM (resp., TM ) be the set of states ϕ consistent with M and

8 h∗ and with phase 1 (resp., −1) resulting from measurement of M (ignoring the con′ + − stant phase ω yz d ). Let TM = TM ∪ TM , and + − + let tM (resp., tM , tM ) be |TM | (resp., |TM |, − |TM |). Then ψ is well-behaved for a value of √ − −n/2 h∗ if |t+ tM ). M − tM | ≥ Ω(2 Lemma 3 [15]. With probability 1 − O(2−n ) (over choices of M ), the superposition ψ at the end of step 7 is well-behaved for at least one value of h∗ . Moreover, if it’s wellbehaved for a particular h∗ , then the probability (over choices of M ) that for some z ∗ ∗ consistent with P that value of h the amplitude αz∗ = ν4 ϕA ∈Az∗ ,W ′ Cz̄∗ has magnitude greater than Ω(23n/2 ) is less than O(2−n ). In our notation D is ϕ′ , ν4 is λ4 = (E02 + E12 )−1/2 , z̄ ∗ is z̃ , and Az∗ ,W ′ is A′z∗ ,W ′ , all of which appear in Table III. The set TM of Definition 1 and its size tM have nothing to do with the Fourier-side quantity Tj (k) of Lemma B. Both halves in [15] rest on a variance computation for ′ ± tM , in which the signs (−1)ϕ·ϕ are taken to be pairwise independent as ϕ′ varies. However, a sign depends on ϕ only through ϕB since ϕ′A = 0, so two states of TM that share a ϕB carry the same sign. Lemma D below reads the same object as an exact Walsh transform, which asks nothing of the signs. Separately from the signs, the proof of Lemma 3 in [15] implies a hypothesis that the algorithm steps alone do not give. It sums ϕ′B over the whole cube {0, 1}QB with the rest of the record held fixed. The set A consists of the first a all-zero groups, so the partition is itself a function of ϕ′ and the admissible strings form a proper subset of the cube. We take the freedom as a hypothesis and carry it in the statements. Theorem E and Theorem E′ are both stated under Hypothesis (U), as is the result of Appendix B. ∗

Hypothesis (U). The A/B partition is fixed and does not vary with ϕ′ . With the rest of the record held fixed, ϕ′B therefore ranges over all of {0, 1}QB . Here we summarize our proof of Lemma 3. It is the only one of the four that involves both the size of an amplitude and the probability of a record. Its second half is the one the argument consumes, and [15] states that half conditionally for an h∗ at which the superposition is well-behaved. The first half supplies that predicate with high probability. The proof below carries no such condition, because it runs a Parseval identity p directly on the distribution of records. The normalisation E02 + E12 that defines αz∗ is the weight of the record itself. Appendix B records the first half regardless, in the sharper form that the failure probability is ε2 at every threshold ε. The second half is a statement about the probability of a record. Once ϕ′ is measured, the state left by Section II

is E0 (ϕ′ ) |0⟩ + (−1)dn E1 (ϕ′ ) |1⟩.

(63)

The probability of that record is the squared norm of this unnormalised vector, so it is proportional to E0 (ϕ′ )2 + E1 (ϕ′ )2 . Theorem E is proved directly on the record distribution, whose weights E0 (ϕ′ )2 + E1 (ϕ′ )2 are not uniform in ϕ′ . The constant of proportionality is fixed by Q, N , L and the number of faulty samples, so it does not depend on the record and cancels from every ratio below. That non-uniformity is not itself an obstacle, since the weight enters the numerator and the denominator of Step 4 alike and leaves the value unchanged.

A.

The signed count as a Walsh transform ′

′

Recall that ϕ′A = 0 and (−1)ϕ·ϕ = (−1)ϕB ·ϕB , so the whole content of ϕ′ sits in its B-side part ϕ′B . Define  Nh∗ (ϕB ) = # ϕA : (ϕA , ϕB ) ∈ TM for that h∗ (64) as the number of A-side completions of a given B-side configuration, which takes nonnegative integer values. ′ d Lemma D. Eh∗ (ϕ′ ) = N h∗ (ϕB ) (the Walsh–Hadamard QB transform on {0, 1} ), and consequently

X

Eh∗ (ϕ′ )2 = 2QB

ϕ′B ∈{0,1}QB

X

Nh∗ (ϕB )2 .

(65)

ϕB

Proof. We first group the states of TM by their B-side part. States in one group share a ϕB and therefore the same sign, which may be pulled outside the inner sum, Eh∗ (ϕ′ ) =

′

X

(−1)ϕB ·ϕB

ϕ∈TM

=

XX   ′ 1 (ϕA , ϕB ) ∈ TM (−1)ϕB ·ϕB , (66) ϕB

ϕA

|

{z

= Nh∗ (ϕB )

}

and the right side is the Walsh–Hadamard transform of Nh∗ evaluated at ϕ′B . Next, square and sum over ϕ′B , X

Eh∗ (ϕ′ )2 =

ϕ′B

X

Nh∗ (ϕB ) Nh∗ (ψB )

ϕB ,ψB

×

′

X

(−1)(ϕB ⊕ψB )·ϕB

(67)

ϕ′B ∈{0,1}QB

= 2QB

X

Nh∗ (ϕB )2 ,

ϕB

where the inner sum is a character sum and only the diagonal term ϕB = ψB survives.

9 B.

which adds to Nh∗ (ϕB ) the requirement that the A-side sum equal this particular z ∗ . The question is whether the extra requirement removes anything. If z ∗ ̸= z ∗ (ϕB ) then no ϕA qualifies and Nz∗ (ϕB ) = 0. If instead z ∗ = z ∗ (ϕ A making (ϕA , ϕB ) lie in TM PB ), then every ϕP satisfies i∈A ϕi yi = z − i∈B ϕi yi = z ∗ automatically. Therefore

The amplitude bound

Write ∆z∗ for the single term of Eq. (20) carried by one value of z ∗ X

Eh∗ (ϕ′ ) =

∆z∗ (ϕ′ ),

(68)

∆z∗ (ϕ′ ) = A′z∗ ,W ′ C(z′ ,z̃∗ ),S,h′ ,

(69)

z̃ ∗ ∈{0,1}n−1

Nz∗ (ϕB ) = Nh∗ (ϕB ) · 1[z ∗ (ϕB ) = z ∗ ], which means that X

and after normalisation the amplitude carried by z ∗ is p ′ ′ αz∗ (ϕ ) = ∆z∗ (ϕ )/ E0 (ϕ′ )2 + E1 (ϕ′ )2 , which is the αz∗ of [15].

X

and hence

Pr max αz∗ > θ ∗ z

Nz∗ (ϕB )2 = Nh∗ (ϕB )2 .

(74)

Step 3. Equation (66) applies to Nz∗ , giving ∆z∗ (ϕ′ ) = d Nz∗ (ϕ′B ), and then XX XX ∆z∗ (ϕ′ )2 = 2QB Nz∗ (ϕB )2

(70) i

(73)

z∗

hX i E αz2∗ ≤ 1, z∗

Nz∗ (ϕB ) = Nh∗ (ϕB ),

z∗

Theorem E. Assume Hypothesis (U), then for every threshold θ > 0,

h

(72)

≤ θ−2 .

ϕ′B

z∗ Step 2

Q

Here E and Pr are defined over ϕ′B ∈ {0, 1} B . Taking θ = 23n/2 gives 2−3n , stronger than the O(2−n ) of Lemma 3 of [15].

z∗

ϕB

QB

X

= 2

Nh∗ =0 (ϕB )2

ϕB

+ 2QB

X

Nh∗ =1 (ϕB )2

(75)

ϕB

Proof. We take five steps. ∗ Step P 1. Once the total sum is determined, z = z − i∈B ϕi yi , where the right side depends only on ϕB beyond the fixed z. So z ∗ is a function of ϕB , written as z ∗ (ϕB ). Step 2. Let n Nz∗ (ϕB ) = # ϕA : (ϕA , ϕB ) ∈ TM o P ∗ , and i∈A ϕi yi = z

z∗

E0 (ϕ′ )2 + E1 (ϕ′ )2 ,

ϕ′B

where the last equality is Lemma D again. Step 4. The weight of a record is proportional to ′ 2 E0 (ϕ′ )2 + Ep 1 (ϕ ) and the constant cancels. The quantity αz∗ carries E02 + E12 in its denominator and is defined only where the weight is positive, so the average runs over those records alone,

(71)

′ 2 ∗ z ∗ ∆z (ϕ ) E0 (ϕ ) + E1 (ϕ ) · | {z } E0 (ϕ′ )2 + E1 (ϕ′ )2 ϕ′B : E02 +E12 >0 | {z } weight P

X

hX i E αz2∗ =

=

X

′ 2

′ 2

P

′ 2 z ∗ αz ∗ (ϕ )

=

X

E0 (ϕ′ )2 + E1 (ϕ′ )2

.

(76)

ϕ′B ∈{0,1}QB

The term cancel, leaving P two factorsPin each numerator ′ 2 ∗ (ϕ ) . The identity of Step 3 runs ∆ ′ 2 2 ∗ z ϕB : E0 +E1 >0 z over every ϕ′B , and the two sums differ by the nonnegative contribution of the zero-weight records. Dropping that contribution only decreases the value, so P P ′ 2 hX i ∗ ϕ′B z ∗ ∆z (ϕ ) 2
= 1. (77) E αz∗ ≤ P ′ 2 ′ 2 ϕ′ E0 (ϕ ) + E1 (ϕ ) z∗

tive with E[V ] ≤ 1 by Step 4. Pointwise maxz∗ αz∗ (ϕ′ )2 ≤ V (ϕ′ ), so the event {maxz∗ |αz∗ | > θ} is contained in {V > θ2 }. Splitting E[V ] according to whether V exceeds θ2 , we have   E[V ] ≥ θ2 Pr V > θ2 ,

B

′

Step 5. Write V (ϕ ) =

P

z ∗ αz

∗

(ϕ′ )2 , which is nonnega-

so Pr[V > θ2 ] ≤ E[V ]/θ2 ≤ θ−2 .

(78)

10 C.

The corollary

The corollary to Lemma 3 asks the same question of the aggregate X αzh∗ = αz∗ , (79) ∗ z ∗ : top(z ∗ ) = zh

a class containing 2 n−L values of z ∗ . The proof of Theorem E used only that z ∗ is a function of ϕB , so any coarser classification carries the same argument. Theorem E′ . Assume Hypothesis (U). Let ζ be any function of ϕB , with values in an arbitrary set. Write ∆ζ (ϕ′ ) for the part of Eh∗ (ϕ′ ) contributed by the terms p with ζ(ϕB ) = ζ, and αζ = ∆ζ / E02 + E12 . Then for every θ > 0, hX i E αζ2 ≤ 1, (80) ζ

h i Pr max |αζ | > θ ≤ θ−2 . ζ

(81)

Proof. Repeat the five steps of Theorem E with z ∗ replaced by ζ. Step 1 is now the hypothesis on ζ. Step 2 uses only that hypothesis and gives Nζ (ϕB ) = Nh∗ (ϕB )1[ζ(ϕB ) = ζ], which has at most one nonzero entry for fixed ϕB . Steps 3 to 5 never refer to the meaning of ζ. Taking ζ(ϕB ) = z ∗ (ϕB ) recovers Theorem E. Taking ζ(ϕB ) = top(z ∗ (ϕB )) gives hX i E αz2h∗ ≤ 1, (82) ∗ zh

h i 3/2 ∗ > n Pr max α ≤ n−3 , z h ∗ zh

LEMMA 4

Lemma 4 [15]. For any z ∗ , let zh∗ be the most significant log n bits of z ∗ , and zl∗ be the ∗ remaining bits. Then for any two values zh,0 ∗ ∗ and zh,1 of zh that differ only in the most significant bit h∗ , and for c ≥ 12, the amplitudes αzh,0 and αzh,1 (defined as in the corollary to Lemma 3) differ by an expected multiplicative factor 1 ± O(n−(((c−1)/2)−1) ) with probability at least 1 − 1/n.

zl∗ ∈Zν

h

l

Two values of zh∗ differing only in the top bit share every bit of z̃ ∗ that the B-side factor sees, so C is the same function of zl∗ for both, which is Lemma 2. The comparison therefore sits entirely in the unsigned counts |A′ |, and the rest of this section is about them. The skeleton in [15] is a pair of balls-in-bins models, one at the level of zh∗ and one at the level of zl∗ . A mean and a variance are read off each model and Chebyshev is applied to those two numbers. The balls are subset sums and are pairwise independent without being independent, which is all a variance needs, so both numbers the sketch reads off come out right. Sections V A to V D replace the two models by exact computations and recover the exponents and failure probabilities the paper displays. The assumption that ga carries no faulty samples is removed along the way. The A side factorises over groups, and ga sits differently in the record from the other a − 1 groups
ϕA = ϕg1 , . . . , ϕga−1 , ϕga . (85) |{z} | {z } top blocks pinned by W ′

top block free

Three constraints define A′z∗ ,W ′ , namely top(rj ) = Wj′ for j < a, ls∗ = 0, and z ∗ (ϕA ) = z ∗ . Split the third one along z ∗ = zh∗ ν + zl∗ . For the high half, the top L bits sa of the sum over the distinguished group ga determine zh∗ by X zh∗ = Wj′ + sa (ϕga ) mod 2L . (86) j<a

(83)

well beyond the O(1/n) the corollary asks for. Theorem E and Theorem E′ give the second half of Lemma 3 and its corollary under Hypothesis (U), at every threshold and for either value of h∗ . Both of these go beyond the published statement. The first half is in Appendix B and nothing above or below draws on it.

V.

The two amplitudes being compared are built out of the A-side counts. Substituting αz∗ = λ4 |A′z∗ ,W ′ |C(z′ ,z̃∗ ),S,h′ into the aggregate of Eq. (79), X αzh∗ = λ4 A′(z∗ ,z∗ ),W ′ C(z′ ,z̃∗ ),S,h′ . (84)

Every Wj′ here is a measured constant, so fixing zh∗ is the same as fixing sa and confines ϕga to the block top(rga ) = sa . For the low half, writing rj = sj ν + ρj for each group j as in Section V D X zl∗ ≡ ρga (ϕga ) + ρj (mod ν). (87) j<a

Enumerating ϕga first and counting the remaining groups afterwards turns the count into a double sum X A′(z∗ ,z∗ ),W ′ = Xzl∗ −ρga , (88) h

l

ϕga : top(rga )=sa

where n o P Xρ = # (ϕgj )j<a : top(rj ) = Wj′ ∀j < a, j<a ρj ≡ ρ (89) counts the configurations of the pinned groups whose low parts add up to ρ. That bin count is taken up again in Section V D.

11 A.

An exact covariance

We start from the covariance computation using Eq. (48). Lemma F. For any group j and any r, r′ ∈ ZN ,
2m − 1  1 δrr′ − . (90) Cov nj [r], nj [r′ ] = N N P Consequently the top-block count Xσ = r : top(r)=σ nj [r] has variance exactly (2m − 1)2−L (1 − 2−L ). Proof. The first moment behind Eq. (48) is E[nj [r]] = 1[r=0] + β, with β = (2m − 1)/N as in Section III D, so     E nj [r] E nj [r′ ] = 1[r=0]1[r′ =0]
(91) + β 1[r=0] + 1[r′ =0] + β 2 . Subtracting this from Eq. (48) leads to 2m − 1 (4m − 3 · 2m + 2) − (2m − 1)2 = β δrr′ − . 2 N N2 (92) Summing over r and r′ inside one block top(r) = top(r′ ) = σ gives β δrr′ +

2m − 1  ν2  ν ν Var(Xσ ) = ν− = (2m − 1) 1− N N N N
= (2m − 1) 2−L 1 − 2−L .

B.

The term 1[σ=0] comes from the atom at r = 0, since top(0) = 0 places the empty subset in the block σ = 0. The 2m − 1 nonempty subsets divide evenly among the 2L blocks, and the block σ = 0 holds one more. Step 2. Lemma F gives Var(Xσ ) = (2m −1)2−L (1−2−L ) for every σ. pStep 3. Fix one σ. The standard deviation sd(Xσ ) = Var(Xσ ) does not depend on σ, so one threshold serves all blocks, and Chebyshev gives h i Var(Xσ ) 1 Pr Xσ − EXσ > κ sd(Xσ ) ≤ 2 = 2. κ Var(Xσ ) κ (97) Only finiteness of the variance is used, and nothing about the shape of the distribution of Xσ . Step 4. Let Bσ be the event that block σ leaves the range, for σ = 0, 1,S. . . , 2L − P 1. We need to exclude the union. Pointwise 1[ σ Bσ ] ≤ σ 1[Bσ ], since the left side taking the value 1 forces at least one term on the right to do the same and the terms are nonnegative. Taking expectations and using Step 3, L 2X −1 h[ i 2L Pr Bσ ≤ Pr[Bσ ] ≤ 2 , κ σ σ=0

(98)

and the complementary event is Eq. (93). Step 5. For σ ̸= 0, Step 1 gives EXσ = (2m −1)2−L , and dividing the bound of Step 4 by it produces the relative form. Substituting p 2m = nc and 2L = n, the relative standard deviation is n(1 − 1/n)/(nc − 1) = n(1−c)/2 (1 + O(n−1 )). Taking κ = n turns this into n 1−(c−1)/2 = n−((c−1)/2−1) with failure probability 2L /κ2 = n/n2 .

Concentration of the block counts

Theorem G. Let κ > 0 and let gj be any group. With probability at least 1 − 2L /κ2 over the samples of that group, every top block satisfies q
Xσ − EXσ ≤ κ (2m − 1) 2−L 1 − 2−L . (93) For σ ̸= 0 the mean is EXσ = (2m −1)2−L , and the bound takes the relative form s
2L 1 − 2−L Xσ − EXσ ≤ κ . (94) EXσ 2m − 1 At the parameters 2m = nc and 2L = n of [15], taking κ = n gives a relative deviation at most n−((c−1)/2−1) with failure probability at most 1/n. Those are the exponent and the failure probability displayed in Lemma 4. Proof. We take five steps. Step 1. The first moment behind Eq. (48) is E[nj [r]] = 1[r=0] + β, and a top block holds ν = N/2L residues, so X
EXσ = 1[r=0] + β = 1[σ=0] + νβ, (95) r : top(r)=σ

νβ = (2m − 1)2−L .

(96)

C.

Faulty samples

Suppose ga carries fa faulty samples. A faulty sample fixes its bit ϕi at a definite value and takes no part in the superposition, so the group has only m − fa free bits. The count nga [r] then ranges over 2 m−fa configurations, and the frozen bits contribute one fixed shift, which moves the whole distribution without changing its shape. So Lemma F, Theorem G and Lemma H below all hold with 2m replaced by 2 m−fa . Since fa ∼ Bin(m, pf ) with pf = 1/(c′ log n) and m = c log n, the mean Efa = mpf = c/c′ is a constant. On average     E 2 m−fa = 2m E 2−fa  (99) ′ pf m = 2m 1 − −→ 2m e−c/(2c ) , 2 indicating a loss of one constant factor. Passing from a ratio of averages to an average of ratios costs one application of Cauchy–Schwarz and stays at the same order. Theorem G needs the high probability version. From
m k ≤ m /k!, k     m k (mpf )k (c/c′ )k Pr fa ≥ k ≤ pf ≤ = , (100) k! k! k

12 TABLE V. The two models. They part company in the first row, where the second one sees the record.

Balls

First, at zh∗

Second, at zl∗

all 2m strings ϕga of ga

the ϕA compatible with W ′ a value of zl∗ ν = 2 n−L

One bin a top block of rga Bins 2L = n

the window slice   uj (ρ) := nj sj ν + ρ ,

representing the same numbers as nj , taken on one block and reindexed. a−1 ), the number of comQ Fixing (ρ1 , . . . , ρQ patible ϕA is j nj [sj ν + ρj ] = j uj (ρj ). Summing over P all choices with j ρj ≡ ρ gives Xρ =

and k = Θ(log n/ log log n) makes the right side smaller than 1/n. With probability 1 − 1/n we therefore have 2 m−fa = n c 2−fa = n c−o(1) , so the relative deviation of Theorem G picks up a factor no(1) and the exponent in n−((c−1)/2−1) is unchanged. So the assumption that ga carries no faulty samples can be dropped, and no constant probability has to be paid for it. Both failure probabilities are of order 1/n and may be added, and the same applies to the other A groups.

D.

The second model under the conditioning

The two balls-in-bins arguments are not the same construction, as Table V shows. The first model lets ϕga run over all 2m values with the other groups absent, while the second fixes the value ϕga first and lets the remaining groups run. The A groups therefore fall into two classes in the second model. The a − 1 groups with j < a are pinned by W ′ to top(rj ) = Wj′ while the m bits inside each of them stay free, and all of the balls come from there. The group ga has its bits fixed and contributes one definite number. The record W ′ = (s1 , . . . , sa−1 , ls∗ ) holds top blocks only for j < a, and sa is not among them. Write  Xsj = # ϕj ∈ {0, 1}m : top(rj ) = sj , (101) Y P = Xsj , (102) j<a

so that Xsj is the block count of Theorem G taken at the pinned block, and P is the total number of ϕA compatible with W ′ . Write rj = sj ν + ρj with 0 ≤ ρj < ν. Since sj ν ≡ 0 (mod ν), the low n − L bits of z ∗ come only from the low parts, X zl∗ ≡ ρg a + ρj (mod ν). (103) |{z} j<a a definite number

The term from ga has to be separated out. Its effect is to shift every bin cyclically by one fixed amount and is independent of the other groups. The bin count Xρ of Eq. (89), which runs over the pinned groups j < a alone, is then a convolution of their low parts on Zν . Restricting nj to the pinned block gives

(104)

X

Y

uj (ρj ) (105)

ρ1 +···+ρa−1 ≡ρ (mod ν) j

=

u1 ∗ · · · ∗ ua−1 (ρ),

a cyclic convolution on Zν . Lemma H. Suppose at least one group has sj ̸= 0, and write µ = E[P ]/ν. Split each bin count into Xρ =

P + Yρ , ν

(106)

the first piece being the share of each bin when there are P balls in all, and the second Phow far bin ρ departs from its share. Then EXρ = µ, ρ Yρ = 0, the variables Yρ and P are uncorrelated, and
µ Cov Yρ , Yρ′ = µ δρρ′ − . ν

(107)

This is the covariance of νµ balls thrown uniformly into ν bins, and the proof of Lemma 4 assumes exactly that. The conditioning onQW ′ enters only through the ball count P , and since P = j Xsj has independent factors, Var(Xsj )  Var(P ) Y 2L = 1 +
2
2 − 1 ≈ a m , 2 EP EXsj j √ so the relative fluctuation of P is about n(2−c)/2 (log n)−1/2 .

(108)

a 2 L−m =

A bin count fluctuates in two ways. The ball count itself changes, which makes every bin rise and fall together. The balls also scatter differently once the count is fixed, which makes the bins trade against one another. Written separately, Eq. (107) is the scattering and Eq. (108) is the change in the count. Proof. Bin counts are a convolution of the slices. One Fourier transform turns that into a pointwise product, and different groups use independent weights, so the whole computation factors group by group. Write P fˆ(k) = ρ f (ρ)e−2πikρ/ν for the transform on Zν , so that Q X̂(k) = j ûj (k). The zero frequency is the ball count, P X̂(0) = ρ Xρ = P . The proof consists of four steps. Step 1, a slice with sj ̸= 0. Let sj0 ̸= 0. Of the four terms in Eq. (48), the atom and the two cross-atoms sit at r = 0, and top(0) = 0 places them in the block sj = 0

13 alone. Every r in the block sj0 is nonzero, so only two terms survive, 2m − 1 , (109) N m m m   2 −1 4 −3·2 +2 , δρρ′ + E uj0 (ρ) uj0 (ρ′ ) = N N2 (110) E uj0 (ρ) =

If k = k ′ = 0, then X̂(0) = P and the second moment is E[P 2 ], used only in Step 4. These four cases also show that Yρ and P are uncorrelated. We have P = X̂(0) while Yρ is a linear combination of the X̂(k) with k ̸= 0, and term by term 
 Cov X̂(k), X̂(0) = E X̂(k)X̂(0) − E X̂(k) E X̂(0) =0

a constant together with a diagonal term. Transforming each leads to E ûj0 (k) = β ν δk0 , (111) m m   4 − 3 · 2 + 2 ν 2 δk0 δk′ 0 . E ûj0 (k)ûj0 (k ′ ) = β ν δkk′ + N2 (112) Equation (111) vanishes at k ̸= 0, and Eq. (112) vanishes at k ̸= k ′ , since then the two indices cannot both be 0. Step 2, multiplying over groups. Distinct groups use disjoint weights and all weights are independent, so the expectation of a product factors into the product of the expectations, Y E X̂(k) = E ûj (k), (113)

(119) The variance of a single bin is therefore the sum of the two pieces with no cross term, 
Var(P ) 1 Var Xρ = +µ 1− , 2 ν ν

Xρ =

1X X̂(k) e2πikρ/ν ν k

(114)

j

There are four cases in (k, k ′ ). (a) First moment. E ûj0 (k) = 0 by Eq. (111), so one factor of the product vanishes and E X̂(k) = 0. SubstitutP ing into the inverse transform Xρ = ν1 k X̂(k)e2πikρ/ν and taking expectations, only k = 0 survives as 1 EP E X̂(0) = =µ (115) ν ν that is independent of ρ. (b) Second moment. By Eq. (112) one factor is again zero for k ̸= k ′ , so E[X̂(k)X̂(k ′ )] = 0. As for k = k ′ ̸= 0, we compute E|ûj (k)|2 group by group from X   ′ 2 E ûj (k) = E uj (ρ)uj (ρ′ ) e−2πik(ρ−ρ )/ν , (116) EXρ =

ρ,ρ′ ∈Zν

taking the four terms of Eq. (48) in turn. At k = ̸ 0 only the atom and the diagonal survive. A group with sj = 0 carries both and a group with sj = ̸ 0 carries only the diagonal, so in either case   2 E ûj (k) = (2m − 1)2−L + 1 sj =0 = EXsj (k ̸= 0), (117) the right side being the block mean of Eq. (95). Multiplying over j and using independence to turn the product back into an expectation, Y 2 E X̂(k) = EXsj j

j

(120)

the first piece from the ball count moving and the second from the balls scattering. Step 3, back to the bins. Splitting the inverse transform by frequency,

j

  Y   E ûj (k)ûj (k ′ ) . E X̂(k)X̂(k ′ ) =

hY i =E Xsj = EP = νµ

(k ̸= 0).

(118) (k ̸= 0).

=

X̂(0) 1 X X̂(k) e2πikρ/ν . + ν ν | {z } k̸=0 | {z } = P/ν

(121)

= Yρ

Since EYρ = 0, expanding both factors and using X̂(k ′ ) = X̂(−k ′ ) gives the covariance of two bins ρ and ρ′ as
  Cov Yρ , Yρ′ = E Yρ Yρ′ (122)  2πi(kρ−k′ ρ′ )/ν 1 XX  = 2 E X̂(k)X̂(k ′ ) e ν ′ k̸=0 k ̸=0

(123) νµ X 2πik(ρ−ρ′ )/ν = 2 e ν k̸=0
µ µ = ν δρρ′ − 1 = µ δρρ′ − , ν ν

(124) (125)

where only the terms with k = k ′ survive. Q Step 4, the ball count. The factors of P = j Xsj Q are independent, so E[P 2 ] = j E[Xs2j ] and (EP )2 = Q 2 j (EXsj ) , giving  2 Yh Var(Xsj ) i Var(P ) Y E Xsj 1+
2 =
2 − 1 =
2 − 1. EP EXsj EXsj j j (126) By Lemma F the numerator is Var(Xsj ) = (2m − 1)2−L (1−2−L ), and EXsj ≥ (2m −1)2−L , so each bracket carries a term at most (2m − 1)2−L (1 − 2−L ) 2L − 1 = m ≈ 2 L−m .
2 2 −1 (2m − 1)2−L

(127)

14 With a = n/ log n factors and (1 + x)a − 1 ≈ ax, we finally obtain n n 2−c Var(P ) L−m = · n 1−c = ,
2 ≈ a 2 log n log n EP

(128)

whose square root is n(2−c)/2 (log n)−1/2 . E.

Fitting the two levels together

Lemma H splits the bin count into Xρ = P/ν + Yρ and shows that the ball count P fluctuates, an effect a fixed-count picture leaves out. This subsection shows that the extra term does not affect the conclusion of Lemma 4, because P takes one value across both branches and cancels from the comparison. Following Eq. (88), we first sort the ϕA by the string ϕga of bits in ga , and keep the convention that zh∗ is determined by sa = top(rga ). Fixing ϕga contributes a definite ρga to the low part, so this class holds Xρ−ρga configurations with zl∗ = ρ. Substituting Eq. (88) into Eq. (79) then gives  X X αzh∗ = λ4 Xρ−ρga Cρ . (129) ρ∈Zν ϕga : top(rga )=sa

Now put Xρ−ρga = P/ν + Yρ−ρga into the sum. The first piece is a constant and depends on neither ρ nor ϕga , so the two sums separate as P X  αzh∗ = λ4 Cρ Xsa ν ρ {z } | main term (130) X X + λ4 Yρ−ρga Cρ , ϕga : top(rga )=sa

|

ρ

{z

}

=: Rh∗

where Xsa counts the strings ϕga consistent with sa , and Rh∗ names the error term, one number per branch. Everything in the main term except Xsa takes the same value on the two branches. The coefficient λ4 = (E02 + E12 )−1/2 normalises the two branches together and Q is one number per record. The ball count P = j<a XWj′ is fixed by the measured W ′ and by the weights of the groups j < a, P and neither h∗ nor zh∗ occurs in it. Writing J := λ4 (P/ν) ρ Cρ , the main term becomes J Xsa with the same J on both branches. For the main term,Pthe quantities sa and zh∗ differ by the fixed shift s∗ = j<a Wj′ + sa , so flipping the top bit of zh∗ flips the top bit of sa and Theorem G applies directly as Xsa,0 − Xsa,1 EXsa

c−1

≤ 2 n−( 2 −1) ,

(131)

where each block departs from the mean by at most c−1 n−( 2 −1) , with failure probability still 1/n. If one of the

two blocks is sa = 0, its mean carries the extra empty subset of Eq. (95) in a relative amount 2L /(2m − 1) ≈ n1−c . For c ≥ 12 that lies far below n−((c−1)/2−1) and is absorbed. The ball count P is a common factor of the main term and factors out of the difference, so the size of its fluctuation is immaterial. The remaining quantity to control is Rh∗ , which involves only Y . Lemma H asks that at least one pinned block be nonzero. All a − 1 of them vanish with probability 2−L(a−1) = 2−(n−log n) , which joins the other failure probabilities and is negligible against them. The lemma gives Var(Yρ ) = µ(1−1/ν) with µ = E[P ]/ν, and E[P ] follows from Eq. (95),  Y E[P ] = (2m − 1)2−L + 1[sj =0] ≈ 2 (a−1)(m−L) . j<a

(132) With am = cn and aL = n, and with m replaced by m(1− 1/(c′ log n)) to carry the faulty samples of Section V C, ′ E[P ] = 2 cn(1−1/(c log n))−2n−(c−2) log n , ν √ σ = µ.

µ=

(133) (134)

Chebyshev bounds the probability that one bin violates |Yρ | ≤ 2 n σ by 2−2n . Following Section II E, the union bound runs over the ν = 2 n−L bins and over all 2 L(a−1) = 2 n−log n values of the label vector W ′ . The exceptional event that survives has probability −2n n−log n n = 2−2 log n = n−2 , 2| n−log {z } · 2| {z } · 2 W′

(135)

bins

which joins the other failure probabilities of order 1/n. Outside it every bin sits within a relative 2 n σ/µ of its share. Taken at a single ρ, the summand of Eq. (129) is the amplitude αz∗ with zl∗ = ρ. The matching summand of Rh∗ is at most 2 n σ/µ times that amplitude, and Theorem E at θ = 2 3n/2 bounds it. Summing over the ν values of ρ, Rh∗ ≤ Rmax :=

2 nσ · |{z} ν · |2 3n/2 {z } . µ | {z } summands Lemma 3

(136)

one bin

Taking logarithms at c = 12, log Rmax ≤ −

3n 6n + ′ + 4 log n. 2 c log n

(137)

The middle term is o(n) for every constant faulty rate c′ , so Rmax ≤ 2−3n/2+o(n) , comfortably below the 2−n the argument needs.

F.

Path to the algorithm

Everything needed for the difference of the two aggregated amplitudes is now in place, and the difference is

15 the weaker of the two statements at issue. Equation (130) reads αzh∗ = J Xsa + Rh∗ on each branch, and the prefactor J is the same number for the two members of a pair. Subtracting the two copies therefore leaves it outside the bracket,

∗ ∗ αzh,0 − αzh,1 = J Xsa,0 − Xsa,1 + R0 − R1 . (138) The two terms are handled separately. Equation (131) bounds the count difference by 2n−((c−1)/2−1) EXsa , and each error term obeys |Rh∗ | ≤ Rmax , so c−1

∗ ∗ αzh,0 − αzh,1 ≤ 2 n−( 2 −1) J EXsa + 2Rmax . (139)

Meanwhile, Theorem G in relative form gives |Xsa,0 − EXsa | ≤ n−((c−1)/2−1) EXsa on the same record, leading to EXsa ≤

Xsa,0 . 1 − n−((c−1)/2−1)

(140)

Multiplying by |J| and reading Eq. (130) backwards ∗ (J Xsa,0 = αzh,0 − R0 ), we have J EXsa ≤

J Xsa,0 1 − n−((c−1)/2−1)

=

∗ αzh,0 − R0

(141)

the last line by the triangle inequality with |R0 | ≤ Rmax ,
−1 together with 1 − n−((c−1)/2−1) = 1 + o(1) once c ≥ ∗ |, so every 12. The corollary to Lemma 3 bounds |αzh,0 quantity on the right of Eq. (139) is already bounded. Nothing along the way needs J to be large, or even to have a definite sign. Lemma 4 is stated as a bound on the ratio in the form 1 ± O(n−((c−1)/2−1) ), which is strictly stronger than Eq. (139). To be more specific, ∗ αzh,1

=

Xsa,0 + R0 /J , Xsa,1 + R1 /J

(142)

which is close to 1 only when |J| Xsa dominates Rmax . A pair whose prefactor satisfies |J| Xsa ≲ Rmax has a ratio nowhere near 1. P Such a pair can occur, since J carries the signed sum ρ Cρ over the ν = 2 n−L values of zl∗ and no argument keeps such a sum far from zero on every record. This section therefore establishes Eq. (139) and not the ratio. The rest of the section shows that the difference is all the closing argument ever consumes, so nothing downstream is weakened. The index zh∗ carries L = log n bits and therefore takes n values, which form n/2 pairs differing only in the top bit h∗ . Grouping Eq. (21) by pairs, the quantity to bound is a sum of n/2 differences, X ∗ ∗ Ê0 − Ê1 ≤ αzh,0 − αzh,1 , (143) pairs

with failure probability O(1/n), and the exponent is consistent with the one obtained from the multiplicative form, so the weaker statement loses nothing. The two branch amplitudes are now pinned. Since Ê02√+ Ê12 = 1, at least one of |Ê0 | and |Ê1 | is at least 1/ 2. Equation (144) makes the√two differ by O(n−2 ), so both are within O(n−2 ) of 1/ 2 and carry the same sign. The normalisation cancels from the ratio, so q =

1 − n−((c−1)/2−1) 
 ∗ ≤ 1 + o(1) αzh,0 + Rmax ,

∗ αzh,0

which is the form Eq. (139) was stated in. Both sides carry the normalisation λ4 , since αzh∗ does. By Theorem E′ at θ = n3/2 , every aggregated amplitude obeys |αzh∗ | ≤ n3/2 except with probability n−3 , so Eqs. (139) and (141) bound each summand by 2n−((c−1)/2−1) (n3/2 + Rmax )(1 + o(1)) + 2Rmax . Since Rmax ≤ 2−3n/2+o(n) is exponentially small, the Rmax terms are negligible against everything else and
n · 2 n3/2 · O n−((c−1)/2−1) Ê0 − Ê1 ≤ 2 (144)
c ≥ 12 7/2−(c−1)/2 −2 = O n ≤ O(n ),

E0 − E1 E0 + E1

=

Ê0 − Ê1 Ê0 + Ê1

= O n−2 ,

(145)

and Eq. (15) gives p = 1 − O(n−4 ), which exceeds 1/2 by a constant. Polynomially many repetitions and a majority vote then return dn , and the recursion on the remaining bits of d finishes the algorithm. VI.

NUMERICAL CHECKS

The parameters of [15] put a direct simulation of the algorithm out of reach, since c ≥ 12 makes Q = Knc+1 exceed 1016 already at n = 16. The three results proved above are statements about classical counting quantities, and those can be evaluated in full at small parameters. Figure 1 collects one check for each. Panel (a) plots the two terms of Eq. (58) against n at the parameters of [15]. The correlation coefficient η is obtained in closed form from Eq. (49) in exact rational arithmetic, using the averages of Eqs. (50), (A9) and (A10). The value agrees with a direct sum over k for n ≤ 16. The curve rises while 2m exceeds N and falls once 2m drops below it, crossing the Poisson term c/(Ka) at n ≈ 164. Beyond that point η contributes nothing and the bound of Theorem C is carried by 1/E[Z] alone, which leaves Pr[Z ≥ a] at least 0.81 for n = 256 and at least 0.96 for n = 2048. Panel (b) takes a toy instance small enough to enumerate, with n = 6 and Q = 20 sample bits cut into G = 4 groups of m = 5, of which a = 2 sit on the A side. Every one of the 210 strings ϕ′B is summed over, which imposes Hypothesis (U) by construction. The measured tail runs a factor of 20 below θ−2 at θ = 1 and a factor of 103 below it at θ = 16, so the bound of Theorem E is comfortable as well as valid.

16

(a) Theorem C

(b) Theorem E

20

10

0

10 −3

−20

−80

24

10 9

1.1 1.0 0.9

10 −4

−40 −60

−2

variance of the sum

10 −1

Pr[ max|α| > θ ]

log 2 of each term

40

10 0

meas./pred.

η negligible

60

(c) Lemma H 10 10

θ −2

10 −5

∗

η c/(Ka) 26

max |αz | z max |αzh | z

10 −6

n

28

2 10

∗

h

10 −1

∗ ∗

10 0

θ

10 1

X

Xρ

analytical sampled

10 8 10 7 10 6 10 5 10 4

X

Yρ

analytical sampled

1

4

16

64 128

k (bins merged)

FIG. 1. One numerical check for each of the three results. (a) The two terms that bound Var[Z]/E[Z]2 in Eq. (58), at c = 12 and K = 1.5c. The correlation term η is computed exactly and drops below the Poisson term at n ≈ 164. (b) Measured tail of the amplitude against the bound of Theorem E, taken over the full cube of 210 measurement outcomes of a toy instance with n = 6 and Q = 20. (c) Variance of k merged bins in the second balls-in-bins model, at n = 12, m = 10, L = 3, ν = 512 and three pinned groups, from 2 × 105 samples. The upper curve carries the ball-count term and the lower one does not. The lines are computed from Lemma H, with µ and Var(P ) taken from Eq. (95) and Eq. (108), while the points are measured from the samples. The strip below gives the measured value over the computed one, with 95% bootstrap intervals.

Panel (c) tests Lemma H by merging k adjacent bins. Since P Yρ and P are uncorrelated, Eq. (107) predicts Var( ρ<k Yρ ) = µk(1 − k/ν), while the same sum of the bin counts themselves carries the further term k 2 Var(P )/ν 2 . Both are computed from the lemma alone, with µ taken from Eq. (95) and Var(P ) from Eq. (108). The measured values come from 2 × 105 sampled runs and agree with both. The gap between the two curves is the term a fixed ball count leaves out, and it exceeds the scattering term by orders of magnitude. Therefore, the ball count governs the bin variance completely, and Section V E is where it cancels between the two branches. None of these checks bears on Hypothesis (U), since panel (b) imposes it by construction and the other two never meet it. The agreement reported here therefore says nothing about the one gap recorded in Section VII.

VII.

CONCLUSIONS AND DISCUSSIONS

In this paper we have restated the three sketched lemmas of [15] in a form that admits a single reading and have proved each of them, as summarized in Table VI. Only Lemma 4 comes out weaker than the original claim, with a bound on the difference of the two branch amplitudes in place of their ratio, and Section V E shows that the closing argument consumes only the difference. One condition survives all of this. Hypothesis (U) asks

that the A/B partition be fixed independently of ϕ′ , so that ϕ′B ranges over the whole cube {0, 1}QB with the rest of the record held fixed. However, the algorithm itself does not supply it. It requires A to consist of the first a all-zero groups, which makes the partition a function of ϕ′ . The hypothesis enters at a single step in Lemma D, X ϕ′B ∈{0,1}QB

Eh∗ (ϕ′ )2 = 2QB

X

Nh∗ (ϕB )2 ,

(146)

ϕB

where the character sum over the whole cube collapses to the diagonal ϕB = ψB and leaves the factor 2QB . Narrowing that range is not a perturbation of the identity. A group that the rule forces away from the all-zero block contributes X ′ (−1)(ϕj ⊕ψj )·ϕj = 2m δϕj ψj − 1 (147) ϕ′j ̸=0

in place of 2m δϕj ψj , so Eq. (146) acquires one term for every subset of the forced groups and the off-diagonal ones no longer cancel. Controlling them would need the autocorrelation of Nh∗ , which is the one object Lemma D is built to avoid. Nor does it help that the discarded strings are few, because Eq. (146) holds only after the whole cube has been summed. Its left side collects squares of signed sums and its right side squares of counts, and the two are unrelated at a fixed ϕ′B .

17 TABLE VI. The four lemmas in the forms proved here. In [15]

Status

Lemma 1 Holds, with probability tending to one (Theorem C), stronger than the constant claimed Lemma 2 Exact as published, with a two-line proof (Section II) Lemma 3 and Corollary The amplitude bound holds at every threshold (Theorem E, E′ ) and needs no well-behavedness hypothesis, so the first half of the lemma never enters and is recorded only in Appendix B Lemma 4 Both counting estimates hold, the first with the constant [15] displays (Theorem G), the second together with the term a fixed ball count leaves out (Lemma H), and the assumption that ga carries no faulty samples can be dropped (Section V C). The comparison of the two branches is proved in the weaker form of Eq. (139), which is the form the closing argument uses.

The two demands on A pull against each other, and that is why a change of rule does not remove the point. The groups of A have to be all-zero, since only then do they carry no sign and leave the A-side factor an unsigned count that both branches of the final interference share. Selecting them therefore means looking at ϕ′ , and that look costs the freedom Hypothesis (U) asks for. Fixing the index set before Step 4 would grant the hypothesis and give up the all-zero property. Therefore, establishing these four lemmas does not by itself establish the correctness of the algorithm.

Appendix A: The second moment of a group’s subset-sum count

This appendix derives Eq. (48) and Eq. (49), together with the two averages of the Fejér kernel quoted in Eq. (50).

2.

Carrying the four classes through T (k)

Substitute Table VII into Tj (k) = P P ′ −k(r−r ′ ) n [r]n [r ] ω , where the inner ′ j s r,r ∈s j sum runs over the r with the top L bits fixed and the low n − L bits free. P P The diagonal term contributes β s r∈s 1 = βN = 2m − 1, and the atom contributes 1, the two together making 2m . For the constant term, ZN is cut into 2L blocks of length ν, and the bottom one is B0 = {0, 1, . . . , ν − 1}. Its indicator has transform  k = 0, ν−1 ν, X ω −kr = 1 − ω −kν (A3) 1̂B0 (k) =  , k = ̸ 0, r=0 1 − ω −k and taking the squared modulus with |1 − e−iθ |2 = 4 sin2 (θ/2) and ν/N = 2−L sin2 (πkν/N ) sin2 (πk/2L ) = , sin2 (πk/N ) sin2 (πk/N ) (A4) the unnormalised Fejér kernel of order ν. Every block is a translate P Pof B0 and translation contributes only a phase, so s | r∈s ω −kr |2 = 2L Dν (k), and the constant term contributes β2 Dν (k). For the cross-atom terms, one of the two indices is pinned to 0 and the other runs over B0 . The two cases give complex conjugate expressions, so together they contribute 2β Re 1̂B0 (k) = β1 Re 1̂B0 (k). Collecting the four gives Eq. (49). Dν (k) := 1̂B0 (k)

1.

The four classes of pairs

P Write Σ(ϕ) = i∈gj ϕi yi mod N , so that nj [r] = P 1[Σ(ϕ) = r]. Multiplying two of these gives a m ϕ∈{0,1} double sum over pairs of subsets,   X   E nj [r] nj [r′ ] = Pr Σ(ϕ) = r, Σ(ψ) = r′ . (A1) ϕ,ψ

y

For a single subset, Pry [Σ(ϕ) = r] depends only on whether ϕ is empty. The empty subset gives Σ ≡ 0 with certainty, and any nonempty subset gives Σ uniform on ZN , since a sum of independent uniform values is uniform. Hence   E nj [r] = 1[r = 0] + β , | {z } |{z} ϕ=0

β=

2m − 1 . N

(A2)

ϕ̸=0

For a pair, the same distinction applies to each member, and the four resulting classes are collected in Table VII. In the last case, ϕ and ψ are distinct and neither is empty, so the two sums are jointly uniform on Z2N . Adding the four contributions gives Eq. (48).

3.

2

=

Averages over the frequency line

Parseval with f = g = 1B0 gives the first X 1 X 2 Dν k = 1̂B0 (k) = 1B0 [r]2 = ν. N r

(A5)

k

⋆ f (k) = |fˆ(k)|2 from the proof For the second, we use f[ of Lemma B to give
1 X Dν (k) ω kδ = 1B0 ⋆ 1B0 [δ] =: Λ[δ], (A6) N k

18 TABLE VII. The four classes of subset pairs and what each contributes to Eq. (48). Class

Condition

atom ϕ=ψ=0 cross-atom exactly one empty diagonal ϕ = ψ ̸= 0 constant

Pr[Σϕ =r, Σψ =r′ ]

Pairs

Contribution

′

1 2(2m − 1) 2m − 1

1[r=r′ =0]
β 1[r=0] + 1[r′ =0] β δrr′ 4m − 3 · 2m + 2 N2

1[r=0]1[r =0] 1 1[r=0] or N1 1[r′ =0] N 1 δ ′ N rr 1 m m ϕ ̸= ψ, neither empty (2 − 1)(2 − 2) N2

and since 1B0 takes values in {0, 1},  Λ[δ] = # r : r ∈ B0 and r − δ ∈ B0

(A7)

= B0 ∩ (B0 + δ) = (ν − |δ|)+ ,

the overlap of two intervals of length ν offset by δ, with (x)+ = max(x, 0). Applying Parseval once more to Λ gives Dν2 k =

X 1 X 2 Λ̂(k) = Λ[δ]2 N δ

k

2

= |{z} ν +

2

ν−1 X

j

2

j=1

δ=0

ν 2ν 2 + 1 = 3

≤ ν3,

| {z }

δ=±1,...,±(ν−1)

(A8)

− The signed count of Section II is Eh∗ =√t+ M − tM , so ∗ being well-behaved for h says Eh∗ ≥ ε tM,h∗ . The dependence of tM on h∗ is written explicitly, since TM is by definition the set consistent with the record and a given h∗ , and the two branches carry their own counts. Failing to be well-behaved is the same as carrying little weight. The predicate of Definition 1 contains Ω(·), which names a class of functions and not a number, so the clause becomes a definition only once a constant is fixed. That constant matters, because the failure probability scales √ as its square. The threshold is therefore written as ε tM,h∗ and the conclusion as ε2 . One consequence of Lemma D is needed and was not drawn there. The function Nh∗ (ϕB ) takes nonnegative 2 integer P values, so Nh∗ ≥ Nh∗ pointwise, and summing with ϕB Nh∗ (ϕB ) = tM,h∗ turns Eq. (65) into

X which is Eq. (50). Three further averages are used by the numerical check of Section VI, and the same two tools deliver them. Writing f = 1B0 and reading the inverse transform at δ = 0 gives ⟨fˆ⟩k = f [0] = 1, so ⟨Re fˆ⟩k = 1. Since ⋆ f (k) up to the reflection r 7→ −r, the same fˆ(k)2 = f[ reading gives ⟨fˆ2 ⟩k = #{r ∈ B0 : −r ∈ B0 } = 1, where the only such r is 0 because ν ≤ N/2. Expanding 2 (Re fˆ)2 = 14 (fˆ2 + 2|fˆ|2 + fˆ ) and using ⟨|fˆ|2 ⟩k = ν, we have (Re 1̂B0 )2 k =

1 + 2ν + 1 ν+1 = . 4 2

(A9)

For the last one, fˆ2 fˆ at δ = 0 counts the triples of B0 with r1 + r2 = r3 , so  Dν Re 1̂B0 k = # (r1 , r2 ) ∈ B02 : r1 + r2 ≤ ν − 1 =

ν(ν + 1) . 2 (A10)

Appendix B: The first half of Lemma 3

This appendix records the other half of the statement quoted at the start of Section IV. Its role there is to make the second half non-vacuous, and the proof given in Section IV B does not need that service.

Eh∗ (ϕ′ )2 ≥ 2QB tM,h∗ .

(B1)

ϕ′B ∈{0,1}QB

Theorem I. Assume Hypothesis (U). Fix ε > 0 and call ∗ ′ ∗ the √ superposition well-behaved for h when |Eh (ϕ )| ≥ ε tM,h∗ . The probability that it is well-behaved for neither value of h∗ is then at most ε2 . Taking ε = 2−n/2 gives 2−n , which is the conclusion of the first half of Lemma 3 of [15]. Proof. Fix everything in the record except ϕ′ , i.e., Y , z ′ , W ′ , S, h′ and the A/B partition, and let ϕ′B vary. The weight of a record is proportional to E0 (ϕ′ )2 + E1 (ϕ′ )2 , so the quantity to bound is   Pr neither h∗ well-behaved
P ′ 2 ′ 2 (B2) ϕ′B failing both E0 (ϕ ) + E1 (ϕ )
. = P ′ 2 ′ 2 ϕ′ ∈{0,1}QB E0 (ϕ ) + E1 (ϕ ) B

A record failing both satisfies E0 (ϕ′ )2 < ε2 tM,0 and E1 (ϕ′ )2 < ε2 tM,1 , so E0 (ϕ′ )2 + E1 (ϕ′ )2 < ε2 (tM,0 + tM,1 ). There are at most 2QB such strings, so the numerator is below 2QB ε2 (tM,0 + tM,1 ). Applying Eq. (B1) to each branch, the denominator is X

2QB N0 (ϕB )2 + N1 (ϕB )2 ≥ 2QB tM,0 + tM,1 . ϕB

(B3) Dividing the numerator by the denominator, both 2QB and tM,0 + tM,1 cancel and ε2 remains.

19 Note added. Since [15] appeared, its lemmas have been the subject of active public scrutiny. We became aware of parts of that discussion while this work was in preparation. Where our findings overlap with analyses circulated elsewhere we claim no priority. Our results were obtained independently and are stated so that each can be checked against [15] directly.

No. 125B2100) and the Quantum Science and Technology - National Science and Technology Major Project (Grant No. 2021ZD0302100).

ACKNOWLEDGMENTS

This work is supported by the National Natural Science Foundation of China (NSFC) (Grant No. 12475022 and

[1] M. Ajtai, Generating Hard Instances of Lattice Problems, STOC 1996, pp. 99–108. [2] D. Bacon, A. M. Childs and W. van Dam, From Optimal Measurement to Efficient Quantum Algorithms for the Hidden Subgroup Problem over Semidirect Product Groups, FOCS 2005, pp. 469–478. [3] Z. Brakerski, E. Kirshanova, D. Stehlé and W. Wen, Learning with Errors and Extrapolated Dihedral Cosets, PKC 2018, pp. 702–727. [4] Y. Chen, Quantum Algorithms for Lattice Problems, Cryptology ePrint Archive, Paper 2024/555, 2024. [5] A. M. Childs and W. van Dam, Quantum Algorithms for Algebraic Problems, Rev. Mod. Phys. 82, 1–52, 2010. [6] M. Ettinger and P. Høyer, On Quantum Algorithms for Noncommutative Hidden Subgroup Problems, Adv. Appl. Math. 25(3), 239–251, 2000. [7] G. Kuperberg, A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem, SIAM J. Comput. 35(1), 170–188, 2005. [8] G. Kuperberg, Another Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem, TQC

2013, LIPIcs 22, pp. 20–34. [9] National Institute of Standards and Technology, ModuleLattice-Based Key-Encapsulation Mechanism Standard, FIPS 203, 2024. [10] R. O’Donnell, Analysis of Boolean Functions, Cambridge University Press, 2014. [11] O. Regev, Quantum Computation and Lattice Problems, SIAM J. Comput. 33(3), 738–760, 2004. [12] O. Regev, A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space, arXiv:quant-ph/0406151, 2004. [13] O. Regev, On Lattices, Learning with Errors, Random Linear Codes, and Cryptography, J. ACM 56(6), Article 34, 2009. [14] P. W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM J. Comput. 26(5), 1484–1509, 1997. [15] D. R. Simon, A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem (Preliminary Draft), Cryptology ePrint Archive, Paper 2026/1591, 31 July 2026.

Related documents

• Rigorous Statements and Proofs of the Lemmas in Simon's Algorithm for the Dihedral Coset Problem and Their Underlying Hypothesis#625174
• Rigorous Statements and Proofs of the Lemmas in Simon's Algorithm for the Dihedral Coset Problem and Their Underlying Hypothesis#622901
• Tripartite Form Universality in Holographic Entropy Inequalities#1037187
• A Note on Gödel, Priest and Naïve Proof#707954
• Wave Numbers: Discrete Sequence Algebras, Sieve Projectors, and Dynamical Geometry#1048977