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.

**2024**

Publication

#### Computational supremacy in quantum simulation

Publication

#### Quantum fluctuations drive nonmonotonic correlations in a qubit lattice

**2023**

Publication

#### Kagome qubit ice

Publication

#### Quantum error mitigation in quantum annealing

Publication

#### Tutorial: calibration refinement in quantum annealing

Publication

#### Milestones on the Quantum Utility Highway

Publication

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

Publication

#### Probing Flux and Charge Noise with Macroscopic Resonant Tunneling

**2022**

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

#### Annealing-based Quantum Computing for Combinatorial Optimal Power Flow

Publication

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

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

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