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.02145v1quant-phcs.CCcs.DS

TL;DR

Whether DQI’s approximation guarantees yield a provable separation from arbitrary classical algorithms remains an open question. The paper constructs balanced folded Reed–Solomon OPI instances and combines DQI with a classical query lower bound adapted from exact search to approximation. At R = 3/10, αQ(3/10) ≈ 0.8571 versus αC(3/10) = 0.65; under the sampled-oracle distribution, fixed improvements over αC(𝑅) require superpolynomially many classical queries with constant probability within Theorem 1’s stated range.

  • Problem

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

    Source: §1 · p. 3

  • Method

    The paper constructs balanced folded Reed–Solomon OPI instances and combines DQI with a classical query lower bound adapted from exact search to approximation.

    Source: §1 · p. 3

  • Results

    At R = 3/10, αQ(3/10) ≈ 0.8571 versus αC(3/10) = 0.65; under the sampled-oracle distribution, fixed improvements over αC(𝑅) require superpolynomially many classical queries with constant probability within Theorem 1’s stated range.

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

  • Takeaways & Limitations

    The results establish an unconditional approximation separation for DQI relative to an oracle and show that stronger guarantees are attainable on typical sampled oracles.

    Source: §6 · p. 27

    The separation is established for a balanced folded-OPI membership-oracle family whose acceptance sets each contain half of the block alphabet.

    Source: §1.1 · p. 4

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 larger gap on the folded OPI problem, yielding an even stronger quantum separation. As a concrete example, for code rate $0.3$, DQI and the modified algorithm achieve expected scores of approximately $0.85$ and $0.95$, respectively. 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 addresses whether DQI can provably outperform arbitrary classical algorithms, establishing an approximation separation for folded OPI in a membership-oracle model. It also develops stronger typical-instance quantum guarantees and outlines the proof strategy and related work.

1.1 Main result

  • At rate R = 3/10, the classical threshold is 0.65 and DQI’s threshold is approximately 0.8571; the DQI guarantee holds on every promised instance.The family uses balanced acceptance sets, each containing half of the block alphabet.Source: §1.1 · pp. 4–5
  • For typical sampled instances, complete list decoding with coherent fiber summation gives stronger score guarantees, and a separate construction achieves exact search when R > 1/2.The score thresholds below αfib hold on a 1 − o(1) fraction of sampled instances; exact search uses linearly many membership queries.Source: §1.1 · p. 5

1.3 Related work

  • The work’s main novelty is the rigorous separation in a shared membership-oracle setting, rather than a new code family, decoding paradigm, or DQI mechanism.The paper relates this result to conditional approximation separations, other oracle separations, and recent work extending DQI beyond unique decoding.Source: §1.2 · p. 6, §1.3 · pp. 7–8

1.2 Proof ideas

  • For folded Reed–Solomon codes, conventional unique decoding below half the unfolded dual code’s minimum distance yields the DQI score guarantee uniformly over promised instances.The DQI framework turns coherent decoding of the dual code into optimization over the primal code.Source: §1.2 · p. 6
  • Prange’s block strategy interpolates a polynomial through selected accepted symbols, while each remaining independent half-size acceptance set accepts with probability one half.This establishes the classical benchmark used in the separation.Source: §1.2 · p. 7
  • The proof adapts Yamakawa and Zhandry’s exact-search lower-bound argument to approximation using a conditional binomial-tail estimate and a union bound over list-recovery candidates.The tail bound controls the chance that a candidate is accepted on enough unqueried blocks to exceed the score threshold.Source: §1 · p. 3, §1.2 · p. 7

1.4 Organization

  • The paper defines the problem and code family, proves the separation, establishes stronger typical-oracle guarantees, and concludes with discussion.Appendices provide the score analysis and implementation, ratio-separation argument, and stronger typical-instance constructions.Source: §1.4 · p. 8

2 Preliminaries

Section 2 sets notation and recasts polynomial optimization over folded linear-code blocks, with acceptance tested through membership oracles.

2.2 Codes and folding

  • Unique decoding uses a radius strictly below half the relevant minimum distance; rescaling lets the generalized Reed–Solomon dual be decoded as ordinary Reed–Solomon while preserving error support.Source: §2.2 · pp. 10–11
  • Folding groups scalar coordinates into h-tuples without changing a code’s dimension or rate.Source: §2.2 · pp. 9–10

