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 or see a list of the most important research papers here.
2024

Publication
Cyclic quantum annealing: searching for deep low-energy states in 5000-qubit spin glass

Publication
Optimization Applications as Quantum Performance Benchmarks

Publication
Experience with Quantum Annealing Computation

Publication
Quantum Annealing-Based Algorithm for Efficient Coalition Formation Among LEO Satellites

Publication
Real World Application of Quantum-Classical Optimization for Production Scheduling

Publication
Solving the resource constrained project scheduling problem with quantum annealing

Publication
Quantum Annealing-Infused Microgrids Formation: Distribution System Restoration and Resilience Enhancement

Publication
Short-depth QAOA circuits and quantum annealing on higher-order ising models

Publication
Computational supremacy in quantum simulation

Publication
Using quantum annealing to design lattice proteins

Publication
Quantum fluctuations drive nonmonotonic correlations in a qubit lattice

Publication
Scaling Advantage in Approximate Optimization with Quantum Annealing
2023

Publication
Kagome qubit ice

Publication
Quantum error mitigation in quantum annealing

Publication
Inter-generational comparison of quantum annealers in solving hard scheduling problems

Publication
Effectiveness of quantum annealing for continuous-variable optimization

Publication
Tutorial: calibration refinement in quantum annealing

Publication
Milestones on the Quantum Utility Highway

Publication
Efficient low temperature Monte Carlo sampling using quantum annealing

Publication
Comparing Three Generations of D-Wave Quantum Annealers for Minor Embedded Combinatorial Optimization Problems

Publication
Quantum Critical Dynamics in a 5,000-Qubit Programmable Spin Glass

Publication
Hybrid Quantum Annealing for Larger-than-QPU Lattice-structured Problems (1)

Publication
Probing Flux and Charge Noise with Macroscopic Resonant Tunneling
2022

Publication
On the Emerging Potential of Quantum Annealing Hardware for Combinatorial Optimization

Publication
Multilevel Resonant Tunneling in the Presence of Flux and Charge Noise

Publication
Coherent Quantum Annealing in a Programmable 2,000 Qubit Ising Chain

Publication
On constant-time quantum annealing and guaranteed approximations for graph optimization problems

Publication
Annealing-based Quantum Computing for Combinatorial Optimal Power Flow

Publication
Quantum-Enhanced Selection Operators for Evolutionary Algorithms

Publication
Quantum annealing algorithms for Boolean tensor networks

Publication
High quality thermal Gibbs sampling with quantum annealing hardware

Publication
Benchmarking Advantage and D-Wave 2000Q quantum annealers with exact cover problems

Publication
Parallel quantum annealing

Publication
Hybrid Quantum Annealing for Larger-than-QPU Lattice-Structured Problems

Publication
A Method for Reducing Time-to-Solution in Quantum Annealing Through Pausing
2021

Publication
Community Detection in Electrical Grids Using Quantum Annealing

Publication
Quantum Permutation Synchronization

Publication
Multi-qubit Correction for Quantum Annealers

Publication
Essentially Exact Numerical Modelling of Flux Qubit Chains Subject to Charge and Flux Noise

Publication
SU(2) lattice gauge theory on a quantum annealer

Publication
Architectural Considerations in the Design of a Third-Generation Superconducting Quantum Annealing Processor

Publication
Qubit Spin Ice

Publication
Improving Nonstoquastic Quantum Annealing with Spin-Reversal Transformations

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

Publication
Quantum Computing in Green Energy Production

Publication
Scaling Advantage Over Path-Integral Monte Carlo in Quantum Simulation of Geometrically Frustrated Magnets

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

Publication
Quantum Annealing Simulation of Out-of-Equilibrium Magnetization in a Spin-Chain Compound
2020

Publication
Simulating the Shastry-Sutherland Ising Model Using Quantum Annealing

Publication
Improving Performance of Logical Qubits by Parameter Tuning and Topology Compensation

Publication
Performance Benefits of Increased Qubit Connectivity in Quantum Annealing 3-Dimensional Spin Glasses

Publication
De-Signing Hamiltonians for Quantum Adiabatic Optimization

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

Publication
Theory Versus Practice in Annealing-Based Quantum Computing

Publication
Hybrid Quantum Annealing via Molecular Dynamics

Publication
Probing Environmental Spin Polarization with Superconducting Flux Qubits

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

Publication
Demonstration of a Nonstoquastic Hamiltonian in Coupled Superconducting Flux Qubits

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
A Path Towards Quantum Advantage in Training Deep Generative Models with Quantum Annealers

Publication
Unconventional Machine Learning of Genome-Wide Human Cancer Data

Publication
PixelVAE++: Improved PixelVAE with Discrete Prior

Publication
Quantum-Assisted Genetic Algorithm

Publication
The Mathematics of Quantum-Enabled Applications on the D-Wave Quantum Computer

