PaperlayerView exact revision on arXiv

Source-linked AI summary

A provable quantum advantage for approximate optimization via decoded quantum interferometry

Maximilian J. Kramer, Elies Gil-Fuster, Benjamin D. M. Jones, Jens Eisert, Franz J. Schreiber

arXiv:2610.02145v2quant-phcs.CCcs.DS

TL;DR

Whether DQI can provably outperform classical algorithms for approximate optimization remains an open question. This paper constructs a folded-OPI oracle setting and proves a strict quantum–classical separation: at rate 0.3, DQI’s limiting expected score is approximately 0.8571 versus the classical benchmark of 0.65.

  • Problem

    Whether DQI’s approximation guarantees yield a provable separation from arbitrary classical algorithms in a common oracle model remains an open question.

    Source: §1 · p. 3

  • Method

    The paper constructs balanced folded-OPI instances from folded Reed–Solomon codes and combines DQI decoding with a classical membership-query lower bound.

    Source: §1 · p. 3, §6 · p. 27

  • Results

    At R=3/10, DQI’s limiting expected score αQ≈0.8571 exceeds the classical benchmark αC=0.65; sampled-oracle improvements over αC with constant probability require superpolynomial classical queries.

    Source: §1.1 · p. 5, §6 · p. 27

  • Takeaways & Limitations

    The result establishes an unconditional approximation separation for DQI relative to an oracle, against computationally unbounded classical algorithms.

    Source: §6 · p. 27

    The achievable envelope is not an upper bound on arbitrary quantum algorithms, and exact score one is obtained only for rates R>1/2.

    Source: §5 · p. 26

Abstract

from arXiv · show

Decoded quantum interferometry (DQI) is a novel paradigm for tackling approximate optimization problems on quantum computers. This framework comes with strong performance guarantees and exploits a well-established duality between optimization and coding theory. A central question, however, is whether DQI can actually provably outperform all polynomial-time classical algorithms. In this work, we establish such an advantage in an oracle setting: we consider an optimization task called folded optimal polynomial intersection (folded OPI), where the acceptance sets are chosen randomly and accessed through membership oracles. We establish a strict gap between the approximation ratio achievable by any polynomial-time classical algorithm and the approximation ratio achieved by the DQI algorithm. Our proof builds on Jordan et al.'s DQI framework for approximate optimization and extends the classical lower-bound method underlying Yamakawa and Zhandry's exact-search oracle separation to approximation. Building on recent developments by Sun and Wootters, Horinaga and Yamakawa, and Jo, we further show that a modified version of the DQI algorithm achieves a strictly higher score guarantee on typical sampled folded OPI instances. As a concrete example, for code rate $0.3$, DQI achieves expected scores of approximately $0.85$. In contrast, exceeding the classical threshold of $0.65$ by any fixed amount with constant probability on sampled instances requires super-polynomially many classical membership queries.

1 Introduction

The paper establishes a query-complexity separation for approximate optimization: on balanced folded OPI, DQI exceeds the classical threshold while constant-probability classical improvement requires super-polynomially many queries. It also gives stronger quantum guarantees on typical sampled instances using coherent fiber summation.

1 Introduction

  • DQI’s approximation guarantees raised whether it provably separates from arbitrary classical algorithms; this work answers affirmatively in a balanced folded-OPI membership-oracle model.The acceptance sets contain exactly half of each block alphabet and are accessed through separate block-membership oracles.Source: §1 · p. 3, §1.1 · p. 4

1.1 Main result

  • At R=0.3, DQI achieves αQ≈0.8571 versus Prange’s αC=0.65; beating αC by any fixed amount with constant probability requires super-polynomially many classical queries.The DQI guarantee holds on every promised instance, while the classical lower bound applies to sampled instances, even with unlimited computation between queries.Source: §1.1 · pp. 4–5, Figure 2 · p. 6
  • Complete list decoding plus coherent fiber summation beats DQI’s score envelope on typical sampled instances; a separate construction achieves exact search for R>1/2.For fixed rate and threshold, the decoder returns lists of constant size, allowing retained errors with the same syndrome to be combined with polynomial overhead; these stronger guarantees are typical-instance rather than worst-case results.Source: §1.1 · p. 5

