Two quantum Ising algorithms for the shortest-vector problem
Authors:
- 26 March 2021
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review A
- Vol. 103 (3) , 032433
Abstract
Quantum computers are expected to break today's public key cryptography within a few decades. New cryptosystems are being designed and standardized for the postquantum 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 qubits, where 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 shows 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
Funding Information
- Engineering and Physical Sciences Research Council (EP/L016524/1, EP/S021043/1)
This publication has 25 references indexed in Scilit:
- Adiabatic Quantum Computation is Equivalent to Standard Quantum ComputationSIAM Journal on Computing, 2007
- Spatial search by quantum walkPhysical Review A, 2004
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum ComputerSIAM Review, 1999
- Quantum annealing in the transverse Ising modelPhysical Review E, 1998
- Improved methods for calculating vectors of short length in a lattice, including a complexity analysisMathematics of Computation, 1985
- 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
- A method for obtaining digital signatures and public-key cryptosystemsCommunications of the ACM, 1978
- New directions in cryptographyIEEE Transactions on Information Theory, 1976