LatticeAlgorithms.jl

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 $D_n$ lattice and two types of repetition-GKP codes, which can be decoded efficiently from a lattice perspective.

This package also contains several algorithms that were used in the paper Exploring the quantum capacity of a Gaussian random displacement channel using Gottesman-Kitaev-Preskill codes and maximum likelihood decoding, including an efficient and exact maximum likelihood decoder (MLD) for surface-square GKP codes, and a tensor-network decoder to approximate the MLD for generic concatenated-GKP codes. The latter is built on top of the decoder in SweepContractor.jl.

Security

See CONTRIBUTING for more information.

Citation

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}
}

Examples

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 $D_n$ lattice.

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.

License

This project is licensed under the Apache-2.0 License.