1.2 Proof ideas

  • The separation combines folded-code DQI and Prange’s benchmark with a Yamakawa–Zhandry lower-bound extension using list recovery and conditional binomial tails.The DQI score follows from conventional Reed–Solomon unique decoding below half the unfolded dual code’s minimum distance; Prange interpolates through selected accepted blocks, with remaining blocks accepting independently with probability one half.Source: §1.2 · pp. 6–7

1.3 Related work

  • Jordan et al. [Jor+25] supplied a folded-DQI construction without an explicit score guarantee, while Yamakawa and Zhandry treated exact search; scalar OPI hardness remains open.Prior beyond-DQI work includes constructive worst-case improvements by Horinaga and Yamakawa [HY26] and Jo [Jo26], which use list decoding.Source: §1 · p. 3, §1.3 · pp. 7–8

1.4 Organization

  • The paper defines the problem and balanced folded Reed–Solomon family, proves the separation, presents stronger quantum guarantees, and places technical analyses in appendices.Appendix B transfers the classical query lower bound to approximation, while Appendix C treats typical-oracle guarantees and exact search.Source: §1.4 · p. 8

2 Preliminaries

The preliminaries establish the notation and coding framework for folded optimization, define folded OPI as polynomial evaluation with block-level acceptance, and specify the membership-oracle interface used below.

2.1 Notation

  • The notation fixes a prime-power field F_q, index sets [L], and indicator functions for statements.The all-zero and all-one vectors are denoted 0 and 1, with dimensions determined by context.Source: §2.1 · p. 9

2.2 Codes and folding

  • Folding groups code coordinates into blocks without changing the code’s dimension or rate, and acceptance is counted per whole block.The framework also distinguishes scalar from block distances and decoding, with error measures specified in scalar coordinates or folded blocks.Source: §2.2 · pp. 9–10

2.3 Optimization problems and oracle access

  • Folded OPI maximizes the fraction of blocks whose joint tuple of polynomial evaluations lies in its acceptance set.A degree-less-than-K polynomial is represented by its folded evaluation word; each accepted block contributes one unit, and an acceptance set may impose arbitrary joint conditions on the tuple.Source: §2.3 · pp. 12–13

2.4 Acceptance sets and membership-oracle access

  • Each membership query tests one complete block symbol in one classically selected oracle, even though symbol and answer registers may be in superposition.The encoder and block alphabet are explicit and oracle-independent; the interface provides no coherent block-index register or unit-cost multiplexed oracle.Source: §2.4 · p. 13

3 Statement of the concrete separation

For balanced folded OPI with randomly sampled acceptance sets accessed by membership oracles, the paper proves that DQI’s achievable score strictly exceeds the polynomial-query classical benchmark. The separation also holds for multiplicative approximation, with a classical query lower bound above that benchmark.

3.1 The instance family and oracle model

  • Balanced folded OPI uses folded Reed–Solomon polynomial evaluations as block symbols, with each membership-oracle acceptance set containing exactly half the alphabet; a polynomial’s score is its accepted-block fraction.The model uses admissible parameter choices, and its score counts blocks whose evaluation symbols belong to their acceptance sets.Source: §3 · p. 13, §3.1 · p. 14, Figure 3 · p. 15

