# Techniques: A Practically Scalable Approach to the Closest Vector Problem for Sieving via QAOA with Fixed Angles

## What the paper contributes (one paragraph)
The paper studies whether the heuristic QAOA approach of Yan et al. to the closest vector problem (CVP) on Schnorr's prime lattice is practical and scalable for cryptanalytic sieving. It encodes the task of refining a classical approximate lattice solution (from LLL reduction plus Babai's nearest-plane algorithm) as a neighbourhood search, expressed as a QUBO and mapped to an Ising Hamiltonian whose minimum eigenstate is the closest vector. It then solves this minimum-eigenstate problem with QAOA. Its main novelty is an overfitting-aware pre-training scheme that fixes a single set of QAOA angles, trained on small instances and validated for generalisation, so the angles scale to larger lattices without per-instance reoptimisation. Numerically, fixed-depth QAOA (up to p=10) gives a refinement-probability decay of about 1/2^{0.225n}, exceeding the Grover quadratic speed-up. Results bear on lattice dimensions needed for quantum-secure cryptography. arXiv: 2503.08403.

## Techniques offered
- **Fixed-angle QAOA** - a quantum approximate optimisation solver run at fixed, pre-determined angles to refine an approximate CVP solution towards the closest lattice vector without per-instance variational reoptimisation.
  - guarantee: none (heuristic; empirical refinement-probability scaling of about 1/2^{0.225n} at p=10, no asymptotic solution-quality bound)
  - quote: "In this work, we proposed a simple yet robust pre-training algorithm to use for fixed-angles QAOA."
- **QAOA angle pre-training scheme** - an overfitting-aware training procedure that learns a single set of QAOA angles on small CVP instances and selects, via a validation loop, those that generalise to larger lattice dimensions.
  - guarantee: none (selects angles minimising empirical decay exponent over a validation set; no proven generalisation bound)
  - quote: "A simple yet robust pre-training scheme that dramatically reduces the computational requirements for refining solutions to the CVP."
- **CVP-refinement Ising/QUBO reduction** - a mapping of the unit-neighbourhood search around the Babai approximate solution into a quadratic unconstrained binary optimisation problem and corresponding Ising Hamiltonian whose minimum eigenstate encodes the closest vector.
  - guarantee: none (exact reformulation of the neighbourhood distance objective; the encoded search space is O(n) qubits and is not guaranteed to contain the true closest vector)
  - quote: "As such, we have formulated a minimum eigenstate problem that may be solved by QAOA (see section \ref{sec:background-QAOA})."

## Where it could apply
- Target primitive(s): QAOA, QUBO/Ising minimum-eigenstate optimisation
- Target application group(s): optimization, error_correction (cryptanalysis of lattice-based post-quantum schemes), platforms_tooling
- Code family / hardware assumptions: hardware-agnostic gate-model (noiseless simulation; authors note shallow-depth circuits could run on near-term hardware and the method could also serve as an early fault-tolerant routine); no specific code family

## Caveats
The paper is a heuristic, simulation-only study with no noise model and no asymptotic solution-quality guarantee; the supplied techniques are methods, not certificates. Applicability is demonstrated only on the highly constrained prime lattice with an O(n) (constant-per-basis-vector) search space, which is known to be too small to guarantee the true closest vector; generalisation to arbitrary CVP structure or to the more standard O(n log n) search space is left open. The work explicitly neither affirms nor denies the downstream sublinear-factoring claims it builds on.