Which optimization problems could give decoded quantum interferometry an advantage?

Why DQI needs a screening rule before building decoders

DQI is usually applied to max-LINSAT: an instance is a matrix B over a finite field together with an accepted set for each row, and the goal is to satisfy as many rows as possible. The matrix B defines two dual linear codes — the optimizer code im B and the decoder code ker Bᵀ. DQI prepares a superposition over sparse error patterns, computes their syndromes under Bᵀ, and erases the patterns by running a classical decoder for ker Bᵀ coherently. The minimum distance of that decoder code caps how many errors can be corrected in the worst case, and with it the solution quality DQI can guarantee.

The problem is that every candidate has so far been studied on its own terms, with a code, a decoder and a classical comparison built for that one problem. That makes it hard to tell in advance which problems deserve a closer look. The paper's response is to turn the structure of DQI into explicit screening criteria, so that candidate problems can be filtered by code parameters, decoding guarantees and classical baselines before anyone builds a decoder or a classical attack.

Prange completion sets the classical bar

The classical baseline builds a word in im B directly. Suppose B has m rows and n linearly independent columns. A Prange completion picks n linearly independent rows — an information set — and an accepted value for each of them. Solving those n linear equations gives x, so the picked rows are satisfied by construction; computing Bx then fixes the remaining m − n coordinates. This step is the completion, and it needs no decoding.

If the information set is fixed in advance and the accepted sets are independent and random with density ρ, each remaining coordinate is satisfied with probability ρ. A single attempt therefore satisfies an expected fraction n/m + (1 − n/m)ρ. The optimizer-code rate n/m is the fraction Prange completion satisfies deliberately, and the rest are satisfied at the rate of a random guess. This is the benchmark the paper's margin cap is measured against, and it is a theoretical baseline rather than a description of the strongest classical algorithm available for any particular problem.

The margin cap and what OPI already achieves

For the standard objective of counting satisfied constraints, under worst-case Hamming decoding, the paper proves that DQI's asymptotic expected-quality margin over one Prange completion is at most κ(α) = √((α/2)(1 − α/2)) − α/2, where α is the optimizer-code rate. Maximizing over the rate gives the universal cap (√2 − 1)/2. Optimal polynomial intersection (OPI) attains the fixed-rate cap asymptotically as the field size grows and the accepted-set density tends to 1/2.

The consequence is a ceiling on the whole class: no candidate in this setting can exceed OPI's margin. OPI's known performance is therefore the best possible within the class covered by the Hamming-license analysis, and it serves as a benchmark for other candidate constructions rather than as one promising example among many. The cap is a statement about asymptotic expected quality under a specific decoding license, not a claim about wall-clock runtime or about every possible objective.

Real-valued objectives change which errors must be decoded

The paper extends the analysis from counting objectives to real-valued ones, in which every row uses the same function up to a shift over prime fields. Two properties of that function matter. Its moments give an exact formula for DQI's expected score at every length. Its Fourier support determines which error values the decoder has to correct — the error alphabet — so a decoder built for just those values is enough.

For the cosine objective the Fourier support is {±1}, and decoders for these signed errors can certify reach beyond half the minimum Hamming distance. This is the mechanism behind the paper's second candidate: a restricted error alphabet can admit a useful decoding guarantee even when the corresponding Hamming guarantee is unavailable. The objective therefore fixes both the solution quality and which errors the decoder must correct, which is why the paper treats the objective as a design variable rather than a fixed part of the problem statement.

Alternant max-agreement tests what a secret decoder is worth

Alternant max-agreement (AMA) asks for a word in a public linear code that lies in as many of the coordinate-wise accepted sets as possible. The instances are built from McEliece-type public keys: the public matrix is a scrambled parity-check matrix of an alternant code, obtained by restricting a generalized Reed–Solomon code over an extension field to codewords with entries in the base field. The secret key exposes the alternant structure, and since ker(Bᵀ) = ker(H_pub), the cryptosystem's secret decoding algorithm is precisely a decoder for the code DQI needs. Knowing the underlying Reed–Solomon description permits correction of up to ⌊r/2⌋ Hamming errors, where r is the number of parity rows.

The comparison is deliberately asymmetric: DQI gets the secret decoder, while the classical baseline receives only the public instance — the public matrix and the accepted sets. Against a finite-budget Prange-restart baseline the advantage is a theorem. Against classical searches that see only the public instance, the comparison turns in DQI's favor between m = 6000 and m = 14000, and at m = 14000 and 20000 the searches the authors tested stay below DQI even when given the key. With the key, the problem becomes OPI with trace-defined accepted sets, so AMA also asks how quantum and classical optimization use the same decoding representation. The hardness assumptions concern solvers that see only the public instance.

Multiplicative polynomial intersection gives both sides the decoder

Multiplicative polynomial intersection (MPI) is a cosine-optimization problem whose matrix entries are discrete logarithms of finite-field elements. Its public polynomial-lattice decoder uses rational reconstruction to recover signed errors, which are exactly the errors the cosine objective produces. That pairing supplies the restricted-error license the objective-dependent law requires, and with it a rigorous DQI quality guarantee — with quantum and classical solvers both receiving the decoding structure, unlike AMA.

Against the tested classical solvers, including lattice reduction, the comparison turns in DQI's favor between m = 1000 and m = 2000, and DQI's exact expected score is higher at m = 2000 and 6000. The paper is explicit that a valid DQI guarantee can coexist with a stronger classical algorithm: at the smallest tested lengths the lattice methods beat DQI. At the larger tested lengths DQI stays ahead, and the scaling study suggests the effort the tested attacks need to match it grows with length, although that extrapolates beyond the measured budgets.

Three strengths of evidence and one open question

For both constructions the evidence comes in three distinct strengths. The comparison with Prange restarts is a theorem. The comparisons with the authors' tested solvers are experiments, and the DQI values there are computed expectations rather than observed quantum-sampling averages. Broader classical hardness is stated as an assumption — Assumptions (A) and (B) for AMA at m = 40000, and Assumption (C) for MPI. Attack-cost calculations are estimates within their stated models, and costs derived from the scaling runs are extrapolations rather than bounds.

One question also remains open. An efficient classical encoder that reaches the existential line would remove the advantage, and none is known. Meeting the screening conditions therefore makes each problem a candidate, not a proven quantum advantage. The guarantees concern expected optimization quality under the stated decoding licenses, and turning a quality advantage into a runtime advantage would require accounting for state preparation, coherent decoding and the number of samples needed to obtain the target score.

The paper's own priority is the distinction between a decoding guarantee and an upper bound on decoding reach. Expander codes, for example, admit worst-case decoders for a positive fraction of errors, but for the expander and Tanner decoders examined in the search the established radii lie below the critical threshold, so they do not certify an advantage. Because those radii come from specific decoders rather than from distance bounds, they exclude neither better decoders for the same codes nor sparse codes as a class. That is the judgment worth carrying away: a candidate is excluded only relative to a named decoder and a named baseline, and the violated condition shows which feature of the candidate must change.

Sources used in this answer