3.2 Concrete separation theorem

  • Prange’s information-set algorithm uses O(M) classical membership queries and achieves scores converging in probability to αC(R) on sampled instances.The convergence is over the sampled instance and the algorithm’s randomness.Source: §3.2 · p. 16
  • For every fixed rate R, DQI’s expected-score guarantee αQ(R) strictly exceeds the classical benchmark αC(R), while classical algorithms need exponentially many queries to beat it by any fixed amount with constant probability.The classical lower bound applies to algorithms making at most exp(θR,η M/log M) queries under the sampled-oracle distribution.Source: §3.2 · p. 16
  • For rational R∈(0,1) and rational r with αC(R)<r<αQ(R), DQI uses O_{R,r}(M) queries and achieves ratio at least r with probability ≥2/3 on every promised oracle; the classical score-query lower bound transfers to approximation.Under the sampled-oracle distribution, OPT=1 except with doubly exponentially small probability; when OPT=1, approximation ratio and score coincide.Source: §3.2 · pp. 16–17

4 Proof of the concrete separation

The proof establishes a separation for folded OPI: DQI reaches its limiting expected score, while classical algorithms need super-polynomially many queries to beat their score threshold by a fixed amount with high probability.

4 Proof of the concrete separation

  • DQI’s limiting expected score is αQ(R), while beating the classical threshold αC(R) by any fixed amount with high probability requires super-polynomially many classical queries.The classical lower bound is proved for folded Reed–Solomon codes using list-recoverability and adaptive-query analysis.Source: §4 · p. 17, §4.3 · p. 21, §4.2 · p. 21

4.1 Part (i): quantum guarantee

  • For balanced folded predicates, the semicircle law extends to DQI, and efficient coherent decoding makes the folded Reed–Solomon algorithm efficient with at most M quantum membership queries.The construction implements conventional generalized Reed–Solomon unique decoding coherently and achieves the guarantee uniformly over balanced instances.Source: §4.1 · pp. 17, 19

4.2 Part (ii): Prange’s algorithm

  • Prange’s algorithm fits J≈RM blocks and achieves score converging in probability to (1+R)/2 = αC(R) on sampled instances.It uses at most 4M membership queries; untouched blocks accept independently with probability 1/2 after successful target search.Source: §4.2 · pp. 20–21

4.3 Part (iii): classical query lower bound

  • For folded Reed–Solomon codes, the classical query lower bound combines list-recoverability bounds on candidate codewords with a binomial-tail bound on their scores.The analysis assumes the query budget is negligible compared with the alphabet size; prior answers then raise an unqueried symbol’s acceptance probability by only o(1) above 1/2.Source: §4.3 · p. 21

5 Stronger quantum guarantees on typical oracles

Complete list decoding of the folded dual and coherent fiber summation strengthen DQI’s guarantees on typical balanced sampled-oracle instances. The algorithms achieve every score threshold below α_fib(R), and for R > 1/2 they also achieve exact score one.

Stronger quantum guarantees

  • Complete list decoding and Jo’s coherent fiber summation [Jo26] combine compatible Fourier-label amplitudes, while concentration ensures constant-probability success despite possible cancellation.For fixed rational 0 < μ ≤ 1/2 with μ < R, conditioned on success the output has limiting expected score α_sc(μ); the guarantees hold outside a doubly exponentially small set of instances.Source: §5 · pp. 25–26
  • Guruswami’s folded Reed–Solomon list decoder [Gur11] and Chen and Zhang’s list-size bound [CZ25] yield a polynomial-time, constant-size decoder for every fixed rational cutoff 0 < μ < R.The bound holds for sufficiently large M, and the list-size constant may depend on the gap R − μ.Source: §5 · p. 25
  • For every fixed rational β < α_fib(R), a quantum algorithm uses O_R,β(M) queries and returns score at least β with probability ≥2/3 on typical sampled instances.The guarantee holds for all sufficiently large admissible M, except on a set of instances of probability at most exp(-exp(Ω_R,β(M log M))).Source: §5 · p. 25
  • When R > 1/2, a quantum algorithm uses O_R(M) queries and returns a polynomial with score one and approximation ratio one with probability ≥2/3 on typical instances.The guarantee holds for all sufficiently large admissible M outside a doubly exponentially small set of sampled instances; no exact-search claim is made at R = 1/2.Source: §5 · p. 26
  • For thresholds between α_C(R) and α_fib(R), linearly many quantum queries suffice on typical instances, while classical constant success requires exp(Ω_R,r(M/log M)) queries.On these typical instances, score and approximation ratio coincide because the optimum is one; for R > 1/2, exact search also crosses every such fixed threshold.Source: §5 · p. 27

