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.
2022

Publication
Coherent Quantum Annealing in a Programmable 2000-qubit Ising Chain

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