Quantum computers are expected to break today’s public key cryptography within a few decades. New cryptosystems are being designed and standardized 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(N log N) 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.
Scientific Publications
D-Wave is the world’s first commercial supplier of quantum computers. Learn more about the science behind our cutting-edge quantum technology and the use cases it can be applied to. Visit our resource library to read our technical white papers.
2021
![Publications Thumb 7](/media/dl2cs2kn/publications-thumb-7.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795001230000)
Publication
Community Detection in Electrical Grids Using Quantum Annealing
![Publications Thumb 9](/media/1p0apij1/publications-thumb-9.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795013870000)
Publication
Quantum Permutation Synchronization
![Publications Thumb 30](/media/5thdpugy/publications-thumb-30.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795148770000)
Publication
Multi-qubit Correction for Quantum Annealers
![Publications Thumb 29](/media/u0adpjmm/publications-thumb-29.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795143100000)
Publication
Computing Molecular Excited States on a D-Wave Quantum Annealer
![Publications Thumb 23](/media/fnmjmm12/publications-thumb-23.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795103430000)
Publication
Quantum Computing in Green Energy Production
![Publications Thumb 19](/media/anshe3ii/publications-thumb-19.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795077100000)
Publication
Two Quantum Ising Algorithms for the Shortest Vector Problem: One for Now and One for Later
2020
![Publications Thumb 20](/media/iitf2mpl/publications-thumb-20.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795084300000)
Publication
Coupler-Induced Errors for Flux-qubit Quantum Annealer: Measurements for One-Dimensional Ising Model with Twisted Boundary Fields
![Publications Thumb 1](/media/dwglqyit/publications-thumb-1.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718794963270000)
Publication
Hybrid Quantum Annealing via Molecular Dynamics
![Publications Thumb 21](/media/pakkdhpf/publications-thumb-21.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795090730000)
Publication
Accuracy and Minor Embedding in Subqubo Decomposition with Fully Connected Large Problems
![Publications Thumb 12](/media/t4umjft4/publications-thumb-12.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795032030000)
Publication
Traffic Signal Optimization on a Square Lattice using the D-Wave Quantum Annealer
![Publications Thumb 14](/media/aznfzh40/publications-thumb-14.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795044170000)
Publication
Designing Metamaterials with Quantum Annealing and Factorization Machines
![Publications Thumb 30](/media/5thdpugy/publications-thumb-30.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795148770000)
Publication
Reinforcement Quantum Annealing: A Quantum-Assisted Learning Automata Approach
2019
![Publications Thumb 13](/media/ujpjr1iv/publications-thumb-13.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795038470000)
Publication
Unconventional Machine Learning of Genome-Wide Human Cancer Data
2018
![Publications Thumb 32](/media/jgyjsrxg/publications-thumb-32.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795162770000)
Publication
Flight Gate Assignment with a Quantum Annealer
![Publications Thumb 5](/media/jxndkbit/publications-thumb-5.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718794989130000)
Publication
Mathematical Methods for a Quantum Annealing Computer
![Publications Thumb 4](/media/0hlouyun/publications-thumb-4.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718794982670000)
Publication
Quantum-Assisted Cluster Analysis on a Quantum Annealing Device
![Publications Thumb 28](/media/5lsdxgko/publications-thumb-28.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795136730000)
Publication
Quantum Annealing Versus Classical Machine Learning Applied to a Simplified Computational Biology Problem
![Publications Thumb 33](/media/frgppke5/publications-thumb-33.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795169170000)
Publication
Leveraging Adiabatic Quantum Computation for Election Forecasting
![Publications Thumb 26](/media/st0muq2g/publications-thumb-26.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795123170000)
Publication
Efficient Combinatorial Optimization Using Quantum Annealing
2017
![Publications Thumb 12](/media/t4umjft4/publications-thumb-12.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795032030000)
Publication
Traffic Flow Optimization using a Quantum Annealer
![Publications Thumb 10](/media/frwhhtiy/publications-thumb-10.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795020030000)
Publication
A Deceptive Step Towards Quantum Speedup Detection
![Publications Thumb 24](/media/lzihognx/publications-thumb-24.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795109530000)
Publication
Solving a Higgs Optimization Problem with Quantum Annealing for Machine Learning
![Publications Thumb 17](/media/a0gnk20n/publications-thumb-17.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795064600000)
Publication
Graph Partitioning using Quantum Annealing on the D-Wave System
![Publications Thumb 26](/media/st0muq2g/publications-thumb-26.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795123170000)
Publication
Nonnegative/Binary Matrix Factorization with a D-Wave Quantum Annealer
![Publications Thumb 1](/media/dwglqyit/publications-thumb-1.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718794963270000)
Publication
A Study of Complex Deep Learning Networks on High Performance, Neuromorphic, and Quantum Computers
2016
![Publications Thumb 7](/media/dl2cs2kn/publications-thumb-7.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795001230000)
Publication
Not Magic…Quantum
![Publications Thumb 10](/media/frwhhtiy/publications-thumb-10.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795020030000)
Publication
Spanning Tree Calculations on D-Wave 2 Machines
2015
![Publications Thumb 14](/media/aznfzh40/publications-thumb-14.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795044170000)
Publication
Adiabatic Quantum Computing Challenges
2014
![Publications Thumb 31](/media/zn0nqx15/publications-thumb-31.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795155370000)
Publication
Reexamining Classical and Quantum Models for the D-Wave One Processor
![Publications Thumb 20](/media/iitf2mpl/publications-thumb-20.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795084300000)
Publication
Quantum Annealing Correction for Random Ising Problems
![Publications Thumb 9](/media/1p0apij1/publications-thumb-9.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795013870000)
Publication
A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
![Publications Thumb 29](/media/u0adpjmm/publications-thumb-29.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795143100000)
Publication
Quantum Optimization of Fully-Connected Spin Glasses
![Publications Thumb 21](/media/pakkdhpf/publications-thumb-21.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795090730000)
Publication
Consistency Tests of Classical and Quantum Models for a Quantum Annealer
![Publications Thumb 31](/media/zn0nqx15/publications-thumb-31.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795155370000)
Publication
Glassy Chimeras Could be Blind to Quantum Speedup: Designing Better Benchmarks for Quantum Annealing Machines
2013
![Publications Thumb 12](/media/t4umjft4/publications-thumb-12.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795032030000)
Publication
Experimental Determination of Ramsey Numbers
![Publications Thumb 9](/media/1p0apij1/publications-thumb-9.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795013870000)
Publication
Error Corrected Quantum Annealing with Hundreds of Qubits
![Publications Thumb 27](/media/ilib3abr/publications-thumb-27.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795130300000)
Publication
MAX 2-SAT with up to 108 Qubits
![Publications Thumb 28](/media/5lsdxgko/publications-thumb-28.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795136730000)
Publication
Hearing the Shape of Ising Models: On the Distinguishability Power of Physics
![Publications Thumb 5](/media/jxndkbit/publications-thumb-5.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718794989130000)
Publication
Experimental Signature of Programmable Quantum Annealing
![Publications Thumb 33](/media/frgppke5/publications-thumb-33.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795169170000)
Publication
Quantum Annealing with More Than One Hundred Qubits
![Publications Thumb 14](/media/aznfzh40/publications-thumb-14.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795044170000)
Publication
How Fast Can Quantum Annealers Count?
2012
![Publications Thumb 10](/media/frwhhtiy/publications-thumb-10.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795020030000)
Publication
Construction of Energy Functions for Lattice Heteropolymer Models: A Case Study in Constraint Satisfaction Programming and Adiabatic Quantum Optimization
![Publications Thumb 17](/media/a0gnk20n/publications-thumb-17.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795064600000)
Publication
Solving the Graph Isomorphism Problem with a Quantum Annealer
![Publications Thumb 18](/media/gqlhcqih/publications-thumb-18.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795070730000)
Publication
Robust Classification with Adiabatic Quantum Optimization
![Publications Thumb 26](/media/st0muq2g/publications-thumb-26.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795123170000)
Publication
A Near-Term Quantum Computing Approach for Hard Computational Problems in Space Exploration
![Publications Thumb 30](/media/5thdpugy/publications-thumb-30.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795148770000)
Publication
Quantum Speedup by Quantum Annealing
2009
![Publications Thumb 8](/media/x0blzmsk/publications-thumb-8.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795007330000)
Publication
Training a Large Scale Classifier with the Quantum Adiabatic Algorithm
2008
![Publications Thumb 12](/media/t4umjft4/publications-thumb-12.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795032030000)
Publication
Training a Binary Classifier with the Quantum Adiabatic Algorithm
![Publications Thumb 7](/media/dl2cs2kn/publications-thumb-7.jpg?anchor=center&mode=crop&width=720&height=404&rnd=132718795001230000)
Publication