6 Discussion

The paper establishes an oracle-based query-complexity separation for approximate optimization: DQI exceeds the classical benchmark for balanced folded OPI, and a list-decoding variant strengthens its guarantees.

6 Discussion

  • For every fixed rational rate R, DQI’s limiting expected score αQ(R) strictly exceeds Prange’s classical benchmark αC(R), while constant-probability improvement over that benchmark requires superpolynomially many classical queries in Theorem 1’s stated range.The quantum algorithm uses unique decoding of the dual code and at most M coherent membership queries; the classical lower bound also holds for fully adaptive algorithms with unlimited computation between queries.Source: §6 · p. 27
  • Complete list decoding of the folded dual, followed by coherent combination of labels sharing a syndrome, yields higher guarantees on typical sampled oracles and exact search above rate one half.The paper also establishes separations in both scores and approximation ratios (Corollary 1).Source: §6 · p. 27
  • The contribution is an unconditional approximation separation relative to an oracle against computationally unbounded classical algorithms, addressing an open question raised in Refs. [Jor+25] [Mar+26].The authors identify the separation and matching classical query lower bound—not a new code family, decoding paradigm, or DQI mechanism—as the novelty.Source: §6 · p. 27
  • The proof combines primal list recoverability and a conditional binomial-tail bound on classical query scores with dual-code coherent decoding radius, which determines DQI’s score.A separation follows when the quantum score exceeds the classical threshold; finding codes with strong primal list recoverability and efficiently coherent-decodable duals is a future direction.Source: §6 · pp. 27–28
  • The oracle hides acceptance-set structure while both algorithms share the same membership interface; instantiating the oracle conditionally on computational assumptions remains open.The analysis assumes exact balance for simplicity, but the authors expect the proof architecture to extend to fixed rational acceptance densities using centered, normalized predicates and density-dependent score guarantees.Source: §6 · p. 28

AI-disclosure

The authors used AI systems to develop and check parts of the proof and manuscript, then verified and substantially revised the material and take full responsibility for the work.

AI-disclosure

  • GPT-5.6 Sol helped generate candidate proof strategies and preliminary drafts, while several AI systems assisted with checking and editing; the authors verified and revised the final arguments.The authors supplied the research question, mathematical setting, and intended scope, and state that they understand and can defend all parts of the work.Source: AI-disclosure · p. 28

A Detailed proof of the DQI guarantee

The proof extends the semicircle score law for scalar DQI to folded codes with balanced acceptance sets and applies the result to the folded Reed–Solomon family.

A Detailed proof of the DQI guarantee

  • For every fixed collection of balanced acceptance sets, the proof derives the folded-code semicircle score law missing from Jordan et al.’s scalar DQI analysis [Jor+25] and applies it to folded Reed–Solomon codes.Jordan et al. derive the scalar Jacobi-matrix formula and semicircle score law, and develop the folded-instance circuit and its oracle implementation [Jor+25].Source: A Detailed proof of the DQI guarantee · p. 31

A.1 The code and its syndrome decoder

The folded Reed–Solomon construction provides a polynomial-time syndrome decoder that recovers errors up to the chosen block-weight cutoff. Conventional Reed–Solomon unique decoding suffices, and the decoder has a reversible implementation with polynomial overhead.

