Two quantum Ising algorithms for the Shortest Vector Problem: one for now and one for later
Authors:
Preprint
Abstract
Quantum computers are expected to break today's public key cryptography within a few decades. New cryptosystems are being designed and standardised for the post-quantum era, and a significant proportion of these rely on the hardness of problems like the Shortest Vector Problem to a quantum adversary. In this paper we describe two variants of a quantum Ising algorithm to solve this problem. One variant is spatially efficient, requiring only O(NlogN) qubits where N is the lattice dimension, while the other variant is more robust to noise. Analysis of the algorithms' performance on a quantum annealer and in numerical simulations show that the more qubit-efficient variant will outperform in the long run, while the other variant is more suitable for near-term implementation.Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- Quantum supremacy using a programmable superconducting processorNature, 2019
- Quantum Lattice Enumeration and Tweaking Discrete Pruning2018
- Learning with Errors and Extrapolated Dihedral Cosets2018
- The Matter Simulation (R)evolutionACS Central Science, 2018
- Solving the Shortest Vector Problem in Lattices Faster Using Quantum Search2013
- Public-key cryptosystems from lattice reduction problems1997
- Lattice basis reduction: Improved practical algorithms and solving subset sum problemsMathematical Programming, 1994
- Algorithms to construct minkowski reduced and hermite reduced lattice basesTheoretical Computer Science, 1985
- Factoring polynomials with rational coefficientsMathematische Annalen, 1982
- The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machinesJournal of Statistical Physics, 1980