Symplectic Lattices and GKP Codes -- Simple Randomized Constructions from Cryptographic Lattices
This provides a practical, randomized method for building quantum error-correcting codes, addressing a need in quantum computing, though it is incremental as it builds on existing lattice-based approaches.
The paper tackles the problem of constructing good Gottesman-Kitaev-Preskill (GKP) codes by using standard cryptographic lattices (SIS, R-SIS, M-SIS), achieving a distance of √(n/πe), which improves upon prior NTRU-based constructions with distance Ω(√(n/q)).
We construct good GKP (Gottesman-Kitaev-Preskill) codes (in the sense of Conrad, Eisert and Seifert proposed) from standard short integer solution lattices (SIS) as well as from ring SIS and module SIS lattices, R-SIS and M-SIS lattices, respectively. These lattice are crucial for lattice-based cryptography. Our construction yields GKP codes with distance $\sqrt{n/Ïe}$. This compares favorably with the NTRU-based construction by Conrad et al. that achieves distance $Ω(\sqrt{n/q}),$ with $n\le q^2/0.28$. Unlike their codes, our codes do not have secret keys that can be used to speed-up the decoding. However, we present a simple decoding algorithm that, for many parameter choices, experimentally yields decoding results similar to the ones for NTRU-based codes. Using the R-SIS and M-SIS construction, our simple decoding algorithm runs in nearly linear time. Following Conrad, Eisert and Seifert's work, our construction of GKP codes follows directly from an explicit, randomized construction of symplectic lattices with (up to constants $\approx 1$) minimal distance $(1/Ï_{2n})^{1/2n}\approx \sqrt{\frac{n}{Ïe}}$, where $Ï_{2n}$ is the volume of the 2n-dimensional unit ball. Before this result, Buser and Sarnak gave a non-constructive proof for the existence of such symplectic lattices.