A.1 The code and its syndrome decoder

  • A polynomial-time decoder Dec_M recovers every error e with block weight at most ℓ_M from syndrome B^T e, and admits reversible implementation with polynomial overhead.This is the folded Reed–Solomon decoding interface required by DQI.Source: §A.1 · p. 33
  • The cutoff ensures ℓ_M-block errors unfold to fewer than (K + 1)/2 scalar errors, so conventional Reed–Solomon unique decoding suffices without a folded-code decoder.The scalar dual code has minimum distance K + 1, while the folded error's scalar weight is at most hℓ_M.Source: §A.1 · p. 33
  • The syndrome decoder solves B^T r = σ, decodes r to a dual codeword, and subtracts it to recover the promised error; compute–copy–uncompute makes this operation coherent.Injectivity of B makes B^T surjective, so Gaussian elimination supplies r; the resulting total deterministic function is reversible with polynomial overhead.Source: §A.1 · pp. 33–34

A.2 The folded DQI score law

The folded DQI score law expresses expected score through a symmetric tridiagonal matrix and applies beyond Reed–Solomon encoders. It also yields explicit layer weights whose scores asymptotically match the optimum.

A.2 The folded DQI score law

  • The score calculation requires a full-column-rank encoder over a characteristic-two field, balanced local predicates, and a block-distance condition preventing collisions among retained labels.The argument uses no Reed–Solomon structure; the distance condition ensures injectivity of the syndrome map on labels of block weight at most ℓ.Source: §A.2 · p. 34
  • For any real unit vector of retained-layer weights, the expected score is given by the balanced folded-DQI score law, with the optimum obtained from its tridiagonal matrix.For fixed weights, the expectation is independent of the particular balanced acceptance sets.Source: §A.2 · p. 36
  • Equal-amplitude weights on a short window of the highest retained layers achieve scores converging to the optimum as M grows with ℓ/M → μ ∈ [0, 1/2].The window width is chosen as a power of two, allowing exact preparation of its layer-register superposition.Source: §A.2 · p. 38

A.3 Membership queries and the folded-DQI circuit · A.4 Completion of the quantum guarantee

The folded-DQI state can be prepared efficiently from membership-oracle access, with controlled approximation error. The proof completes the quantum guarantee for the folded Reed–Solomon family uniformly over balanced instances.

A.3 Membership queries and the folded-DQI circuit

  • The strict distance condition makes B^T injective on retained labels, enabling the coherent decoder to recover and erase those labels from their syndromes.The decoder recovers every retained label in the folded Reed–Solomon construction.Source: §A.3 · p. 38, §A.4 · p. 40
  • One membership query implements the local predicate phase, adapting Jordan et al. [Jor+25]’s phase-oracle step without assuming f_i(0) = 1.The implementation uses a constant number of additional gates.Source: §A.3 · p. 39
  • At most M membership queries and polynomially many gates prepare the weighted state within trace distance M^-c, with measured distributions and expected scores within M^-c of ideal uniformly over balanced sets.The guarantee holds for every fixed c > 0.Source: §A.3 · p. 39
  • The circuit prepares retained layers using weight-j masks, local QFTs and predicate phases; balance removes the zero frequency so the mask bits can be erased.The mask preparation and phase application use reversible operations, with one query per block for the phase step.Source: §A.3 · p. 39
  • Approximating each of the polynomially many synthesized rotations to error M^-c/L(M) yields total state-preparation error at most M^-c, preserved through decoding and measurement.The resulting measured distributions and expectations of scores in [0, 1] differ from their ideal values by at most the same amount, uniformly over the oracle.Source: §A.3 · p. 40

A.4 Completion of the quantum guarantee

  • The folded Reed–Solomon construction uses at most M queries and polynomially many gates, and the completed quantum guarantee holds uniformly over every balanced instance.The proof uses the cutoff ℓ_M, verifies the strict distance condition, and recovers every retained label.Source: §A.4 · p. 40

B Additional results for the DQI separation

Typical sampled folded OPI instances are perfectly satisfiable with overwhelming probability, enabling a ratio separation between verified DQI and polynomial-time classical algorithms. DQI’s quantum ratio guarantee itself holds for every promised oracle.

