Quantum algorithmic solutions to the shortest vector problem on simulated coherent Ising machines

2023/04/08 by Edmund Dable-Heath, Dable-Heath, Edmund, Casas, Laura +7
Computer Science · #Computability, Logic, AI Algorithms #FOS: Physical sciences #Machine Learning and Algorithms #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.2304.04075

openalex publication_date 2023/04/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Quantum computing poses a threat to contemporary cryptosystems, with advances to a state in which it will cause problems predicted for the next few decades. Many of the proposed cryptosystems designed to be quantum-secure are based on the Shortest Vector Problem and related problems. In this paper we use the Quadratic Unconstrained Binary Optimisation formulation of the Shortest Vector Problem implemented as a quantum Ising model on a simulated Coherent Ising Machine, showing progress towards solving SVP for three variants of the algorithm.

Related

• Heuristic Time Complexity of NISQ Shortest-Vector-Problem Solvers
• On the practicality of quantum sieving algorithms for the shortest vector problem
• An effcient variational quantum Korkin-Zolotarev algorithm for solving shortest vector problems
• Quantum Algorithm for Shortest Vector Problems with Folded Spectrum Method
• Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding