Quantum computers are expected to break today’s public key cryptography within a few decades. New cryptosystems are being designed and standardised 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. 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.
This work was done in collaboration with David Joseph, Adam Callison and Florian Mintert, using D-Wave Systems quantum computing resources.
Speaker short biography
Dr Cong Ling is currently a Reader in the Electrical and Electronic Engineering Department at Imperial College London. He leads the QUAIL (Quantum Artificial Intelligence Lab) at Imperial-X, White City Campus.
For further information please see Dr Ling’s homepage.