B Additional results for the DQI separation

  • Sampled oracles have a perfect solution with overwhelming probability, although perfect satisfiability is not part of the balance promise.Thus the typical-instance conclusion supports the wider ratio interval, while the quantum guarantee does not assume OPT = 1.Source: B Additional results for the DQI… · p. 42
  • For any fixed αC(R) < r < αQ(R), verified DQI reaches ratio at least r with probability at least 2/3, while classical success is exponentially small.DQI uses O_R,r(M) queries; the classical bound is over the sampled oracle and the algorithm’s random tape.Source: B Additional results for the DQI… · p. 42
  • Under the sampled-oracle distribution, Prange’s output ratio converges in probability to αC(R).Its score converges to αC(R), and score equals ratio on the event OPT = 1, whose probability tends to one.Source: B Additional results for the DQI… · p. 42
  • Without typical perfect satisfiability, a narrower ratio separation holds when αQ(R)^2 > αC(R), for αC(R)/αQ(R) < r < αQ(R).The condition makes this interval nonempty; typical perfect satisfiability yields the wider interval αC(R) < r < αQ(R) for every fixed R in (0, 1).Source: B Additional results for the DQI… · p. 43

C Proof of the stronger quantum guarantees on typical oracles · C.1 Quantum primitives for the stronger constructions · The success flag is observed with probability

The appendix develops quantum primitives for stronger guarantees on typical balanced folded-OPI oracles, including coherent summation over complete syndrome fibers adapted from Jo [Jo26]. It specifies how the success flag rejects unmatched labels and notes that success probability must be bounded separately for each input state.

C Proof of the stronger quantum guarantees on typical oracles

  • The appendix adapts Jo’s coherent summation over complete syndrome fibers [Jo26] to balanced folded-OPI instances and combines it with complete list decoding to prove stronger score thresholds and an exact-search guarantee.It also compares these constructions with the Yamakawa–Zhandry random-oracle model.Source: C Proof of the stronger quantum… · p. 43

C.1 Quantum primitives for the stronger constructions

  • The shared quantum interfaces use standard additive Fourier transforms with the syndrome map B^T.The appendix fixes a rational rate and the balanced folded family, whose acceptance sets are sampled independently and uniformly among half-size subsets.Source: §C.1 · p. 43, C Proof of the stronger quantum… · p. 43
  • Three membership queries prepare each block’s uniform accepted-symbol state cleanly, with polynomially many additional gates and constant-factor query overhead for coherent control.The preparation uses exact amplitude amplification without measurement or postselection; applying it to all M blocks takes O(M) queries.Source: §C.1 · pp. 44–45
  • A complete-list decoder and a measured success flag enable coherent syndrome-fiber summation: matching labels are erased reversibly, then Hadamards on the list index make amplitudes in each fiber add.The list size is assumed polynomially bounded, keeping the oracle-free circuit efficient.Source: §C.1 · p. 45, The success flag is observed with… · p. 46

The success flag is observed with probability

  • Inputs outside the enumerated set are rejected by the measured flag, and the successful branch is not assumed to have constant probability for arbitrary amplitudes because fiber amplitudes can cancel.The proof separately establishes a constant lower bound on fiber-success probability for each state used in the constructions.Source: The success flag is observed with… · pp. 45–46
  • For fixed τ in (0, R), a deterministic complete folded-dual fiber decoder enumerates every label in the specified block-weight interval with syndrome σ, in M^{O_{R−τ}(1)} time.The construction converts syndrome decoding to received-word decoding using a canonical preimage, then retains labels in the target interval; its list size is bounded by L_τ.Source: The success flag is observed with… · pp. 46–48

C.2 Part (i): coherent-fiber thresholds

At fixed cutoffs, coherent-fiber DQI achieves the filtered score guarantee on typical balanced sampled oracles, and its attainable thresholds extend to the rate-dependent envelope. The section also identifies when these thresholds exceed the classical query threshold and clarifies that a score guarantee below one is not an exact-search guarantee.

