<figure><img src="image_1.png" /></figure>

HAL
open science

# OPI x Soft Decoders

André Chailloux

► To cite this version:

André Chailloux. OPI x Soft Decoders. 2025. hal-05468050

HAL Id: hal-05468050

https://inria.hal.science/hal-05468050v1

Preprint submitted on 20 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
OPI × Soft Decoders

André Chailloux

December 1, 2025

**Abstract**

In recent years, a particularly interesting line of research has focused on designing quantum algorithms for code and lattice problems inspired by Regev's reduction. The core idea is to use a decoder for a given code to find short codewords in its dual. For example, Jordan et al. [JSW+24] demonstrated how structured codes can be used in this framework to exhibit some quantum advantage. In particular, they showed how the classical decodability of Reed-Solomon codes can be leveraged to solve the Optimal Polynomial Intersection (OPI) problem quantumly. This approach was further improved by Chailloux and Tillich [CT25] using stronger soft decoders, though their analysis was restricted to a specific setting of OPI.

In this work, we reconcile these two approaches. We build on a recent formulation of the reduction by Chailloux and Hermouet [CH25] in the lattice-based setting, which we rewrite in the language of codes. With this reduction, we show that the results of Jordan et al. can be recovered under Bernoulli noise models, simplifying the analysis. This characterization then allows us to integrate the stronger soft decoders of Chailloux and Tillich into the OPI framework, yielding improved algorithms.

**Contents**

<table><tr><td>1 Introduction</td><td>2</td></tr><tr><td>2 Preliminaries</td><td>2</td></tr><tr><td>2.1 Basic notations and probability theory</td><td>2</td></tr><tr><td>2.2 Finite fields and Fourier transform.</td><td>3</td></tr><tr><td>2.3 Linear Codes</td><td>3</td></tr><tr><td>2.4 Code problems and OPI</td><td>4</td></tr><tr><td>2.5 The [CH25] Reduction Theorem and applications</td><td>5</td></tr><tr><td>3 Choice of error function</td><td>5</td></tr><tr><td>4 Applications</td><td>6</td></tr><tr><td>4.1 The case of binary codes</td><td>6</td></tr><tr><td>4.2 OPI</td><td>7</td></tr><tr><td>4.2.1 Using the Berlekamp-Welch decoder</td><td>8</td></tr><tr><td>4.2.2 Using the Guruswami-Sudan decoder</td><td>8</td></tr><tr><td>4.2.3 Using the Koetter-Vardy decoder in the case of the infinity norm</td><td>9</td></tr><tr><td>4.3 Graphical representation of our results</td><td>10</td></tr><tr><td>A Rewriting [CH25] for codes</td><td>14</td></tr><tr><td>A.1 Characterization of quantum algorithms for QDP</td><td>14</td></tr><tr><td>A.2 Description of the algorithm</td><td>15</td></tr><tr><td>A.3 First analysis and running time of the algorithm</td><td>15</td></tr><tr><td>A.4 Proof of main theorem</td><td>16</td></tr><tr><td>B Proof of Lemma 1</td><td>19</td></tr></table>
# 1 Introduction

Regev's reduction [Reg05] is one of the foundational results of lattice-based cryptography and is a quantum reduction between the Short Integer Solution (SIS) problem and the Learning With Errors (LWE) problem. The reduction is actually to a somewhat easier problem than LWE, where the errors are in quantum superposition. This has been leveraged in [BKSW18] where they showed relations between these problems and variants of the Dihedral Coset Problem. Then, Chen, Liu, and Zhandry [CLZ22] showed how to use these ideas not to obtain complexity reductions but rather to construct new quantum algorithms. They give an efficient quantum algorithm for $SIS_\infty$ in a somewhat contrived parameter regime. While this algorithm has been dequantized [KOW25], it paved the way for several new quantum algorithms. Notably, Yamakawa and Zhandry [YZ24] showed cases that exhibit a provable quantum advantage with this approach in the Random Oracle Model. There has been a series of recent works that studied the algorithmic aspects as well as extensions to coding-theoretic settings [DRT24, DFS24, CT24, JSW$^{+}$24, CHL$^{+}$25, CT25, BCT25, CH25, Hil25, GJ25, SLS$^{+}$25].

In particular, Jordan et al. [JSW$^{+}$24] studied structured codes in order to propose simple problems with a large quantum advantage. They looked at particular instances of LDPC codes and Reed–Solomon codes, and the resulting problems they solved can be phrased in terms of the MAX LINSAT problem (from LDPC codes) or the Optimal Polynomial Interpolation (OPI) problem (from Reed–Solomon codes). Chailloux and Tillich [CT25] presented a more general reduction for these algorithms that tolerates errors in the decoders. This allowed them to use more powerful decoders for Reed–Solomon codes. However, they could not fully integrate these decoders into the framework of [JSW$^{+}$24]. In [CH25], the authors extended the main reduction of [CT25] to make it both more general and easier to use in the context of Euclidean lattices.

In this work, we rephrase the reduction of [CH25] in terms of codes. In light of this new reduction, we reprove and extend some of the results of [JSW$^{+}$24] and [CT25] in an arguably simpler fashion and show how to use the more powerful decoders studied in [CT25] within the framework of [JSW$^{+}$24], thus combining the strengths of both approaches. We recover and extend the results of the Decoded Quantum Interferometry algorithm with explicit error functions $f$, and we also extend the results of [CT25] to more general instances of ICC. More precisely:

1. For MAX Linsat, we recover the same results as in [JSW$^{+}$24] with product error functions $f$.

2. In the case of OPI, we recover the results of Decoded Quantum Interferometry with product error functions $f$. With this new characterization, we can incorporate the stronger decoders of [CT25] in this framework, which gives improved results for the OPI problem.

All of these results are obtained in an arguably simpler framework which can easily encompass other choices of codes and decoding problems.

# 2 Preliminaries

## 2.1 Basic notations and probability theory

A probability function $p$ on a set $U$ is a function $p: U \to \mathbb{R}_+$ such that $\sum_{x \in U} p(x) = 1$. For a function $f: U \to \mathbb{C}$, we have $\|f\|_2 = \sqrt{\sum_{x \in U} |f(x)|^2}$. We will work in a finite field $\mathbb{F}_q$ for any $q$ that is a prime power. Lowercase bold letters $\mathbf{x}, \mathbf{y}$ denote (row) vectors with coefficients in $\mathbb{F}_q$, and uppercase bold letters $\mathbf{G}, \mathbf{H}$ denote matrices with coefficients in $\mathbb{F}_q$.

**Claim 1.** Let $X_1, \dots, X_n$ be independent Bernoulli random variables with $\Pr[X_i = 0] = 1-\tau$ and $\Pr[X_i = 1] = \tau$ for all $i$. Let $S_n = \sum_{i=1}^n X_i$. For any $\tilde{\tau} < \tau$,

$$ \Pr[S_n \le \tilde{\tau}n] \le 2e^{-2n(\tau-\tilde{\tau})^2}. $$
## 2.2 Finite fields and Fourier transform.

For $x = (x_i)_{i \in [1,n]} \in \mathbb{F}_q^n$ and $y = (y_i)_{i \in [1,n]} \in \mathbb{F}_q^n$, we define their inner product $x \cdot y = \sum_i x_i y_i$, where the sum and multiplication are over $\mathbb{F}_q$. We now give a brief overview of the characters of $\mathbb{F}_q$, following [CT25].

**Definition 1.** Let $q = p^s$ for a prime integer $p$ and an integer $s \ge 1$. The characters of $\mathbb{F}_q$ are the functions $\chi_y : \mathbb{F}_q \to \mathbb{C}$ indexed by elements $y \in \mathbb{F}_q$, defined as follows:

$$ \chi_y(x) \triangleq e^{\frac{2i\pi \operatorname{tr}(x \cdot y)}{p}}, \quad \text{with} $$

$$ \operatorname{tr}(a) \triangleq a + a^p + a^{p^2} + \dots + a^{p^{s-1}}. $$

where the product $x \cdot y$ corresponds to multiplication in $\mathbb{F}_q$. We extend the definition to vectors $x, y \in \mathbb{F}_q^n$ as follows:

$$ \chi_y(\mathbf{x}) \triangleq \prod_{i=1}^{n} \chi_{y_i}(x_i) = e^{\frac{2i\pi \operatorname{tr}(\mathbf{x} \cdot \mathbf{y})}{p}}. $$

Notice that inner product $x \cdot y$ is equal to the vector multiplication $xy^\top$. This means that for $x \in \mathbb{F}_q^k, y \in \mathbb{F}_q^n$ and $G \in \mathbb{F}_q^{k \times n}$, we have $xG \cdot y = x \cdot yG^\top$ hence $\chi_y(xG) = \chi_{yG^\top}(x)$. Characters have many desirable properties that we can use for our calculations.

**Proposition 1.** The characters $\chi_y : \mathbb{F}_q^n \to \mathbb{C}$ have the following properties:

