# Techniques: Heuristic Time Complexity of NISQ Shortest-Vector-Problem Solvers

## What the paper contributes (one paragraph)

The paper studies how well NISQ variational algorithms can solve the Shortest Vector Problem (SVP), the hardness assumption underlying NIST post-quantum cryptography. It adapts QAOA angle pre-training from k-SAT to SVP: angles trained on small lattices (dimensions 4 to 10) are reused, optimiser-free, on much larger instances (up to 22), so the method dodges barren plateaux and lets performance be extrapolated. From this it gives a heuristic upper bound on the time complexity of QAOA-based SVP solvers, with success probability scaling as roughly 2^{-0.695n} at depth p=3, hence time O(2^{0.695n}) with only polynomial circuit depth and O(n log n) qubits, far shallower than Grover. It introduces CM-QAOA (controlled-mixer QAOA), a Quantum Alternating Operator Ansatz that provably avoids the trivial zero-vector solution without adding qubits, and a method to generate small but representatively hard SVP instances for classical emulation.

## Techniques offered

- **QAOA angle pre-training (fixed-angle QAOA)** - pre-trains QAOA ansatz angles on small SVP instances and reuses them, without an optimiser, on much larger unseen instances, supplying a barren-plateau-free, extrapolatable heuristic SVP solver.
  - guarantee: heuristic; fixed-angle QAOA performance lower-bounds and therefore upper-bounds the time complexity of optimised QAOA SVP solvers, validated empirically up to dimension 22 with no optimiser-related limiting phenomena.
  - quote: "We introduce pre-training of QAOA angles for SVP instances\footnote{Whenever we mention QAOA for SVP we mean running QAOA with Hamiltonian $\mathcal{H}$ obtained by mapping the SVP problem to $\mathcal{H}$ without introducing a penalisation for the zero-vector solution as outlined in \cite{vqaSvpMilos}} and show that there exist sets of angles that universally provide advantage across classes of SVP instances."

- **CM-QAOA (controlled-mixer QAOA)** - a Quantum Alternating Operator Ansatz with a mixing unitary that leaves the overlap with the zero-vector solution invariant, excluding the trivial solution from the SVP search space without introducing extra logical qubits.
  - guarantee: provably converges towards the shortest non-zero lattice vector as depth p increases and provably does not increase the overlap with the zero-vector solution, at no additional qubit cost.
  - quote: "We propose a novel way to exclude the zero vector solution from the search space of the SVP variational algorithm solver based on QAOA. Our novel method, called CM-QAOA (controlled mixer QAOA) is a usage of Quantum Alternating Operator Ansatz with specific mixing unitaries that do not increase an overlap of the quantum system's statevector with the zero vector solution."

- **Heuristic time-complexity resource estimation for NISQ SVP solvers** - extrapolates the measured success probability of fixed-angle (CM-)QAOA into cryptographically interesting dimensions to give a conjectured upper bound on the time complexity of QAOA-based SVP solving.
  - guarantee: heuristic upper bound 2^{0.695n+o(n)} (QAOA) and 2^{0.895n+o(n)} (CM-QAOA) at depth p=3, conjectured from extrapolation of data up to dimension 22, not a rigorous analytical result.
  - quote: "We experimentally estimate and extrapolate upper bound on time complexity of QAOA based SVP solver."

- **Hard small-instance SVP generation for classical emulation** - constructs small SVP instances convertible to QUBO form that remain hard for variational quantum algorithms, enabling meaningful benchmarking and angle pre-training within classically emulatable sizes.
  - guarantee: none; a benchmark-instance construction whose representativeness is expected to improve with instance size, not a proven hardness bound.
  - quote: "We design a method for generating SVP-instances of small sizes that are capable of being converted to QUBO formulations and run in classical quantum emulations of variational quantum algorithms, and yet which mimic hardness of SVP for the variational quantum algorithms in such small instances."

## Where it could apply

- Target primitive(s): QAOA (and the Quantum Alternating Operator Ansatz generalisation); VQE-adjacent variational ground-state search
- Target application group(s): optimization, cryptography / post-quantum security, platforms_tooling
- Code family / hardware assumptions: NISQ devices (noiseless emulation assumed in experiments), O(n log n) qubits, polynomial circuit depth; no error-correction, QRAM, or specific code family required

## Caveats

Time-complexity figures are heuristic, conjectured from classically emulated, noiseless experiments on lattice dimensions up to 22 (trained on 4 to 10), not rigorous analytical bounds; the tightness of the fixed-angle upper bound on optimised (CM-)QAOA is unknown, the depth p needed for CM-QAOA to converge in practice is open, and noise effects are not modelled. The instance-generation method is a benchmarking aid without a proven hardness guarantee.