# Quantum Advantage from Soft Decoders

André Chailloux, Jean-Pierre Tillich

► To cite this version:

André Chailloux, Jean-Pierre Tillich. Quantum Advantage from Soft Decoders. STOC 2025 - 57th Annual ACM Symposium on Theory of Computing, Jun 2025, Prague, Czech Republic. pp.738-749, 10.1145/3717823.3718319 . hal-05462301

HAL Id: hal-05462301

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

Submitted on 16 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_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Quantum advantage from soft decoders

André Chailloux

Inria de Paris, COSMIQ team

Paris, France

andre.chailloux@inria.fr

Jean-Pierre Tillich

Inria de Paris, COSMIQ team

Paris, France

jean-pierre.tillich@inria.fr

## Abstract

In the last years, Regev's reduction has been used as a quantum algorithmic tool for providing a quantum advantage for variants of the decoding problem. Following this line of work, the authors of [?] have recently come up with a quantum algorithm called "decoded quantum interferometry" that is able to solve in polynomial time several optimization problems. They study in particular the Optimal Polynomial Interpolation (OPI) problem, which can be seen as a decoding problem on Reed-Solomon codes.

In this work, we provide strong improvements for some instantiations of the OPI problem. The most notable improvements are for the $ISI_{\infty}$ problem (originating from lattice-based cryptography) on Reed-Solomon codes but we also study different constraints for OPI. Our results provide natural and convincing decoding problems for which we believe to have a quantum advantage.

Our proof techniques involve the use of a *soft decoder* for Reed-Solomon codes, namely the decoding algorithm from Koetter and Vardy [?]. In order to be able to use this decoder in the setting of Regev's reduction, we provide a novel generic reduction from a syndrome decoding problem to a coset sampling problem, providing a powerful and simple to use theorem, which generalizes previous work and is of independent interest. We also provide an extensive study of OPI using the Koetter and Vardy algorithm.

## CCS Concepts

* Theory of computation → Quantum computation theory; 
* Security and privacy → Cryptanalysis and other attacks.

## ACM Reference Format:

André Chailloux and Jean-Pierre Tillich. 2025. Quantum advantage from soft decoders. In. ACM, New York, NY, USA, 12 pages. https://doi.org/10.1145/nnnnnnn.nnnnnnn

# 1 Introduction

## 1.1 Context

In the last years, Regev's reduction has been used as a quantum algorithmic tool for providing a quantum advantage for variants of decoding problems. Chen, Liu and Zhandry [?] initiated this line of research and showed how to use Regev's reduction for algorithmic purposes. They solved in quantum polynomial time the

$SIS_{\infty}$ problem for some parameters. While the parameters where this quantum algorithm works in polynomial time are somewhat extreme, there is no known classical algorithm that solves $SIS_{\infty}$ for these parameters. Then, Yamakawa and Zhandry [?] proved their algorithm for quantum advantage without structure using essentially a decoding problem.