1. (Group homomorphism). For all $y \in \mathbb{F}_q^n$, $\chi_y$ is a group homomorphism from $(\mathbb{F}_q^n, +)$ to $(\mathbb{C}, \cdot)$, meaning that for all $x, x' \in \mathbb{F}_q^n$, $\chi_y(x + x') = \chi_y(x) \cdot \chi_y(x')$.

2. (Symmetry). For all $x, y \in \mathbb{F}_q^n$, $\chi_y(x) = \chi_x(y)$.

3. (Orthogonality of characters). The characters are orthogonal functions: for all $x, x' \in \mathbb{F}_q^n$,

$$ \sum_{y \in \mathbb{F}_q^n} \chi_y(\mathbf{x}) \overline{\chi_y(\mathbf{x}')} = q^n \delta_{\mathbf{x}, \mathbf{x}'} \cdot \text{In particular, } \sum_{y \in \mathbb{F}_q^n} |\chi_y(\mathbf{0})|^2 = q^n \text{ and for all } \mathbf{x} \in \mathbb{F}_q^n \setminus \{\mathbf{0}\}, \\ \sum_{y \in \mathbb{F}_q^n} \chi_y(\mathbf{x}) = 0. $$

**Definition 2.** For a function $f : \mathbb{F}_q^n \to \mathbb{C}$, we define its Fourier transform as $\hat{f}(\mathbf{x}) = \frac{1}{\sqrt{q^n}} \sum_{\mathbf{y} \in \mathbb{F}_q^n} \chi_{\mathbf{x}}(\mathbf{y}) f(\mathbf{y})$.

**Claim 2** (Parseval's Identity). For any $f : \mathbb{F}_q^n \to \mathbb{C}$, we have $\|f\|_2 = \|\hat{f}\|_2$.

**Claim 3.** Let $C$ be a $q$-ary linear code. Then

$$ \sum_{c \in C} \chi_y(c) = \begin{cases} |C| & \text{if } y \in C^{\perp}, \\ 0 & \text{otherwise.} \end{cases} $$

## 2.3 Linear Codes

A $q$-ary linear code $C$ of dimension $k$ and length $n$ is characterized by a full-rank generating matrix $G \in \mathbb{F}_q^{k \times n}$ or equivalently by a full-rank parity-check matrix $H \in \mathbb{F}_q^{(n-k) \times n}$, and we write

$$ C = \{xG : x \in \mathbb{F}_q^k\} \quad \text{or} \quad C = \{y \in \mathbb{F}_q^n : Hy^\top = 0\}. $$

Each code $C$ has an associated dual code $C^\perp = \{y \in \mathbb{F}_q^n : \forall c \in C, y \cdot c = 0\}$. Any generating matrix of $C$ is a parity-check matrix of $C^\perp$. For a string $u \in \mathbb{F}_q^{n-k}$ called syndrome, we define the coset $C_u = \{y \in \mathbb{F}_q^n : Hy^\top = u^\top\}$. For $u \in \mathbb{F}_q^k$, called a dual syndrome, we also have the dual coset $C_u^\perp = \{y \in \mathbb{F}_q^n : Gy^\top = u^\top\}$. We will be particularly interested in full-support Reed–Solomon codes. The full-support Reed–Solomon code of length $n$ and dimension $k$ is the code

$$ \mathrm{RS}_k = \{(P(\alpha_1), \dots, P(\alpha_q)) : P \in \mathbb{F}_q[X], \deg(P) < k\}, $$

where $\{\alpha_1, \dots, \alpha_q\} = \mathbb{F}_q$. Note that for these codes we have $n = q$. An important property of the full-support Reed–Solomon code is that its dual is also a full-support Reed–Solomon code.

**Claim 4.** $RS_k^\perp = RS_{n-k}^\perp$.
## 2.4 Code problems and OPI

We will be interested in the following code problems.

**Problem 1 (Syndrome Decoding Problem SD($C$, $p$)).**

**Given:** ($C$, $c + e$, $p$) where $C$ is a $q$-ary linear code of dimension $k$ and length $n$ for which we have a description (e.g., via a generating matrix $G$), $c \leftarrow C$, and $e$ is distributed according to $p: \mathbb{F}_q^n \to \mathbb{R}_+$.

**Goal:** Find $c$.

This problem has been extended to the case of codes in [CT24] where the errors are considered in quantum superposition,

**Problem 2 (Quantum Decoding Problem QDP($C$, $f$)).**

**Given:** ($C$, $|\psi_c\rangle$, $f$) where $C$ is a $q$-ary linear code of dimension $k$ and length $n$ for which we have a description, $c \leftarrow C$, and $|\psi_c\rangle = \sum_{e \in \mathbb{F}_q^n} f(e)|c + e\rangle$ for a function $f: \mathbb{F}_q^n \to \mathbb{C}$ with $\|f\|_2 = 1$.

**Goal:** Find $c$.

Notice that QDP($C$, $f$) is easier than the SD($C$, $|f|^2$) problem, as one can just measure $|\psi_c\rangle$ in the computational basis in order to recover an instance of SD($C$, $|f|^2$).

**Problem 3 (Constrained Codeword Problem CC($C$, $T$)).**

**Given:** The description of a $q$-ary linear code $C$ of length $n$ and dimension $k$, and a set $T \subseteq \mathbb{F}_q^n$.

**Goal:** Find $y \in C \cap T$.

We will actually be more interested in the inhomogeneous variant of the above problem, where we want to find $y \in C_u \cap T$ for a randomly chosen dual syndrome $u$.

**Problem 4 (Inhomogeneous Constrained Codeword Problem ICC($C$, $T$)).**

**Given:** The description of a $q$-ary linear code $C$ of length $n$ and dimension $k$ as well as a parity-check matrix $H \in \mathbb{F}_q^{(n-k) \times n}$ of $C$, and a random syndrome $u \in \mathbb{F}_q^{n-k}$.

**Goal:** Find $y \in C_u \cap T$.

For this problem, we will quantify the success probability on average over the syndrome $u$.

**Definition 3.** Let $\mathcal{A}(C, T, u)$ be an algorithm that solves ICC($C$, $T$) for a fixed $u$, and let $p_u$ be the probability that it finds $y \in C_u \cap T$. We say that $\mathcal{A}$ solves ICC($C$, $T$) with probability $p$ if $E_{u \leftarrow \mathbb{F}_q^{n-k}}[p_u] = p$.

Finally, we present the Optimal Polynomial Interpolation problem.

**Problem 5 (Optimal Polynomial Interpolation Problem OPI($k$, $q$, $\{S_i\}_{i \in \mathbb{F}_q}$, $\tau$)).**

**Given:** Positive integers $k$, $q > k$ and subsets $S_i \subseteq \mathbb{F}_q$ for $i \in \mathbb{F}_q$, and a real number $\tau \in [0, 1]$. A random string $x = (x_i)_{i \in \mathbb{F}_q} \in \mathbb{F}_q^k$.

**Goal:** Find $P \in \mathbb{F}_q[X]$ with $\deg(P) < k$ such that $|\{i \in \mathbb{F}_q : P(i) + x_i \in S_i\}| \ge \tau q$.

One can remark that the OPI problem is a special instantiation of the ICC problem.

**Claim 5.** The OPI($k$, $q$, $\{S_i\}_{i \in \mathbb{F}_q}$, $\tau$) problem and the ICC($RS_k$, $T$) problem are equivalent, with

$$T = \{ (y_i)_{i \in \mathbb{F}_q^k} : |\{i : y_i \in S_i\}| \ge \tau q \}.$$

*Proof.* Fix $k$, $q$ and let $H_k \in \mathbb{F}_q^{q-k}$ be the parity matrix of $RS_k$. Assume we start from an OPI($k$, $q$, $\{S_i\}_{i \in \mathbb{F}_q}$, $\tau$) instance with random string $x$. Let $u = H_k x$ and run an algorithm for ICC($RS_k$, $T$) with

$$T = \{ (y_i)_{i \in \mathbb{F}_q^k} : |\{i : y_i \in S_i\}| \ge \tau q \}.$$

We obtain $y \in (RS_k)_u \cap T$. In particular, $H_k(y - x) = 0$ hence $y - x \in RS_k$. Let $y' = y - x \in RS_k$. We write $y' = (y'_i)_{i \in \mathbb{F}_q} = (P(i))_{i \in \mathbb{F}_q}$ for some polynomial $P \in \mathbb{F}_q[X]$ such that $\deg(P) < k$ which can be
easily recovered from $\mathbf{y}'$ using polynomial interpolation. This $P$ will be a solution to our OPI instance. Indeed, using $P(i) + x_i = y_i$, we have

$$|\{i \in \mathbb{F}_q : P(i) + x_i \in S_i\}| = |\{i \in \mathbb{F}_q : y_i \in S_i\}| \geq \tau q, \quad \text{since } \mathbf{y} \in T.$$

We now prove the other direction. Start from an ICC($RS_k, T$) instance with a choice of $\{S_i\}$ and $\tau$ which defines $T$ as above; and a random $\mathbf{u} \in \mathbb{F}_q^{n-k}$. Let $\mathbf{x} \in \mathbb{F}_q^n$ be a random element of $C_u$. This can be done using Gaussian Elimination after randomly permuting the lines. Run the OPI($k, q, \{S_i\}, \tau$) solver to obtain $P \in \mathbb{F}_q[X]$ with $\deg(P) < k$ such that $|\{i \in \mathbb{F}_q : P(i) + x_i \in S_i\}| \geq \tau q$. Let $\mathbf{y} = (y_i)_{i \in \mathbb{F}_q}$ with $y_i = P(i)$. Notice that $\mathbf{y} \in RS_k$. This implies $\mathbf{y} + \mathbf{x} \in C_u \cap T$ so we can output $\mathbf{x} + \mathbf{y}$ to obtain a solution of ICC($RS_k, T$). $\square$

## 2.5 The [CH25] Reduction Theorem and applications

In [CH25], the authors present a reduction from the ISIS problem to the $S$-$|LWE\rangle$ problem which can be lattice-based variants of the ICC problem and the QDP problem respectively. This theorem can be translated to the setting of codes as follows:

**Theorem 1.** Let $C$ be a $q$-ary linear code of dimension $k$ and length $n$ and let $\mathbf{G} \in \mathbb{F}_q^{k \times n}$ be a generating matrix of $C$. Let $T \subseteq \mathbb{F}_q^n$. Let $f: \mathbb{F}_q^n \to \mathbb{C}$ with $\|f\|_2 = 1$. Assume that

1. We have a quantum algorithm $\mathcal{A}_{QDP}$ that solves $QDP(C, f)$ in time $\text{Time}_{QDP}$ and succeeds with probability $P_{Dec}$.

2. The state $\sum_{e \in \mathbb{F}_q^n} f(e)|e\rangle$ is constructible in time $T_{Sampl}$.

3. $\sum_{\mathbf{y} \in T} |\hat{f}(\mathbf{y})|^2 = 1 - \eta$.

Then there exists a quantum algorithm that solves ICC($C^\perp, T$) with probability

$$P \geq P_{Dec}(1 - \eta) - 2\sqrt{\eta P_{Dec}(1 - P_{Dec})},$$

and runs in time

$$\text{Time} = O\left( \frac{1}{P_{Dec}} (\text{Time}_{QDP} + \text{Time}_{Sampl}) + \text{poly}(n, \log(q)) \right).$$

*Proof.* The proof of [CH25] can almost verbatim be translated by replacing the lattice-based concepts to the code-based concepts. The only difference is that we work on $\mathbb{F}_q$ while [CH25] worked on $\mathbb{Z}_q$ but this is a very minor difference and doesn't alter the proof. For completeness, we rewrite the proof of [CH25] in the code-based setting in Appendix A. $\square$

This theorem shows how to construct a quantum algorithm for ICC($C^\perp, T$) given an algorithm for $QDP(C, f)$ Here, the third item of our theorem allows us to study very simple product functions $f$, and we can handle distribution tails arising from these product error functions.

## 3 Choice of error function

Our goal is to construct functions for which we can apply Theorem 1. For the set $T$, we pick sets $\{S_i\}_{i \in \mathbb{F}_q}$ where each $S_i \subseteq \mathbb{F}_q$ as well as a threshold $\tilde{\tau} \in (0, 1)$. We consider the set

$$T = \{\mathbf{y} = (y_i)_{i \in [1, n]} : |\{i : y_i \in S_i\}| \geq \tilde{\tau} n\}.$$

The case $\tilde{\tau} = 1$ corresponds to [CT25], whereas arbitrary $\tilde{\tau}$ was studied in [JSW$^+$24].
**Proposition 2.** Let subsets $S_i \subseteq \mathbb{F}_q$ of a fixed same size for each $i \in \mathbb{F}_q$. Let $\rho = \frac{|S_i|}{q}$ which is independent of $i$. Let a threshold $\tilde{\tau} \in (0, 1)$ and $T_{\tilde{\tau}} = \{\mathbf{y} = (y_i)_{i \in [1,n]} : |\{i : y_i \in S_i\}| \ge \tilde{\tau}n\}$. Let $\tau = \tilde{\tau}+n^{-1/3} = \tilde{\tau}+o(1)$ and consider the functions $u_i : \mathbb{F}_q \to \mathbb{C}$ such that

$$ \hat{u}_i(\alpha) = \begin{cases} \sqrt{\frac{\tau}{|S_i|}} & \text{if } \alpha \in S_i \\ \sqrt{\frac{1-\tau}{q-|S_i|}} & \text{if } \alpha \notin S_i \end{cases} $$

Finally, let $f = \otimes_{i=1}^n u_i$. We have

$$ 1. \sum_{\mathbf{y} \in T_{\tilde{\tau}}} |\hat{f}(\mathbf{y})|^2 = 1 - \eta \text{ with } \eta = \text{negl}(n). $$

$$ 2. \forall i \in \mathbb{F}_q, |u_i(0)|^2 = \left(\sqrt{\tau\rho} + \sqrt{(1-\tau)(1-\rho)}\right)^2, \text{ where } \tau = \tilde{\tau} + o(1). $$

*Proof.* The relation $f = \otimes_{i=1}^n u_i$ implies $\hat{f} = \otimes_{i=1}^n \hat{u}_i$, which means we can write

$$ \sum_{\mathbf{y} \in \mathbb{F}_q^n} \hat{f}(\mathbf{y}) |\mathbf{y}\rangle = \bigotimes_{i \in \mathbb{F}_q} \left( \sum_{\alpha \in \mathbb{F}_q} \hat{u}_i(\alpha) |\alpha\rangle \right) = \bigotimes_{i \in \mathbb{F}_q} \left( \sum_{\alpha \in S_i} \sqrt{\frac{\tau}{|S_i|}} |\alpha\rangle + \sum_{\alpha \notin S_i} \sqrt{\frac{1-\tau}{q-|S_i|}} |\alpha\rangle \right). $$

From Hoeffding's inequality, we have

$$ \sum_{\mathbf{y} \in T} |\hat{f}(\mathbf{y})|^2 \ge 1 - e^{-2n(\tau - \tilde{\tau})^2} = 1 - \text{negl}(n). \quad (1) $$

For the second point, we use $u_i(\alpha) = \frac{1}{\sqrt{q}} \sum_{\beta \in \mathbb{F}_q} \chi_{-\alpha}(\beta) \hat{u}_i(\beta)$. In particular,

$$ \begin{aligned} |u_i(0)|^2 &= \frac{1}{q} \left| \sum_{\beta \in \mathbb{F}_q} \hat{u}_i(\beta) \right|^2 = \frac{1}{q} \left( \sum_{\beta \in S_i} \sqrt{\frac{\tau}{|S_i|}} + \sum_{\beta \notin S_i} \sqrt{\frac{1-\tau}{q-|S_i|}} \right)^2 \\ &= \frac{1}{q} \left( \sqrt{\tau|S_i|} + \sqrt{(1-\tau)(q-|S_i|)} \right)^2 \\ &= \left(\sqrt{\tau\rho} + \sqrt{(1-\tau)(1-\rho)}\right)^2 \end{aligned} $$

since $\rho = \frac{|S_i|}{q}$ for each $i \in \mathbb{F}_q$. $\square$

We suppose each $|S_i|$ has the same size as it is the standard setting and it is easier to assess the performance of decoders with this kind of error functions, but the above theorem can be easily generalized to the case where the $|S_i|$ do not have the same size.

# 4 Applications

## 4.1 The case of binary codes

We first apply our theorem to the binary setting

**Proposition 3.** Let $C$ be a binary linear code of length $n$. Assume there exists an efficient algorithm $A_{Dec}$ that can decode a $t$ fraction of errors with probability $P_{Dec}$. Then there exists a quantum algorithm that solves efficiently $\text{ICC}(C^\perp, T_{\tilde{\tau}})$ where

$$ T_{\tilde{\tau}} = \{\mathbf{y} \in \mathbb{F}_2^n : |\mathbf{y}| \le (1 - \tilde{\tau})n\} = \{\mathbf{y} = (y_i)_{i \in [1,n]} : |\{i : y_i \in S\}| \ge \tilde{\tau}n\}, \text{ for } S = \{0\} $$

where $\tilde{\tau} = \tau - n^{1/3} = \tau - o(1)$ and $\tau = \frac{1}{2} + \sqrt{t(1-t)} = \left(\sqrt{\frac{t}{2}} + \sqrt{\frac{1-t}{2}}\right)^2$. This quantum algorithm succeeds with probability $P_{Dec} - \text{negl}(n)$.
Proof. In this setting, saying that $\mathcal{A}_{Dec}$ solves a t-fraction of errors means it can solve $\text{SD}(\mathcal{C}, p^{\otimes n})$ with $p(0) = 1-t$ and $p(1) = t$. Fix $u: \mathbb{F}_2^n \to \mathbb{C}$ with $u(0) = \sqrt{1-t}$ and $u(1) = \sqrt{t}$. Let $f = u^{\otimes n}$. $\mathcal{A}_{Dec}$ solves $\text{SD}(\mathcal{C}, u^{\otimes n})$, hence $\text{QDP}(\mathcal{C}, f)$ with probability $P_{Dec}$. We can compute

$$ \begin{aligned} \hat{u}(0) &= \frac{1}{\sqrt{2}} (u(0) + u(1)) = \left( \sqrt{\frac{t}{2}} + \sqrt{\frac{1-t}{2}} \right) = \sqrt{\tau} \\ \hat{u}(1) &= \frac{1}{\sqrt{2}} (u(0) - u(1)) = \left( \sqrt{\frac{t}{2}} - \sqrt{\frac{1-t}{2}} \right) = \sqrt{1-\tau} \end{aligned} $$

We use Proposition 2, with $q = 2$ and each $S_i = \{0\}$ to obtain that

$$ \sum_{yv \in T_{\tau}} |\hat{f}(\mathbf{y})|^2 = 1 - \eta \text{ with } \eta = \text{negl}(n). $$

We can therefore conclude using Theorem 1 that there exists an efficient quantum algorithm for $\text{ICC}(\mathcal{C}^{\perp}, T_{\tau})$ that succeeds with probability $P_{Dec} - \text{negl}(n)$. $\square$

**Corollary 1** (Recovering results of [JSW+24]). Consider a code $\mathcal{C}$ for which we can decode on average a fraction $t = \frac{6350}{50000}$ of errors. Then, we can solve efficiently $\text{ICC}(\mathcal{C}^{\perp}, T)$ where

$$ T = \{ \mathbf{y} \in \mathbb{F}_2^n : |\mathbf{y}| \le (1 - \tilde{\tau})n \}, \text{ for } \tilde{\tau} \approx 0.833^1. $$

The $\text{ICC}(\mathcal{C}^{\perp}, T)$ solved in this corollary corresponds exactly to the Max XORSAT instance solved in [JSW+24], for the choice of LDPC code specified therein.

## 4.2 OPI

Now, we consider a prime $q$ and sets $S_i \subseteq \mathbb{F}_q$ of the same size for $i \in \mathbb{F}_q$. Let $\rho = \frac{|S_i|}{q}$. The idea is to work on full rank Reed-Solomon codes. We know from Claim 5 that solving $\text{ICC}(\text{RS}_k, T)$ for a well chosen $T$ is equivalent to solving an OPI problem. Recall also that for the case of full rank Reed-Solomon codes, the length of the code $n$ is equal to the alphabet size $q$ but we will still use the two variables for readability. We first recall the performance of Reed-Solomon decoders

**Proposition 4.** We consider the different decoders applied on $\text{RS}_{n-k}$, i.e. the full support Reed-Solomon codes of dimension $(n-k)$ and length $n$. Let $p$ be a probability function on $\mathbb{F}_q^n$ with $p = \otimes_{i=1}^n p_i$ such that $\forall i, p_i(0) = 1-t$.

* The Berlekamp-Welch algorithm solves $\text{SD}(\text{RS}_{n-k}, p)$, $wp$. at least $\frac{1}{\text{poly}(n)}$ for $\frac{k}{n} \ge 2t = 2(1-p_i(0))$.

* The Guruswami-Sudan algorithm solves $\text{SD}(\text{RS}_{n-k}, p)$, $wp$. at least $\frac{1}{\text{poly}(n)}$ for $\frac{k}{n} \ge 1 - (1-t)^2 = 1 - p_i^2(0)$.

*Proof.* The Berlekamp-Welch algorithm [Wel83] can solve the decoding problem on $\text{RS}_{n-k}$ as long as the number of errors is at most $t_0 = \lfloor \frac{k}{2} \rfloor$. If we take the error distribution $p$ where each $p_i(0) \ge 1 - \frac{k}{2n}$ then the number of errors will smaller than $t_0 \approx n(1-p_i(0))$ with constant probability. We can rewrite the inequality as $\frac{k}{n} \ge 2(1-p_i(0))$.

The Guruswami-Sudan algorithm [GS98] can solve the decoding problem on $\text{RS}_{n-k}$ as long as the number of errors is at most $t_0 = n - \sqrt{n(n-k)}$. If we take the error distribution $p$ where each $p_i(0) \ge \sqrt{\frac{n-k}{n}}$, then the number of errors will smaller than $t_0 = n(1-p_i(0))$ with constant probability. We can rewrite the inequality as $\frac{k}{n} \ge 1 - p_i^2(0)$. $\square$

In the case $p$ is a product function of the same distribution, so $p = v^{\otimes n}$, we have the following improvement over the Guruswami Sudan algorithm.

**Proposition 5.** [[MT17]] Let $v$ be a probability function on $\mathbb{F}_q$. The Koetter-Vardy algorithm solves $\text{SD}(\text{RS}_{n-k}, v^{\otimes n})$ $wp$. at least $\frac{1}{\text{poly}(n)}$ for $\frac{k}{n} \ge 1 - \sum_{\alpha \in \mathbb{F}_q} v^2(\alpha)$.

<footnote n="1">¹In [JSW+24], they claim only $\tilde{\tau} \approx 0.831$ which comes from a non-asymptotic analysis, but actually arises from the same calculations.</footnote>
### 4.2.1 Using the Berlekamp-Welch decoder

**Theorem 2** (Recovering results of [JSW+24]). Let positive integers $k, q$ and $n = q$. Let $S_1, \dots, S_q \subseteq \mathbb{F}_q$ of the same length with $\rho = \frac{|S_i|}{q}$. Let $T_{\tilde{\tau}} = \{\mathbf{y} = (y_i)_{i \in [1,n]} : |\{i : y_i \in S_i\}| \ge \tilde{\tau}q\}$ for any $\tilde{\tau} \in (0, 1)$. There exists a quantum algorithm that solves ICC($RS_k, T_{\tilde{\tau}}$) with probability $\frac{1}{\text{poly}(n)}$ for $\tilde{\tau} = \tau - n^{-1/3} = \tau - o(1)$ where $\tau$ is any real such that

$$1 - \frac{k}{2n} \le \left( \sqrt{\tau\rho} + \sqrt{(1-\tau)(1-\rho)} \right)^2. \qquad (2)$$

In particular, for $\frac{k}{n} = 0.1$ and $\rho = 0.5$, we recover numerically that $\tau \approx 0.7179$ saturates the above inequality.

*Proof.* Fix $\tau$ that satisfies Equation 2. We consider the functions $u_i : \mathbb{F}_q \to \mathbb{C}$ such that

$$\hat{u}_i(\alpha) = \begin{cases} \sqrt{\frac{\tau}{|S_i|}} & \text{if } \alpha \in S_i \\ \sqrt{\frac{1-\tau}{q-|S_i|}} & \text{if } \alpha \notin S_i \end{cases}$$

Also, let $f = \otimes_{i=1}^n u_i$ and $p = |f|^2 = \otimes_{i=1}^n p_i$ with $p_i = |u_i|^2$. First, we have from Proposition 2 that

$$p_i(0) = |u_i(0)|^2 = \left( \sqrt{\tau\rho} + \sqrt{(1-\tau)(1-\rho)} \right)^2.$$

We therefore obtain $1 - \frac{k}{2n} \le p_i(0)$ which implies $\frac{k}{n} \ge 2(1 - p_i(0))$. We can use Proposition 4 to say that there exists an efficient algorithm to solve SD($RS_{n-k}, p$), hence QDP($RS_{n-k}, f$) with probability $\frac{1}{\text{poly}(n)}$. This gives the first condition required in Theorem 1. Since states $\sum_{\alpha \in \mathbb{F}_q} \hat{u}_i(\alpha) |\alpha\rangle$ are efficiently computable, the state $\sum_{e \in \mathbb{F}_q} f(e) |e\rangle$ is also efficiently computable. For the third condition, we know from Proposition 2 that

$$\sum_{\mathbf{y} \in T_{\tilde{\tau}}} |\hat{f}(\mathbf{y})|^2 = 1 - \eta \text{ with } \eta = \text{negl}(n).$$

We use Theorem 1 to conclude that there exists an efficient quantum algorithm that solves ICC($RS_{n-k}^{\perp}, T_{\tilde{\tau}}$) = ICC($RS_k, T_{\tilde{\tau}}$) efficiently with success probability $\frac{1}{\text{poly}(n)} - \text{negl}(n) = \frac{1}{\text{poly}(n)}$. $\square$

### 4.2.2 Using the Guruswami-Sudan decoder

We can reproduce the above argument by replacing the Berlekamp-Welch algorithm with the Guruswami-Sudan algorithm. This gives the following theorem

**Theorem 3** (Generalizing results of [CT25], Guruswami-Sudan decoder). Let positive integers $k, q$ and $n = q$. Let $S_1, \dots, S_q \subseteq \mathbb{F}_q$ of the same length with $\rho = \frac{|S_i|}{q}$. Let $T_{\tilde{\tau}} = \{\mathbf{y} = (y_i)_{i \in [1,n]} : |\{i : y_i \in S_i\}| \ge \tilde{\tau}q\}$ for any $\tilde{\tau} \in (0, 1)$. There exists a quantum algorithm that solves ICC($RS_k, T_{\tilde{\tau}}$) with probability $\frac{1}{\text{poly}(n)}$ for $\tilde{\tau} = \tau - n^{-1/3} = \tau - o(1)$ where $\tau$ is any real such that

$$1 - \frac{k}{n} \le \left( \sqrt{\tau\rho} + \sqrt{(1-\tau)(1-\rho)} \right)^4. \qquad (3)$$

In particular, for $\frac{k}{n} = \frac{3}{4}$ and $\rho = 0.5$, the above is satisfied even with $\tau = 1$, recovering the results [CT25].

The proof is the same as the previous one but with a different decoder. We reproduce it here for completeness and clarity.

*Proof.* Fix $\tau$ that satisfies Equation 2. We consider the functions $u_i : \mathbb{F}_q \to \mathbb{C}$ such that

$$\hat{u}_i(\alpha) = \begin{cases} \sqrt{\frac{\tau}{|S_i|}} & \text{if } \alpha \in S_i \\ \sqrt{\frac{1-\tau}{q-|S_i|}} & \text{if } \alpha \notin S_i \end{cases}$$
Also, let $f = \otimes_{i=1}^n u_i$ and $p = |f|^2 = \otimes_{i=1}^n p_i$ with $p_i = |u_i|^2$. First, we have from Proposition 2 that

$$p_i(0) = |u_i(0)|^2 = \left( \sqrt{\tau \rho} + \sqrt{(1-\tau)(1-\rho)} \right)^2.$$

We therefore obtain $1 - \frac{k}{n} \le p_i^2(0)$ which implies $\frac{k}{n} \ge 1 - p_i^2(0)$. We can use the second bullet of Proposition 4 to say that there exists an efficient algorithm to solve SD($RS_{n-k}, p$), hence QDP($RS_{n-k}, f$) with probability $\frac{1}{\text{poly}(n)}$. This gives the first condition required in Theorem 1. Since states $\sum_{\alpha \in \mathbb{F}_q} \hat{u}_i(\alpha)|\alpha\rangle$ are efficiently computable, the state $\sum_{e \in \mathbb{F}_q} f(e)|e\rangle$ is also efficiently computable. For the third condition, we know from Proposition 2 that

$$\sum_{\mathbf{y} \in T_{\tilde{\tau}}} |\hat{f}(\mathbf{y})|^2 = 1 - \eta \text{ with } \eta = \text{negl}(n).$$

We use Theorem 1 to conclude that there exists an efficient quantum algorithm that solves ICC($RS_k, T_{\tilde{\tau}}$) efficiently with success probability $\frac{1}{\text{poly}(n)}$. $\square$

### 4.2.3 Using the Koetter-Vardy decoder in the case of the infinity norm

A natural case is when each $S_i = \llbracket -z, z \rrbracket$ (recall that we write $\mathbb{F}_q = \llbracket -\lfloor \frac{q-1}{2} \rfloor, \lceil \frac{q-1}{2} \rceil \rrbracket$). In this case, the Koetter-Vardy decoder gives improvements over the Guruswami-Sudan decoder. In our case, we obtain the following

**Theorem 4** (Generalizing results of [CT25], Koetter-Vardy decoder). Let $q$ be a prime integer, $n = q$ and $k \le n$. Let $S = \llbracket -z, z \rrbracket \subseteq \mathbb{F}_q$ and $T_{\tilde{\tau}} = \{\mathbf{y} = (y_i)_{i \in \llbracket 1, n \rrbracket} : |\{i : y_i \in S\}| \ge \tilde{\tau} n\}$ for any $\tilde{\tau} \in (0, 1)$. There exists a quantum algorithm that solves ICC($RS_k, T_{\tilde{\tau}}$) with probability $\frac{1}{\text{poly}(n)}$ for $\tilde{\tau} = \tau - o(1)$ where $\tau$ is any real such that

$$(1 - \frac{k}{n}) \le U(\tau, \rho), \qquad (4)$$

for some quantity $U(\tau, \rho)$ specified below. Let $B = \sqrt{\frac{1-\tau}{q-2z+1}}$, $A = \sqrt{\frac{\tau}{2z+1}} - B$ and $\Gamma = 2AB(2z+1) + qB^2$.

For $\rho \le 0.5$, we have

$$U(\tau, \rho) = A^4 \frac{2\rho^3 q^2}{3} + 2A^2 \Gamma \rho^2 q + \Gamma^2.$$

For $\rho \ge 0.5$, we have

$$U(\tau, \rho) = A^4 \left( q^2 \rho^2 \left( \frac{10\rho}{3} - 4 + \frac{2}{\rho} - \frac{1}{3\rho^2} \right) \right) + \frac{2A^2\Gamma}{q} (2z + 1 + l(4z + 1 - l) + (2z + 1 - l)(q - 2l - 1)) + \Gamma^2.$$

In particular, for $\frac{k}{n} = \frac{2}{3}$ and $\rho = 0.5$, one can show numerically that the above is satisfied even with $\tau = 1$, recovering the results [CT25].

The proof idea will be the same but the calculations are more complicated.

*Proof.* Fix $\tau$ that satisfies Equation 2. We consider the function $u : \mathbb{F}_q \to \mathbb{C}$ such that

$$\hat{u}(\alpha) = \begin{cases} \sqrt{\frac{\tau}{|S|}} & \text{if } \alpha \in S \\ \sqrt{\frac{1-\tau}{q-|S|}} & \text{if } \alpha \notin S \end{cases}$$

Also, let $f = u^{\otimes n}$ and $p = |f|^2 = (|u|^2)^{\otimes n}$. The crucial calculation is captured by the following lemma

**Lemma 1.** $\sum_{\alpha} |u|^{\otimes 4}(\alpha) \ge U(\tau, \rho)$
Proof. We defer the proof of this lemma to Appendix B.

<figure><img src="image_3.png" /></figure>

From this lemma, we obtain

$$1 - \frac{k}{n} \le U(\tau, \rho) \le \sum_{\alpha} |u|^4(\alpha).$$

We can use Proposition 5 with $v = |u|^2$ to say that there exists an efficient algorithm to solve SD($RS_{n-k}, p$), hence QDP($RS_{n-k}, f$) with probability $\frac{1}{\text{poly}(n)}$. This gives the first condition required in Theorem 1. Since states $\sum_{\alpha \in \mathbb{F}_q} \hat{u}_i(\alpha)|\alpha\rangle$ are efficiently computable, the state $\sum_{e \in \mathbb{F}_q^n} f(e)|e\rangle$ is also efficiently computable. For the third condition, we know from Proposition 2 that

$$\sum_{\mathbf{y} \in T_{\tilde{\tau}}} |\hat{f}(\mathbf{y})|^2 = 1 - \eta \text{ with } \eta = \text{negl}(n).$$

We use Theorem 1 to conclude that there exists an efficient quantum algorithm that solves ICC($RS_k, T_{\tilde{\tau}}$) efficiently with success probability $\frac{1}{\text{poly}(n)}$. □

## 4.3 Graphical representation of our results

As an example, we provide a few numerical results for the case $\rho = \frac{1}{2}$, which corresponds to the case studied in previous work. First we give in Figure 1 a plot presenting existing results as well as our new theorems.

<figure><img src="image_4.png" /><figcaption>Figure 1: Ratio of satisfied constraints $\tilde{\tau}$ as a function of the code rate $R = \frac{k}{n}$, for $\rho = \frac{|S|}{q} = \frac{1}{2}$.</figcaption></figure>

The authors of [JSW+24] considered for OPI an instance where the best efficient classical algorithm solve 55% of the constraints. We also show, for different decoders, what are the parameters that achieve the highest advantage for this classical threshold.
<table><caption>Table 1: Different achievable thresholds $\tilde{\tau}$ given parameters $R, \rho$</caption><thead><tr><th>R = <sup>k</sup>/<sub>n</sub></th><th>ρ = <sup>|S|</sup>/<sub>q</sub></th><th>τ̃(Classical)</th><th>τ̃(DQI)</th><th>τ̃(Th. 3)</th><th>τ̃(Th. 4)</th><th>Comments</th></tr></thead><tbody><tr><td>0.1</td><td>0.5</td><td>0.55</td><td>0.718</td><td>0.721</td><td>0.722</td><td>P1 point</td></tr><tr><td>0.75</td><td>0.5</td><td>0.875</td><td>0.984</td><td>1</td><td>1</td><td>P2 point</td></tr><tr><td><sup>2</sup>/<sub>3</sub></td><td>0.5</td><td>0.833</td><td>0.971</td><td>0.994</td><td>1</td><td>P3 point</td></tr><tr><td>0.234</td><td>0.413</td><td>0.55</td><td>0.749</td><td>0.760</td><td>0.763</td><td>Opt. τ̃(DQI) for τ̃(Classical) = 0.55</td></tr><tr><td>0.259</td><td>0.393</td><td>0.55</td><td>0.748</td><td>0.761</td><td>0.765</td><td>Opt. τ̃(Th. 3) for τ̃(Classical) = 0.55</td></tr><tr><td>0.267</td><td>0.386</td><td>0.55</td><td>0.748</td><td>0.761</td><td>0.765</td><td>Opt. τ̃(Th. 4) for τ̃(Classical) = 0.55</td></tr></tbody></table>

**Acknowledgments.** The author thanks Noah Shutty for valuable feedback. We acknowledge funding from the French PEPR integrated projects EPIQ (ANR-22-PETQ-007), PQ-TLS (ANR-22-PETQ-008) and HQI (ANR-22-PNCQ-0002) all part of plan France 2030.
References

[BCT25] Agathe Blanvillain, André Chailloux, and Jean-Pierre Tillich. The quantum decoding problem: Tight achievability bounds and application to Regev's reduction, 2025. https://arxiv.org/abs/2509.24796.

[BKSW18] Zvika Brakerski, Elena Kirshanova, Damien Stehlé, and Weiqiang Wen. Learning with errors and extrapolated dihedral cosets. In *Public-Key Cryptography – PKC 2018*, volume 10770 of *Lecture Notes in Computer Science*, pages 702–727. Springer, 2018.

[CH25] André Chailloux and Paul Hermouet. On the quantum equivalence between $S|LWE\rangle$ and *ISIS*, 2025. https://arxiv.org/abs/2510.06097.

[CHL+25] Yilei Chen, Zihan Hu, Qipeng Liu, Han Luo, and Yaxin Tu. Lwe with quantum amplitudes: Algorithm, hardness, and oblivious sampling. In *CRYPTO 2025*. Springer, Lecture Notes in Computer Science, 2025.

[CLZ22] Yilei Chen, Qipeng Liu, and Mark Zhandry. Quantum algorithms for variants of average-case lattice problems via filtering. In Orr Dunkelman and Stefan Dziembowski, editors, *Advances in Cryptology - EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 - June 3, 2022, Proceedings, Part III*, volume 13277 of LNCS, pages 372-401. Springer, 2022.

[CT24] André Chailloux and Jean-Pierre Tillich. The quantum decoding problem. In *Theory of Quantum Computation, Communication and Cryptography, TQC 2024, September 9-13, 2024, Okinawa, Japan*, volume 310 of LIPIcs, pages 6:1-6:14, 2024.

[CT25] André Chailloux and Jean-Pierre Tillich. Quantum advantage from soft decoders. In *Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC '25*, page 738-749, New York, NY, USA, 2025. Association for Computing Machinery.

[DFS24] Thomas Debris-Alazard, Pouria Fallahpour, and Damien Stehlé. Quantum oblivious LWE sampling and insecurity of standard model lattice-based snarks. In Bojan Mohar, Igor Shinkar, and Ryan O'Donnell, editors, *Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024*, pages 423-434. ACM, 2024.

[DRT24] Thomas Debris-Alazard, Maxime Remaud, and Jean-Pierre Tillich. Quantum reduction of finding short code vectors to the decoding problem. *IEEE Trans. Inf. Theory*, 70(7):5323-5342, 2024.

[GJ25] Andi Gu and Stephen P. Jordan. Algebraic geometry codes and decoded quantum interferometry, 2025. https://arxiv.org/abs/2510.06603.

[GS98] Venkatesan Guruswami and Madhu Sudan. Improved decoding of Reed-Solomon and algebraic-geometric codes. In *Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280)*, pages 28-37. IEEE, 1998.

[Hil25] Daniel Cohen Hillel. Optimization of quadratic constraints by decoded quantum interferometry, 2025. https://arxiv.org/abs/2510.08061.

[JSW+24] Stephen P. Jordan, Noah Shutty, Mary Wootters, Adam Zalcman, Alexander Schmidhuber, Robbie King, Sergei V. Isakov, and Ryan Babbush. Optimization by decoded quantum interferometry, 2024.

[KOW25] Robin Kothari, Ryan O'Donnell, and Kewen Wu. No exponential quantum speedup for $SIS^{\infty}$ anymore, 2025. https://arxiv.org/abs/2510.07515.
[MT17] Irene Márquez-Corbella and Jean-Pierre Tillich. Attaining capacity with iterated $(u|u + v)$ codes based on AG codes and koetter-vardy soft decoding. In *2017 IEEE International Symposium on Information Theory (ISIT)*, page 6–10. IEEE Press, 2017.

[Reg05] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In *Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing*, STOC '05, page 84–93, New York, NY, USA, 2005. Association for Computing Machinery.

[SLS+25] Alexander Schmidhuber, Jonathan Z. Lu, Noah Shutty, Stephen Jordan, Alexander Poremba, and Yihui Quek. Hamiltonian decoded quantum interferometry, 2025. https://arxiv.org/abs/2510.07913.

[Wel83] Lloyd R. Welch. The theory of error-correcting codes. In *Coding Theory and Applications*, pages 343–360. Springer, 1983.

[YZ24] Takashi Yamakawa and Mark Zhandry. Verifiable quantum advantage without structure. *J. ACM*, 71(3):20, 2024.
# A Rewriting [CH25] for codes

In this work, we prove Theorem 1. As we mentioned, this is a direct adaptation of the reduction theorem in [CH25] that we reproduce verbatim, only by changing all lattice concepts with the corresponding code concepts. So we start from a $q$-ary code $\mathcal{C}$ with associated generating matrix $\mathbf{G}$ and we construct an algorithm to solve ICC($\mathcal{C}^{\perp}, T$) for some $T \subseteq \mathbb{F}_q^n$.

## A.1 Characterization of quantum algorithms for QDP

A quantum algorithm for QDP($\mathcal{C}, f$) can be described by a unitary $U$ (that depends on $\mathcal{C}$ and $f$) such that

$$ \forall s \in \mathbb{F}_q^k, U|\psi_s\rangle|0\rangle = \sum_{s' \in \mathbb{F}_q^k} \gamma_{s,s'}|s'\rangle|\tilde{\psi}_{s,s'}\rangle, \text{ for some unit vectors } |\tilde{\psi}_{s,s'}\rangle \text{ and } \gamma_{s,s'} \in \mathbb{C}, $$

and the result is obtained by measuring the first register. The success probability of this algorithm for each $s$ is $p_s = |\gamma_{s,s}|^2$ and the overall success probability is $p = \frac{1}{q^k} \sum_s |\gamma_{s,s}|^2$. We first prove that any such quantum algorithm can be symmetrized in the sense that each $\gamma_{s,s}$ is equal to $\sqrt{p}$.

**Proposition 6.** Let $\mathcal{A}$ be an efficient quantum algorithm for QDP($\mathcal{C}, f$) that succeeds with probability $p$. There exists an efficiently computable unitary $U$ such that

$$ \forall s \in \mathbb{F}_q^k, U|\psi_s\rangle|0\rangle = \sum_{s' \in \mathbb{F}_q^k} \gamma'_{s,s'}|s'\rangle|\tilde{\psi}''_{s,s'}\rangle, \text{ for some unit vectors } |\tilde{\psi}''_{s,s'}\rangle \text{ and each } \gamma'_{s,s} = \sqrt{p}. $$

*Proof.* The idea is to use the symmetries inherent to the states $|\psi_s\rangle$. We present a first algorithm that succeeds with probability $p$ for each input state $|\psi_s\rangle$. Consider the shift unitaries $S_z : |x\rangle \to |x+z\rangle$ for $x, z \in \mathbb{F}_q^n$ which are efficiently computable. Notice that $\forall s, t \in \mathbb{F}_q^k$, we have $|\psi_t\rangle = S_{(t-s)G}|\psi_s\rangle$. We consider the following algorithm

1. Given input $|\psi_s\rangle$, construct

$$ |\Omega_1\rangle = \frac{1}{\sqrt{q^k}} \sum_{t \in \mathbb{F}_q^k} S_{tG}|\psi_s\rangle|0\rangle|t\rangle = \sum_{t \in \mathbb{F}_q^k} |\psi_{s+t}\rangle|0\rangle|t\rangle. $$

2. Apply $U$ on the first two registers to obtain

$$ |\Omega_2\rangle = \frac{1}{\sqrt{q^k}} \sum_{t \in \mathbb{F}_q^k} \sum_{s' \in \mathbb{F}_q^k} \gamma_{s+t,s'} |s'\rangle |\tilde{\psi}_{s+t,s'}\rangle |t\rangle. $$

3. We subtract the value from the third register in the first register to obtain

$$ \begin{aligned} |\Omega_3\rangle &= \frac{1}{\sqrt{q^k}} \sum_{t \in \mathbb{F}_q^k} \sum_{s' \in \mathbb{F}_q^k} \gamma_{s+t,s'} |s' - t\rangle |\tilde{\psi}_{s+t,s'}\rangle |t\rangle \\ &= \frac{1}{\sqrt{q^k}} \sum_{s' \in \mathbb{F}_q^k} \sum_{t \in \mathbb{F}_q^k} \gamma_{s+t,s'+t} |s'\rangle |\tilde{\psi}_{s+t,s'+t}\rangle |t\rangle \end{aligned} $$

If we measure the first register, we obtain $s$ with probability $\frac{1}{q^k} \sum_t |\gamma_{s+t,s+t}|^2 = p$ which is independent of $s$. If we perform the above algorithm fully coherently, we obtain a quantum unitary $U'$ such that

$$ \forall s \in \mathbb{F}_q^k, U'|\psi_s\rangle|0\rangle = \sum_{s' \in \mathbb{F}_q^k} \gamma'_{s,s'}|s'\rangle|\tilde{\psi}'_{s,s'}\rangle, \text{ for some unit vectors } |\tilde{\psi}'_{s,s'}\rangle \text{ and each } |\gamma'_{s,s}| = \sqrt{p}. $$
In order to conclude, we just have to put the potential phases of $\gamma'_{s,s}$ into the second register so if we define $|\tilde{\psi}_{s,s'}''\rangle = \frac{\gamma_{s,s'}}{|\gamma_{s,s'}|} |\tilde{\psi}_{s,s'}'\rangle$, we can indeed write

$$U'|\psi_s\rangle|0\rangle = \sum_{s' \in \mathbb{F}_q^k} \gamma'_{s,s'} |s'\rangle|\tilde{\psi}_{s,s'}''\rangle \quad \text{with each } \gamma'_{s,s'} = \sqrt{p}. \quad \square$$