2.3 Optimization problems and oracle access

  • Folded max-LINSAT optimizes accepted blocks over a linear code, while folded OPI specializes the encoder to low-degree polynomial evaluations tested jointly by block.Source: §2.3 · pp. 11–13

2.4 Acceptance sets and membership-oracle access

  • For even alphabets, balanced acceptance sets contain exactly half the symbols; the separation uses separately callable fixed-block membership oracles.Source: §2.4 · p. 13

3 Statement of the concrete separation

The section specifies a balanced folded Reed–Solomon oracle family and proves a rate-by-rate separation between DQI and classical algorithms. It also gives a verified approximation-ratio form of the gap.

3.1 The instance family and oracle model

  • The explicit folded Reed–Solomon family has M blocks, each accepting exactly half of its block alphabet.Source: §3.1 · p. 14

3.2 Concrete separation theorem

  • Prange’s randomized polynomial-time information-set algorithm uses O(M) membership queries and has approximation ratio converging in probability to alphaC(R).Source: §3.2 · pp. 16–17
  • The classical lower-bound comparison allows unlimited computation and fixed finite advice, while restricting algorithms to an exponential-in-M/log M query budget under the sampled-oracle distribution.Source: §3.2 · pp. 15–16
  • For every fixed rate R in (0, 1), DQI’s expected score alphaQ(R) strictly exceeds the classical benchmark alphaC(R) in the sampled-oracle setting.Source: §3.2 · pp. 14, 16
  • On sampled instances, OPT equals 1 except with doubly exponentially small probability, allowing the classical score lower bound to transfer to approximation ratio.Source: §3.2 · pp. 16–17
  • For rational r between alphaC(R) and alphaQ(R), DQI achieves ratio at least r with probability at least 2/3 on every promised oracle, using quantum polynomial time and O(M) queries.Source: §3.2 · p. 17

4 Proof of the concrete separation

The proof combines a uniform DQI guarantee, a classical algorithm attaining the threshold, and a query lower bound above it. The arguments use folded Reed–Solomon codes and balanced block-membership oracles.

4.1 Part (i): quantum guarantee

  • DQI attains limiting expected score αQ(R) uniformly over promised instances, using one quantum query to each block-membership oracle.The folded Reed–Solomon decoder is implemented efficiently and coherently using conventional unique decoding.Source: §4 · p. 17, §4.1 · p. 19

4 Proof of the concrete separation

  • The proof establishes the separation by extending the folded-predicate semicircle guarantee, analyzing Prange’s threshold, and bounding classical success above that threshold.The lower bound assumes the code is fixed independently of the oracle and the number of queries is small compared with the alphabet size.Source: §4 · p. 17, §4.1 · p. 17, §4.3 · p. 21

4.2 Part (ii): Prange’s algorithm

  • Prange’s algorithm uses at most 4M membership queries and its score converges in probability to αC(R) = (1 + R)/2.It fits J selected blocks and the untouched blocks accept independently with probability 1/2.Source: §4.2 · pp. 20–21

4.3 Part (iii): classical query lower bound

  • Exceeding αC(R) by any fixed amount with constant probability requires super-polynomially many classical queries under the sampled-oracle distribution.The lower-bound argument combines a list-recoverability bound with a tail bound on the probability that candidate codewords exceed the target score.Source: §4.3 · pp. 21, 23, 24

5 Stronger quantum guarantees on typical oracles

The paper strengthens the quantum guarantees by combining complete list decoding of the folded dual with coherent fiber summation. This yields higher score thresholds on typical sampled instances and, for rates above one half, an exact-search guarantee.