*Quantum advantage with "decoded quantum interferometry".* Recently, [?] has come up with a quantum algorithm called “decoded quantum interferometry” that is able to solve in polynomial time several optimization problems. One of them is sparse max-XORSAT and the other one is Optimal Polynomial Interpolation (OPI). The quantum algorithm achieves on certain instances of the first problem a better approximation ratio on average than simulated annealing. However, there are specialized classical algorithms tailored to this problem which provide a better approximation ratio. Much more intriguing is the second problem, namely OPI. It basically consists for a finite field $\mathbb{F}_q$ in finding a polynomial in $\mathbb{F}_q[X]$ of some degree less than some bound $k$ which satisfies as many intersection constraints as possible. Here there are as many intersection constraints as there are non zero elements $x$ in $\mathbb{F}_q$. Each constraint corresponds to a set $S_x \subset \mathbb{F}_q$ and the intersection constraint at $x$ just means that $P(x)$ should be in $S_x$. To illustrate the quantum speedup which can be achieved, the authors of [?] consider the case of balanced sets (the size of the $S_x$'s is $\approx \frac{q}{2}$), the bound on the degree is $k = \frac{q}{10}$. In this case, their quantum algorithm is able to produce in polynomial time polynomials of degree $\le d$ which satisfy a fraction $\frac{1}{2} + \frac{\sqrt{19}}{20} \approx 0.7179$ of constraints. Remarkably the best known polynomial time classical algorithm achieves to satisfy only a fraction 0.55 of the constraints. As the authors note in [?], the margin of the quantum advantage for the approximation fraction is satisfyingly large.

Both problems are actually an instance of a decoding problem which appears in rate distortion theory. We are given a linear code $C$, i.e. a subspace of $\mathbb{F}_q^n$ of some dimension $k$ and a word $\mathbf{y} = (y_i)_{1\le i \le n} \in \mathbb{F}_q^n$ and we are asked to find a codeword $\mathbf{c} = (c_i)_{1\le i \le n}$ ($\mathbf{c}$ is an element of $C$) which is sufficiently close to $\mathbf{y}$, where the distance $d(\cdot, \cdot)$ is say some additive function $d(\mathbf{y}, \mathbf{c}) = \sum_{i=1}^n f_i(\mathbf{c}_i, \mathbf{y}_i)$, where the $f_i$'s are some suitable nonnegative functions. This problem is generally solved (and interesting) for parameters $k$ and bound $D$ on the distance $d(\cdot, \cdot)$ for which there might be even exponentially many codewords meeting the distance bound, but this does not make the problem necessarily easy. Right now, there are only very special classes of codes for which there is a satisfying solution to this problem such as for instance convolutional codes, LDGM codes or polar codes. Interestingly enough, decoded quantum interferometry solves this kind of problem by using the quantum Fourier transform to transform a (classical) solver of the decoding problem in the injective regime into a solver in the surjective regime. Here by

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.

Conference’17, Washington, DC, USA

© 2025 Copyright held by the owner/author(s). Publication rights licensed to ACM.

ACM ISBN 978-x-xxxx-xxxx-x/YYYY/MM

https://doi.org/10.1145/nnnnnnn.nnnnnnn
injective regime, we mean that the distance bound is so strong, that for a given $\mathbf{y}$ there is typically at most one solution of the decoding problem, namely at most a unique $c \in C$ such that $d(\mathbf{y}, c) \le D$. This corresponds to the more traditional decoding problem appearing in error correction where we are given a noisy codeword $c + e$, where $c \in C$ and $e$ is a "small" error vector in $\mathbb{F}_q^n$, where we want a decoding algorithm $\mathcal{A}_{dec}$ which given as input $c + e$ is able to recover the close codeword $c$. We are in this case typically in the regime where it is only $c$ which is close enough to $c + e$. It turns out that this way of turning a classical algorithm solving the decoding problem in the injective regime into a quantum algorithm solving the decoding problem in the surjective regime is precisely what Regev has achieved in lattice based cryptography when he reduced quantumly the SIS problem to the LWE problem.

**Regev's reduction.** To explain Regev's reduction [?] in coding theoretic terms, let us bring the notion of dual code. The dual $C^\perp$ of a linear code $C \subset \mathbb{F}_q^n$ is a subspace of $\mathbb{F}_q^n$ defined as

$$C^{\perp} = \{ \mathbf{y} \in \mathbb{F}_q^n : \mathbf{y} \cdot c = 0 \text{ for each } c \in C \}$$

where $\mathbf{y} \cdot c$ is the canonical inner product of these vectors in $\mathbb{F}_q^n$. We fix a function $f: \mathbb{F}_q^n \to \mathbb{C}$ with $\|f\|_2 = 1$ so that $|f|^2$ will serve as a probability distribution of the errors we feed in the decoder. Regev's reduction consists in performing the following operations:

$$ \frac{1}{\sqrt{|C|}} \sum_{c \in C, e \in \mathbb{F}_q^n} f(\mathbf{e})|c + e\rangle|e\rangle \xrightarrow{\text{Decoder}} \frac{1}{\sqrt{|C|}} \sum_{c \in C, e \in \mathbb{F}_q^n} f(\mathbf{e})|c + e\rangle \\ \xrightarrow{\text{QFT}_{\mathbb{F}_q^n}} \frac{q^n}{\sqrt{|C|}} \sum_{\mathbf{y} \in C^{\perp}} \hat{f}(\mathbf{y})|\mathbf{y}\rangle, $$

where $\text{QFT}_{\mathbb{F}_q^n}$ denotes the quantum Fourier transform with respect to $\mathbb{F}_q^n$. The initial state can be easily constructed from a uniform superposition of codewords tensored with a superposition of errors $\frac{1}{\sqrt{|C|}} \sum_{c \in C} |c\rangle \otimes \sum_{e \in \mathbb{F}_q^n} f(\mathbf{e})|e\rangle$ and adding the second register to the first one to create the entangled state $\frac{1}{\sqrt{|C|}} \sum_{c \in C, e \in \mathbb{F}_q^n} f(\mathbf{e})|c + e\rangle|e\rangle$.

The idea of Regev's algorithm is to make use of a classical decoder which is an algorithm $\mathcal{A}_{dec}$ such that $\mathcal{A}_{dec}(c + e) = e$. To be able to perform this operation, we are necessarily in the aforementioned injective regime of decoding. Such an algorithm, if it exists, allows us to "erase" the $|e\rangle$ register when applied coherently. The resulting state $\frac{1}{\sqrt{|C|}} \sum_{c \in C, e \in \mathbb{F}_q^n} f(\mathbf{e})|c + e\rangle = \sum_{\mathbf{y} \in \mathbb{F}_q^n} \alpha_{\mathbf{y}}|\mathbf{y}\rangle$ is periodic in the sense that its amplitudes $\alpha_{\mathbf{y}}$ clearly satisfy $\alpha_{\mathbf{y}} = \alpha_{\mathbf{y}+c}$ for any $c$ in $C$. This explains why when we apply the quantum Fourier transform to it, we only get non zero amplitudes on the orthogonal space $C^\perp$. Measuring the final state will give a dual codeword according to a probability distribution proportional to $|\hat{f}|^2$ restricted on the dual code. If $|f(\mathbf{e})|^2$ concentrates its weight on small $e$'s, then it turns out that in many examples of interest $|\hat{f}(\mathbf{y})|^2$ also concentrates on rather small $\mathbf{y}$'s. This gives a way to sample codewords in $C^\perp$ of rather small weight/norm.

In other words, this reduction shows that if we have access to a decoder $\mathcal{A}_{dec}$ for the code $C$ with error distribution $|f|^2$ for our choice of $f$ then we can sample dual codewords according to a distribution proportional to $|\hat{f}|^2$. This reduction works exactly the

same way in $\mathbb{Z}_q^n$ except we apply the Quantum Fourier Transform $\text{QFT}_{\mathbb{Z}_q^n}$ instead. [?] can be viewed as taking in Regev's reduction, codes $C$ which can be decoded efficiently in the injective regime, namely LDPC codes in the case of the sparse max-XORSAT problem and Reed-Solomon codes in the case of the OPI problem, together with a well chosen function $f$, to have a sampler in the dual code which yields interesting solutions of the optimization problem.

**The SIS$_\infty$ and ISIS$_\infty$ problems.** In lattice based cryptography, Regev's reduction has also been shown to be a candidate for giving quantum algorithms that provide a quantum advantage [?]. This concerns the Short Integer Solution with infinity norm, and its inhomogeneous version, which are standard in lattice-based cryptography. These problems can be defined by changing slightly the code alphabet which becomes $\mathbb{Z}_q$ which will conveniently be viewed as $\mathbb{Z}_q = \{-\frac{q-1}{2}, \dots, \frac{q-1}{2}\}$. For $x \in \mathbb{Z}_q$, we define $|x| = x$ iff. $x \in \{0, \dots, \frac{q-1}{2}\}$ and $|x| = -x$ otherwise. Finally, for $x = (x_1, \dots, x_n)$, we define $\|x\|_\infty = \max_i|\llbracket 1,n\rrbracket| |x_i|$. In the case $q$ is prime, we work in $\mathbb{F}_q$ and use the same notation as above.

**PROBLEM 1 (SIS$_\infty$ - SHORT INTEGER SOLUTION WITH INFINITY NORM).**

**Input:** a code $C$ specified by a parity-check matrix $\mathbf{H} \in \mathbb{F}_q^{n \times (n-k)}$ i.e. $C = \{\mathbf{x} \in \mathbb{F}_q^n : \mathbf{Hx}^\top = \mathbf{0}\}$ with prime $q$, an integer $u \in \{0, \dots, \frac{q-1}{2}\}$.

**Goal:** find a non zero $\mathbf{y} = (y_1, \dots, y_n) \in C$ such that $\|\mathbf{y}\|_\infty \le u$.

Many cryptosystems are based on the hardness of SIS$_\infty$ against classical and quantum computers, such as for instance Lyubashevsky's signature schemes [??] or the NIST-standardized DILITHIUM$^1$. A closely related problem is the Inhomogeneous Short Integer Solution with infinity norm.

**PROBLEM 2 (ISIS$_\infty$ - INHOMOGENEOUS SHORT INTEGER SOLUTION WITH INFINITY NORM).**

**Input:** a code $C$ specified by a parity-check matrix $\mathbf{H} \in \mathbb{F}_q^{n \times (n-k)}$ with prime $q$, an integer $u \in \{0, \dots, \frac{q-1}{2}\}$, a random syndrome $s \in \mathbb{F}_q^{n-k}$.

**Goal:** find $\mathbf{y} \in \mathbb{F}_q^n$ such that $\mathbf{H}\mathbf{y}^\top = \mathbf{s}^\top$ and $\|\mathbf{y}\|_\infty \le u$.

[?] gives a polynomial time quantum algorithm for solving the SIS$_\infty$ problem by considering in Regev's reduction a suitable function $f$ such that $\text{Supp}(\hat{f}) \subseteq \{\mathbf{y} \in \mathbb{F}_q^n : \|\mathbf{y}\|_\infty \le u\}$ and by improving Regev's reduction. The improvement comes from noticing that in Regev's reduction instead of solving the classical problem asking to recover $e$ from the noisy codeword $c + e$, we may as well recover $c$ from the knowledge of the quantum superposition $\sum_e f(\mathbf{e})|c + e\rangle$ (this is the so called quantum decoding problem [?]). This can be used to create the superposition $\frac{1}{\sqrt{|C|}} \sum_{c \in C, e \in \mathbb{F}_q^n} f(\mathbf{e})|c + e\rangle$ if we start instead with the superposition $\frac{1}{\sqrt{|C|}} \sum_{c \in C, e \in \mathbb{F}_q^n} f(\mathbf{e})|c + e\rangle|c\rangle$ and use a quantum solver of the quantum decoding problem to erase the second register. There are some reasons to believe that this quantum decoding problem is easier to solve than the classical decoding problem [??]. In [?] the authors are able to achieve this for random linear codes in a regime where $k$ is quite small compared to $n$ thanks to a filtering technique and the Arora-Ge

<footnote>$^1$https://pq-crystals.org/dilithium/</footnote>
algorithm [?]. For the regime of parameters considered in [?], it turns out that the best known algorithms have subexponential complexity.

It is worthwhile to note that Regev's reduction can be easily modified, using the same decoding algorithm in order to construct $\sum_{y \in \nu + C^{\perp}} \hat{f}(y)|y\rangle$ for any $\nu \in \mathbb{F}_q^n$. Indeed, Regev's reduction is slightly modified as follows

$$ \frac{1}{\sqrt{|C|}} \sum_{c \in C, e \in \mathbb{F}_q^n} \chi_c(-\nu) f(e)|c+e\rangle|e\rangle \xrightarrow{\text{Decoder}} \\ \frac{1}{\sqrt{|C|}} \sum_{c \in C, e \in \mathbb{F}_q^n} \chi_c(-\nu) f(e)|c+e\rangle \xrightarrow{\text{QFT}_{\mathbb{F}_q^n}} \\ \frac{q^n}{\sqrt{|C|}} \sum_{y \in \nu + C^{\perp}} \hat{f}(y)|y\rangle. $$

Here $\chi_c$ is the character of $\mathbb{F}_q^n$ associated to $c$ (see §2.2), the Fourier transform over $\mathbb{F}_q^n$ being defined by

$$ \hat{f}(y) \triangleq \frac{1}{\sqrt{q^n}} \sum_{x \in \mathbb{F}_q^n} \chi_y(x)f(x). $$ The fact that the quantum Fourier transform yields a state of the form $\frac{q^n}{\sqrt{|C|}} \sum_{y \in \nu + C^{\perp}} \hat{f}(y)|y\rangle$ follows on the spot from Proposition 3 in §2.2. This means we can solve the (I)SIS$_\infty$ problem for $C^{\perp}$ as long as we have a decoder for $C$ w.r.t. function $f$.

Improving Regev's reduction by taking better decoders. In order to have the most of Regev's reduction, it makes sense to move to decoders which have a better decoding capacity. This is well illustrated in [? ] where Regev's reduction is analyzed in the context of random linear codes and for producing codewords of low Hamming weight. There it is proved that the higher the Hamming weight corrected by the decoding algorithm for $C$, the smaller the weight of the dual codewords which are produced become. In order to have a useful reduction, the authors of [? ] had for many parameters to go beyond the Hamming weight $t$ for which there is always a unique solution to the decoding problem. Another example could be the OPI problem considered in [? ]. As explained above, the authors solve this problem through Regev's reduction applied to Reed-Solomon codes. These codes can be readily decoded by the Berlekamp-Welch decoder which decode all errors up to half the minimum distance of the code. This is precisely the largest Hamming weight for which unique decoding is ensured. Potentially we could improve the OPI quantum algorithm of [? ] by using instead of the Berlekamp-Welch decoder an algorithm which decodes more errors, such as the Guruswami-Sudan list decoder [? ] or the Koetter-Vardy decoding algorithm [? ]. However, this means that we have to use a decoding algorithm beyond the limit where we can ensure that it always recovers from $c+e$ the right error $e$. It would be particularly nice to be able to use the Koetter-Vardy decoding algorithm, since it is able to use soft information. To explain what we mean by this consider a random codeword $c = (c_1, \dots, c_n)$ and assume that we add an error on each coordinate according to some probability function $p: \mathbb{F}_q \to \mathbb{R}_+$. The efficiency of this decoder will not only depend on the amount of errors (i.e., $n(1-p(0))$ on average) but actually on the error distribution in general and this could be helpful to improve the amount of errors that the decoder can correct. Such decoders are called soft decoders. However, there

is an issue: while the Berlekamp-Welch decoder always outputs the correct value, the other decoders work in parameters where there are necessarily some decoding errors. Small errors may not seem very problematic for the overall algorithm but it can actually be devastating as we now recall.

The issue with errors in the decoder. One important technical difficulty when dealing with this family of algorithms is that small errors in the decoding algorithm can lead to large errors when measuring the dual codeword. Say we have a function $f: \mathbb{F}_q^n \to \mathbb{C}$ with $\|f\|_2 = 1$. Now assume there is a decoding algorithm $\mathcal{A}_{dec}$ and a set Good $\subseteq \mathbb{F}_q^n$ such that $\forall c \in C, \forall e \in Good, \mathcal{A}_{dec}(c+e) = e$. In the ideal setting, we want to create $|\phi_{ideal}\rangle$ while we actually create the state $|\phi_{real}\rangle$ where:

$$ |\phi_{\text{ideal}}\rangle = \frac{1}{\sqrt{Z}} \sum_{c \in C} f(e)|c+e\rangle; \quad |\phi_{\text{real}}\rangle = \frac{1}{\sqrt{Z'}} \sum_{e \in \text{Good}} f(e)|c+e\rangle $$

where $Z, Z'$ are normalizing factors. Now assume our decoder succeeds with probability $1 - \epsilon$ which means $\sum_{e \in \text{Good}} |f(e)|^2 = 1 - \epsilon$. It is possible to construct a function $f$ and a decoder where $\epsilon = o(1)$ but $|\langle\phi_{\text{ideal}}|\phi_{\text{real}}\rangle| = \text{negl}(n)$. Some examples of this phenomenon were provided in [? ], and this means that there is no hope of a generic and unconditional reduction between decoding $C$ according to $|f|^2$ and sampling dual codewords according to $|\hat{f}|^2$ in the case we have errors in the decoder. This is a pity, since as explained before in order to improve the reduction we are naturally lead to use decoders which can not decode all errors we are interested in and dealing with this kind of issue is really delicate due to the complicated shape of the errors which can not be decoded by a given code/decoder pair. The example of the previous Reed-Solomon code/Guruswami-Sudan algorithm is an example of this kind.

Another closely related setting is the inhomogeneous setting. Here, we have a random dual syndrome $s$ and we want a reduction theorem that says that if we can decode a code $C$ according to $|f|^2$ in polynomial time then we can sample words from the dual coset $C_s^\perp = \{y \in \mathbb{F}_q^n : H^\perp y^\top = s^\top\}$ according to $|\hat{f}|^2$ where $H^\perp$ is a parity-check matrix of $C^\perp$. The previous case corresponds to the case $s = 0$. The computational complexity of the problem for a random $s$ is most often at least as hard as the homogeneous setting. Moreover, we do not know whether errors in the decoder can cause the reduction to collapse.

## 1.2 Overview of our contributions

We have two main contributions:

(1) We first show a that in the inhomogeneous setting, the reduction always works even with errors in the decoder. This result is generic and captures the full power of quantum algorithms based on Regev's reduction.

(2) We apply the above result for the case of Reed-Solomon codes using the Koetter and Vardy soft decoder. We provide powerful quantum polynomial algorithms for the Optimal Polynomial Interpolation problem. In the particular case of ISIS$_\infty$ on Reed-Solomon codes, we show for example how to solve the problem for $u \approx q/4$ in quantum polynomial
time for $k = \frac{2n}{3}$ while the decoded quantum interferometry algorithm cannot solve this problem except for $k \ge n(1 - o(1))$. This provides improvements on the problems that can be proposed for quantum advantage in this setting.

### 1.2.1 Generic reduction theorem for the inhomogeneous setting.
Our first result is to show that indeed a generic reduction theorem holds in the inhomogeneous setting. This is the first time there is a unconditional reduction with errors in the decoder. This can be considered as an important step for using Regev's reduction beyond the unique decoding regime. As explained before, this is indeed important to improve the quality of the dual codewords we find through this reduction. In order to present our reduction theorem, we first define the problems that will be involved.

**PROBLEM 3 (SYNDROME DECODING - SD(H, p)).**

**Given**: $(H, \mathbf{H}\mathbf{e}^\top)$ where $H \in \mathbb{F}_q^{(n-k)\times n}$ and $\mathbf{e}$ is distributed according to some probability function $p: \mathbb{F}_q^n \to \mathbb{R}_+$.

**Goal**: Find $\mathbf{e}$.

This is basically an equivalent form of the decoding problem we mentioned in the introduction which will be more convenient here. The fact that this is an equivalent form of the decoding problem can be verified as follows. From the knowledge of a noisy code- word $\mathbf{c} + \mathbf{e}$ and a parity-check matrix $\mathbf{H}$ of the code $C$ we want to decode, meaning that $C = \{\mathbf{c} \in \mathbb{F}_q^n : \mathbf{H}\mathbf{c}^\top = \mathbf{0}\}$, we can compute $\mathbf{H}(\mathbf{c} + \mathbf{e})^\top = \mathbf{H}\mathbf{e}^\top$ and use this knowledge to recover $\mathbf{e}$ by solving the syndrome decoding problem.

**DEFINITION 1.** For a probability function $p: \mathbb{F}_q^n \to \mathbb{R}_+$, a parity-check matrix $\mathbf{H} \in \mathbb{F}_q^{(n-k)\times n}$ and a syndrome $\mathbf{s} \in \mathbb{F}_q^{n-k}$, we define the probability function $u_p^{\mathbf{H},\mathbf{s}}$ as follows

$$u_p^{\mathbf{H},\mathbf{s}}(\mathbf{x}) = \begin{cases} \frac{p(\mathbf{x})}{\sum_{\mathbf{x}:\mathbf{H}\mathbf{x}^\top = \mathbf{s}^\top} p(\mathbf{x})} & \text{if } \mathbf{H}\mathbf{x}^\top = \mathbf{s}^\top \\ 0 & \text{otherwise} \end{cases}$$

$u_p^{\mathbf{H},\mathbf{s}}$ corresponds to the probability function $p$ restricted to the coset $\{\mathbf{x} \in \mathbb{F}_q^n : \mathbf{H}\mathbf{x}^\top = \mathbf{s}^\top\}$. In the case $\sum_{\mathbf{x}:\mathbf{H}\mathbf{x}^\top = \mathbf{s}^\top} p(\mathbf{x}) = 0$, we just define the above function to be the null function (in which case we say that sampling from this function always fails).

Basically with the help of an algorithm solving the syndrome decoding problem and Regev's reduction we wish to solve the following coset sampling problem.

**PROBLEM 4 (COSET SAMPLING - CS(H, p)).**

**Given**: $(\mathbf{H}, \mathbf{s})$ where $\mathbf{H} \in \mathbb{F}_q^{(n-k)\times n}$ and $\mathbf{s} \leftarrow \mathbb{F}_q^{n-k}$

**Goal**: sample from the probability function $u_p^{\mathbf{H},\mathbf{s}}$.

Our reduction relates the syndrome decoding problem on a parity-check matrix $\mathbf{H}$ of a code $C$ and the coset sampling problem on a parity-check $\mathbf{H}^\perp$ of the dual code $C^\perp$. It can informally be described as follows

**THEOREM 1 (INFORMAL).** For a function $f: \mathbb{F}_q^n \to \mathbb{C}$, if we have access to an algorithm that efficiently solves SD(H, |f|<fnref n="2" />) with some error $P_{dec} \ge \frac{1}{\text{poly}(n)}$ then we can construct an efficient quantum algorithm for CS(H^⊥, |f|<fnref n="2" />) that will sample outputs with a probability function at least $\frac{1}{\text{poly}(n)}$ close to $u_p^{\mathbf{H},\mathbf{s}}$ on average on s.

Roughly speaking, what this reduction means, is that as soon as we have an algorithm solving the decoding problem with probability at least 1/poly when the error is distributed according to the distribution |f|<fnref n="2" />, then we can efficiently sample in the coset $\{\mathbf{x} \in \mathbb{F}_q^n : \mathbf{H}\mathbf{x}^\top = \mathbf{s}^\top\}$ roughly as the distribution |f|<fnref n="2" /> conditioned that we are in this coset for most of the s's. In other words, this means that we have a way to solve the inhomogeneous decoding/sampling problem for most of entries s.

**Comparison with existing algorithms.** It is natural to compare this theorem with existing similar theorems. Indeed, all the works using quantum algorithms based on Regev's reduction must provide some variant of the above theorem to work.

First, most results deal with the homogeneous case, meaning that $\mathbf{s} = \mathbf{0}$ in the sampling problem. This case works fine when $P_{dec} = 1$ (in which case the faithfulness<fnref n="2" /> is 1) but we know we cannot achieve with Regev's reduction an equivalent of Theorem 1. Indeed, we know examples where $P_{dec} = 1 - o(1)$ but the resulting algorithm has faithfulness negl($n$) (see [?] for some examples). In [?], the authors are in a regime where $1 - P_{dec} \ll q^{-k}$ in which case the reduction works similarly to the perfect setting. They obtain such small errors in the decoder by considering the setting where $n$ is superlinear in $k$. In [?], the authors manage to prove that their real and ideal setting are close by using the randomness of the random oracle inherent to their problem. In the adaptation of Regev's reduction for codes, the authors of [? ] overcome the impossibility result by restricting themselves to real non-negative functions $f$ and also random matrices $\mathbf{H} \in \mathbb{F}_q^n$. In [? ], the authors perform oblivious sampling using Regev's reduction. They use a quantum decoder which is unambiguous i.e. it always outputs the correct value or aborts. In our work, we are in none of the situations above so we cannot use these results.

Finally, the case the closest to our setting is the work of [? ]. They also consider the inhomogeneous setting. They manage to prove something equivalent to Theorem 1. In their setting, they consider random matrices $\mathbf{H}$ according to some specific distribution and need a heuristic on the weight distribution of the underlying codes in order to prove that the reduction works. As a direct consequence, Theorem 1 implies that this claim of [? ] can be done without any heuristic (Conjecture 7.1 from [? ]).

### 1.2.2 Using the KV decoder for solving the S-Polynomial Interpolation problem.
The Koetter-Vardy decoder will allow us to solve a more constrained problem than the OPI problem in a regime of parameters that the [? ] is unable to handle. In a nutshell, instead of trying to obtain a polynomial meeting a large fraction of the intersection constraints in the OPI problem we want to satisfy all of them. This can be rephrased as the following S-Polynomial Interpolation problem.

**PROBLEM 5 (S-POLYNOMIAL INTERPOLATION PROBLEM).**

**Given**: a uniformly random $\mathbf{y} = (y_\alpha)_{\alpha \in \mathbb{F}_q} \in (\mathbb{F}_q)^q$, an integer $k$ in $[1, q]$, a fixed subset $S$ of $\mathbb{F}_q$.

**Goal**: find a polynomial $P(X) \in \mathbb{F}_q[X]$ of degree $< k$ such that $y_\alpha - P(\alpha) \in S$ for any $\alpha \in \mathbb{F}_q$.

<footnote n="2">²See Definition 9 for a definition of faithfulness.</footnote>
Notice here that we consider here the full support setting, i.e., $n = q$. This ensures that the dual of a Reed-Solomon code is a Reed-Solomon code and simplifies a little bit the statements and the discussion, but strictly speaking this is not needed. In a sense, this is a more natural problem than the OPI problem. An important case is when $q$ is prime and $S = \llbracket -u, u \rrbracket$, in which case, this is actually an $\text{ISIS}_\infty$ problem for Reed Solomon codes which is defined more formally in Section 2.5. We call it the $\text{RS-ISIS}_\infty$ problem. Informally, we have a vector $s$ in $\mathbb{F}_q^{q-k}$ and want to find $e$ in $\mathbb{F}_q^q$ such that we have at the same time $\mathbf{He}^\top = \mathbf{s}^\top$ and $\|e\|_\infty \le u$. Here $\mathbf{H}$ is parity-check matrix of a Reed-Solomon code over $\mathbb{F}_q$ of full length $q$.

Using our reduction theorem combined with the Koetter and Vardy soft decoder, we manage to show the following

**THEOREM 2.** Consider any function $f: \mathbb{F}_q \to \mathbb{C}$ s.t. $\text{Supp}(\hat{h}) \in S$ and $\|f\|_2 = 1$. There exists a quantum polynomial time algorithm for the S-P polynomial Interpolation problem defined above as long as $\frac{k}{q} > 1 - \sum_{\alpha \in \mathbb{F}_q} |f(\alpha)|^4$.

Remark that the above theorem, we consider functions $f: \mathbb{F}_q \to \mathbb{C}$ and the corresponding error function is actually $f^{\otimes n}$. In the theorem above, the efficiency of our algorithm depends actually on the choice of the function $f$ and there are many candidates satisfying $\text{Supp}(\hat{f}) \in S$. In the case we pick $\hat{f} = \frac{1}{\sqrt{|S|}} \mathbb{1}_S$, we manage to prove the following, first for the case of a randomly chosen $S$.

**THEOREM 3.** There exists a quantum polynomial time algorithm that solves S-P polynomial Interpolation with parameters $q, k, S$ as long as $\frac{k}{q} < 1 - \rho^2$ where $\rho = \frac{s}{q}$, with high probability over a randomly chosen $S \subseteq \mathbb{F}_q$ of size $s$.

In the specific case of $\text{ISIS}_\infty$, meaning that we take $S = \llbracket -u, u \rrbracket$, we obtain the following stronger result.

**THEOREM 4.** There exists a quantum algorithm that solves $\text{RS-ISIS}_\infty$ with parameters $q, k, u$ as long as $k \ge V(\rho)q$ where $\rho = \frac{|S|}{q} = \frac{2u+1}{q}$ and

$$V(\rho) = \begin{cases} 1 - \frac{2\rho}{3} & \text{for } \rho \le \frac{1}{2} \\ 5 - \frac{10\rho}{3} - \frac{2}{\rho} + \frac{1}{3\rho^2} & \text{for } \rho \ge \frac{1}{2} \end{cases}$$

*Comparison with existing work.* We compare ourselves with the Decoded Quantum Interferometry algorithm of [?] which gives the following

**PROPOSITION 1 ([? ]).** There is a quantum polynomial time algorithm that solves S-P polynomial Interpolation with parameters $q, k, S$ as long as $\frac{k}{q} \ge \min(1, 2 - 2\rho)$ where $\rho = \frac{|S|}{q}$.

The comparison between the three algorithms is depicted in Figure 1.

*How to read this plot.* We can read the above plot as follows. Consider the case $S \approx \frac{q}{2}$, the Decoded Quantum Interferometry will find a polynomial with degree $k \approx q$, no matter the structure of $S$. This is dangerously close to the case when the problem becomes trivial. With our algorithm, we get improvements depending on the structure of $S$. If $S$ is chosen randomly from a subset of size approximately $\frac{q}{2}$, then we can find a polynomial satisfying the

<figure><img src="image_2.png" /><figcaption>**Figure 1:** Minimum admissible degree ratio $R = \frac{k}{n}$ as a function of $\rho = \frac{|S|}{q}$. The (top) purple line corresponds to the Decoded Quantum Interferometry algorithm for S-P polynomial Interpolation. The (middle) green line corresponds to our algorithm for S-P polynomial Interpolation with random $S$ and the (bottom) blue line corresponds to our algorithm with $S = \llbracket -u, u \rrbracket$.</figcaption></figure>

constraints with a degree $k \le \frac{3q}{4}$. Finally, if we additionally have the requirement that $S = \llbracket -u, u \rrbracket$ (with still $|S| \approx \frac{q}{2}$), then our algorithm finds a polynomial satisfying the constraints with a degree $k \le \frac{2q}{3}$.

*Other results.* Even if the uniform function $\hat{f}$ on $S$ is appealing, nothing says that this will be the optimal function in Theorem 2. What we show is that the uniform function is actually in general not optimal. For the special case of $u = 1$ in $\text{SIS}_\infty$, we provide the optimal function that performs better for any $q \ge 5$. We also provide a numerical analysis for $q = 1009$ and all values of $u \in \llbracket 0, (q-1)/2 \rrbracket$ for some non uniform function $\hat{f}$ that slightly outperforms the uniform function. Finally, we present the best known classical algorithm for this problem and compare with our quantum algorithm.

# 2 Preliminaries

## 2.1 Notation

*Sets, finite field.* The finite field with $q$ elements is denoted by $\mathbb{F}_q$. $\mathbb{Z}_q$ denotes the ring of integers modulo $q$. We will represent the elements of $\mathbb{F}_q$ when $q$ is an odd prime as $\mathbb{F}_q = \{-\frac{q-1}{2}, \dots, \frac{q-1}{2}\}$ and also use in this case the notation $\omega_q = e^{\frac{2\pi i}{q}}$. The cardinality of a finite set $\mathcal{E}$ is denoted by $|\mathcal{E}|$. The set of integers $\{a, a+1, \dots, b\}$ between the integers $a$ and $b$ is denoted by $\llbracket a, b \rrbracket$. For a positive integer $n$, $[n]$ denotes $\llbracket 1, n \rrbracket$.

*Vector and matrices.* Vectors are row vectors as is standard in the coding community and $\mathbf{x}^\top$ denotes the transpose of a vector or a matrix. In particular, vectors will always be denoted by bold small letters and matrices with bold capital letters.

*Functions.* Functions defined on $\mathbb{F}_q$ will be denoted by small letters, such as $f$ or $g$, whereas functions defined on $\mathbb{F}_q^n$ we be denoted by capital letters such as $F$ and $G$. The tensor product $f \otimes g$
PROOF. The proposition follows from the following computation

$$
\begin{align*}
|\Omega\rangle &\triangleq \text{QFT}\left(\sum_{c \in C} \sum_{\mathbf{e} \in \mathbb{F}_q^n} F(\mathbf{e}) \chi_c(\nu) |c+\mathbf{e}\rangle\right) \\
&= \sum_{\mathbf{e} \in \mathbb{F}_q^n} F(\mathbf{e}) \sum_{c \in C} \chi_c(\nu) \sum_{\mathbf{y} \in \mathbb{F}_q^n} \chi_{\mathbf{y}(c+\mathbf{e})} |\mathbf{y}\rangle \\
&= \sum_{\mathbf{e} \in \mathbb{F}_q^n} F(\mathbf{e}) \sum_{\mathbf{y} \in \mathbb{F}_q^n} \chi_{\mathbf{y}(\mathbf{e})} |\mathbf{y}\rangle \sum_{c \in C} \chi_c(\nu) \chi_{\mathbf{y}(c)} \\
&= \sum_{\mathbf{e} \in \mathbb{F}_q^n} F(\mathbf{e}) \sum_{\mathbf{y} \in \mathbb{F}_q^n} \chi_{\mathbf{y}(\mathbf{e})} |\mathbf{y}\rangle \sum_{c \in C} \chi_{\mathbf{y}+\nu(c)} \\
&= |C| \sum_{\mathbf{e} \in \mathbb{F}_q^n} F(\mathbf{e}) \sum_{\mathbf{y} \in -\nu+C^{\perp}} \chi_{\mathbf{y}(\mathbf{e})} |\mathbf{y}\rangle \tag{1} \\
&= |C| \sum_{\mathbf{y} \in -\nu+C^{\perp}} |\mathbf{y}\rangle \sum_{\mathbf{e} \in \mathbb{F}_q^n} F(\mathbf{e}) \chi_{\mathbf{y}(\mathbf{e})} \\
&= |C| \sum_{\mathbf{y} \in -\nu+C^{\perp}} \hat{F}(\mathbf{y}) |\mathbf{y}\rangle
\end{align*}
$$

where (1) follows from a slight generalization of (3) of Proposition 2, namely that

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

which follows by a similar reasoning by noticing that $C^{\perp}$ can be
viewed as the set of trivial characters acting on $C$:

$$
\{ \mathbf{y} \in \mathbb{F}_q^n : \chi_{\mathbf{y}}(\mathbf{c}) = 1, \forall \mathbf{c} \in C \} = C^{\perp}.
$$

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

2.3 Coding theory

DEFINITION 4. A q-ary linear code C of dimension k and length is a linear subset of $\mathbb{F}_q^n$. It can be specified by a generating matrix $G \in \mathbb{F}_q^{k \times n}$, in which case

$$
C = \{ \mathbf{x}G : \mathbf{x} \in \mathbb{F}_q^k \}.
$$

It can also be specified by a parity matrix $\mathbf{H} \in \mathbb{F}_q^{(n-k) \times n}$ in which case

$$
C = \{c \in \mathbb{F}_q^n : \mathbf{H}c = \mathbf{0}^T\}.
$$

DEFINITION 5. For a code C specified by a parity matrix $\mathbf{H} \in \mathbb{F}_q^{(n-k) \times n}$ and $\mathbf{s} \in \mathbb{F}_q^{n-k}$, we define $C_s = \{\mathbf{y} \in \mathbb{F}_q^n : \mathbf{H}\mathbf{y}^\top = \mathbf{s}^\top\}$. In particular, $C_0 = C$.

DEFINITION 6. For a code C, a decoding algorithm $\mathcal{A}_{dec}$ takes as input a noisy codeword $\mathbf{c} + \mathbf{e} \in \mathbb{F}_q^n$ and tries to recover $\mathbf{e}$ (hence $\mathbf{c}$). We assume that it always outputs an element in $\mathbb{F}_q^n$. Its success probability for an error probability function $p: \mathbb{F}_q^n \to \mathbb{R}_+$ is given by

$$
P_{\text{dec}} = \Pr_{c \in C, e \leftarrow p} [\mathcal{A}_{\text{dec}}(c + e) = e].
$$

An important class of decoding algorithms consists, when given
a parity-check matrix $\mathbf{H} \in \mathbb{F}_q^{(n-k) \times n}$ of the code and $\mathbf{y} \in \mathbb{F}_q^n$ the
word which is to be decoded, in

(i) computing $\mathbf{s}$ such that $\mathbf{s}^{\top} = \mathbf{H}\mathbf{y}^{\top}$,

(ii) outputting a fixed element $\mathbf{e}$ in $\mathbb{F}_q^n$ of syndrome $\mathbf{s}$ i.e. such that

$\mathbf{H}^{\top} = \mathbf{s}^{\top}$. In other words a fixed element is chosen in $C_s$ and
output by the algorithm.

These algorithms are called syndrome decoders. Equivalently
they are characterized by the following property

DEFINITION 7 (SYNDROME DECODER AND DECODING SET). For a code C specified by its parity-check matrix **H**, a decoding algorithm $\mathcal{A}_{dec}$ is called a syndrome decoder if it outputs for an element **y** ∈ $\mathbb{F}_q^n$ a fixed element in $C_{\mathbf{H}\mathbf{y}^\top}$. The element which is chosen in $C_s$ is denoted by $\mathbf{e}_s$. The set $\mathcal{D} = \{\mathbf{e}_s, \mathbf{s} \in \mathbb{F}_q^{n-k}\}$ is called the decoding set of the syndrome decoder.

Note that by definition the e_s's are precisely the errors which we
can correct by our syndrome decoder. Indeed, for any s ∈ F_q^{n-k}
any c ∈ C, the syndrome decoder outputs by definition e_s when
being fed with c + e_s and never outputs e when being given c + e
for e which does not belong to D. Another important property of
the syndrome decoder is that its answer does not depend on the
codeword c when being given a noisy codeword c + e: we have
A_{dec}(x) = A_{dec}(y) iff. x - y ∈ C.

2.4 Reed-Solomon codes and decoding
algorithms for these codes

An important family of codes which have an efficient decoding
algorithm is given by the family of Reed-Solomon codes. Since we
will also be interested in decoding their dual, it will be convenient to
enlarge a slightly bit the family, so that it is at the same invariant by
taking the dual and so that we can also decode any member of the
family with the same (efficient) decoding algorithm. Generalized
Reed-Solomon codes are the right object here.

DEFINITION 8 ((GENERALIZED) REED-SOLOMON CODES). Let $\mathbf{x} = (x_1, \dots, x_n) \in \mathbb{F}_q^n$ be a vector of pairwise distinct entries and $\mathbf{y} = (y_1, \dots, y_n) \in \mathbb{F}_q^n$ a vector of nonzero entries. The generalized Reed-Solomon (GRS) code $\mathbf{GRS}_k(\mathbf{x}, \mathbf{y})$ with support $\mathbf{x}$, multiplier $\mathbf{y}$ and dimension $k$ is

$$
\mathbf{GRS}_r(\mathbf{x}, \mathbf{y}) \triangleq \{(y_1 P(x_1), \dots, y_n P(x_n)) \mid P \in \mathbb{F}_q[z], \deg P < k\}
$$

A Reed-Solomon code $\mathbf{RS}_k(\mathbf{x})$ of dimension $k$ and support $\mathbf{x}$ is nothing but a GRS code with multiplier the constant 1 vector, i.e.

$$
\mathbf{RS}_k(\mathbf{x}) \triangleq \mathbf{GRS}_k(\mathbf{x}, \mathbf{1}) = \{(P(x_1), \dots, P(x_n)) \mid P \in \mathbb{F}_q[z], \deg P < k\}.
$$

When $\mathbf{x} = (x_\alpha)_{\alpha \in \mathbb{F}_q}$ is of length $q$ and its entries is the whole finite field $\mathbb{F}_q$, then we simply write $\mathbf{RS}_k$ and say it is the full support Reed-Solomon code of dimension $k$.

The dual of a GRS code is also a GRS code as shown by

PROPOSITION 4. [? , Theorem 4, p. 304] Let $\mathbf{GRS}_k(\mathbf{x}, \mathbf{y})$ be a GRS code of length $n$. Its dual is also a GRS code. In particular

$$
\mathbf{GRS}_k(\mathbf{x}, \mathbf{y})^{\perp} = \mathbf{GRS}_{n-k}(\mathbf{x}, \mathbf{y}^{\perp}),
$$

where

$$
\mathbf{y}^{\perp} \triangleq \left( \frac{1}{\pi'_{\mathbf{x}}(x_1) y_1}, \dots, \frac{1}{\pi'_{\mathbf{x}}(x_n) y_n} \right)
$$

and $\pi_x'$ is the derivative of $\pi_x(x) \triangleq \Pi_{i=1}^n (x - x_i)$. We also have

$$
\mathbf{RS}_{k}^{\perp} = \mathbf{RS}_{q-k}
$$
The Koetter and Vardy decoding algorithm has the following performance.

**PROPOSITION 5 ([? ]).** Consider a (generalized) Reed-Solomon code over $\mathbb{F}_q$ of length $n$ and dimension $k$. Let $R = \frac{k}{n}$, a probability function $p: \mathbb{F}_q \to \mathbb{R}$ and let $C_{KV} = \sum_{e \in \mathbb{F}_q} p^2(e)$. If $R < C_{KV}$ then the Koetter-Vardy algorithm is a decoder (as per Definition 6) for $C$ with error function $p$, that finds with probability $1 - e^{-\Omega((\frac{C_{KV}-R}{R})^2n)}$ a list $L$ of size poly($q, n$) that contains the valid codeword.

This means in particular that if $C_{KV}$ is an absolute constant strictly smaller than $R$, then the Koetter-Vardy succeeds wp. $P_{dec} = \frac{1}{\text{poly}(n,d)}$, by choosing a random element of the list $L$. We consider the above decoder but we want it to be deterministic, so we fix beforehand the randomness of the algorithm. Moreover, the Koetter-Vardy decoder is a syndrome decoder.

## 2.5 Computational problems related to Reed-Solomon codes

We now look at specific computational problems related to Reed-Solomon codes that we will study. The first one, which we call S-RSC, is a slightly special case of the Optimal Polynomial Interpolation introduced in [? ]. Recall that we consider here Reed-Solomon codes with full support, i.e. $n = q$.

**PROBLEM 6 (S-RSC PROBLEM).**

**Given:** a uniformly random $s \in \mathbb{F}_q^{q-k}$, an integer $k$ in $[1, q]$, a subset $S$ of $\mathbb{F}_q$, a parity-check matrix $\mathbf{H} \in \mathbb{F}_q^{(q-k) \times q}$ of a full support Reed-Solomon code of dimension $k$.

**Goal:** find $\mathbf{x} = (x_\alpha)_{\alpha \in \mathbb{F}_q} \in \mathbb{F}_q^q$ st. $\mathbf{H}\mathbf{x}^\top = \mathbf{s}^\top$ and $\forall \alpha \in \mathbb{F}_q, x_\alpha \in S$.

This problem can be interpreted as a polynomial interpolation problem.

**PROBLEM 7 (S-POLYNOMIAL INTERPOLATION PROBLEM).**

**Given:** a uniformly random $\mathbf{y} = (y_\alpha)_{\alpha \in \mathbb{F}_q} \in (\mathbb{F}_q)^q$, an integer $k$ in $[1, q]$, a fixed subset $S$ of $\mathbb{F}_q$.

**Goal:** find a polynomial $P(X) \in \mathbb{F}_q[X]$ of degree $< k$ such that $y_\alpha - P(\alpha) \in S$ for any $\alpha \in \mathbb{F}_q$.

An instance of the problem S-Polynomial Interpolation can be transformed in an instance of the S-RSC problem by taking $\mathbf{s}^\top = \mathbf{H}\mathbf{y}^\top$. A solution $\mathbf{e}$ of the latter problem yields a solution of the first, since $\mathbf{y} - \mathbf{e}$ is necessarily a codeword $\mathbf{c}$ of $\mathbf{RS}_k$ and therefore of the form $\mathbf{c} = (P(\alpha))_{\alpha \in \mathbb{F}_q}$. $P$ can be found efficiently by interpolation. The other way round, from $\mathbf{s} \in \mathbb{F}_q^{q-k}$ we find by solving a linear system a solution $\mathbf{y}$ of the linear system $\mathbf{H}\mathbf{y}^\top = \mathbf{s}^\top$. A solution $P(X) \in \mathbb{F}_q[X]$ of the first problem yields a solution $\mathbf{e}$ of the second by taking $\mathbf{e}_\alpha = y_\alpha - P(\alpha)$ for any $\alpha \in \mathbb{F}_q$.

A particular case is when $S = [-u, u]$. In this case, the problem is actually an $\text{ISIS}_\infty$ problem on Reed-Solomon codes.

**PROBLEM 8 (RS-ISIS$_\infty$ PROBLEM).**

**Given:** a uniformly random $\mathbf{s} \in \mathbb{F}_q^{q-k}$, an integer $k$ in $[1, q]$, an integer $u \in [0, \frac{q-1}{2}]$, a parity-check matrix $\mathbf{H} \in \mathbb{F}_q^{(q-k) \times q}$ of a full support Reed-Solomon code of dimension $k$.

**Goal:** find $\mathbf{x} = (x_\alpha)_{\alpha \in \mathbb{F}_q} \in \mathbb{F}_q^q$ st. $\mathbf{H}\mathbf{x}^\top = \mathbf{s}^\top$ and $\|\mathbf{x}\|_\infty \le u$.

We study both the more general problem with a discussion the choice of $S$ and also put a special focus on the $\text{RS-ISIS}_\infty$ problem, where our algorithms will be the most efficient and which will give the best quantum advantage.

## 3 General reduction

In this section, our goal is to present a general reduction from the syndrome decoding problem of a code $C$ to a coset sampling problem in the dual code $C^\perp$. Unless specified otherwise $C$ is a code defined over a finite $\mathbb{F}_q$ where $q$ is a prime power.

### 3.1 Statement of the theorem

We refer to the definitions for syndrome decoding and coset sampling presented in Section 1.2.1, as well as the definition of the probability function $u_p^{\mathbf{H},s}$. In our setting, we will have a sampler for the coset sampling problem that will have some errors. We define the faithfulness of such an algorithm as follows

**DEFINITION 9 (FAITHFULNESS OF A CS SOLVER).** Consider an algorithm $\mathcal{A}(\mathbf{H}, s)$ with $\mathbf{H} \in \mathbb{F}_q^{(n-k) \times n}$. Let $t_s: \mathbb{F}_q^n \to \mathbb{R}_+$ be probability functions defined as

$$t_s(\mathbf{x}) \stackrel{\Delta}{=} \Pr[\mathcal{A}(\mathbf{H}, s) \text{ outputs } \mathbf{x}]$$

We say that $\mathcal{A}$ solves CS($\mathbf{H}, p$) with faithfulness $\gamma$ if $\mathbb{E}_{s \leftarrow \mathbb{F}_q^{n-k}} [\Delta(t_s, u_p^{\mathbf{H},s})] \le 1 - \gamma$.

We can now provide the formal statement of our reduction.

**THEOREM 5.** Let $C$ be a $q$-ary code specified by the parity-check matrix $\mathbf{H} \in \mathbb{F}_q^{(n-k) \times n}$. Let $\mathbf{H}^\perp$ be a parity-check matrix of the dual code $C^\perp$. Let $F: \mathbb{F}_q^n \to \mathbb{C}$ with $\|F\| = 1$. Assume that:

(1) we have access to an algorithm that solves $\text{SD}(\mathbf{H}, |F|^2)$ with probability $P_{dec}$, and runs in time $T_{dec}$.

(2) we have access to a quantum algorithm that outputs the superposition $\sum_{e \in \mathbb{F}_q^n} F(e)|e\rangle$, and runs in time $T_F$.

Then, we can construct a quantum algorithm that solves CS($\mathbf{H}^\perp$, $|\hat{F}|^2$) with faithfulness $\gamma = 1 - \sqrt{1 - P_{dec}}$ which runs in time $O(\frac{1}{P_{dec}}(T_{dec} + T_F))$.

Notice that the above works for any parity matrix $\mathbf{H}$ (without the need of having random matrices for instance). The only price we pay is that we are in the inhomogeneous setting but as we discussed, such a reduction doesn't hold in the homogeneous setting. Notice also that the second condition, i.e. being able to efficiently construct $\sum_{e \in \mathbb{F}_q^n} F(e)|e\rangle$ is necessary for all quantum algorithms based on Regev's reduction.

Notice that an algorithm $\mathcal{A}$ for solving $\text{SD}(\mathbf{H}, |F|^2)$ is in particular a syndrome decoder for the code $C$ associated to the parity matrix $\mathbf{H}$, with error $|F|^2$.

### 3.2 A first technical proposition

The following statement is here to deal with errors in the decoding algorithm. We want to compare the obtained state in the ideal setting (with an error function $F$) after the first step of Regev's reduction with the real setting, with an error function $G$.
**PROPOSITION 6.** Let $C$ be a linear code described by a parity-check matrix $\mathbf{H} \in \mathbb{F}_q^{(n-k) \times n}$. Let $F, G: \mathbb{F}_q^n \to \mathbb{C}$ such that $\|F\|_2 = \|G\|_2 = 1$ where $G$ also satisfies for each $\mathbf{v} \in \mathbb{F}_q^n$

$$ \| \sum_{c \in C, \mathbf{e} \in \mathbb{F}_q^n} G(\mathbf{e}) \chi_c(\mathbf{v}) |c+\mathbf{e}\rangle \|^2 = q^k. \quad (2) $$

Let $|U_{\mathbf{v}}^F\rangle = \sum_{c \in C, \mathbf{e} \in \mathbb{F}_q^n} F(\mathbf{e}) \chi_c(\mathbf{v}) |c+\mathbf{e}\rangle$ and $Z_{\mathbf{v}}^F \triangleq \| |U_{\mathbf{v}}^F\rangle \|^2$, and $V \triangleq \{\mathbf{v} \in \mathbb{F}_q^n : Z_{\mathbf{v}}^F \neq 0\}$. For each $\mathbf{v} \in \mathbb{F}_q^n$, we define the vectors

$$ |\phi_{\mathbf{v}}^F\rangle \triangleq \frac{1}{\sqrt{Z_{\mathbf{v}}^F}} \sum_{c \in C, \mathbf{e} \in \mathbb{F}_q^n} F(\mathbf{e}) \chi_c(\mathbf{v}) |c+\mathbf{e}\rangle \quad \text{if } \mathbf{v} \in V $$

$$ |\phi_{\mathbf{v}}^F\rangle \triangleq \mathbf{0} \quad (\text{the null vector}) \qquad \text{otherwise} $$

Notice that $|\phi_{\mathbf{v}}^F\rangle$ is a unit vector for $\mathbf{v} \in V$. For each $\mathbf{v} \in \mathbb{F}_q^n$, we also define the unit vectors $|\phi_{\mathbf{v}}^G\rangle \triangleq \frac{1}{\sqrt{q^k}} \sum_{c \in C, \mathbf{e} \in \mathbb{F}_q^n} G(\mathbf{e}) \chi_c(\mathbf{v}) |c+\mathbf{e}\rangle$. We have

$$ \mathbb{E}_{\mathbf{v} \leftarrow \mathbb{F}_q^n} \left[ |\langle \phi_{\mathbf{v}}^F | \phi_{\mathbf{v}}^G \rangle|^2 \right] \geq \left| \sum_{\mathbf{e} \in \mathbb{F}_q^n} \overline{F(\mathbf{e})} G(\mathbf{e}) \right|^2. $$

**PROOF.** We write for $\mathbf{v} \in V$.

$$ \begin{aligned} \langle \phi_{\mathbf{v}}^F | \phi_{\mathbf{v}}^G \rangle &= \frac{1}{\sqrt{Z_{\mathbf{v}}^F q^k}} \sum_{c, c' \in C} \sum_{\mathbf{e}, \mathbf{e}' \in \mathbb{F}_q} \chi_{c'-c}(\mathbf{v}) \overline{F(\mathbf{e})} G(\mathbf{e}') \\ &= \frac{1}{\sqrt{Z_{\mathbf{v}}^F q^k}} \sum_{c' \in C} \sum_{c \in C} \sum_{\mathbf{e}' \in \mathbb{F}_q} \chi_{c'-c}(\mathbf{v}) \overline{F(\mathbf{e}'+c'-c)} G(\mathbf{e}') \\ &= \frac{1}{\sqrt{Z_{\mathbf{v}}^F q^k}} \sum_{c' \in C} \sum_{c \in C} \sum_{\mathbf{e}' \in \mathbb{F}_q} \chi_c(\mathbf{v}) \overline{F(\mathbf{e}'+c)} G(\mathbf{e}') \\ &= \frac{\sqrt{q^k}}{\sqrt{Z_{\mathbf{v}}^F}} \sum_{c \in C} \sum_{\mathbf{e} \in \mathbb{F}_q^n} \chi_c(\mathbf{v}) \overline{F(\mathbf{e}+c)} G(\mathbf{e}) \end{aligned} $$

We now prove two short lemmata that will then allow us to apply a Cauchy-Schwartz inequality to bound the expected value of $|\langle \phi_{\mathbf{v}}^F | \phi_{\mathbf{v}}^G \rangle|^2$.

**LEMMA 1.** $\mathbb{E}_{\mathbf{v} \leftarrow \mathbb{F}_q^n} [Z_{\mathbf{v}}^F] = q^k$.

**PROOF.** Using similar calculations as the ones to compute $\langle \phi_{\mathbf{v}}^G | \phi_{\mathbf{v}}^F \rangle$, we can write

$$ \begin{aligned} Z_{\mathbf{v}}^F &= \| \sum_{c \in C, \mathbf{e} \in \mathbb{F}_q^n} F(\mathbf{e}) \chi_c(\mathbf{v}) |c+\mathbf{e}\rangle \|^2 \\ &= \sum_{c, c' \in C} \sum_{\mathbf{e}, \mathbf{e}' \in \mathbb{F}_q} \chi_{c'-c}(\mathbf{v}) \overline{F(\mathbf{e})} F(\mathbf{e}') \\ &= \sum_{c' \in C} \sum_{c \in C} \sum_{\mathbf{e}' \in \mathbb{F}_q} \chi_{c'-c}(\mathbf{v}) \overline{F(\mathbf{e}'+c'-c)} F(\mathbf{e}') \\ &= \sum_{c' \in C} \sum_{c \in C} \sum_{\mathbf{e}' \in \mathbb{F}_q} \chi_c(\mathbf{v}) \overline{F(\mathbf{e}'+c)} F(\mathbf{e}') \\ &= q^k \sum_{c \in C} \sum_{\mathbf{e} \in \mathbb{F}_q^n} \chi_c(\mathbf{v}) \overline{F(\mathbf{e}+c)} F(\mathbf{e}). \end{aligned} $$

We then write

$$ \begin{aligned} \mathbb{E}_{\mathbf{v} \leftarrow \mathbb{F}_q^n} [Z_{\mathbf{v}}^F] &= \frac{1}{q^n} \sum_{\mathbf{v} \in \mathbb{F}_q^n} q^k \sum_{c \in C} \sum_{\mathbf{e} \in \mathbb{F}_q^n} \chi_c(\mathbf{v}) \overline{F(\mathbf{e}+c)} F(\mathbf{e}) \\ &= \frac{q^k}{q^n} \sum_{c \in C} \left( \sum_{\mathbf{v} \in \mathbb{F}_q^n} \chi_c(\mathbf{v}) \right) \sum_{\mathbf{e} \in \mathbb{F}_q^n} \overline{F(\mathbf{e}+c)} F(\mathbf{e}) \end{aligned} $$

Now, notice that $\sum_{\mathbf{v} \in \mathbb{F}_q^n} \chi_c(\mathbf{v}) = q^n$ for $c = 0$ and $\sum_{\mathbf{v} \in \mathbb{F}_q^n} \chi_c(\mathbf{v}) = 0$ otherwise. This means we can conclude

$$ \mathbb{E}_{\mathbf{v} \leftarrow \mathbb{F}_q^n} [Z_{\mathbf{v}}^F] = q^k \sum_{\mathbf{e} \in \mathbb{F}_q^n} \overline{F(\mathbf{e})} F(\mathbf{e}) = q^k \|F\|^2 = q^k. $$

**LEMMA 2.** Let $\beta_{\mathbf{v}} \triangleq \sqrt{\frac{1}{q^k}} \langle U_{\mathbf{v}}^F | \phi_{\mathbf{v}}^G \rangle = \sum_{c \in C, \mathbf{e} \in \mathbb{F}_q^n} \chi_c(\mathbf{v}) \overline{F(\mathbf{e}+c)} G(\mathbf{e})$. We have

$$ \mathbb{E}_{\mathbf{v} \leftarrow \mathbb{F}_q^n} [ |\beta_{\mathbf{v}}| ] \geq \left| \sum_{\mathbf{e}} \overline{F(\mathbf{e})} G(\mathbf{e}) \right|. $$

**PROOF.** We write

$$ \begin{aligned} \mathbb{E}_{\mathbf{v} \leftarrow \mathbb{F}_q^n} [ |\beta_{\mathbf{v}}| ] &\geq \left| \frac{1}{q^n} \sum_{\mathbf{v} \in \mathbb{F}_q^n} \beta_{\mathbf{v}} \right| \\ &= \frac{1}{q^n} \left| \sum_{c \in C} \left( \sum_{\mathbf{v} \in \mathbb{F}_q^n} \chi_c(\mathbf{v}) \right) \sum_{\mathbf{e} \in \mathbb{F}_q^n} \overline{F(\mathbf{c}+\mathbf{e})} G(\mathbf{e}) \right| \\ &= \left| \sum_{\mathbf{e}} \overline{F(\mathbf{e})} G(\mathbf{e}) \right|, \end{aligned} $$

where we used the same argument as in the previous lemma for determining the sum $\sum_{\mathbf{v} \in \mathbb{F}_q^n} \chi_c(\mathbf{v})$. $\square$

We can now conclude. Notice that $|\beta_{\mathbf{v}}| = \frac{\sqrt{Z_{\mathbf{v}}^F}}{\sqrt{q^k}} |\langle \phi_{\mathbf{v}}^F | \phi_{\mathbf{v}}^G \rangle|$ for each $\mathbf{v} \in \mathbb{F}_q^n$ since $|U_{\mathbf{v}}^F\rangle = \sqrt{Z_{\mathbf{v}}^F} |\phi_{\mathbf{v}}^G\rangle$. Using the Cauchy-Schwartz inequality, we have

$$ \left( \mathbb{E}_{\mathbf{v} \leftarrow \mathbb{F}_q^n} [ |\beta_{\mathbf{v}}| ] \right)^2 \leq \mathbb{E}_{\mathbf{v} \leftarrow \mathbb{F}_q^n} \left[ \frac{Z_{\mathbf{v}}^F}{q^k} \right] \mathbb{E}_{\mathbf{v} \leftarrow \mathbb{F}_q^n} \left[ |\langle \phi_{\mathbf{v}}^F | \phi_{\mathbf{v}}^G \rangle|^2 \right], $$

which allows us to conclude

$$ \begin{aligned} \mathbb{E}_{\mathbf{v} \leftarrow \mathbb{F}_q^n} \left[ |\langle \phi_{\mathbf{v}}^F | \phi_{\mathbf{v}}^G \rangle|^2 \right] &\geq q^k \frac{\left( \mathbb{E}_{\mathbf{v} \leftarrow \mathbb{F}_q^n} [ |\beta_{\mathbf{v}}| ] \right)^2}{\mathbb{E}_{\mathbf{v} \leftarrow \mathbb{F}_q^n} [ Z_{\mathbf{v}}^F ]} \\ &= \left| \sum_{\mathbf{e}} \overline{F(\mathbf{e})} G(\mathbf{e}) \right|^2, \end{aligned} $$

where we used our two lemmata for the last inequality. $\square$

The constraint on $G$ (Equation 2 in the above Proposition) may seem quite stringent. However all decoders we consider here (and most decoders in general) will produce with our algorithm a state $|\phi_{\mathbf{v}}^G\rangle$ where $G$ satisfies this property, so we will be able to widely use this proposition. This is characterized by the following proposition.
**PROPOSITION 7.** Let $\mathbf{H} \in \mathbb{F}_q^{(n-k)\times n}$ be a parity matrix and let $\mathcal{D} \subseteq \mathbb{F}_q^n$ such that the mapping which associates to $\mathbf{e} \in \mathbb{F}_q^n$ its syndrome $\mathbf{He}^\mathrm{T}$ is one to one on $\mathcal{D}$. Let $\mathbf{G} : \mathbb{F}_q^n \to \mathbb{C}$ be such that $\mathrm{Supp}(\mathbf{G}) \subseteq \mathcal{D}$ and $\|\mathbf{G}\| = 1$. Then for each $\mathbf{v} \in \mathbb{F}_q^n$, we have

$$ \| \sum_{c \in C, \mathbf{e} \in \mathbb{F}_q^n} G(\mathbf{e}) \chi_c(\mathbf{v}) |c+\mathbf{e}\rangle \|^2 = q^k. $$

**PROOF.** We write

$$ \| \sum_{c \in C, \mathbf{e} \in \mathbb{F}_q^n} G(\mathbf{e}) \chi_c(\mathbf{v}) |c+\mathbf{e}\rangle \|^2 = \sum_{c, c' \in C} \sum_{\substack{\mathbf{e}, \mathbf{e}' \in \mathcal{D} \\ c+\mathbf{e}=c'+\mathbf{e}'}} \chi_{c-c'}(\mathbf{v}) G(\mathbf{e}) \overline{G(\mathbf{e}')} $$

Using the property on $\mathcal{D}$, we have that for $c, c' \in C$ and $\mathbf{e}, \mathbf{e}' \in \mathcal{D}$, $(c+\mathbf{e} = c' + \mathbf{e}') \Rightarrow (c, \mathbf{e}) = (c', \mathbf{e}')$. We can therefore rewrite the above sum as

$$ \| \sum_{c \in C, \mathbf{e} \in \mathbb{F}_q^n} G(\mathbf{e}) \chi_c(\mathbf{v}) |c+\mathbf{e}\rangle \|^2 = \sum_{c \in C} \sum_{\mathbf{e} \in \mathcal{D}} G(\mathbf{e}) \overline{G(\mathbf{e})} = q^k \|\mathbf{G}\|^2 = q^k. $$

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

This proposition will actually imply that we can use our proposition from any state arising from a syndrome decoder - which can be immediately obtained from an algorithm that solves the SD(H, p) problem.

## 3.3 Analysis of the general algorithm

The goal of this section is now to prove Theorem 5. We present the quantum algorithm based on Regev's reduction that performs this reduction. The algorithm uses a syndrome decoder $\mathcal{A}_{dec}$ (which can be directly obtained from an algorithm $\mathcal{A}$ that solves SD(H, $|F|^2$)) and then construct a certain state $|\psi_v\rangle$. Our dual coset sampler will consist of constructing this state and then measuring it in the computational basis.

### Algorithm 1: shifted dual code sampler from a primal decoder

**Input:**

* A linear code $C \in \mathbb{F}_q^n$ of dimension $k$ described by a parity-check matrix $\mathbf{H} \in \mathbb{F}_q^{n-k\times n}$,

* a function $F \in \mathbb{F}_q^n \to \mathbb{C}$ of norm 1,

* an element $\mathbf{v} \in \mathbb{F}_q^n$.

**Decoder:** a syndrome decoder $\mathcal{A}_{dec}$ of $C$ for the error function $|F|^2$ that succeeds with probability $P_{dec}$. We denote by $\mathcal{D}$ the decoding set of $\mathcal{A}_{dec}$.

**Goal:** Use $\mathcal{A}_{dec}$ in order to construct a state $|\psi_v\rangle$ which is not too far from a state proportional to $\sum_{\mathbf{y} \in -\mathbf{v}+C^\perp} \hat{F}(\mathbf{y})|\mathbf{y}\rangle$.

**Algorithm:**

(1) $\frac{1}{\sqrt{q^k}} \sum_{c \in C} \chi_c(\mathbf{v}) |c\rangle \otimes \sum_{\mathbf{e} \in C} F(\mathbf{e}) |\mathbf{e}\rangle$

(2) $\mapsto \frac{1}{\sqrt{q^k}} \sum_{c \in C, \mathbf{e} \in \mathbb{F}_q^n} F(\mathbf{e}) \chi_c(\mathbf{v}) |c+\mathbf{e}\rangle |\mathbf{e}\rangle$

(3) $\mapsto \frac{1}{\sqrt{q^k}} \sum_{c \in C, \mathbf{e} \in \mathbb{F}_q^n} F(\mathbf{e}) \chi_c(\mathbf{v}) |c+\mathbf{e}\rangle |\mathbf{e} - \mathcal{A}_{dec}(c+\mathbf{e})\rangle$

(4) if not 0 start again until getting

$$ |\Psi_v^1\rangle = \frac{1}{\sqrt{q^k P_{dec}}} \sum_{c \in C, \mathbf{e} \in \mathcal{D}} F(\mathbf{e}) \chi_c(\mathbf{v}) |c+\mathbf{e}\rangle $$

(5) $\mapsto |\psi_v\rangle = |\Psi_v^1\rangle$

(1) Initial state. (2) add $\mathbf{e}$ to $c$. (3) apply coherently $\mathcal{A}_{dec}$. (4) measure last register. (5) apply $QFT_q^n$.

The following theorem analyzes this algorithm

**THEOREM 6.** Let $C$ be a linear code and let $F : \mathbb{F}_q^n \to \mathbb{C}$ such that $\|F\|_2 = 1$. Assume we have a syndrome decoder $\mathcal{A}_{dec}$ that succeeds with probability $P_{dec}$. Let $|\Phi_v\rangle \stackrel{\Delta}{=} \frac{1}{\sqrt{Y_v^F}} \sum_{\mathbf{y} \in -\mathbf{v}+C^\perp} \hat{F}(\mathbf{y})|\mathbf{y}\rangle$, where $Y_v^F$ is a normalizing constant which makes this state to be a unit vector. If $\hat{F}$ is zero on all $-\mathbf{v}+C^\perp$, then $|\Phi_v\rangle$ is defined to be the zero vector. Then the above algorithm constructs a state $|\psi_v\rangle$ such that

$$ \mathbb{E}_{v \in \mathbb{F}_q^n} [ |\langle \Phi_v | \psi_v \rangle|^2 ] = P_{dec}. $$

**PROOF.** In the algorithm, after applying the decoder $\mathcal{A}_{dec}$, we have the state

$$ |\Psi_v^0\rangle = \frac{1}{\sqrt{q^k}} \sum_{c \in C} \sum_{\mathbf{e} \in E} F(\mathbf{e}) \chi_c(\mathbf{v}) |c+\mathbf{e}\rangle |\mathbf{e} - \mathcal{A}_{dec}(c+\mathbf{e})\rangle. $$

Let $\mathcal{D} \subseteq \mathbb{F}_q^n$ be the decoding set of $\mathcal{A}_{dec}$. We can rewrite the above as

$$ |\Psi_0\rangle = \frac{1}{\sqrt{q^k}} \sum_{c \in C} \sum_{\mathbf{e} \in \mathcal{D}} F(\mathbf{e}) \chi_c(\mathbf{v}) |c+\mathbf{e}\rangle |0^n\rangle + \sum_{\mathbf{x} \neq \mathbf{0}} |W_{\mathbf{x}}\rangle |\mathbf{x}\rangle. $$

$\mathcal{D}$ has also the property that the mapping $\mathbf{e} \mapsto \mathbf{He}^\mathrm{T}$ is one to one on $\mathcal{D}$. Here $\mathbf{H}$ denotes any parity-check matrix of $C$. The success probability of the decoding algorithm is $P_{dec} = \sum_{\mathbf{e} \in \mathcal{D}} |F(\mathbf{e})|^2$. Let $\mathbf{G}$ be the function such that $G(\mathbf{e}) = \frac{F(\mathbf{e})}{\sqrt{P_{dec}}}$ for $\mathbf{e} \in \mathcal{D}$ and $G(\mathbf{e}) = 0$ otherwise. Using Proposition 7, we have that

$$ \| \sum_{c \in C} \sum_{\mathbf{e} \in \mathbb{F}_q^n} G(\mathbf{e}) \chi_c(\mathbf{v}) |c+\mathbf{e}\rangle |0^n\rangle \|^2 = q^k \quad (3) $$
and conditioned on measuring $0^n$ in the second register, we obtain the unit vector

$$|\Psi_{\nu}^{1}\rangle = \frac{1}{\sqrt{q^k}} \sum_{c \in C} \sum_{\boldsymbol{e} \in \mathbb{F}_{q}^{n}} G(\boldsymbol{e}) \chi_{c}(\boldsymbol{v}) |c + \boldsymbol{e}\rangle.$$

Let $Z_{\nu}^{F} \triangleq \|\sum_{c \in C, \boldsymbol{e} \in \mathbb{F}_{q}^{n}} F(\boldsymbol{e})\chi_{c}(\boldsymbol{v}) |c + \boldsymbol{e}\rangle\|^{2}$, and $V \triangleq \{\boldsymbol{v} \in \mathbb{F}_{q}^{n} : Z_{\nu}^{F} \neq 0\}$. For each $\boldsymbol{v} \in \mathbb{F}_{q}^{n}$, we define the ‘ideal” vectors

$$|\phi_{\nu}^{F}\rangle \triangleq \frac{1}{\sqrt{Z_{\nu}^{F}}} \sum_{c \in C, \boldsymbol{e} \in \mathbb{F}_{q}^{n}} F(\boldsymbol{e}) \chi_{c}(\boldsymbol{v}) |c + \boldsymbol{e}\rangle \quad \text{if } \boldsymbol{v} \in V$$

$$|\phi_{\nu}^{F}\rangle \triangleq 0 \quad (\text{the null vector}) \qquad \text{otherwise}$$

Thanks to Equation 3, we can use Proposition 6 and obtain

$$\mathbb{E}_{\boldsymbol{v} \leftarrow \mathbb{F}_{q}^{n}} \left[ |\langle \Psi_{\boldsymbol{v}}^{1} | \phi_{\boldsymbol{v}}^{F} \rangle|^{2} \right] \geq \left| \sum_{\boldsymbol{e} \in \mathbb{F}_{q}^{n}} \overline{F(\boldsymbol{e})} G(\boldsymbol{e}) \right|^{2} = \left( \frac{1}{\sqrt{P_{\text{dec}}}} \sum_{\boldsymbol{e} \in D} |F(\boldsymbol{e})|^{2} \right)^{2} \\ = P_{\text{dec}}.$$

Also, notice that by using Proposition 3 we have $|\phi_{\nu}^{F}\rangle = |\Phi_{\nu}\rangle$. Since we also have by definition of $|\psi_{\nu}\rangle$, $|\tilde{\Psi}_{\nu}^{1}\rangle = |\tilde{\psi}_{\nu}\rangle$, we can conclude

$$\mathbb{E}_{\boldsymbol{v} \leftarrow \mathbb{F}_{q}^{n}} \left[ |\langle \Phi_{\boldsymbol{v}} | \psi_{\boldsymbol{v}} \rangle|^{2} \right] = \mathbb{E}_{\boldsymbol{v} \leftarrow \mathbb{F}_{q}^{n}} \left[ |\langle \Psi_{\boldsymbol{v}}^{1} | \phi_{\boldsymbol{v}}^{F} \rangle|^{2} \right] \geq P_{\text{dec}}. \quad \square$$

**COROLLARY 1.** Take the above algorithm for a fixed $s \in \mathbb{F}_{q}^{k}$ a given parity-check matrix $H^{\perp}$ of $C^{\perp}$ and any $\boldsymbol{v} \in \mathbf{V}$. $-H^{\perp}\boldsymbol{v}^{\top} = s^{\top}$, and measure the state $|\psi_{\boldsymbol{v}}\rangle$ in the computational basis. Let $t_{s}(\boldsymbol{y})$ be the probability of measuring each $\boldsymbol{y}$. We have

$$\mathbb{E}_{s \leftarrow \mathbb{F}_{q}^{k}} \left[ \Delta(t_{s}, u_{|\tilde{F}|^{2}}^{H^{\perp}, s}) \leq \sqrt{1 - P_{\text{dec}}} \right].$$

**PROOF.** Using the above notation, we have that $|\phi_{\nu}^{F}\rangle = |\Phi_{\nu}\rangle$ is a unit vector proportional to $\sum_{\boldsymbol{y} \in -\nu + C^{\perp}} \tilde{F}(\boldsymbol{y})|\boldsymbol{y}\rangle$ which means that if this state is measured in the computational basis, we get $\boldsymbol{y}$ with probability $u_{|\tilde{F}|^{2}}^{H^{\perp}, s}(\boldsymbol{y})$. Now the algorithm produces a state $|\psi_{\nu}\rangle$, and measuring it in the computational basis gives $\boldsymbol{y}$ with probability $t_{s}$. From there, we have

$$\Delta(t_s, u_{|\tilde{F}|^2}^{H^\perp, s}) \le \Delta(|\Phi_\nu\rangle, |\psi_\nu\rangle),$$

where we use the fact that the trace distance of two quantum pure states $\sum_{x} a(x)|x\rangle$ and $\sum_{x} b(x)|x\rangle$ is at least as large as the trace distance between $|a|^2$ and $|b|^2$ (see [?] for instance). This allows us to conclude

$$\mathbb{E}_{s \leftarrow \mathbb{F}_{q}^{k}} \left[ \Delta(t_s, u_{|\tilde{F}|^2}^{H^{\perp}, s}) \right] \le \mathbb{E}_{s \leftarrow \mathbb{F}_{q}^{k}} \left[ \sqrt{1 - |\langle \Phi_{\nu} | \psi_{\nu} \rangle|^2} \right] \\ \le \sqrt{1 - \mathbb{E}_{s \leftarrow \mathbb{F}_{q}^{k}} \left[ |\langle \Phi_{\nu} | \psi_{\nu} \rangle|^2 \right]} = \sqrt{1 - P_{\text{dec}}}.$$

where we use Jensen's inequality and the concavity of $x \to \sqrt{1-x^2}$ on $[0, 1]$. This proves our corollary. $\square$

**Running time of the algorithm.** Let $T_F$ be the time required to compute $\sum_e F(\boldsymbol{e})|\boldsymbol{e}\rangle$. Let $T_{\mathcal{A}_{\text{dec}}}$ be the running time of the decoder. The above algorithm runs in average time $O(\frac{1}{P_{\text{dec}}}(T_F + T_{\mathcal{A}_{\text{dec}}}))$. The corollary and the running time give immediately Theorem 5.

Notice that the above can be improved to $O(\frac{1}{\sqrt{P_{\text{dec}}}}(T_F + T_A))$ if needed using quantum amplitude amplification instead of measuring just the final register and conditioning on obtaining $0^n$. We work in regimes where there this has little impact but could be an interesting remark in other settings.

## 3.4 Solving the S-Polynomial Interpolation problem by using the KV decoder

We will now instantiate the above algorithm with Reed-Solomon codes using the Koetter-Vardy decoder. Our problem of interest will be the S-RSC problem defined in Section 2.5, which is equivalent to S-Polynomial Interpolation. Recall that since we consider full support Reed-Solomon codes, we have $n = q$. We consider the following algorithm

**Algorithm 2 solving S-RSC**

**Input:** A parity-check matrix $H' \in \mathbb{F}_{q}^{(q-k) \times q}$ of $C' = \mathbf{RS}_k$, a subset $S$ of $\mathbb{F}_q$, a random syndrome $s \in \mathbb{F}_q^{q-k}$.

**Parameter:** a function $f: \mathbb{F}_q \to \mathbb{C}$ such that $\text{Supp}(\hat{f}) \subseteq S$ and $\|f\| = 1$.

**Algorithm:**

(1) Let $H \in \mathbb{F}_{q}^{k,q}$ be a parity matrix of $C = (C')^{\perp}$. Run Algorithm 1 on $H$ with $n = q, k = q - k'$, with $F = f^{\otimes n}$, and using the Koetter-Vardy decoder $\mathcal{A}_{KV}$.

(2) Let $\boldsymbol{y}$ be the output of Algorithm 1 with these parameters. If $\boldsymbol{y}$ is a correct solution to our S-RSC instance, output $\boldsymbol{y}$, otherwise repeat.

**THEOREM 7.** The above quantum algorithm solves in polynomial time the S-RSC problem as long as $\frac{k'}{q} > 1 - \sum_{\alpha \in \mathbb{F}_q} |f(\alpha)|^4$.

**PROOF.** Using notations from Section 3.3, notice that if we sample according $u_{|\tilde{F}|^2}^{H', s}$ then we always output a valid solution $\boldsymbol{y}$. From Corollary 1, we output a valid solution $\boldsymbol{y}$ wp. at least $1 - \sqrt{1 - P_{\text{dec}}}$ on average on $s$. $P_{\text{dec}}$ here is the success probability of the KV decoder. From Proposition 5, we know that $P_{\text{dec}} \ge \frac{1}{\text{poly}(q)}$ as long as $\frac{k}{q} < \sum_{\alpha \in \mathbb{F}_q} |f(\alpha)|^4$ which implies $\frac{k'}{q} > 1 - \sum_{\alpha \in \mathbb{F}_q} |f(\alpha)|^4$. When this happens, we will repeat Step 2 at most poly($q$) times and our whole algorithm runs in quantum polynomial time. $\square$

With this algorithm, we can provide efficient quantum algorithms for the S-Polynomial Interpolation problem as described in Section 1.2.2. We refer to the full paper for proofs of these statements and further discussion.
Acknowledgments

We acknowledge funding from the Plan France 2030 through projects
ANR-22-PETQ-0007 and ANR-22-PETQ-0008. The second author

also acknowledges the hospitality of the Simmons Institute in
Spring 2024 where part of this research was done.