## A.2 Description of the algorithm

We present now a detailed description of our algorithm. We assume we have access to a quantum algorithm for QDP that satisfies the condition of Proposition 6 and we use it to construct an algorithm for ICC.

### Algorithm 1: Quantum algorithm based on Regev's reduction for ICC

**Input:** We start from a $q$-ary code $\mathcal{C}$ of length $k$ and dimension $n$ with a associated generating matrix $\mathbf{G} \in \mathbb{F}_q^{k \times n}$. Let $T \subseteq \mathbb{F}_q^n$ and $f: \mathbb{F}_q^n \to \mathbb{C}$ such that $\|f\|_2 = 1$. For each $\mathbf{s} \in \mathbb{F}_q^k$, we write $|\psi_{\mathbf{s}}\rangle = \sum_{e \in \mathbb{F}_q^n} f(e)|\mathbf{s}\mathbf{G} + e\rangle$. Assume we have a codeword independent quantum algorithm $\mathcal{A}$ that solves QDP($\mathcal{C}, f$) with probability $P_{Dec}$. This means we have a quantum unitary

$$U|\psi_{\mathbf{s}}\rangle|0\rangle = \sum_{\mathbf{s}' \in \mathbb{F}_q^k} \gamma_{\mathbf{s},\mathbf{s}'} |\tilde{\psi}_{\mathbf{s},\mathbf{s}'}\rangle|\mathbf{s}'\rangle, \quad \text{where } \forall \mathbf{s} \in \mathbb{F}_q^k, \gamma_{\mathbf{s},\mathbf{s}} = \sqrt{P_{Dec}} \text{ and each } |\tilde{\psi}_{\mathbf{s},\mathbf{s}'}\rangle \text{ is a unit vector.}$$

Finally, we are given a random $\mathbf{u} \in \mathbb{F}_q^k$.

**Goal:** Find $\mathbf{y} \in \mathcal{C}_{\mathbf{u}}^{\perp} \cap T$, where $\mathcal{C}_{\mathbf{u}}^{\perp} = \{\mathbf{y} \in \mathbb{F}_q^n : \mathbf{G}\mathbf{y}^{\top} = \mathbf{u}^{\top}\}$

**Execution of the algorithm:**

1. First construct the state $\frac{1}{\sqrt{q^k}} \sum_{\mathbf{s} \in \mathbb{F}_q^k} \chi_{-\mathbf{u}}(\mathbf{s}) |\psi_{\mathbf{s}}\rangle|0\rangle|\mathbf{s}\rangle$.

2. Perform the operation

$$\frac{1}{\sqrt{q^k}} \sum_{\mathbf{s} \in \mathbb{F}_q^k} \chi_{-\mathbf{u}}(\mathbf{s}) |\psi_{\mathbf{s}}\rangle|0\rangle|\mathbf{s}\rangle \xrightarrow{\textcircled{1}} \frac{1}{\sqrt{q^k}} \sum_{\mathbf{s}, \mathbf{s}' \in \mathbb{F}_q^k} \chi_{-\mathbf{u}}(\mathbf{s}) \gamma_{\mathbf{s}, \mathbf{s}'} |\tilde{\psi}_{\mathbf{s}, \mathbf{s}'}\rangle|\mathbf{s}'\rangle|\mathbf{s} - \mathbf{s}'\rangle$$

Here, $\textcircled{1}$ is done by applying $U$ on the first two registers and then subtracting the second register from the third register.

3. Measure the third register. If we don't obtain $\mathbf{0}^n$, start again from step 1. Otherwise, we obtain the state $\frac{1}{\sqrt{q^k}} \sum_{\mathbf{s} \in \mathbb{F}_q^k} \chi_{-\mathbf{u}}(\mathbf{s}) |\tilde{\psi}_{\mathbf{s},\mathbf{s}}\rangle|\mathbf{s}\rangle|0\rangle$.

4. Discard the third register and apply $U^{\dagger}$ on the first two registers. The resulting state is

$$|\Phi_{\mathbf{u}}\rangle = \frac{1}{\sqrt{q^k}} \sum_{\mathbf{s} \in \mathbb{F}_q^k} \chi_{-\mathbf{u}}(\mathbf{s}) \sqrt{P_{Dec}} |\psi_{\mathbf{s}}\rangle + \chi_{-\mathbf{u}}(\mathbf{s}) \sqrt{1 - P_{Dec}} |Z_{\mathbf{s}}\rangle \text{ for some unit vector } |Z_{\mathbf{s}}\rangle \perp |\psi_{\mathbf{s}}\rangle.$$

5. Compute $|\tilde{\Phi}_{\mathbf{u}}\rangle$ and measure in the computational basis. Output the outcome of the measurement.

## A.3 First analysis and running time of the algorithm

We first provide some details over each step of the algorithm.
1. The initialization step of the algorithm can be done as follows

$$ \sum_{s \in \mathbb{F}_q^k} |s\rangle \otimes \sum_{e \in \mathbb{F}_q^k} f(e)|e\rangle \xrightarrow{\textcircled{1}} \sum_{\substack{s \in \mathbb{F}_q^k \\ e \in \mathbb{F}_q^n}} f(e)|s\rangle|s\mathbf{G} + e\rangle = \sum_{s \in \mathbb{F}_q^k} |s\rangle|\psi_s\rangle, $$

which corresponds to the initial state by adding a $|0\rangle$ register and reordering. In ①, we use the fact that $s \to s\mathbf{G}$ is easily computable and apply this operation coherently. We then need to compute $\sum_{e \in \mathbb{F}_q^n} f(e)|e\rangle$ which take some time $T_{Sampl}$. In practice, $f$ is chosen such that this state can be computed efficiently. The running time of this is therefore in $O(T_{Sampl} + \text{poly}(n, \log(q)))$.

2. In step 3, before the measurement, we have the state

$$ \frac{1}{\sqrt{q^k}} \sum_{s,s' \in \mathbb{F}_q^k} \chi_{-u}(s) \gamma_{s,s'} |\tilde{\psi}_{s,s'}\rangle |s'\rangle |s-s'\rangle = \frac{1}{\sqrt{q^k}} \left( \sum_s \chi_{-u}(s) \sqrt{P_{Dec}} |\tilde{\psi}_{s,s}\rangle |s\rangle |0\rangle + \sum_{s,s' \neq s} \chi_{-u}(s) \sqrt{1-P_{Dec}} |\tilde{\psi}_{s,s'}\rangle |s'\rangle |s-s'\rangle \right). $$

which means that we successfully measure $\mathbf{0}$ in the last register with probability $P_{Dec}$ and that conditioned on this outcome, the resulting state is indeed $\frac{1}{\sqrt{q^k}} \sum_s \chi_{-u}(s) |\tilde{\psi}_{s,s}\rangle |s\rangle |0\rangle$. This means we have to repeat steps 1 to 3 $O(\frac{1}{P_{Dec}})$ times. Moreover, step 2 requires to compute $U$, which takes time $T_{Dec}$ which is the running time of the decoder. From there, we conclude that the time required for this algorithm to successfully pass step 3 is

$$ O\left( \frac{1}{P_{Dec}} \left( \text{Time}_{Dec} + \text{Time}_{Sampl} \right) + \text{poly}(n, \log(q)) \right). $$

3. In order to see step 4, we start from $U|\psi_s\rangle|0\rangle = \sum_{s' \in \mathbb{F}_q^k} \gamma_{s,s'} |\tilde{\psi}_{s,s'}\rangle |s'\rangle$ which implies

$$ \langle \tilde{\psi}_{s,s} | \langle s | U (| \psi_s \rangle | 0 \rangle) = \langle \psi_s | \langle 0 | U^\dagger (| \tilde{\psi}_{s,s} \rangle | s \rangle) = \gamma_{s,s} = \sqrt{P_{Dec}}. $$

This means that for each $s \in \mathbb{F}_q^k$, we can indeed write

$$ U^{\dagger}(|\tilde{\psi}_{s,s}\rangle|s\rangle) = \sqrt{P_{Dec}}|\psi_s\rangle + \sqrt{1-P_{Dec}}|Z_s\rangle, $$

for some unit vector $|Z_s\rangle$ orthogonal to $|\psi_s\rangle$, which justifies step 4 of the algorithm. Finally, in step 5, we have to perform $n$ quantum Fourier transforms in $F_q$ and measure, which takes time $\text{poly}(n, \log(q))$.

From this analysis, we can conclude that the running time of the algorithm satisfies

$$ \text{Time} = O\left( \frac{1}{P_{Dec}} \left( \text{Time}_{Dec} + \text{Time}_{Sampl} \right) + \text{poly}(n, \log(q)) \right). $$

The trickier part will be to argue about the success probability of the algorithm, which is the goal of the following section.

## A.4 Proof of main theorem

We use the notations as in the beginning of the section. We prove the following

**Theorem 5** (Theorem 1 restated). Let $C$ be a $q$-ary linear code of dimension $k$ and length $n$ and let $\mathbf{G} \in \mathbb{F}_q^{k \times n}$ be a generating matrix of $C$. Let $T \subseteq \mathbb{F}_q^n$. Let $f: \mathbb{F}_q^n \to \mathbb{C}$ with $\|f\|_2 = 1$. Assume that
1. We have a (classical or quantum) codeword independent algorithm $\mathcal{A}_{Dec}$ that solves $\text{SD}(C, |f|^2)$ in time $\text{Time}_{Dec}$ and succeeds with probability $P_{Dec}$.

2. The state $\sum_{e \in \mathbb{F}_q^n} f(e)|e\rangle$ is constructible in time $T_{Sampl}$.

3. $\sum_{y \in T} |\hat{f}(y)|^2 = 1 - \eta$.

Then there exists a quantum algorithm that solves $\text{ICC}(C^{\perp}, T)$ with probability

$$P \geq P_{Dec}(1 - \eta) - 2\sqrt{\eta P_{Dec}(1 - P_{Dec})},$$

and runs in time

$$\text{Time} = O\left( \frac{1}{P_{Dec}} \left( \text{Time}_{Dec} + \text{Time}_{Sampl} \right) + \text{poly}(n, \log(q)) \right).$$

The running time of the algorithm has been discussed in the previous section so we just need to prove the success probability. We fix $\mathbf{u} \in \mathbb{F}_q^k$, and let $p_u$ be the probability that the algorithm outputs an element $\mathbf{y} \in C_u^{\perp} \cap T$ given this $\mathbf{u}$. We write $|\hat{Z}_s\rangle = \sum_{y \in \mathbb{F}_q^n} z_{s,y}|\mathbf{y}\rangle$ and have

**Lemma 2.** $p_u = \sum_{\mathbf{y} \in C_u^{\perp} \cap T} \left| \sqrt{P_{Dec}} \sqrt{q^k} \hat{f}(\mathbf{y}) + \frac{\sqrt{1-P_{Dec}}}{\sqrt{q^k}} \sum_{\mathbf{s} \in \mathbb{F}_q^k} \omega^{-\mathbf{s} \cdot \mathbf{u}} z_{\mathbf{s},\mathbf{y}} \right|^2$.

*Proof.* In order to compute $p_u$, we have to compute $|\hat{\Phi}_u\rangle$. We have

$$|\hat{\Phi}_u\rangle = \frac{1}{\sqrt{q^k}} \sum_{\mathbf{s} \in \mathbb{F}_q^k} \chi_u(\mathbf{s}) \sqrt{P_{Dec}} |\hat{\psi}_s\rangle + \chi_u(\mathbf{s}) \sqrt{1-P_{Dec}} |\hat{Z}_s\rangle.$$

We first write

$$\begin{aligned}
|\hat{\psi}_s\rangle &= \frac{1}{\sqrt{q^k}} \sum_{\mathbf{y} \in \mathbb{F}_q^n} \sum_{\mathbf{e} \in \mathbb{F}_q^n} \chi_y(\mathbf{s}\mathbf{G} + \mathbf{e}) f(e) |\mathbf{y}\rangle \\
&= \frac{1}{\sqrt{q^k}} \sum_{\mathbf{y} \in \mathbb{F}_q^n} \chi_y(\mathbf{s}\mathbf{G}) \sum_{\mathbf{e} \in \mathbb{F}_q^n} \chi_y(e) f(e) |\mathbf{y}\rangle \\
&= \sum_{\mathbf{y} \in \mathbb{F}_q^n} \chi_{\mathbf{y}\mathbf{G}^{\top}}(\mathbf{s}) \hat{f}(\mathbf{y}) |\mathbf{y}\rangle \\
&= \sum_{\mathbf{u}' \in \mathbb{F}_q^k} \chi_{\mathbf{u}'}(\mathbf{s}) \sum_{\mathbf{y} \in C_{\mathbf{u}'}^{\perp}} \hat{f}(\mathbf{y}) |\mathbf{y}\rangle
\end{aligned}$$

which gives

$$\sum_{\mathbf{s} \in \mathbb{F}_q^k} \chi_{-\mathbf{u}}(\mathbf{s}) |\hat{\psi}_s\rangle = \sum_{\mathbf{s} \in \mathbb{F}_q^k} \sum_{\mathbf{u}' \in \mathbb{F}_q^k} \chi_{(\mathbf{u}' - \mathbf{u})}(\mathbf{s}) \sum_{\mathbf{y} \in C_{\mathbf{u}'}^{\perp}} \hat{f}(\mathbf{y}) |\mathbf{y}\rangle = q^k \sum_{\mathbf{y} \in C_{\mathbf{u}'}^{\perp}} \hat{f}(\mathbf{y}) |\mathbf{y}\rangle.$$

From there, we have

$$|\hat{\Phi}_u\rangle = \sqrt{q^k P_{Dec}} \sum_{\mathbf{y} \in C_u^{\perp}} \hat{f}(\mathbf{y}) |\mathbf{y}\rangle + \sqrt{\frac{1-P_{Dec}}{q^k}} \sum_{\mathbf{y} \in \mathbb{F}_q^n} \sum_{\mathbf{s} \in \mathbb{F}_q^k} \chi_{-\mathbf{u}}(\mathbf{s}) z_{\mathbf{s},\mathbf{y}} |\mathbf{y}\rangle.$$

The algorithm computes this state and measures in the computational basis. The probability to output an element of $C_u^{\perp} \cap T$ is therefore

$$p_u = \sum_{\mathbf{y} \in C_u^{\perp} \cap T} \left| \sqrt{q^k P_{Dec}} \hat{f}(\mathbf{y}) + \sqrt{\frac{1-P_{Dec}}{q^k}} \sum_{\mathbf{s} \in \mathbb{F}_q^k} \chi_{-\mathbf{u}}(\mathbf{s}) z_{\mathbf{s},\mathbf{y}} \right|^2 . \quad \square$$
We can now proceed to the main proof of this section

**Proposition 7.** $P = E_{u \leftarrow \mathbb{F}_q^k} [p_u] \ge P_{\text{Dec}}(1 - \eta) - 2\sqrt{\eta P_{\text{Dec}}(1 - P_{\text{Dec}})}$.

*Proof.* We write

$$ 
\begin{aligned}
p_u &= \sum_{\mathbf{y} \in C_u^{\perp} \cap T} \left| \sqrt{P_{\text{Dec}}} \sqrt{q^k} \hat{f}(\mathbf{y}) + \frac{\sqrt{1-P_{\text{Dec}}}}{\sqrt{q^k}} \sum_{\mathbf{s} \in \mathbb{F}_q^k} \chi_{-u}(\mathbf{s}) \overline{z_{s,y}} \right|^2 \\
&= \sum_{\mathbf{y} \in C_u^{\perp} \cap T} \left( P_{\text{Dec}} q^k |\hat{f}(\mathbf{y})|^2 + \frac{1-P_{\text{Dec}}}{q^k} \left| \sum_{\mathbf{s} \in \mathbb{F}_q^k} \chi_{-u}(\mathbf{s}) \overline{z_{s,y}} \right|^2 + 2 \text{Re} \left( \sqrt{P_{\text{Dec}}} \sqrt{q^k} \hat{f}(\mathbf{y}) \frac{\sqrt{1-P_{\text{Dec}}}}{\sqrt{q^k}} \sum_{\mathbf{s} \in \mathbb{F}_q^k} \chi_{u}(\mathbf{s}) \overline{z_{s,y}} \right) \right)
\end{aligned}
$$

where we used $|a+b|^2 = (a+b)(\bar{a}+\bar{b}) = |a|^2 + |b|^2 + 2\text{Re}(ab)$. We now bound each term separately. We first write

$$ E_{u \leftarrow \mathbb{F}_q^k} \left[ \sum_{\mathbf{y} \in C_u^{\perp} \cap T} \left( P_{\text{Dec}} q^k |\hat{f}(\mathbf{y})|^2 \right) \right] = P_{\text{Dec}}(1-\eta) $$

$$ \forall \mathbf{u} \in \mathbb{F}_q^k, \quad \sum_{\mathbf{y} \in C_u^{\perp} \cap T} \left( \frac{1-P_{\text{Dec}}}{q^k} \left| \sum_{\mathbf{s} \in \mathbb{F}_q^k} \chi_{-u}(\mathbf{s}) \overline{z_{s,y}} \right|^2 \right) \ge 0 $$

$$ \sum_{\mathbf{y} \in C_u^{\perp} \cap T} \left( 2 \text{Re} \left( \sqrt{P_{\text{Dec}}} \sqrt{q^k} \hat{f}(\mathbf{y}) \frac{\sqrt{1-P_{\text{Dec}}}}{\sqrt{q^k}} \sum_{\mathbf{s} \in \mathbb{F}_q^k} \chi_{u}(\mathbf{s}) \overline{z_{s,y}} \right) \right) = 2 \sqrt{P_{\text{Dec}}(1-P_{\text{Dec}})} \text{Re} \left( \sum_{\substack{\mathbf{y} \in C_u^{\perp} \cap T \\ \mathbf{s} \in \mathbb{F}_q^k}} \hat{f}(\mathbf{y}) \chi_{u}(\mathbf{s}) \overline{z_{s,y}} \right) $$

From there, we write

$$ p = E_{u \leftarrow \mathbb{F}_q^k} [p_u] \ge P_{\text{Dec}}(1-\eta) + 2\sqrt{P_{\text{Dec}}(1-P_{\text{Dec}})} E_{u \leftarrow \mathbb{F}_q^k} \left[ \text{Re} \left( \sum_{\substack{\mathbf{y} \in C_u^{\perp} \cap T \\ \mathbf{s} \in \mathbb{F}_q^k}} \hat{f}(\mathbf{y}) \chi_{u}(\mathbf{s}) \overline{z_{s,y}} \right) \right] . \quad (5) $$

In order to conclude, we prove the following lemma

**Lemma 3.**

$$ \forall \mathbf{s} \in \mathbb{F}_q^k, \quad \left| \sum_{\mathbf{u} \in \mathbb{F}_q^k} \sum_{\mathbf{y} \in C_u^{\perp}} \hat{f}(\mathbf{y}) \chi_{u}(\mathbf{s}) \overline{z_{s,y}} \right| \le \sqrt{\eta}. $$

*Proof.* We start from the equality $\langle Z_s | \psi_s \rangle = \langle \tilde{Z}_s | \psi_s \rangle = 0$ for each $\mathbf{s} \in \mathbb{F}_q^k$, which can be rewritten

$$ \sum_{\mathbf{u} \in \mathbb{F}_q^k} \sum_{\mathbf{y} \in C_u^{\perp}} \chi_{u}(\mathbf{s}) \hat{f}(\mathbf{y}) \overline{z_{s,y}} = 0. $$
This implies

$$
\begin{aligned}
\left| \sum_{\mathbf{u} \in \mathbb{F}_q^k} \sum_{\mathbf{y} \in C_u^\perp \cap T} \chi_u(s) \hat{f}(\mathbf{y}) \overline{z_{s,y}} \right| &= \left| \sum_{\mathbf{u} \in \mathbb{F}_q^k} \sum_{\mathbf{y} \in C_u^\perp \cap \overline{T}} \chi_u(s) \hat{f}(\mathbf{y}) \overline{z_{s,y}} \right| \\
&= \left| \sum_{\mathbf{y} \notin T} \chi_{yG^T}(s) \hat{f}(\mathbf{y}) \overline{z_{s,y}} \right| \\
&\le \sqrt{\sum_{\mathbf{y} \notin T} |\chi_{yG^T}(s) \hat{f}(\mathbf{y})|^2} \sqrt{\sum_{\mathbf{y} \notin T} |z_{s,y}|^2} \\
&\le \sqrt{\eta} \sqrt{1} = \sqrt{\eta},
\end{aligned}
$$

where we used the fact that $|Z_s\rangle$ is a unit vector.

We can now conclude our main proof. We have

$$
\begin{aligned}
\mathbb{E}_{u \leftarrow \mathbb{F}_q^k} \left[ \mathrm{Re} \left( \sum_{\substack{\mathbf{y} \in C_u^\perp \cap T \\ s \in \mathbb{F}_q^k}} \hat{f}(\mathbf{y}) \chi_u(s) \overline{z_{s,y}} \right) \right] &= \frac{1}{q^k} \sum_{s \in \mathbb{F}_q^k} \mathrm{Re} \left( \sum_{\mathbf{u} \in \mathbb{F}_q^k} \sum_{\mathbf{y} \in C_u^\perp} \hat{f}(\mathbf{y}) \chi_u(s) \overline{z_{s,y}} \right) \\
&\geq -\frac{1}{q^k} \sum_{s \in \mathbb{F}_q^k} \left| \sum_{\mathbf{u} \in \mathbb{F}_q^k} \sum_{\mathbf{y} \in C_u^\perp} \hat{f}(\mathbf{y}) \chi_u(s) \overline{z_{s,y}} \right| \\
&\geq -\frac{1}{q^k} \sum_{s \in \mathbb{F}_q^k} \sqrt{\eta} \\
&= -\sqrt{\eta}
\end{aligned}
$$

Plugging this inequality into Equation 5, we get

$$P \geq P_{\text{Dec}}(1 - \eta) - 2\sqrt{P_{\text{Dec}}(1 - P_{\text{Dec}})}\sqrt{\eta}.$$

## B Proof of Lemma 1

**Proposition 8.** Let $u : \mathbb{F}_q \to \mathbb{C}$ be the function such that

$$ \hat{u}(\alpha) = \begin{cases} \sqrt{\frac{\tau}{|S|}} & \text{if } \alpha \in S \\ \sqrt{\frac{1-\tau}{q-|S|}} & \text{if } \alpha \notin S \end{cases} $$

We have

$$ \sum_{\alpha} (u \star u)^2(\alpha) = \sum_{\alpha} |u(\alpha)|^4 = U(\tau, \rho) $$

*Proof.* We write $\hat{u} = A1_{[-z,z]} + B1_{\mathbb{F}_q}$ with $B = \sqrt{\frac{1-\tau}{q-|S|}}$ and $A = \sqrt{\frac{\tau}{|S|}} - B$. We then write

$$ \hat{u} \star \hat{u} = A^2(1_{[-z,z]} \star 1_{[-z,z]}) + AB(1_{[-z,z]} \star 1_{\mathbb{F}_q}) + AB(1_{\mathbb{F}_q} \star 1_{[-z,z]}) + B^2(1_{\mathbb{F}_q} \star 1_{\mathbb{F}_q}) $$

Now, notice that

$$ (1_{[-z,z]} \star 1_{\mathbb{F}_q}) = (1_{\mathbb{F}_q} \star 1_{[-z,z]}) = (2z + 1)1_{\mathbb{F}_q}, $$
and $(1_{\mathbb{F}_q} \star 1_{\mathbb{F}_q}) = q1_{\mathbb{F}_q}$. From there, we write

$$ (\hat{u} \star \hat{u})(\alpha) = A^2(1_{[-z,z]} \star 1_{[-z,z]})(\alpha) + 2AB(2z+1) + qB^2. $$

We define $\Gamma = 2AB(2z+1) + qB^2$. We can now write

$$ (\hat{u} \star \hat{u})^2(\alpha) = A^4(1_{[-z,z]} \star 1_{[-z,z]})^2(\alpha) + 2A^2\Gamma(1_{[-z,z]} \star 1_{[-z,z]})(\alpha) + \Gamma^2. $$

which gives us

$$ \sum_{\alpha \in \mathbb{F}_q} (\hat{u} \star \hat{u})^2(\alpha) = A^4 \left( \sum_{\alpha \in \mathbb{F}_q} (1_{[-z,z]} \star 1_{[-z,z]})^2(\alpha) \right) + 2A^2\Gamma \left( \sum_{\alpha \in \mathbb{F}_q} (1_{[-z,z]} \star 1_{[-z,z]})(\alpha) \right) + q\Gamma^2. $$

In order to conclude we use the analysis of [CT25]. Let $\rho = \frac{|S|}{q} = \frac{2z+1}{q}$. We distinguish two cases

**Case 1:** $\rho \le \frac{1}{2}$. In this case, we have

$$ (1_{[-z,z]} \star 1_{[-z,z]})(\alpha) = \begin{cases} 2z+1-|\alpha| & \text{if } \alpha \in [-2z, 2z] \\ 0 & \text{otherwise} \end{cases} $$

which gives

$$ \sum_{\alpha \in \mathbb{F}_q} (1_{[-z,z]} \star 1_{[-z,z]})(\alpha) = 2z+1+2 \sum_{\alpha=1}^{2z} (2z+1-\alpha) = (2z+1)+2z(2z+1) = (2z+1)^2 = \rho^2 q^2. $$

Moreover, we know from [CT25] that $\sum_{\alpha \in \mathbb{F}_q} (1_{[-z,z]} \star 1_{[-z,z]})(\alpha) \ge \frac{2\rho^3 q^3}{3}$. From there, we can conclude

$$ \sum_{\alpha \in \mathbb{F}_q} (\hat{u} \star \hat{u})^2(\alpha) \ge A^4 \frac{2\rho^3 q^3}{3} + 2A^2\Gamma\rho^2 q^2 + q\Gamma^2. $$

and

$$ \sum_{\alpha \in \mathbb{F}_q} |u(\alpha)|^4 = \frac{1}{q} \sum_{\alpha \in \mathbb{F}_q} (\hat{u} \star \hat{u})^2(\alpha) \ge A^4 \frac{2\rho^3 q^2}{3} + 2A^2\Gamma\rho^2 q + \Gamma^2. \quad (6) $$

**Case 2:** $\rho \ge \frac{1}{2}$. Let $l = q - (2z+1)$. We have

$$ (1_{[-z,z]} \star 1_{[-z,z]})(\alpha) = \begin{cases} 2z+1-|\alpha| & \text{if } \alpha \in [-l, l] \\ 2z+1-l & \text{otherwise} \end{cases} $$

which gives

$$ \sum_{\alpha \in \mathbb{F}_q} (1_{[-z,z]} \star 1_{[-z,z]})(\alpha) = 2z+1+2 \left( \sum_{\alpha=1}^{l} (2z+1-\alpha) \right) + (2z+1-l)(q-2l-1) \\ = 2z+1+l(4z+1-l) + (2z+1-l)(q-2l-1) $$

Moreover, we know from [CT25] that

$$ \sum_{\alpha \in \mathbb{F}_q} (1_{[-z,z]} \star 1_{[-z,z]})(\alpha) \ge q^3 \rho^2 \left( \frac{10\rho}{3} - 4 + \frac{2}{\rho} - \frac{1}{3\rho^2} \right). $$

which gives

$$ \sum_{\alpha \in \mathbb{F}_q} (\hat{u} \star \hat{u})^2(\alpha) \ge A^4 \left( q^3 \rho^2 \left( \frac{10\rho}{3} - 4 + \frac{2}{\rho} - \frac{1}{3\rho^2} \right) \right) + 2A^2\Gamma (2z+1+l(4z+1-l) + (2z+1-l)(q-2l-1)) + q\Gamma^2 $$
and hence

$$ \sum_{\alpha \in \mathbb{F}_q} |u(\alpha)|^4 = A^4 \left( q^2 \rho^2 \left( \frac{10\rho}{3} - 4 + \frac{2}{\rho} - \frac{1}{3\rho^2} \right) \right) + \frac{2A^2\Gamma}{q} (2z + 1 + l(4z + 1 - l) + (2z + 1 - l)(q - 2l - 1)) + \Gamma^2. $$

□