amazon-science / latticealgorithms.jl Goto Github PK

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.

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

This project is licensed under the Apache-2.0 License.