5 Stronger quantum guarantees on typical oracles

  • Complete list decoding finds retained labels in each syndrome fiber, and coherent fiber summation combines their amplitudes before the final Fourier transform.The list size is constant for fixed cutoff 0 < μ < R, making the decoder polynomial-time; amplitudes within a fiber may otherwise cancel.Source: §5 · p. 25
  • For R > 1/2, a separate quantum algorithm finds a polynomial satisfying every block, achieving approximation ratio one on typical sampled instances.The exact-search claim does not extend to R = 1/2.Source: §5 · p. 26
  • The comparison with Yamakawa and Zhandry concerns decoding ingredients, not a direct improvement of their oracle separation.Their construction uses an i.i.d. vector-output random oracle, whereas this work uses separately callable one-bit predicates subject to exact balance.Source: §5 · pp. 26–27
  • Coherent fiber summation raises the achievable score envelope from αQ(R) to the strictly larger αfib(R) on typical sampled instances.For each fixed threshold below αfib(R), a polynomial-time algorithm uses linearly many queries and succeeds with probability at least 2/3 on all but a doubly exponentially small fraction of instances.Source: §5 · pp. 25, 27

6 Discussion

For the balanced folded-OPI family, DQI achieves a strictly higher limiting expected score than Prange’s classical benchmark, while surpassing that benchmark by any fixed amount with constant probability requires superpolynomially many classical queries in the stated range. The separation rests on complementary primal list-recoverability and dual coherent-decoding properties, and the result is relative to an oracle.

6 Discussion

  • DQI achieves a strictly higher limiting expected score than Prange’s benchmark αC(R) at every fixed rational rate R.Under the sampled-oracle distribution, any fixed improvement over αC(R) with constant probability requires superpolynomially many classical queries in the range of Theorem 1, even with unlimited computation between queries.Source: §6 · p. 27
  • The result is an unconditional approximation separation relative to an oracle, not a new coding-theoretic family, decoding paradigm, or DQI mechanism.The oracle answers membership in acceptance sets; instantiating a similar result conditionally on computational assumptions is left open, while exact balance is not expected to be essential.Source: §6 · pp. 27–28
  • The proof pairs primal list recoverability, which limits codewords exposed by classical queries, with dual coherent-decoding radius, which determines the quantum score.A separation follows when the quantum score exceeds the classical threshold; finding other codes with both properties is identified as future work.Source: §6 · pp. 27–28

AI-disclosure

The authors used language models during proof development and manuscript preparation, then verified and revised the resulting material. They state that they understand and take responsibility for the final arguments.

AI-disclosure

  • The authors supplied the research question, mathematical setting, and intended scope before iteratively discussing candidate proof strategies with GPT-5.6 Sol.The central proof strategy ultimately used in the manuscript emerged through that exchange.Source: AI-disclosure · p. 28
  • The authors also used GPT-5.6 Sol, GPT-6 Astra, and Claude Opus 5.5 to check calculations and proof consistency and assist with exposition and restructuring.Source: AI-disclosure · p. 28
  • The authors verified the mathematical claims, corrected and substantially revised model-generated material, and take full responsibility for the final arguments.They 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 balanced DQI score analysis to folded codes and constructs the coherent syndrome decoder required for the folded Reed–Solomon family. Its decoder reduces promised block-weight errors to conventional unique decoding of the unfolded dual code.

A Detailed proof of the DQI guarantee

  • The proof extends the balanced DQI score law to folded codes and applies it to the folded Reed–Solomon family.The extension holds for every fixed collection of balanced acceptance sets.Source: A Detailed proof of the DQI guarantee · p. 31

A.1 The code and its syndrome decoder

  • The resulting syndrome decoder is polynomial-time and has a reversible implementation with polynomial overhead.It returns the promised error whenever its block weight is at most ℓ_M.Source: §A.1 · pp. 33–34
  • For an error supported on at most ℓ_M blocks, unfolding gives at most hℓ_M scalar errors, so unique decoding suffices when hℓ_M < (K+1)/2.The folded block-weight cutoff is therefore handled by conventional Reed–Solomon decoding; no dedicated folded-code unique decoder is needed.Source: §A.1 · pp. 32–33
  • To decode a syndrome, the construction finds a word with that syndrome, decodes it to the corresponding dual codeword, and subtracts to recover the error.The syndrome map is B^T; the proof uses Gaussian elimination to find a preimage and the unfolded dual-code decoder to recover the promised error.Source: §A.1 · pp. 33–34

A.2 The folded DQI score law

The folded balanced score analysis represents DQI’s retained Fourier layers through a tridiagonal score matrix. It identifies the optimal expected score and its asymptotic limit, with the score calculation independent of the particular balanced acceptance sets.

