[Model] ClosestVectorProblem #90
Description
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.