Publication
Demonstration of Nonstoquastic Hamiltonian in Coupled Superconducting Flux Qubits
2018

Publication
Flight Gate Assignment with a Quantum Annealer

Publication
Solving SAT and MaxSAT with a Quantum Annealer: Foundations, Encodings, and Preliminary Results

Publication
Computing Wasserstein Distance for Persistence Diagrams on a Quantum Computer

Publication
Theory of Open Quantum Dynamics with Hybrid Noise

Publication
Observation of Topological Phenomena in a Programmable Lattice of 1,800 Qubits

Publication
Phase Transitions in a Programmable Quantum Spin Glass Simulator

Publication
Mathematical Methods for a Quantum Annealing Computer

Publication
Quantum-Assisted Cluster Analysis on a Quantum Annealing Device

Publication
GumBolt: Extending Gumbel Trick to Boltzmann Priors

Publication
DVAE#: Discrete Variational Autoencoders with Relaxed Boltzmann Priors

Publication
Toward Robustness Against Label Noise in Training Deep Discriminative Neural Networks

Publication
Quantum Variational Autoencoder

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

Publication
DVAE++: Discrete Variational Autoencoders with Overlapping Transformations

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
From Near to Eternity: Spin-Glass Planting, Tiling Puzzles, and Constraint Satisfaction Problems

Publication
A Deceptive Step Towards Quantum Speedup Detection

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

Publication
Experimental Demonstration of Perturbative Anticrossing Mitigation using Non-Uniform Driver Hamiltonians

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

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

Publication
Can Quantum Monte Carlo Simulate Quantum Annealing?

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

Publication
Quantum Eigenstate Tomography with Qubit Tunneling Spectroscopy
2016

Publication
Benchmarking Quantum Hardware for Training of Fully Visible Boltzmann Machines

Publication
Discrete Variational Autoencoders

Publication
Not Magic…Quantum

Publication
Global Warming: Temperature Estimation in Annealers

Publication
Mapping Constrained Optimization Problems to Quantum Annealing with Application to Fault Diagnosis

Publication
Spanning Tree Calculations on D-Wave 2 Machines

Publication
Quantum Boltzmann Machine

Publication
A Frequency and Sensitivity Tunable Microresonator Array for High-Speed Quantum Processor Readout
2015

Publication
Degeneracy, Degree, and Heavy Tails in Quantum Annealing

Publication
Fast Clique Minor Generation in Chimera Qubit Connectivity Graphs

Publication
Constructing SAT Filters with a Quantum Annealer

Publication
Performance of a Quantum Annealer on Range-Limited Constraint Satisfaction Problems

Publication
Benchmarking a Quantum Annealing Processor with the Time-to-Target Metric

Publication
Searching for Quantum Speedup in Quasistatic Quantum Annealers

Publication
Adiabatic Quantum Computing Challenges

Publication
Computational Role of Collective Tunneling in a Quantum Annealer
2014

Publication
Discrete Optimization Using Quantum Annealing on Sparse Ising Models

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
A Practical Heuristic for Finding Graph Minors

Publication
Entanglement in a Quantum Annealing Processor

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

Publication
Architectural Considerations in the Design of a Superconducting Quantum Annealing Processor

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

Publication
Evidence for Temperature Dependent Spin-Diffusion as a Mechanism of Intrinsic Flux Noise in SQUIDs

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
Tunneling Spectroscopy Using a Probe Qubit

Publication
Thermally Assisted Quantum Annealing of a 16-Qubit Problem

Publication
Quantum Annealing with More Than One Hundred Qubits

Publication
Adiabatic Quantum Optimization with Qudits

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
Algorithmic Approach to Adiabatic Quantum Optimization

Publication
Approximate Diagonalization Method for Large-Scale Hamiltonian

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
2011

Publication
Probing High-Frequency Noise with Macroscopic Resonant Tunneling

Publication
Does Adiabatic Quantum Optimization Fail for NP-Complete Problems?

Publication
Importance of Explicit Vectorization for CPU and GPU Software Performance

Publication
The Ising Model: Teaching an Old Problem New Tricks

Publication
Investigating the Performance of an Adiabatic Quantum Optimization Processor

Publication
Quantum Annealing with Manufactured Spins
2010

Publication
A Scalable Control System for a Superconducting Adiabatic Quantum Optimization Processor

Publication
Experimental Demonstration of a Robust and Scalable Flux Qubit

Publication
High-Performance Physics Simulations Using Multi-Core CPUs and GPGPUs in a Volunteer Computing Context

Publication
Robust Parameter Selection for Parallel Tempering

Publication
Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor

Publication
Cotunneling in Pairs of Coupled Flux Qubits

Publication
A Scalable Readout System for a Superconducting Adiabatic Quantum Optimization System
2009

