[Model] ClosestVectorProblem

[GiggleLiu]

Motivation

Fundamental lattice problem with known reductions to QUBO and ILP. Central to lattice-based cryptography (LWE decoding) and has a clean quadratic objective ‖Bx - t‖₂² = xᵀ(BᵀB)x - 2tᵀBx + tᵀt that maps directly to QUBO formulation.

Definition

Name: ClosestVectorProblem
Reference: Micciancio & Goldwasser, Complexity of Lattice Problems, 2002

Given a lattice basis B ∈ R^{m×n} (where the columns b₁, ..., bₙ ∈ R^m are basis vectors defining the lattice L(B) = {Bx : x ∈ Z^n}) and a target vector t ∈ R^m, find an integer vector x ∈ Z^n that minimizes ‖Bx - t‖₂.

Variables

• Count: n (one variable per basis vector)
• Per-variable domain: integers Z
• Meaning: x_i is the integer coefficient for the i-th basis vector b_i; the candidate lattice point is Bx = Σ x_i b_i

Schema (data type)

Type name: ClosestVectorProblem<T>
Variants: T = i32 (integer lattice) or T = f64 (real lattice)

Field	Type	Description
basis	Vec<Vec<T>>	The basis matrix B, stored as n column vectors each of dimension m
target	Vec<f64>	The target vector t ∈ R^m

Note: The i32 variant enables direct QUBO reduction with polynomial coefficient bounds (per arXiv:2304.03616). For the f64 variant, QUBO reduction requires Babai's round-off on an LLL-reduced basis (bound degrades exponentially without LLL). Details in the CVP → QUBO reduction rule.

Problem Size

Metric	Expression	Description
num_basis_vectors	n	Number of basis vectors (lattice dimension)
ambient_dimension	m	Dimension of the ambient space R^m

Complexity

• Decision complexity: NP-hard (van Emde Boas, 1981)
• Best known exact algorithm: O(2^n) time via enumeration (Kannan, 1987; Micciancio & Voulgaris, 2010)
• Best known approximation: NP-hard to approximate within n^{c/log log n} for some constant c (Dinur, Kindler, Raz & Safra, 2003)

How to solve

• It can be solved by (existing) bruteforce.
• It can be solved by reducing to integer programming.
• Other: Bruteforce solver, with sphere decoding (detailed below).

Compute an initial lattice point via Babai's round-off (x₀ = round(B⁻¹t)), obtain initial distance d₀ = ‖Bx₀ - t‖₂, then exhaustively enumerate all integer points x satisfying ‖Bx - t‖₂ ≤ d₀. This is exact because the optimal solution is guaranteed to lie within the search sphere.

References for exactness:

• Fincke & Pohst (1985), "Improved methods for calculating vectors of short length in a lattice" — original bounded enumeration
• Viterbo & Boutros (1999), "A universal lattice code decoder for fading channels" — sphere decoding exactness
• Hassibi & Vikalo (2005), "On the Sphere-Decoding Algorithm I. Expected Complexity" — rigorous analysis

Note: The full Kannan/Fincke-Pohst enumeration algorithm uses LLL basis reduction + Gram-Schmidt bounds for much tighter search regions (n^{O(n)} complexity vs exponential for naive sphere decoding). We will not implement it here — the simple sphere decoding suffices for small validation instances.

Example Instance

3D integer lattice (T = i32) with basis vectors:

b₁ = (2, 0, 0), b₂ = (1, 2, 0), b₃ = (0, 1, 2)

Target: t = (3, 3, 3)

No exact solution exists (would require x₃ = 3/2). Optimal: x = (1, 1, 1), Bx = (3, 3, 2), distance = 1.

Nearby lattice points:

x	Bx	‖Bx - t‖₂
(1, 1, 1)	(3, 3, 2)	1
(1, 1, 2)	(3, 4, 4)	√2 ≈ 1.41
(1, 0, 2)	(2, 2, 4)	√3 ≈ 1.73
(0, 1, 1)	(1, 3, 2)	√5 ≈ 2.24
(2, 1, 1)	(5, 3, 2)	√5 ≈ 2.24
(1, 0, 1)	(2, 1, 2)	√6 ≈ 2.45

Visualization (paper figure suggestion):

        z
        ↑     
    4   ·  ·  ·  (3,4,4)          · = lattice point
        |              ╲
    3  ─·──·──·──★──·   ╲         ★ = target t = (3,3,3)
        |        ╱|       ╲
    2   ·  ·  ● ╱ ·  ·    → y    ● = closest Bx = (3,3,2)
        |      d=1                 
    1   ·  ·  ·  ·  ·            d = distance = 1
        |
    0───·──·──·──·──·──→ x
        0  1  2  3  4  5

Recommended: 3D scatter plot for the paper showing lattice points (dots), target (star), closest point (filled circle), and the distance vector as a dashed line.