# A Finite Regime Analysis of Information Set Decoding Algorithms
## 3 A Finite Regime Analysis of Information Set Decoding Techniques
### Lee-Brickell
In particular, the time complexity is \(C_{\mathrm{ISD}}(n,r,t,p,\ell)=\sqrt{\frac{1}{\Pr_{\mathrm{succ}}}}c_{ \mathrm{iter}}=\sqrt{\frac{\binom{k}{p}}{\binom{\ell-\ell}{p}}}\left(C_{\mathrm{ IS}}(n,r)+\binom{k}{p}\left(C_{\mathrm{InfToComb}}+p\ell+\frac{\binom{k}{p}}{2^{t}}p(r- \ell)\right)\right)\), where \(C_{\mathrm{InfToComb}}=\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. Note that, if the value of \(p\) is fixed, it is possible to avoid \(C_{\mathrm{IntToComb}}\), specializing the algorithm with a \(p\)-deep loop nest to generate the combinations. The spatial complexity is \(S_{\mathrm{ISD}}(r,n)=\mathcal{O}(rn)\)._

Finally, we tackle the reformulation of [PERSON]'s ISD for the quantum case. **Proposition 11** (Quantum computational complexity of Algorithm 5). : _As for Algorithm 4, 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 5 requires two additional parameters \(0\leq p\leq t\), \(0\leq\ell\leq(k-p)\)._

_The time complexity of Algorithm 5 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,\ell)=\sqrt{\frac{1}{\Pr_{\mathrm{succ}}}}c_{ \mathrm{iter}}=\sqrt{\frac{\binom{n}{2}}{\binom{k/2}{(p/2)}^{2}(r-\ell)}} \left(C_{\mathrm{IS}}(n,r)+\binom{k/2}{p/2}\frac{p}{2}\ell+\binom{k/2}{p/2}(C_ {\mathrm{InfToComb}}+\frac{p}{2}\ell+\frac{\binom{k/2}{p/2}}{2^{t}}p(r-\ell))\right)\]

_where \(C_{\mathrm{InfToComb}}=\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/2}{p/2}\) ones. Note that, if the value of \(p\) is fixed, it is possible to avoid \(C_{\mathrm{InfToComb}}\), specializing the algorithm with a \(p\)-deep loop nest to generate the combinations. The spatial complexity is \(S_{\mathrm{ISD}}(n,r,t,p,\ell)=\mathcal{O}\left(rn+\binom{k/2}{p/2}(\frac{p}{ 2}\log_{2}(\frac{k}{2})+\ell)\right)\)._

Since advanced ISD algorithms reduce the overall complexity by reducing the number of iterations at the cost of an increased complexity per iteration, the speedup due to [PERSON]'s algorithm is less evident for modern variants than for classical forms of ISD. Indeed, for all cases where the trade-off on a classical computer reduces by a factor \(\alpha\) the number of iterations, at the cost of raising by \(\alpha\) the cost of the iteration itself, we have that the trade-off turns out to be disadvantageous on a quantum computer where the speedup factor \(\alpha\) is cut down to \(\sqrt{\alpha}\) by Grover, while the single iteration slowdown stays the same. This was already observed in [41], where it was found that the quantum variant of [PERSON]'s algorithm does not achieve smaller work factors than the quantum variant of [PERSON]'s algorithm. Indeed, in the same work, it is noted that the complexity of the quantum-computer variant of [PERSON]'s algorithm achieves a smaller complexity than the straightforward quantized version of the BJMM ISD. Finally, we note that the authors of [42] reported a re-elaboration of the MMT and BJMM ISDs for quantum computers which succeeds in effectively lowering their asymptotic complexities. We however do not take them into account in this work, as no finite regime complexity formulas are provided in [42] for the proposed algorithms.