amazon-science/LatticeAlgorithms.jl

amazon-science/LatticeAlgorithms.jl

Description: Algorithms to solve lattice problems in Julia

Language: Julia

License: Apache-2.0

Stars: 9

Forks: 1

Open issues: 1

Created: 2023-06-28T18:28:00Z

Pushed: 2026-04-27T23:37:49Z

Default branch: main

Fork: no

Archived: no

README:

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. The data and code for the paper can be found in the folder examples/papers/Closest_lattice_point_decoding_for_multimode_GKP_codes.

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. The data and code for the paper can be found in the folder examples/papers/Exploring_the_quantum_capacity_of_a_Gaussian_random_displacement_channel_using_GKP_codes_and_maximum_likelihood_decoding.

This package also contains several algorithms that were used in the paper Approximate maximum likelihood decoding with $K$ minimum weight matchings. In this paper, we introduce a novel algorithm to approximate the optimal maximum likelihood decoding strategey via finding $K$ minimum weight matchings from the decoding graph. The data and plots for the paper can be found in the folder examples/papers/Approximate_maximum_likelihood_decoding_with_K_minimum_weight_matchings.

Security

See [CONTRIBUTING](CONTRIBUTING.md#security-issue-notifications) 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

We provide some examples for using the package. The location to the source code of a function can be look up in the src/LatticeAlgorithms.jl file. For example, the function "closest_point" is exported before the line "include("lattice_algorithms.jl")", indicating that the function is in the file src/lattice_algorithms.jl. More tutorials can be found in the examples/tutorials folder.

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``.

Example 5: Exact maximum likelihood decoding (MLD) for the unrotated surface code on a square lattice

using LatticeAlgorithms
d = 25
n = d^2 + (d-1)^2

ϵs = 5/100 * ones(n)
prob_I, prob_X =…