Two quantum Ising algorithms for the Shortest Vector Problem: one for now and one for later

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.

16 pages, 7 figures

References in corpus (13)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum Annealing in the Transverse Ising Model
• A Quantum Approximate Optimization Algorithm
• Spatial search by quantum walk
• Quantum Computation by Adiabatic Evolution
• Low Depth Quantum Simulation of Electronic Structure
• Adiabatic quantum optimization with the wrong Hamiltonian
• Quantum speedup of branch-and-bound algorithms
• Finding spin-glass ground states using quantum walks
• Quantum walk speedup of backtracking algorithms
• Not-so-adiabatic quantum computation for the shortest vector problem
• Fast clique minor generation in Chimera qubit connectivity graphs

Cited by in corpus (16)

• Understanding domain-wall encoding theoretically and experimentally
• Search range in experimental quantum annealing
• Quantum cryptography beyond key distribution: theory and experiment
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Variational quantum solutions to the Shortest Vector Problem
• Quantum annealing with twisted fields
• Iterative Quantum Optimization with Adaptive Problem Hamiltonian
• Grover's oracle for the Shortest Vector Problem and its application in hybrid classical-quantum solvers
• Analysis of the shortest vector problems with the quantum annealing to search the excited states
• Quantum-Classical Hybrid Algorithm for Solving the Learning-With-Errors Problem on NISQ Devices
• Quantum mean value approximator for hard integer value problems
• Heuristic Time Complexity of NISQ Shortest-Vector-Problem Solvers
• Quantum control without quantum states
• Performance of Domain-Wall Encoding for Quantum Annealing
• Beyond Ground States: Physics-Inspired Optimization of Excited States of Classical Hamiltonians
• Signing Information in the Quantum Era