A.2 The folded DQI score law

  • The folded layer analysis adapts the scalar DQI calculation, with dual block distance preventing collisions among retained labels.The score calculation does not require Reed–Solomon structure.Source: §A.2 · pp. 34–35
  • The degree-j layer polynomials form a basis for filters of degree at most ℓ, allowing optimization over layer weights to represent polynomial filters.The filter polynomial is evaluated at the signed objective.Source: §A.2 · pp. 36, 38
  • The optimal expected score over retained layers is characterized by the largest eigenvalue of a symmetric tridiagonal matrix.For any fixed layer-weight vector, the expected score is independent of the particular balanced acceptance sets.Source: §A.2 · p. 36
  • A one-block shift couples only layers of equal or adjacent weight, yielding the tridiagonal score structure.Balance makes the nonconstant same-layer contribution vanish; adjacent layers have the calculated matrix element.Source: §A.2 · p. 37
  • When ℓ/M tends to μ in [0, 1/2], the optimal expected score and the explicit DQI construction’s score converge to the same limit.The convergence is uniform over balanced acceptance sets.Source: §A.2 · p. 38

A.3 Membership queries and the folded-DQI circuit

The folded-DQI circuit implements its local predicate phases with membership queries and prepares the measured state using polynomially many gates. With at most M queries, the resulting score guarantee holds uniformly over balanced instances.

A.3 Membership queries and the folded-DQI circuit

  • One membership query per block implements the local predicate phase without assuming f_i(0)=1.The construction adapts the local Fourier-gate implementation to membership-oracle access.Source: §A.3 · p. 39
  • At most M membership queries and polynomially many gates suffice to prepare the folded-DQI state with score error at most M^-c, uniformly over balanced acceptance sets.The implementation compiles the circuit to trace-distance error at most M^-c, which bounds the difference in expected score by the same amount.Source: §A.3 · pp. 39–40

A.4 Completion of the quantum guarantee

  • The cutoff and decoder conditions yield the claimed DQI guarantee uniformly over every balanced instance.The completion uses at most M queries and polynomially many gates.Source: §A.4 · p. 40

B Additional results for the DQI separation

This appendix establishes that sampled balanced instances typically have perfect solutions, allowing a classical score-query lower bound to transfer to approximation ratios. It also gives a ratio separation under a narrower condition that does not require typical perfect satisfiability.

B Additional results for the DQI separation

  • Typical sampled instances have perfect solutions with overwhelming probability, so their optimum is 1.The proof shows the normalized count of perfect codewords is close to its expectation; perfect satisfiability is not part of the balance promise.Source: B Additional results for the DQI… · pp. 41–42
  • For any fixed rate, verified DQI achieves ratios above the classical threshold and below αQ(R), while classical algorithms need super-polynomially many queries to exceed αC(R) by a fixed amount with constant probability.The sampled-instance transfer uses typical perfect satisfiability, under which score and approximation ratio agree.Source: B Additional results for the DQI… · p. 42
  • A ratio separation without typical perfect satisfiability is available when αQ(R)^2 > αC(R), giving a nonempty interval of achievable ratios.The quantum output has ratio at least r because OPT ≤ 1; the classical score lower bound applies when rαQ(R) exceeds αC(R).Source: B Additional results for the DQI… · p. 43

C Proof of the stronger quantum guarantees on typical oracles

The stronger constructions combine accepted-symbol state preparation with complete list decoding and coherent summation over syndrome fibers. This appendix develops the shared primitives used for stronger score thresholds and exact search.

C Proof of the stronger quantum guarantees on typical oracles

  • The appendix adapts coherent summation over complete syndrome fibers to the balanced folded-OPI family, alongside complete list decoding of the folded dual.These primitives support proofs of stronger score thresholds and an exact-search guarantee.Source: C Proof of the stronger quantum… · p. 43

C.1 Quantum primitives for the stronger constructions

  • A balanced block’s uniform accepted-symbol state can be prepared cleanly with three membership queries and polynomially many additional gates.The preparation also permits an additional coherent control with only constant-factor query overhead.Source: §C.1 · p. 44
  • Coherent syndrome-fiber summation makes amplitudes of retained labels with the same syndrome add on a shared syndrome state.A complete list decoder identifies labels in each fiber; a success flag rejects labels outside the enumerated set, and polynomial fiber size keeps the procedure efficient.Source: §C.1 · p. 45

