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**

Publication

#### Community Detection in Electrical Grids Using Quantum Annealing

Publication

#### Quantum Permutation Synchronization

Publication

#### Multi-qubit Correction for Quantum Annealers

Publication

#### Computing Molecular Excited States on a D-Wave Quantum Annealer

Publication

#### Quantum Computing in Green Energy Production

Publication

#### Two Quantum Ising Algorithms for the Shortest Vector Problem: One for Now and One for Later

**2020**

Publication

#### Coupler-Induced Errors for Flux-qubit Quantum Annealer: Measurements for One-Dimensional Ising Model with Twisted Boundary Fields

Publication

#### Hybrid Quantum Annealing via Molecular Dynamics

Publication

#### Accuracy and Minor Embedding in Subqubo Decomposition with Fully Connected Large Problems

Publication

#### Traffic Signal Optimization on a Square Lattice using the D-Wave Quantum Annealer

Publication

#### Designing Metamaterials with Quantum Annealing and Factorization Machines

Publication

#### Reinforcement Quantum Annealing: A Quantum-Assisted Learning Automata Approach

**2019**

Publication

#### Unconventional Machine Learning of Genome-Wide Human Cancer Data

**2018**

Publication

#### Flight Gate Assignment with a Quantum Annealer

Publication

#### Mathematical Methods for a Quantum Annealing Computer

Publication

#### Quantum-Assisted Cluster Analysis on a Quantum Annealing Device

Publication

#### Quantum Annealing Versus Classical Machine Learning Applied to a Simplified Computational Biology Problem

Publication

#### Leveraging Adiabatic Quantum Computation for Election Forecasting

Publication

#### Efficient Combinatorial Optimization Using Quantum Annealing

**2017**

Publication

#### Traffic Flow Optimization using a Quantum Annealer

Publication

#### A Deceptive Step Towards Quantum Speedup Detection

Publication

#### Solving a Higgs Optimization Problem with Quantum Annealing for Machine Learning

Publication

#### Graph Partitioning using Quantum Annealing on the D-Wave System

Publication

#### Nonnegative/Binary Matrix Factorization with a D-Wave Quantum Annealer

Publication

#### A Study of Complex Deep Learning Networks on High Performance, Neuromorphic, and Quantum Computers

**2016**

Publication

#### Not Magic…Quantum

Publication

#### Spanning Tree Calculations on D-Wave 2 Machines

**2015**

Publication

#### Adiabatic Quantum Computing Challenges

**2014**

Publication

#### Reexamining Classical and Quantum Models for the D-Wave One Processor

Publication

#### Quantum Annealing Correction for Random Ising Problems

Publication

#### A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems

Publication

#### Quantum Optimization of Fully-Connected Spin Glasses

Publication

#### Consistency Tests of Classical and Quantum Models for a Quantum Annealer

Publication

#### Glassy Chimeras Could be Blind to Quantum Speedup: Designing Better Benchmarks for Quantum Annealing Machines

**2013**

Publication

#### Experimental Determination of Ramsey Numbers

Publication

#### Error Corrected Quantum Annealing with Hundreds of Qubits

Publication

#### MAX 2-SAT with up to 108 Qubits

Publication

#### Hearing the Shape of Ising Models: On the Distinguishability Power of Physics

Publication

#### Experimental Signature of Programmable Quantum Annealing

Publication

#### Quantum Annealing with More Than One Hundred Qubits

Publication

#### How Fast Can Quantum Annealers Count?

**2012**

Publication

#### Construction of Energy Functions for Lattice Heteropolymer Models: A Case Study in Constraint Satisfaction Programming and Adiabatic Quantum Optimization

Publication

#### Solving the Graph Isomorphism Problem with a Quantum Annealer

Publication

#### Robust Classification with Adiabatic Quantum Optimization

Publication

#### A Near-Term Quantum Computing Approach for Hard Computational Problems in Space Exploration

Publication

#### Quantum Speedup by Quantum Annealing

**2009**

Publication

#### Training a Large Scale Classifier with the Quantum Adiabatic Algorithm

**2008**

Publication

#### Training a Binary Classifier with the Quantum Adiabatic Algorithm

Publication