Coherent-fiber thresholds at a fixed cutoff

  • One attempt succeeds with probability Ω_{R−μ}(1), and conditioned on fiber success the output law is within total-variation distance M^−c of the ideal filtered distribution.The bounded success probability follows from the normalization concentration and the padding factor bounded independently of M.Source: §C.2 · pp. 49, 53
  • Complete syndrome lists have O_{R−μ}(1) entries, allowing coherent summation of amplitudes for retained labels that share a syndrome instead of unique decoding.Positive slack μ < R keeps the list bound constant in M.Source: §C.2 · pp. 49–50
  • At a fixed cutoff μ, the ideal filtered output has expected score α_sc(μ) + o(1) outside the exceptional set, and every fixed threshold below α_sc(μ) is attainable with bounded error.The expectation bound is uniform over oracles outside the exceptional set.Source: §C.2 · p. 53
  • When α_C(R) < β < α_sc(μ), Theorem 1(iii) supplies the corresponding distributional classical query lower bound.The quantum threshold is attained with O_{R,μ,β}(M) queries outside the same exceptional set.Source: §C.2 · p. 54

Resulting score envelope and scope

  • For R > 1/2, cutoff μ = 1/2 gives limiting expected score one, but this does not guarantee an output satisfying every block; exact search needs a separate argument.For R ≤ 1/2, rational cutoffs approach R from below, while μ = R is excluded by the decoder’s positive-slack requirement.Source: §C.2 · p. 54
  • For every fixed β < α_fib(R), DQI reaches score β with bounded error using O_{R,β}(M) queries and polynomially many gates outside an exp{-exp(Ω_{R,β}(M log M))} exceptional set.The cutoff is chosen with positive decoding slack μ < R and a positive score gap α_sc(μ) − β.Source: §C.2 · p. 54

C.3 Part (ii): exact search by truncated coherent fiber summation · C.4 Yamakawa–Zhandry exact search and its DQI interpretation

The exact-search construction uses truncated coherent fiber summation and verification to find perfect polynomials efficiently on promised oracles; the adjacent discussion relates Yamakawa and Zhandry’s target to a degree-M DQI filter, a connection also discussed by Jordan et al. [Jor+25].

C.3 Part (ii): exact search by truncated coherent fiber summation

  • The algorithm Fourier-transforms accepted-symbol states and uses truncated coherent fiber summation to form candidate polynomials and analyze perfect-output probability.The higher-degree-layer expression is only algebraic notation; no orthogonality or preparation claim for those layer states is needed.Source: §C.3 · pp. 55–57
  • For every balanced promised oracle, odd M makes the retained decoder cover exactly half the Fourier probability: b_M = 1/2.Source: §C.3 · p. 56
  • On almost all sampled oracles, one implemented attempt returns a perfect polynomial with probability at least 1/(16L_exact).The lower bound follows from b_M = 1/2 on good oracles and the implementation’s circuit-approximation guarantee.Source: §C.3 · p. 57
  • Every returned polynomial is perfect (approximation ratio 1), with worst-case query count O_R(M) and polynomial running time.Source: §C.3 · p. 58

C.4 Yamakawa–Zhandry exact search and its DQI interpretation

  • Yamakawa and Zhandry’s vector-output oracle returns all M bits at one symbol address, and it simulates separately callable block oracles with polynomial query overhead, and vice versa [YZ24].Source: §C.4 · p. 58
  • Yamakawa and Zhandry’s target is a degree-M exact-satisfaction DQI filter, uniformly superposing perfect codewords when they exist, a connection also discussed by Jordan et al. [Jor+25].Source: §C.4 · p. 59
  • Yamakawa and Zhandry’s independent random oracle bits produce fluctuating acceptance-set sizes, unlike our exactly balanced blocks, whose within-block dependence yields an exact Bin(M, 1/2) Fourier-weight law [YZ24].Source: §C.4 · p. 59

Related papers

Loading 2610.02145v2…