This package contains lattice algorithms that were used in the paper Closest lattice point decoding for multimode Gottesman-Kitaev-Preskill codes. The package contains several lattice reduction algorithms, such as Lenstra-Lenstra-Lovász and Korkine-Zolotarev algorithms, and a search algorithm for solving the closest point problem and the shortest vector problem. For the Gottesman-Kitaev-Preskill (GKP) codes, the package includes the
See CONTRIBUTING for more information.
If you find our paper or codebase useful, please consider citing us as:
@article{PRXQuantum.4.040334,
title = {Closest Lattice Point Decoding for Multimode Gottesman-Kitaev-Preskill Codes},
author = {Lin, Mao and Chamberland, Christopher and Noh, Kyungjoo},
journal = {PRX Quantum},
volume = {4},
issue = {4},
pages = {040334},
numpages = {36},
year = {2023},
month = {Dec},
publisher = {American Physical Society},
doi = {10.1103/PRXQuantum.4.040334},
url = {https://link.aps.org/doi/10.1103/PRXQuantum.4.040334}
}
Example 1: Finding the closest point for a random lattice
using LatticeAlgorithms
n = 10 # Dimension of the lattice
M = rand(n, n) # A lattice generated by a random matrix
x = rand(n) # A random input vector
y = closest_point(x, M) # The closest lattice point to x
Finding the closest point lies in the core of solving other lattice problems, including shortest lattice vector problem, and finding the relevant vectors for a given lattice. The demonstrations of solving these problems can be found in the folder examples/tutorials
.
Example 2: Finding the closest point for root lattices
using LatticeAlgorithms
n = 20 # Dimension of the lattice
M = Dn(n)
x = rand(n)
@time y1 = closest_point(x, M) # 0.001310 seconds (18.21 k allocations: 633.391 KiB)
@time y2 = closest_point_Dn(x) # 0.000014 seconds (3 allocations: 672 bytes)
@assert y1 ≈ y2 # true
Finding the closest point for root lattices can be done efficiently, in contrast to general lattices. In the above example, we demonstrate this fact with the
Example 3: Lattice reduction
using LatticeAlgorithms
n = 10 # Dimension of the lattice
M = rand(n, n) # A lattice generated by a random matrix
lll_basis = lll(M)
@assert lll_basis.T * lll_basis.L * lll_basis.Q ≈ M # true
In the above example, we perform the LLL reduction to the given matrix. The output lll_basis
contains three matrices such that T*L*Q=M
. Here T
is a unimodular matrix, Q
is an orthogonal matrix and L
is the LLL basis that satisfies the LLL criteria. A given matrix can be checked if it satisfies the LLL criteria via
islllreduced(lll_basis.L) # true
Similarly the given matrix can be KZ reduced via
kz_basis = kz(M)
@assert kz_basis.T * kz_basis.L * kz_basis.Q ≈ M # true
Example 4: Finding the distances of Gottesman-Kitaev-Preskill (GKP) codes
using LatticeAlgorithms
M = surface_code_M(3)
distance(M)
In the above example, we find the code distances of a surface-square GKP code, which is defined as the Euclidean length of the shortest operators. To find the distances of X, Y and Z logical operators, we can use distances(M)
. More utilities regarding GKP codes, including canonization of lattice generator, finding logical operators and others can be found in the file src/gkp.jl
.
This project is licensed under the Apache-2.0 License.