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.
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.
Finding the shortest vector in a lattice is a problem that is believed to be hard both for classical and quantum computers. Many major postquantum secure cryptosystems base their security on the hardness of the shortest vector problem (SVP) (Moody, 2023). Finding the best classical, quantum, or hybrid classical–quantum algorithms for the SVP is necessary to select cryptosystem parameters that offer a sufficient level of security. Grover's search quantum algorithm provides a generic quadratic speedup, given access to an oracle implementing some function, which describes when a solution is found. In this article, we provide concrete implementation of such an oracle for the SVP. We define the circuit and evaluate costs in terms of the number of qubits, the number of gates, depth, and T-quantum cost. We then analyze how to combine Grover's quantum search for small SVP instances with state-of-the-art classical solvers that use well-known algorithms, such as the block Korkine Zolotorev (Schnorr and Euchner, 1994), where the former is used as a subroutine. This could enable solving larger instances of SVP with higher probability than classical state-of-the-art records, but still very far from posing any threat to cryptosystems being considered for standardization. Depending on the technology available, there is a spectrum of tradeoffs in creating this combination.
Due to the development of quantum computing, there is a need for development and analysis of cryptosystems resistant to attacks with using a quantum computer - post-quantum algorithms cryptography. The strength of many well-known post-quantum cryptosystems, based on the theory of lattices, is based on the complexity of solving the problem finding the shortest vector in the lattice (SVP). For the previously proposed models of the quantum oracle used in the hybrid quantum-classical algorithm for solving the SVP problem, new refined estimates of implementation complexity. Designed and analyzed a new quantum oracle model that uses classical memory to storing a list of vectors.
Inspired by quantum annealing, digital annealing computers specified for annealing computations have been realized on a large scale, such as the Digital Annealer (DA) developed by Fujitsu and the CMOS Annealing Machine developed by Hitachi. With the progress achieved using these computers, it has become necessary to estimate the computational hardness of cryptographic problems. This paper focuses on lattice problems, such as the closest vector problem (CVP) and shortest vector problem (SVP), which are a class of optimization problems. These problems form the basis of the security of lattice-based cryptography, which is a prime candidate for the NIST post-quantum cryptography standardization. For these lattice problems, we propose methods for generating an Ising model and solving the Ising model on annealing computers with a bit representation as the input, which represents encodings to map each integer variable in the SVP into binary variables. We propose two methods for SVPs, a basic method and a variant incorporating approximately the concept of the classical lattice enumeration. In our experimental results obtained using the second-generation DA, we succeeded in finding a shortest nonzero lattice vector in 40- and 45-dimensional lattices in the Darmstadt SVP Challenge. The basic method with a hybrid bit representation was the fastest among our methods with a bit representation, and the expected running time was estimated as 664 and 13,750 seconds for the 40- and 45-dimensional lattices, respectively. These results provide a benchmark for solving the SVP with annealing computers.
Quantum computing holds significant potential to accelerate machine learning algorithms, especially in solving optimization problems like those encountered in Support Vector Machine (SVM) training. However, current QUBO-based Quantum SVM (QSVM) methods rely solely on binary optimal solutions, limiting their ability to identify fuzzy boundaries in data. Additionally, the limited qubit count in contemporary quantum devices constrains training on larger datasets. In this paper, we propose a probabilistic quantum SVM training framework suitable for Coherent Ising Machines (CIMs). By formulating the SVM training problem as a QUBO model, we leverage CIMs' energy minimization capabilities and introduce a Boltzmann distribution-based probabilistic approach to better approximate optimal SVM solutions, enhancing robustness. To address qubit limitations, we employ batch processing and multi-batch ensemble strategies, enabling small-scale quantum devices to train SVMs on larger datasets and support multi-class classification tasks via a one-vs-one approach. Our method is validated through simulations and real-machine experiments on binary and multi-class datasets. On the banknote binary classification dataset, our CIM-based QSVM, utilizing an energy-based probabilistic approach, achieved up to 20% higher accuracy compared to the original QSVM, while training up to 104 times faster than simulated annealing methods. Compared with classical SVM, our approach either matched or reduced training time. On the IRIS three-class dataset, our improved QSVM outperformed existing QSVM models in all key metrics. As quantum technology advances, increased qubit counts are expected to further enhance QSVM performance relative to classical SVM.
A fundamental computational problem is to find a shortest non-zero vector in Euclidean lattices, a problem known as the Shortest Vector Problem (SVP). This problem is believed to be hard even on quantum computers and thus plays a pivotal role in post-quantum cryptography. In this work we explore how (efficiently) Noisy Intermediate Scale Quantum (NISQ) devices may be used to solve SVP. Specifically, we map the problem to that of finding the ground state of a suitable Hamiltonian. In particular, (i) we establish new bounds for lattice enumeration, this allows us to obtain new bounds (resp. estimates) for the number of qubits required per dimension for any lattices (resp. random q-ary lattices) to solve SVP; (ii) we exclude the zero vector from the optimization space by proposing (a) a different classical optimisation loop or alternatively (b) a new mapping to the Hamiltonian. These improvements allow us to solve SVP in dimension up to 28 in a quantum emulation, significantly more than what was previously achieved, even for special cases. Finally, we extrapolate the size of NISQ devices that is required to be able to solve instances of lattices that are hard even for the best classical algorithms and find that with approximately 103 noisy qubits such instances can be tackled.
Finding the shortest non-zero vector on a lattice is a fundamental problem in lattices that is believed to be hard both for classical and quantum computers. Two of the three standardised by NIST post-quantum cryptosystems rely on its hardness. Research on theoretical and practical performance of quantum algorithms to solve the Shortest Vector Problem (SVP) is crucial to establish confidence in those new standards. Exploring the capabilities that Variational Quantum Algorithms (VQA) that can run on Noisy Intermediate Scale Quantum (NISQ) devices have in solving SVP has been an active area of research. The qubit-requirement for doing so has been analysed and demonstrated that it is plausible to encode SVP on the ground state of a Hamiltonian in an efficient way. Due to the heuristic nature of VQAs no analysis of the performance and specifically of the time complexity of those approaches for scales beyond the non-interesting classically simulatable sizes has been performed. In this paper, motivated by Boulebnane and Montanaro [1] work on the k-SAT problem, we propose to use angle pretraining of the Quantum Approximate Optimisation Algorithm (QAOA) for SVP and we demonstrate that QAOA with fixed angles performs well on much larger instances than those used in training. Avoiding the limitations that arise due to the use of optimiser, we are able to extrapolate the observed performance and we observe the probability of success scaling as2−0.695nwithnbeing dimensionality of the search space for a depthp=3pre-trained QAOA algorithm. By repeating the algorithm, we get heuristic time complexityO(20.695n)to solve the problem with high probability, a bit worse than the fault-tolerant Grover approach ofO(20.5n). On the other hand, both the number of qubits, and most importantly the depth of each quantum computation, are considerably better in our approach – Grover requires exponential depth, while each run of constantpfixed-angles QAOA requires polynomial depth. Further, we analyse the performance of QAOA in solving approximate-SVP, a version of the problem that one seeks a multiplicative approximation to the shortest vector. As a side result, we propose a novel method to avoid the zero vector solution to SVP without introducing more logical qubits. This improves upon the previous works as it results in more space efficient encoding of SVP on NISQ architectures without ignoring the zero vector problem.