Not-so-adiabatic quantum computation for the shortest vector problem
arXiv:1910.10462 · doi:10.1103/PhysRevResearch.2.013361
Abstract
Since quantum computers are known to break the vast majority of currently-used cryptographic protocols, a variety of new protocols are being developed that are conjectured, but not proven to be safe against quantum attacks. Among the most promising is lattice-based cryptography, where security relies upon problems like the shortest vector problem. We analyse the potential of adiabatic quantum computation for attacks on lattice-based cryptography, and give numerical evidence that even outside the adiabatic regime such methods can facilitate the solution of the shortest vector and similar problems.
arXiv comment15 pages total, 9 figures, journal submission to Phys Rev Research v2, corrected two typos (save --> safe, relies --> relies on)
References in corpus (8)
- Quantum phase transition from a superfluid to a Mott insulator in a gas of ultracold atoms
- Cold bosonic atoms in optical lattices
- Ising formulations of many NP problems
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Bounds for the adiabatic approximation with applications to quantum computation
- Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
- Low Depth Quantum Simulation of Electronic Structure
- Cold bosons in optical lattices: a tutorial for Exact Diagonalization
Cited by in corpus (9)
- Two quantum Ising algorithms for the Shortest Vector Problem: one for now and one for later
- Variational quantum solutions to the Shortest Vector Problem
- Iterative Quantum Optimization with Adaptive Problem Hamiltonian
- Excited state search using quantum annealing
- Grover's oracle for the Shortest Vector Problem and its application in hybrid classical-quantum solvers
- 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
- Beyond Ground States: Physics-Inspired Optimization of Excited States of Classical Hamiltonians