[Rule] ClosestVectorProblem to QUBO

[GiggleLiu]

Source: ClosestVectorProblem<i32> (integer basis variant, #90)
Target: QUBO
Motivation: Enables solving CVP on quantum annealers and Ising machines via QUBO formulation.
Reference: Canale, Qureshi & Viola, "Qubo model for the Closest Vector Problem", arXiv:2304.03616 (2023)

Reduction Algorithm

Notation:

• Source instance: integer basis A ∈ Z^{m×n} with columns a₁, ..., aₙ, target vector t ∈ R^m
• Per-variable bounds: x_i ∈ [lo_i, hi_i] (from CVP's VarBounds)
• G = AᵀA (Gram matrix), h = Aᵀt
• Target instance: QUBO matrix Q ∈ R^{N×N}, where N = total binary variables

Variable mapping:

1. For each integer coefficient x_i with bounds [lo_i, hi_i], let R_i = hi_i - lo_i (range).
2. Binary-encode each x_i as x_i = lo_i + Σⱼ 2ʲ b_{i,j} using L_i = ⌈log₂(R_i + 1)⌉ binary variables.
3. Total binary variables: N = Σᵢ L_i.
4. When 2^{L_i} > R_i + 1, some binary assignments map to out-of-range values; a penalty term with weight M (larger than the maximum objective range) is added to Q for those assignments.

Note: The paper derives a theoretical bound K_i ≤ 2^{⌈n(log₂ n + log₂ b)⌉} (where b = max|A_{ij}|, Proposition 2.4) for the unbounded case. This implementation uses the tighter explicit VarBounds stored on the CVP instance.

Objective transformation:
The CVP objective ‖Ax - t‖₂² expands as:

‖Ax - t‖₂² = xᵀGx - 2hᵀx + tᵀt

Substituting x_i = lo_i + Σⱼ 2ʲ b_{i,j} into the quadratic form xᵀGx - 2hᵀx and using b² = b for binary variables, we obtain a quadratic function in the N binary variables. The off-diagonal Q entries are scaled Gram matrix entries: Q_{(i,j),(k,l)} = 2^{j+l} · G_{ik} for distinct variable pairs; diagonal entries absorb linear terms from the lower-bound offsets and the h vector. The constant tᵀt is dropped (does not affect the optimal binary assignment).

Solution extraction:
Given optimal binary vector b*, reconstruct x_i = lo_i + Σⱼ 2ʲ b*_{i,j} for each i.

Size Overhead

Target metric (code name)	Expression
num_vars	Σᵢ ⌈log₂(R_i + 1)⌉, where R_i = hi_i - lo_i per variable

Validation Method

• Compare source/target optimal values on small instances using brute-force CVP solver and brute-force QUBO solver
• Cross-check with the canonical example below

Example

Use the canonical 2D CVP instance from the codebase:

Source CVP:

• A = [[2, 0], [1, 2]] (columns: a₁=(2,0), a₂=(1,2))
• t = (2.8, 1.5)
• Bounds: x₁ ∈ [-2, 4], x₂ ∈ [-2, 4]

Intermediate values:

• G = AᵀA = [[4, 2], [2, 5]]
• h = Aᵀt = (5.6, 5.8)
• L₁ = L₂ = ⌈log₂(7)⌉ = 3 bits each → N = 6 binary variables
• Encoding: x₁ = -2 + b₀ + 2b₁ + 4b₂, x₂ = -2 + b₃ + 2b₄ + 4b₅

Target QUBO (6×6 upper-triangular Q):

	b₀	b₁	b₂	b₃	b₄	b₅
b₀	−31.2	16	32	4	8	16
b₁		−54.4	64	8	16	32
b₂			−76.8	16	32	64
b₃				−34.6	20	40
b₄					−59.2	80
b₅						−78.4

Verification:

• Optimal CVP solution: x = (1, 1), distance = √0.29 ≈ 0.539
• Binary encoding: b = (1, 1, 0, 1, 1, 0) (offset 3 = 011₂ for each variable)
• QUBO value: bᵀQb = −107.4
• Reconstruction: −107.4 + 97.6 (substitution constant) + 10.09 (‖t‖²) = 0.29 = ‖Ax − t‖₂² ✓

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	No existing path from ClosestVectorProblem to QUBO
Non-trivial	✅ Pass	Binary encoding of integer coefficients + quadratic form expansion
Correctness	❌ Fail	Authors misattributed — paper is by Canale, Qureshi & Viola
Well-written	❌ Fail	Overhead uses nonexistent num_quadratic_terms metric

Overall: 2 passed, 2 failed, 0 warnings

---

Usefulness

No reduction path exists from ClosestVectorProblem to QUBO. CVP currently has zero outgoing reductions, so this would be the first reduction connecting CVP to the broader graph. The motivation (quantum annealer solving) is concrete.

Non-trivial

The reduction involves binary encoding of integer lattice coefficients using ⌈log₂(2Kᵢ+1)⌉ bits per coefficient, then expanding the Gram matrix form x^T G x − 2h^T x into a quadratic function over binary variables. This is a standard but non-trivial construction.

Correctness — FAIL

Author misattribution: The issue cites "Andersen & Yakubovich" as authors of arXiv:2304.03616. The actual authors are Eduardo Canale, Claudio Qureshi, and Alfredo Viola — "QUBO model for the Closest Vector Problem."

The mathematical content (Gram matrix formulation, binary encoding, overhead bounds) is correct and matches the actual paper.

Fix required: Change author attribution to Canale, Qureshi & Viola (2023).

Well-written — FAIL

num_quadratic_terms does not exist. The overhead table references this metric, but QUBO's only registered size_field is num_vars (confirmed via pred show QUBO --json). Using this in the #[reduction(overhead = {...})] macro would cause a compile error.

Additional issues:

• Kᵢ derivation is vague ("derive bound Kᵢ from the integer basis A, per the paper") — should give the explicit formula
• The example does not show the resulting QUBO matrix — only states "should have the same minimum energy"
• CVP has no registered size_fields, so overhead expressions cannot reference source getter methods

Required fixes

1. Correct authors to Canale, Qureshi & Viola
2. Replace num_quadratic_terms with num_vars in the overhead table (or add the getter to QUBO)
3. Provide explicit Kᵢ formula
4. Show the full QUBO matrix Q in the example

[isPANN]

Fix-issue changelog

• Fixed author misattribution: "Andersen & Yakubovich" → Canale, Qureshi & Viola (confirmed via arXiv:2304.03616)
• Removed nonexistent num_quadratic_terms from overhead table; QUBO only has num_vars
• Replaced vague Kᵢ derivation with direct use of CVP's VarBounds; paper's theoretical bound noted as context
• Rewrote example using canonical 2D CVP instance with full 6×6 QUBO matrix and numerical verification
• Added implementation note: num_encoding_bits() getter needed on CVP (parallels Knapsack::num_slack_bits())

Applied by /fix-issue.