Publication
Training a Large Scale Classifier with the Quantum Adiabatic Algorithm

Publication
Geometrical Dependence of the Low-Frequency Noise in Superconducting Flux Qubits

Publication
Non-Markovian Incoherent Quantum Dynamics of a Two-State System

Publication
Decoherence in Adiabatic Quantum Computation

Publication
A Compound Josephson Junction Coupler for Flux Qubits With Minimal Crosstalk

Publication
Landau-Zener Transitions in an Adiabatic Quantum Computer

Publication
Consistency of the Adiabatic Theorem

Publication
Landau-Zener Transitions in the Presence of Spin Environment

Publication
First Order Quantum Phase Transition in Adiabatic Quantum Computation

Publication
The Role of Single Qubit Decoherence Time in Adiabatic Quantum Computation
2008

Publication
Training a Binary Classifier with the Quantum Adiabatic Algorithm

Publication
Minor-Embedding in Adiabatic Quantum Computation: I. The Parameter Setting Problem

Publication
Macroscopic Resonant Tunneling in the Presence of Low Frequency Noise

Publication
On the Construction of Model Hamiltonians for Adiabatic Quantum Computing and its Application to Finding Low Energy Conformations of Lattice Protein Models

Publication
Effect of Local Minima on Adiabatic Quantum Optimization

Publication
Thermally Assisted Adiabatic Quantum Computation

Publication
Probing Noise in Flux Qubits via Macroscopic Resonant Tunneling

Publication
Realizable Hamiltonians for Universal Adiabatic Quantum Computers

Publication
Image Recognition with an Adiabatic Quantum Computer I. Mapping to Quadratic Unconstrained Binary Optimization
2007

Publication
Sign- and Magnitude-Tunable Coupler for Superconducting Flux Qubits

Publication
A Characterization of Global Entanglement
2006

Publication
Rabi Oscillations in Systems with Small Anharmonicity

Publication
Four-Qubit Device with Mixed Couplings

Publication
Adiabatic Quantum Computation with Flux Qubits, First Experimental Results
2005

Publication
Silent Phase Qubit Based on D-Wave Josephson Junctions

Publication
Flux Qubit in Charge-Phase regime

Publication
Mediated Tunable Coupling of Flux Qubits

Publication
Direct Josephson Coupling Between Superconducting Flux Qubits

Publication
Simulated Quantum Computation of Molecular Energies

Publication
Hamiltonian for Coupled Flux Qubits

Publication
Quantum Nondemolition Charge Measurement of a Josephson Qubit
2004

Publication
Evidence for Entangled States of Two Coupled Flux Qubits

Publication
Low-Frequency Measurement of the Tunneling Amplitude in a Flux Qubit

Publication
Quasiparticle Decoherence in D-Wave Superconducting Qubits

Publication
Observation of Macroscopic Landau-Zener Tunneling in a Superconducting Device

Publication
Wigner Distribution Function Formalism for Superconductors and Collisionless Dynamics of the Superconducting Order Parameter

Publication
Dephasing-Insensitive Quantum Information Storage and Processing with Superconducting Qubits
2003
Publication
Non-Equilibrium Quasiclassical Theory for Josephson Structures

Publication
Josephson-Phase Qubit without Tunneling

Publication
Dynamical Effects of an Unconventional Current-Phase Relation in YBCO dc SQUIDs

Publication
Anomalous Current-Phase Relation as Basis for HTS Qubit

Publication
Nonequilibrium Quasiclassical Theory for Josephson Structures

Publication
Quasiclassical Calculations of Spontaneous Current in Restricted Geometries

Publication
Continuous Monitoring of Rabi Oscillations in a Josephson Flux Qubit

Publication
Theory of Weak Continuous Measurements in a Strongly Driven Quantum Bit

Publication
Tunable Coupling of Superconducting Qubits
Publication
Dynamical Effects of an Unconventional Current-Phase Relation in YBCO dc-SQUIDs
2002

Publication
Low-Frequency Characterization of Quantum Tunneling in Flux Qubits

Publication
Multi-Terminal Superconducting Phase Qubit

Publication
High Temperature PI/2-SQUID

Publication
Time Reversal Breaking States and Spontaneous Current Pattern in Josephson Junctions of D-Wave Superconductors

Publication
Quasiclassical Theory of Spontaneous Currents at Surfaces and Interfaces of D-Wave Superconductors

Publication
d+is Versus d+id Time Reversal Symmetry Breaking States in Finite Size Systems

Publication
DC-SQUID Based on the Mesoscopic Multi-Terminal Josephson Junction
2001

Publication
Mesoscopic Multi-Terminal Josephson Structures. I. Effects of Nonlocal Weak Coupling

Publication
Degenerate Ground State in a Mesoscopic YBa2CuO Grain Boundary Josephson Junction

Publication