The success flag is observed with probability

The section describes how complete list decoding and a measured success flag implement coherent aggregation over syndrome fibers. Success is not guaranteed for arbitrary input amplitudes because contributions within a fiber can cancel.

The success flag is observed with probability

  • The circuit records whether an input label matches the enumerated list and measures a success flag, rejecting nonmatching labels rather than silently removing them.For matching labels, Hadamards on the list index and acceptance of the all-zero index outcome make same-syndrome amplitudes add coherently.Source: The success flag is observed with… · p. 46
  • The fiber-summation circuit need not succeed with constant probability for arbitrary input amplitudes, because amplitudes within a fiber may cancel.The constructions therefore establish a constant lower bound on success separately for each state they use.Source: The success flag is observed with… · p. 46
  • A complete folded-dual decoder lists every label in a specified block-weight interval that matches a given syndrome, with polynomial running time and bounded list size.The decoder is obtained by adapting folded Reed–Solomon list decoding and retains labels in the required weight interval.Source: The success flag is observed with… · pp. 46–48

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

Coherent fiber summation yields quantum score thresholds up to the folded OPI score envelope, using fixed decoding slack. The method combines amplitudes for labels sharing a syndrome and verifies candidate scores.

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

  • The ideal filtered output has expected score αsc(μ) + o(1), and every fixed lower threshold is attained with bounded error outside the exceptional set.The expectation is over measurement of the ideal filter state; the o(1) is uniform over oracles outside that set.Source: §C.2 · p. 49
  • Coherent fiber summation combines amplitudes for retained labels sharing a syndrome, removing the error register on its success branch.Unlike unique decoding, this procedure must account for interference among labels in a fiber; their summed amplitudes can reinforce or cancel.Source: §C.2 · p. 50
  • One fiber-summation attempt succeeds with probability bounded below by a positive constant, and verification yields an overall O_R,μ,β(M) query bound.The success probability is bounded below because the padding length is constant in M for fixed parameters.Source: §C.2 · pp. 53–54
  • For 0 < R ≤ 1/2, the score envelope is R(1 − R); for 1/2 < R < 1, it is 1.The envelope is the supremum over supported cutoffs μ < R; for R ≤ 1/2, the endpoint μ = R is excluded because decoding requires positive slack.Source: §C.2 · p. 54
  • Every fixed threshold below αfib(R) is attained with bounded error using O_R,β(M) queries, outside an exceptional set of probability exp{−exp(Ω_R,β(M log M))}.The cutoff is chosen with positive decoding slack and a positive score gap above the requested threshold.Source: §C.2 · p. 54

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

For rates above one half, truncated coherent fiber summation gives a polynomial-query quantum algorithm that returns a perfect polynomial. The paper also interprets Yamakawa and Zhandry’s exact-search target as a degree-M DQI filter, while distinguishing their oracle distribution from the balanced one studied here.

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

  • The exact-search construction starts from accepted-symbol states, Fourier transforms them, and uses coherent fiber summation to produce candidate polynomials.The accepted-symbol registers begin in a product state, and the candidate is verified against every block.Source: §C.3 · pp. 55, 58
  • For odd M, the decoder retains exactly half of the Fourier probability for every balanced promised oracle.The Fourier block weight is Bin(M, 1/2); symmetry places half its mass at weights at most (M − 1)/2.Source: §C.3 · p. 56
  • For R > 1/2, the exact-search algorithm returns only perfect polynomials and uses O_R(M) queries with polynomial running time.Its retained labels use complete list decoding at relative block radius 1/2, which is available because R − 1/2 is positive.Source: §C.3 · pp. 55, 58

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

  • Yamakawa and Zhandry’s exact-search target is a DQI filter assigning equal amplitude to perfect candidates and zero amplitude to imperfect ones.When perfect solutions exist, the normalized filter state is their uniform superposition.Source: §C.4 · p. 59
  • The paper’s balanced acceptance sets differ from Yamakawa and Zhandry’s independent-bit oracle distribution, even though the interfaces simulate each other with polynomial query overhead.Exact binomial Fourier-weight behavior follows from the balance promise; interface simulation does not remove the distributional difference.Source: §C.4 · pp. 58–59

Related papers

Loading 2610.02145v1…