# A Finite Regime Analysis of Information Set Decoding Algorithms
## 3 A Finite Regime Analysis of Information Set Decoding Techniques
### Lee-Brickell
Such an approach allows reducing the number of iterations to be performed to the square root of the one for the classical algorithm, since each iteration of [PERSON]'s algorithm is essentially trying (exhaustively) to find a zero of the aforementioned Boolean function. We therefore rephrase the computational complexity of [PERSON]'s algorithm on a quantum computer. For the sake of simplicity in the analysis, we forgo the overhead of implementing the Boolean function as a reversible circuit, obtaining a conservative estimate of the actual complexity. **Proposition 8** (Quantum computational complexity of Algorithm 1). : _Given \(H\), an \(r\times n\) binary parity-check matrix and \(s\), an \(r\)-bit long syndrome (column vector) obtained through \(H\), finding the row error vector \(e\) with length \(n\) and weight \(t\) such that \(s=He^{T}\) with Algorithm 1 running on a quantum computer can be computed starting from the probability of success \(\Pr_{\mathrm{succ}}\) of a single iteration of the loop at Lines 1-7 and the computational requirements of executing the loop body \(c_{\mathrm{iter}}\). In particular, the time complexity is \(C_{\mathrm{ISD}}(n,r,t)=\sqrt{\frac{1}{\Pr_{\mathrm{succ}}}}c_{\mathrm{iter} }=\sqrt{\frac{\binom{n}{t}}{\binom{n}{t}}}\left(C_{\mathrm{IS}}(n,r)+\mathcal{ O}(n)\right)\), with_

\[C_{\mathrm{IS}}(n,r)=\frac{1}{\prod_{i=1}^{r}(1-2^{-i})}\ C_{\mathrm{RREF}}(n, r)+r^{2},\]

\[C_{\mathrm{RREF}}(n,r)=\mathcal{O}\left(\frac{nr^{2}}{2}+\frac{nr}{2}-\frac{r^ {3}}{6}+r^{2}+\frac{r}{6}-1\right).\]

_The spatial complexity is \(S_{\mathrm{ISD}}(n,r,t)=\mathcal{O}(rn)\)._

Following an argument similar to the one for Prange, we note that there is essentially no difficulty in interpreting [PERSON] and [PERSON]'s variant of the ISD as computing a slightly more complex Boolean function at each iteration, allowing to reformulate its complexity (Proposition 2) for the quantum case as follows. **Proposition 9** (Quantum computational complexity of Algorithm 2). : _Given \(H\), an \(r\times n\) binary parity-check matrix and \(s\), an \(r\)-bit long syndrome (column vector) obtained through \(H\), finding the row error vector \(e\) with length \(n\) and weight \(t\) such that \(s=He^{T}\) with Algorithm 2 requires an additional parameter \(0\leq p\leq t\)._

_The time complexity of Algorithm 2 running on a quantum computer can be computed starting from the probability of success \(\Pr_{\mathrm{succ}}\) of a single iteration of the loop at Lines 1-14 and the computational requirements of executing the loop body \(c_{\mathrm{iter}}\). In particular, the time complexity is_

\[C_{\mathrm{ISD}}(n,r,t,p)=\sqrt{\frac{1}{\Pr_{\mathrm{succ}}}}c_{\mathrm{iter }}=\sqrt{\frac{\binom{n}{t}}{\binom{k}{p}\binom{r}{t-p}}}\left(C_{\mathrm{IS} }(n,r)+\binom{k}{p}(C_{\mathrm{IntToComb}}+pr)\right),\]

_where \(C_{\mathrm{IntToComb}}=\mathcal{O}((2k-p)(\log\binom{k}{p})^{2})\) is the cost of decoding an integer into its combinadics representation, i.e., finding the corresponding combination among all the \(\binom{k}{p}\) ones. The spatial complexity is \(S_{\mathrm{ISD}}(r,n)=\mathcal{O}(rn)\)._Similarly, we also reformulate [PERSON]'s Algorithm 4 as follows. **Proposition 10** (Quantum computational complexity of Algorithm 4). : _Given \(H\), an \(r\times n\) binary parity-check matrix, \(s\), an \(r\)-bit long syndrome (column vector) obtained through \(H\), and the two parameters \(0\leq p\leq t\), \(0\leq\ell\leq(k-p)\), the complexity of finding the row error vector \(e\) with length \(n\) and weight \(t\) such that \(s=He^{T}\) with Algorithm 4 running on a quantum computer can be computed starting from the probability of success \(\Pr_{\mathrm{succ}}\) of a single iteration of the loop at Lines 1-10 and the computational requirements of executing the loop body \(c_{\mathrm{iter}}\).